{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![En tête general](img/En_tete_general.png)\n",
    "\n",
    "\n",
    "*(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/*\n",
    "\n",
    "<span style=\"color: #9317B4\"> Pour exécuter une saisie Python, sélectionner la cellule et valider avec </span><span style=\"color: #B317B4\"><strong>SHIFT+Entrée</strong></span>.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <span style=\"color:#6C3483\">Chiffrement RSA </span> <span style=\"color:red\">(corrigé)</span>\n",
    "\n",
    "### <span style=\"color:#6C3483\">Activité sur le chiffrement n°3</span>\n",
    "##### <span style=\"color:#C18FDE\">(prérequis: congruences, équations diophantiennes, nombres premiers, théorème de Gauss, petit théorème de Fermat)</span>\n",
    "\n",
    "![Illustration_detectives](img/Chiffrement_RSA.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cette activité propose, sous forme simplifiée, d'étudier le principe du chiffrement RSA.<br>\n",
    "\n",
    "### <span style=\"color:#8E44AD\">Sommaire</span>\n",
    "\n",
    "<span style=\"color:#8E44AD\">1.</span> <a href=\"#1\">Principe du chiffrement RSA</a><br>\n",
    "<span style=\"color:#8E44AD\">2.</span> <a href=\"#2\">Échanges sécurisés de message</a><br>\n",
    "<span style=\"color:#8E44AD\">3.</span> <a href=\"#3\">Principe d'authentification</a><br>\n",
    "<span style=\"color:#8E44AD\">4.</span> <a href=\"#4\">Compléments arithmétiques</a><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <span style=\"color:#8E44AD\" id=\"1\">1. Principe du chiffrement RSA</span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Archibald, chef d'une agence de détectives, souhaite que tous ses associés cryptent les messages qu'ils lui envoient. Il souhaite donc leur donner à tous la même méthode de chiffrement, mais -méfiant- souhaite aussi s'asssurer d'être le seul à pouvoir décoder les messages qui lui parviennent, au cas où un espion intercepterait un de ces messages.<br><br>\n",
    "Dans les activités de chiffrement précédentes, la connaissance de la clé de chiffrement permettait directement de déterminer la clé de déchiffrement, ce qui ne convient pas à Archibald.<br><br>\n",
    "Pour réaliser son chiffrement, Archibald :\n",
    "<ul>\n",
    "    <li>fixe deux nombres premiers $p$ et $q$ distincts ;</li>\n",
    "    <li>pose $n=pq$ et $m=(p-1)(q-1)$ ;</li>\n",
    "    <li>choisit un entier $c$ premier avec $m$ tel que $1<c<m$.\n",
    "</ul>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<BLOCKQUOTE style='background-color:#96DAF1;'>\n",
    "    <strong>Dans cette partie, on pose $p=11$ ; $q=23$ et $c=9$.</strong>\n",
    "</BLOCKQUOTE>\n",
    "\n",
    "__1.1. Vérifier que $p$ ; $q$ et $c$ vérifient bien les contraintes annoncées, et donner les valeurs de $n$ et $m$.__\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"color:red;\">\n",
    "$p=11$ et $q=23$ sont bien des nombres premiers.<br>\n",
    "$n=pq=11 \\times 23=253$<br>\n",
    "$m=(p-1)(q-1)=10 \\times 22=220$<br>\n",
    "$c=9$ vérifie bien $1<c<m$, et il est premier avec $m=220$<br>\n",
    "</span>\n",
    "\n",
    "Archibald fournit le couple $(n;c)$ à ses associés, et garde les valeurs $p$ et $q$ secrètes.<br><br>\n",
    "Balthazar, un associé d'Archibald, souhaite coder un message à l'aide du couple $(n;c)$, appelé __clé publique__.<br>\n",
    "(pour simplifier, on suppose que le message est exclusivement composé d'espaces et de lettres majuscules, sans accents ni caractères spéciaux)<br>\n",
    "Pour cela, il commence par associer à chaque caractère de son message un entier $x$ compris entre $0$ et $26$ à l'aide du tableau de correspondance ci-dessous.<br>\n",
    "Ensuite, il associe à la valeur $x$ obtenue la valeur $y$ telle que $0 \\leq y \\leq n-1$ et $y \\equiv x^{\\;c} \\;[n]$.<br>\n",
    "\n",
    "| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | (espace) |\n",
    "|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:---------|\n",
    "| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16| 17| 18| 19| 20| 21| 22| 23| 24| 25| 26       |\n",
    "\n",
    "<br>\n",
    "Exemple :<br>\n",
    "Avec les valeurs choisies précédemment, la lettre <strong>I</strong> correspond à la valeur $x=8$.<br>\n",
    "Comme $x^9=8^9=134217728 \\equiv 216 [253]$, cette lettre se code avec la valeur $216$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__1.2. Balthazar souhaite envoyer le message \"BINGO\" à Archibald. Quelle succession de nombres va-t-il lui envoyer ?__<br>\n",
    "$\\;\\;\\;\\;\\;$On pourra utiliser une (des) zone(s) de saisie Python pour effectuer des calculs utiles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 216, 72, 200, 136]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Utiliser si nécessaire cette zone pour les calculs en Python\n",
    "[ k**9 %253 for k in [1,8,13,6,14] ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__1.3. On donne les fonctions Python <mark>chiffrage</mark> et <mark>chiffrement_RSA</mark> ci-dessous.__<br>\n",
    "$\\quad\\;\\;$__À l'aide d'appels à ces fonctions, vérifier le résultat de la question 1.2.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Mise en mémoire de l'alphabet (+espace)\n",
    "Alphabet=\"ABCDEFGHIJKLMNOPQRSTUVWXYZ \"\n",
    "\n",
    "def chiffrage(message):\n",
    "    \"\"\"\n",
    "    Fonction qui renvoie la liste des valeurs correspondantes aux caractères du message\n",
    "    (A->0 , B->1 , ...)\n",
    "    \"\"\"\n",
    "    return [ Alphabet.index(caractere) for caractere in message ]\n",
    "    \n",
    "    \n",
    "def chiffrement_RSA(n,c,liste_nombres):\n",
    "    \"\"\"\n",
    "    Fonction effectuant le codage RSA de la liste de valeurs avec la clé publique (n,c)\n",
    "    \"\"\"\n",
    "    code = []                                 \n",
    "    for x in liste_nombres:             # pour chaque valeur x de la liste donnée\n",
    "        y = x**c %n                     #       on calcule y correspondant à x\n",
    "        code.append(y)                  #       on complète la liste de valeurs avec y\n",
    "    return code\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 216, 72, 200, 136]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Effectuer ici les appels aux fonctions chiffrage et chiffrement_RSA\n",
    "\n",
    "liste = chiffrage(\"BINGO\")\n",
    "\n",
    "chiffrement_RSA(253,9,liste)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__1.4.__ Dans cette question, on souhaite effectuer le décodage du message à l'aide du triplet $(p;q;c)$, appelé __clé privée__.<br>\n",
    "$\\;\\;\\;\\;\\;$__a. Sans chercher à le déterminer, démontrer qu'il existe un unique entier $d$ tel que $1 \\leq d < m$ et $cd \\equiv 1 \\;[m]$.__<br>\n",
    "\n",
    "<span style=\"color:red;\">\n",
    "Existence :\n",
    "Comme $c$ et $m$ sont premiers entre eux, d'après le théorème de Bézout il existe deux entiers $d$ et $v$ tels que $cd+vm=1$. Ce qui donne $cd=1-mv$ et donc $cd \\equiv 1 [m]$.\n",
    "Unicité :\n",
    "Si $d_1$ et $d_2$ sont deux entiers qui conviennent, alors on a $d_1-d_2 \\equiv 0 \\;[m]$, donc $m$ divise $d_1-d_2$.\n",
    "D'autre part, $1 \\leq d_1 < m$ et $1 \\leq d_2 < m$ permettent de déduire que $-m+1 \\leq d_1-d_2 < m-1$.\n",
    "Or le seul multiple de $m$ qui appartient à cet intervalle est $0$, donc $d_1-d_2=0$, c'est à dire $d_1=d_2$.\n",
    "</span>\n",
    "\n",
    "$\\;\\;\\;\\;\\;$__b. Déterminer cette valeur $d$ (on pourra commencer par appliquer l'algorithme d'Euclide).__\n",
    "\n",
    "<span style=\"color:red;\">\n",
    "On a $m=(p-1)(q-1)=10\\times22=220$ et $c=9$.<br>\n",
    "En appliquant l'algorithme d'Euclide et en remontant les calculs, on détermine un couple de coefficients de Bézout :\n",
    "</span>\n",
    "<table style=\"color:red; font-size: 14px; text-align:center;\">\n",
    "    <tr>\n",
    "        <td width=400>Algorithme d'Euclide</td>\n",
    "        <td width=400>Recherche des coefficients de Bézout</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td>$220 = 9 \\times 24 + 4$</td>\n",
    "        <td>$4 = 220 - 9 \\times 24 = m - 24c$</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td>$9 = 4 \\times 2 +1$</td>\n",
    "        <td>$1 = 9 - 4 \\times 2 = c - (m-24c) \\times 2 = -2m+49c$</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td>$4 = 4 \\times 1 +0$</td>\n",
    "        <td> </td>\n",
    "    </tr>\n",
    "</table>\n",
    "<span style=\"color:red;\">\n",
    "On en déduit que $49c=1+2m$, c'est à dire $49c \\equiv 1 \\;[m]$.<br>\n",
    "On pose $d=49$ qui convient puisque $1<49<m$.\n",
    "</span>\n",
    "\n",
    "\n",
    "$\\;\\;\\;\\;\\;$__c. À l'aide de saisies en Python, calculer $x^{cd}$ modulo $n$ pour différentes valeurs entières positives de $x$. Que constate-t-on ?__<br>\n",
    "\n",
    "<span style=\"color:red;\">\n",
    "Il semble que $x^{cd} \\equiv x \\;[n]$ quelle que soit la valeur entière $x$ positive choisie.\n",
    "</span>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[13, 50, 77, 80]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Effectuer ici les calculs\n",
    "c = 9\n",
    "d = 49\n",
    "n = 253\n",
    "\n",
    "[ x**(c*d) %n for x in [13,50,77,80] ] #tests pour diverses valeurs de x\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\;\\;\\;\\;\\;$__d. On admet pour l'instant\\* que l'observation de la question 1.4.b. est correcte pour tout entier positif $x$, et on rappelle que $y$ vérifie $y \\equiv x^{\\;c} \\;[n]$.<br>\n",
    "$\\quad\\quad$<span style=\"font-size:12px\">(*La démonstration mathématique de ce résultat sera détaillé dans <a href=\"#4\">la partie 4</a>)</span><br>\n",
    "$\\quad\\quad$Exprimer $x$ en fonction de $y$ modulo $n$.__<br>\n",
    "\n",
    "<span style=\"color:red;\">\n",
    "On sait que $x^c \\equiv y \\;[n]$.<br>\n",
    "En élevant à la puissance $d$, on obtient:<br>\n",
    "$(x^c)^d \\equiv y^d \\;[n]$<br>\n",
    "$x^{cd} \\equiv y^d \\;[n]$<br>\n",
    "et comme on a admis que $x^{cd} \\equiv x \\;[n]$, on en déduit que :<br>\n",
    "$x \\equiv y^d \\;[n]$<br>\n",
    "</span>\n",
    "\n",
    "$\\;\\;\\;\\;\\;$__e. Effectuer le décodage des nombres de la question 1.2 et vérifier qu'on retrouve bien le message \"BINGO\".__<br>\n",
    "$\\;\\;\\;\\;\\;\\;\\;\\;$On pourra utiliser une (des) zone(s) de saisie Python pour effectuer des calculs utiles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 8, 13, 6, 14]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Utiliser si nécessaire cette zone pour les calculs en Python\n",
    "c = 9\n",
    "d = 49\n",
    "n = 253\n",
    "\n",
    "[y**d %n for y in [1, 216, 72, 200, 136] ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__1.5. On fournit ci-dessous la fonction Python <mark>inv</mark> qui reçoit en argument <mark>m</mark> et <mark>c</mark>, et renvoie <mark>d</mark>.__<br>\n",
    "$\\;\\;\\;\\;\\;\\;$(NB : Cette fonction est basée sur une recherche de coefficients de Bézout ; elle est étudiée dans l'activité <a href=\"https://mybinder.org/v2/gh/PythonLycee/PyLyc/master?filepath=PGCD_Euclide_Bezout.ipynb\">PGCD / Euclide / Bézout</a>)<br>\n",
    "$\\;\\;\\;\\;\\;\\;$__Vérifier que la fonction <mark>inv</mark> permet de retrouver la réponse à la question 1.5.a.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def inv(m,c):\n",
    "    \"\"\"\n",
    "    Recherche de d, inverse de c modulo m\n",
    "    (passage par les coefficients de Bézout)\n",
    "    \"\"\"\n",
    "    a,b=m,c\n",
    "    q = a//b\n",
    "    P = np.array([ [ 0 , 1 ] , [ 1 , -q ] ]) \n",
    "    while a%b!=0:\n",
    "        a,b = b,a%b\n",
    "        q = a//b\n",
    "        P = np.dot( np.array([ [ 0 , 1 ] , [ 1 , -q ] ]) , P )\n",
    "    u,v = P[0]\n",
    "    return int(v%m)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "49"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Effectuer ici un appel à la fonction inv\n",
    "p = 11 ; q = 23\n",
    "m = (p-1)*(q-1) ; c = 9\n",
    "\n",
    "d = inv(m,c)\n",
    "d "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__1.6.a. Écrire une fonction Python <mark>dechiffre_RSA</mark> qui reçoit en argument <mark>p</mark>, <mark>q</mark>, <mark>c</mark> et <mark>code</mark> (liste de valeurs fournie par la fonction chiffrement_RSA) et qui effectue les instructions suivantes:__<br>\n",
    "<ul>\n",
    "    <li>calculer <mark>n</mark></li>\n",
    "    <li>calculer <mark>m</mark></li>\n",
    "    <li>calculer <mark>d</mark></li>\n",
    "    <li>renvoyer la liste des valeurs <mark>x</mark> correspondantes aux valeurs <mark>y</mark> du <mark>code</mark></li>\n",
    "</ul>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Écrire ici la fonction dechiffre_RSA\n",
    "\n",
    "def dechiffre_RSA(p,q,c,code):\n",
    "    \"\"\"\n",
    "    Fonction effectuant le décodage RSA du code à partir des nombres premiers p et q\n",
    "    \"\"\"\n",
    "    n = p*q           #calcul de n\n",
    "    m = (p-1)*(q-1)   #calcul de m\n",
    "    d = inv(m,c)      #calcul de d\n",
    "    \n",
    "    return [y**d %n for y in code] #renvoie la liste des valeurs correspondantes aux valeurs y du code\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\;\\;\\;$__b. On donne la fonction Python <mark>lettrage</mark> ci-dessous.__<br>\n",
    "$\\quad\\;\\;$__Vérifier que votre fonction <mark>dechiffre_RSA</mark> et cette fonction <mark>lettrage</mark> permettent de décoder la liste de valeurs des questions 1.2 et 1.3.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lettrage(code):\n",
    "    \"\"\"\n",
    "    Fonction qui convertit une liste de valeurs (comprises entre 0 et 26) en chaine de caractères\n",
    "    (0->A , 1->B , ...)\n",
    "    \"\"\"\n",
    "    message = \"\"\n",
    "    for y in code:\n",
    "        message += Alphabet[y]\n",
    "    \n",
    "    return message"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 8, 13, 6, 14]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Effectuer ici un appel à la fonction dechiffre_RSA\n",
    "liste = dechiffre_RSA(11,23,9,[1, 216, 72, 200, 136])\n",
    "liste"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'BINGO'"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Effectuer ici un appel à la fonction lettrage\n",
    "lettrage(liste)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\;\\;\\;$__c. Archibald reçoit ce code de la part de Casper, un autre de ses associés : $36, 5, 145, 36, 43, 0$.__<br>\n",
    "$\\;\\;\\;\\;\\;\\;$__Décoder ce message.__<br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 20, 17, 4, 10, 0]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Effectuer ici un appel à la fonction dechiffre_RSA\n",
    "liste=dechiffre_RSA(11,23,9,[36, 5, 145, 36, 43, 0])\n",
    "liste"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'EUREKA'"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Effectuer ici un appel à la fonction lettrage\n",
    "lettrage(liste)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <span style=\"color:#8E44AD\" id=\"2\">2. Échanges sécurisés de message</span>\n",
    "<br><br>\n",
    "On reprend dans cette partie les notations de la partie précédente."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__2.1. Exécuter la cellule ci-dessous, qui permet de générer deux nombres premiers $p$ et $q$ distincts à 3 chiffres et un nombre entier $c$ tel que $c$ et $m=(p-1)(q-1)$ sont premiers entre eux avec $1<c<m$.__<br>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(607, 151, 78391)"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from random import randint\n",
    "\n",
    "def PGCD(a,b):\n",
    "    \"\"\"\n",
    "    Fonction qui calcule le PGCD de a et b\n",
    "    \"\"\"\n",
    "    return a if b==0 else PGCD(b,a%b)\n",
    "\n",
    "def est_premier(n):\n",
    "    \"\"\"\n",
    "    Fonction qui détermine si un entier est premier\n",
    "    \"\"\"\n",
    "    if n%2==0 or n==1: return False\n",
    "    for k in range(3,int(n**0.5)+1,2):\n",
    "        if n%k==0 : return False\n",
    "    return True\n",
    "\n",
    "def premier(min=10**2,max=10**3-1):\n",
    "    \"\"\"\n",
    "    Fonction qui renvoie un nombre premier aléatoire compris entre min et max\n",
    "    \"\"\"\n",
    "    p=0\n",
    "    while not est_premier(p):\n",
    "        p=randint(min,max)\n",
    "    return p\n",
    "\n",
    "#génération d'un nombre premier p à 3 chiffres\n",
    "p = premier() \n",
    "\n",
    "#génération d'un nombre premier q à 3 chiffres, distinct de p\n",
    "q = p\n",
    "while q == p : q = premier() \n",
    "\n",
    "#génération de c premier avec m\n",
    "m = (p-1)*(q-1)    \n",
    "c = 0\n",
    "while PGCD(c,m)!=1: c = randint(2,m-1) \n",
    "\n",
    "    \n",
    "p,q,c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__2.2. Effectuer les saisies nécessaires pour calculer $n$.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "91657"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Effectuer ici les saisies pour le calcul de n\n",
    "n = p*q\n",
    "n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__2.3. Fournir à deux personnes B et C votre clé publique $(n,c)$.__<br> \n",
    "$\\;\\;\\;\\;\\;$__B et C vous envoient alors un message codé à l'aide de la fonction <mark>chiffrement_RSA</mark>.__<br>\n",
    "$\\;\\;\\;\\;\\;$__Décoder ces messages à l'aide de la fonction <mark>dechiffre RSA</mark>.__\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[73240, 0, 86762, 15374, 75670]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Saisies effectuées par B pour générer son message codé\n",
    "message_de_B=\"SALUT\"\n",
    "\n",
    "code=chiffrement_RSA(n,c,chiffrage(message_de_B))\n",
    "code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'SALUT'"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Saisies effectuées pour décoder le message\n",
    "lettrage(dechiffre_RSA(p,q,c,code))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si C interceptait le message codé envoyé par B, pourrait-il le décoder ?...<br><br>\n",
    "Pour décoder un message, il est nécessaire de connaître les valeurs de $p$ et $q$, afin de déterminer $m$ puis $d$.<br>\n",
    "Connaissant $n$, C devrait retrouver la décomposition en facteurs premiers $n=pq$.<br><br>\n",
    "La sécurité du code dépend donc de la difficulté à réaliser cette décomposition. Pour de petites valeurs de $n$, il est possible d'automatiser cette recherche avec un temps de calcul relativement court. C'est pourquoi, dans la pratique, les nombres $p$ et $q$ utilisés pour un chiffrement RSA sont des nombres premiers qui comportent plusieurs centaines de chiffres !<br><br>\n",
    "Par ailleurs, le chiffrement RSA procède en réalité par codage par blocs et non par caractères."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <span style=\"color:#8E44AD\" id=\"3\">3. Principe d'authentification</span>\n",
    "<br><br>\n",
    "On reprend dans cette partie les notations des parties précédentes.<br><br>\n",
    "\n",
    "Archibald et Balthazar disposent chacun d'une clé publique et d'une clé privée pour le chiffrement RSA.<br><br>\n",
    "\n",
    "Archibald souhaite envoyer un message à Balthazar de telle sorte que celui-ci soit certain de l'origine du message.<br>\n",
    "Mais toutes les personnes qui écrivent à Balthazar utilisent la même clé publique...<br><br>\n",
    "\n",
    "Pour l'exemple traité dans cette partie, les clés sont données dans le tableau ci-après :\n",
    "\n",
    "\n",
    "<table style=\"font-size: 14px; text-align:center;\">\n",
    "    <tr>\n",
    "        <td >$\\;\\;\\;$</td>\n",
    "    <td width=250 style=\"text-align:center;\"><strong>Archibald</strong></td>\n",
    "        <td>$\\;\\;\\;$</td>\n",
    "        <td width=250 style=\"text-align:center;\"><strong>Balthazar</strong></td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td><strong>Clé privée</strong></td>\n",
    "        <td width=250>$$ p_A=11 \\;;\\; q_A=23 \\;;\\; c_A=9 $$</td>\n",
    "        <td>$\\;\\;\\;$</td>\n",
    "        <td width=250>$$ p_B=7 \\;;\\; q_B=13 \\;;\\; c_B=5 $$</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td><strong>Clé publique</strong></td>\n",
    "        <td width=250>$$n_A=253 \\;;\\; c_A=9$$</td>\n",
    "        <td>$\\;\\;\\;$</td>\n",
    "        <td width=250>$$n_B=91 \\;;\\; c_B=5$$</td>\n",
    "    </tr>\n",
    "</table>\n",
    "\n",
    "\n",
    "Supposons qu'Archibald souhaite envoyer le message \"VOICI MON MESSAGE IMPORTANT\" à Balthazar :\n",
    "<ul>\n",
    "    <li> il va appliquer la clé publique de cryptage de Balthazar $(n_B,c_B)=(91,5)$ à ce message ;</li>\n",
    "    <li> il va appliquer sa propre clé privée de <strong>dé</strong>cryptage à une partie de ce message (par exemple le premier mot) qui servira à authentifier l'expéditeur ;</li>\n",
    "    <li> enfin, il envoie les deux listes de valeurs à Balthazar.</li>\n",
    "</ul>    \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__3.1. Dans la cellule ci-dessous, on a créé le message à envoyer, ainsi que le mot d'authentification.__<br>\n",
    "$\\quad\\;$__Utiliser les zones de saisie suivantes pour obtenir les deux listes de valeurs <mark>code1</mark> et <mark>code2</mark>qu'Archibald va envoyer à Balthazar.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('VOICI MON MESSAGE IMPORTANT', 'VOICI')"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "message = \"VOICI MON MESSAGE IMPORTANT\"    #message à envoyer\n",
    "mot_auth = message[:5]                     #partie du message pour l'authentification (ici le premier mot)\n",
    "\n",
    "message , mot_auth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([21,\n",
       "  14,\n",
       "  8,\n",
       "  2,\n",
       "  8,\n",
       "  26,\n",
       "  12,\n",
       "  14,\n",
       "  13,\n",
       "  26,\n",
       "  12,\n",
       "  4,\n",
       "  18,\n",
       "  18,\n",
       "  0,\n",
       "  6,\n",
       "  4,\n",
       "  26,\n",
       "  8,\n",
       "  12,\n",
       "  15,\n",
       "  14,\n",
       "  17,\n",
       "  19,\n",
       "  0,\n",
       "  13,\n",
       "  19],\n",
       " [21, 14, 8, 2, 8])"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Effectuer ici les saisies nécessaires pour convertir le message et le mot d'authentification en listes de nombres\n",
    "#(on pourra nommer ces listes l1 et l2)\n",
    "l1 = chiffrage(message)\n",
    "l2 = chiffrage(mot_auth)\n",
    "\n",
    "l1 , l2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([21,\n",
       "  14,\n",
       "  8,\n",
       "  32,\n",
       "  8,\n",
       "  52,\n",
       "  38,\n",
       "  14,\n",
       "  13,\n",
       "  52,\n",
       "  38,\n",
       "  23,\n",
       "  44,\n",
       "  44,\n",
       "  0,\n",
       "  41,\n",
       "  23,\n",
       "  52,\n",
       "  8,\n",
       "  38,\n",
       "  71,\n",
       "  14,\n",
       "  75,\n",
       "  80,\n",
       "  0,\n",
       "  13,\n",
       "  80],\n",
       " [175, 15, 62, 193, 62])"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Effectuer ici les saisies pour obtenir les listes envoyées par Balthazar\n",
    "#(on pourra nommer ces listes code1 et code2)\n",
    "code1 = chiffrement_RSA(91,5,l1) #codage du message à l'aide de la clé publique de Balthazar\n",
    "code2 = dechiffre_RSA(11,23,9,l2) #codage du mot d'authentification à l'aide de la clé privée d'Archibald\n",
    "\n",
    "code1 , code2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__3.2 On se place maintenant du côté de Balthazar, qui souhaite interpréter les deux codes reçus <mark>code1</mark> et <mark>code2</mark>.__<br>\n",
    "$\\quad\\;$__a. Quelles sont les clés qu'il va appliquer à chacun de ces codes pour obtenir les valeurs initiales ?__<br>\n",
    "\n",
    "\n",
    "<span style=\"color:red;\">\n",
    "Balthazar va :\n",
    "<ul style=\"color:red;\">\n",
    "    <li> appliquer sa propre clé privée de décryptage $(p_B,q_B,c_B)=(7,13,5)$ à <mark style=\"color:red;\">code1</mark> ;</li>\n",
    "    <li> appliquer la clé publique d'Archibald $(n_A,c_A)=(253,9)$ à <mark style=\"color:red;\">code2</mark></li>\n",
    "    <li> convertir en lettres les listes de valeurs obtenues.</li>\n",
    "</ul>    \n",
    "</span>\n",
    "\n",
    "$\\quad\\;$__b. Effectuer les saisies Python correspondantes, et convertir les résultats en lettres.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('VOICI MON MESSAGE IMPORTANT', 'VOICI')"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Effectuer les saisies pour interpréter code1 et code2\n",
    "lettrage(dechiffre_RSA(7,13,5,code1)) , lettrage(chiffrement_RSA(253,9,code2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\quad\\;$__c. Qu'est ce qui assure à Balthazar que le message provient bien d'Archibald ?__\n",
    "\n",
    "<span style=\"color:red;\">\n",
    "Seul Archibald a pu déterminer la liste de valeurs <mark style=\"color:red;\">code2</mark> qui redonne le mot d'authentification \"VOICI\" quand on lui applique sa clé publique.<br>\n",
    "Ceci assure donc à Balthazar qu'Archibald est bien l'expéditeur.\n",
    "</span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <span style=\"color:#8E44AD\" id=\"4\">4. Compléments arithmétiques</span>\n",
    "<br>\n",
    "On rappelle l'énoncé du petit théorème de Fermat :\n",
    "<BLOCKQUOTE style='background-color:#CFB5B6;'>\n",
    "<strong>Théorème :</strong> <span style=\"color:#BB0000\">Petit théorème de Fermat.</span><br><br>\n",
    "Soit $x \\in \\mathbb{N}$. Si $\\begin{Bmatrix} p \\text{ est un nombre premier} \\\\ p \\text{ ne divise pas } x \\end{Bmatrix}$ alors $x^{\\;p-1} \\equiv 1 \\;[p]$.\n",
    "</BLOCKQUOTE>\n",
    "\n",
    "On reprend dans cette partie les notations de la partie 1, notamment :<br>\n",
    "<ul>\n",
    "    <li>$p$ et $q$ sont des nombres premiers distincts ;</li>\n",
    "    <li>$n=pq$ et $m=(p-1)(q-1)$ ;</li>\n",
    "    <li>$c$ et $m$ sont premiers entre eux et vérifient $1<c<m$ ;</li>\n",
    "    <li>$d$ vérifie $1 \\leq d < m$ et $cd \\equiv 1 \\;[m]$.</li>\n",
    "</ul>\n",
    "\n",
    "Le but de cette partie est de démontrer le résultat qui a été admis dans la question 1.4.c. :<br>\n",
    "On considère un entier positif $x$ et on souhaite démontrer que $x^{cd} \\equiv x \\;[n]$.<br>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "__4.0. a. Justifier qu'il existe un entier $k$ tel que $cd = km+1$.__<br>\n",
    "\n",
    "<span style=\"color:red;\">\n",
    "$cd \\equiv 1 \\;[m]$ donc il existe un entier $k$ tel que $cd = 1 +km$.\n",
    "</span>\n",
    "\n",
    "$\\quad\\;\\;$__b. Dresser la liste des diviseurs positifs de $n$ et en déduire les valeurs possibles de $PGCD(x,n)$.__<br>\n",
    "\n",
    "<span style=\"color:red;\">\n",
    "La décomposition de $n$ en produit de facteurs premiers est $n=pq$, donc les diviseurs positifs de $n$ sont $1$,$p$,$q$ et $pq$.<br>\n",
    "Comme $PGCD(x,n)$ est un diviseur de $n$, il peut être égal à $1$,$p$,$q$ ou $pq$.\n",
    "</span>\n",
    "\n",
    "\n",
    "Nous allons maintenant procéder à la démonstration par disjonction des cas.<br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__4.1. On suppose dans cette question que $PGCD(x,n)=1$, c'est à dire que $x$ et $n$ sont premiers entre eux.__<br>\n",
    "\n",
    "$\\quad\\;$__a. Justifier que $x^{(p-1)(q-1)} \\equiv 1 \\;[p]$ et que $x^{(p-1)(q-1)} \\equiv 1 \\;[q]$.__<br>\n",
    "\n",
    "<span style=\"color:red;\">\n",
    "$p$ est un nombre premier qui divise $n$, donc il ne peut pas diviser $x$ (sinon $PGCD(x,n)$ ne vaudrait pas 1).<br>\n",
    "$p$ n'apparait donc pas dans la décomposition en facteurs premiers de $x$ et donc pas non plus dans celle de $x^{q-1}$.<br>\n",
    "On peut donc appliquer le petit théorème de Fermat à $p$ et $x^{q-1}$, et on en déduit que :<br>\n",
    "$(x^{q-1})^{p-1} \\equiv 1 \\;[p]$<br>\n",
    "$x^{(p-1)(q-1)} \\equiv 1 \\;[p]$<br>\n",
    "Un raisonnement similaire (en permutant les rôles de $p$ et $q$) permet de démontrer que $x^{(p-1)(q-1)} \\equiv 1 \\;[q]$<br> \n",
    "</span>\n",
    "\n",
    "$\\quad\\;$__b. En déduire que $pq$ divise $x^{(p-1)(q-1)}-1$, et donc que $x^m \\equiv 1 \\;[n]$.__<br>\n",
    "\n",
    "<span style=\"color:red;\">\n",
    "$p$ et $q$ sont premiers, distincts, et divisent tous deux $x^{(p-1)(q-1)}-1$ d'après la question précédente.<br>\n",
    "$p$ et $q$ apparaissent donc dans la décomposition de $x^{(p-1)(q-1)}-1$ en produit de facteurs premiers, et comme ils sont distincts, on en déduit que $pq$ divise $x^{(p-1)(q-1)}-1$.<br>\n",
    "(NB : $p$ et $q$ étant premiers entre eux et divisant $x^{(p-1)(q-1)}-1$, on peut aussi conclure que $pq$ divise $x^{(p-1)(q-1)}-1$ en utilisant le corollaire du théorème de Gauss)<br>\n",
    "Il en résulte que $x^{(p-1)(q-1)}-1 \\equiv 0 \\;[pq]$, ce qui s'écrit aussi $x^m-1 \\equiv 0 \\;[n]$, c'est à dire finalement $x^m \\equiv 1 \\;[n]$.\n",
    "</span>\n",
    "\n",
    "$\\quad\\;$__c. À l'aide des questions 4.0.a et 4.1.b, démontrer que $x^{cd} \\equiv x \\;[n]$.__\n",
    "\n",
    "<span style=\"color:red;\">\n",
    "Comme $x^m \\equiv 1 [n]$, on en déduit en élevant à la puissance $k$ que $(x^m)^k \\equiv 1 [n]$.<br>\n",
    "Enfin, on a :<br>\n",
    "$x^{cd}=x^{km+1}=(x^m)^kx \\equiv x \\;[n]$.<br>    \n",
    "</span>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__4.2. On suppose dans cette question que $PGCD(x,n)=pq$.__<br> \n",
    "$\\quad\\;\\;$__Justifier que, dans ce cas, $x \\equiv 0 \\;[n]$ puis que $x^{cd} \\equiv x \\;[n]$.__<br>\n",
    "\n",
    "<span style=\"color:red;\">\n",
    "$PGCD(x,n)=pq=n$ donc $n$ divise $x$, et il en résulte que $x \\equiv 0 \\;[n]$.<br>\n",
    "En élevant à la puissance $cd$, on obtient $x^{cd} \\equiv 0 \\;[n]$.<br>\n",
    "Finalement, comme $x$ et $x^{cd}$ sont tous deux congrus à $0$ modulo $n$, ils sont congrus entre eux modulo $n$ :<br>\n",
    "$x^{cd} \\equiv x \\;[n]$\n",
    "</span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__4.3. On suppose dans cette question que $PGCD(x,n)=p$.__<br>\n",
    "$\\quad\\;\\;$__a. Justifier que $p$ est un diviseur de $x^{cd}-x$.__<br>\n",
    "\n",
    "<span style=\"color:red;\">\n",
    "$PGCD(x,n)=p$ donc $p$ est un diviseur de $x$.<br>\n",
    "Comme $cd>=1$, $p$ est aussi un diviseur de $x^{cd}$.<br>\n",
    "Enfin, on en déduit que $p$ divise $x^{cd}-x$ (qui est une combinaison linéaire de $x^{cd}$ et $x$).\n",
    "</span>\n",
    "\n",
    "$\\quad\\;\\;$__b. Démontrer que $x^{cd} = (x^{q-1})^{k(p-1)}x$.__<br>\n",
    "\n",
    "<span style=\"color:red;\">\n",
    "$x^{cd}=x^{km+1}=x^{k(p-1)(q-1)+1}=(x^{q-1})^{k(p-1)}x$\n",
    "</span>\n",
    "\n",
    "$\\quad\\;\\;$__c. Justifier que $x^{q-1} \\equiv 1 \\;[q]$.__<br>\n",
    "\n",
    "<span style=\"color:red;\">\n",
    "$q$ divise $n$ donc ne peut pas diviser $x$ (sinon $q$ diviserait $PGCD(x,n)=p$, ce qui est absurde).<br>\n",
    "Comme $q$ est premier et ne divise pas $x$, on peut appliquer le petit théorème de Fermat :<br>\n",
    "$x^{q-1} \\equiv 1 \\;[q]$    \n",
    "</span>\n",
    "\n",
    "$\\quad\\;\\;$__d. Déduire des questions 4.3.b. et 4.3.c que $x^{cd} \\equiv x \\;[q]$, c'est à dire que $q$ est un diviseur de $x^{cd}-x$__<br>\n",
    "\n",
    "<span style=\"color:red;\">\n",
    "$x^{q-1} \\equiv 1 \\;[q]$ donc en élevant à la puissance $k(p-1)$ on obtient $(x^{q-1})^{k(p-1)} \\equiv 1 \\;[q]$.<br>\n",
    "On a donc :<br>\n",
    "$x^{cd}=(x^{q-1})^{k(p-1)}x \\equiv x \\;[q]$\n",
    "</span>\n",
    "\n",
    "\n",
    "\n",
    "$\\quad\\;\\;$__e. À l'aide des questions 4.3.a. et 4.3.d, justifier que $x^{cd} \\equiv x \\;[n]$.__\n",
    "\n",
    "<span style=\"color:red;\">\n",
    "$x^{cd} \\equiv x \\;[q]$ donne $x^{cd}-x \\equiv 0 \\;[q]$, ce qui prouve que $q$ divise $x^{cd}-x$.\n",
    "On a finalement démontré que $p$ et $q$ sont deux facteurs premiers distincts de la décomposition de $x^{cd}-x$ en produit de facteurs premiers.<br>\n",
    "Il en résulte que $n=pq$ divise $x^{cd}-x$, c'est à dire que $x^{cd} \\equiv x \\;[n]$<br>\n",
    "(NB : $p$ et $q$ étant premiers entre eux et divisant $x^{cd}-x$, on peut aussi conclure que $pq$ divise $x^{cd}-x$ en utilisant le corollaire du théorème de Gauss) \n",
    "</span>\n",
    "\n",
    "\n",
    "\n",
    "__4.4. Conclure.__<br>\n",
    "\n",
    "<span style=\"color:red;\">\n",
    "Le cas où $PGCD(x,n)=q$ étant similaire à celui étudié à la question 4.3 (en permutant les rôles de $p$ et $q$), on a bien démontré dans tous les cas que $x^{cd} \\equiv x \\;[n]$.\n",
    "</span>\n",
    "\n",
    "\n",
    "Remarque : Le résultat de la question 4.1.b est un cas particulier du <a href=\"https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_d%27Euler_(arithm%C3%A9tique)\">théorème d'Euler en arithmétique modulaire</a>, qui est une généralisation du petit théorème de Fermat."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![RSA](img/RSA.png)\n",
    "\n",
    "<center> <a href=\"https://fr.wikipedia.org/wiki/Adi_Shamir\">Adi <strong>S</strong>hamir</a>, <a href=\"https://fr.wikipedia.org/wiki/Ronald_Rivest\">Ronald <strong>R</strong>ivest</a>  et <a href=\"https://fr.wikipedia.org/wiki/Leonard_Adleman\">Leonard <strong>A</strong>dleman</a> sont à l'origine de l'<a href=\"https://fr.wikipedia.org/wiki/Chiffrement_RSA\">algorithme de chiffrement <strong>RSA</strong></a></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/*<br>\n",
    "<span style=\"color:#8E44AD\">*Remerciements particuliers à Nicolas EHRSAM pour sa précieuse collaboration.*</span>"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Raw Cell Format",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}