{"cells":[{"metadata":{},"cell_type":"markdown","source":"![En tête general](https://raw.githubusercontent.com/PythonLycee/PyLyc/master/img/En_tete_general.png)\n\n\n<i>© Copyright Franck CHEVRIER 2019-2022 https://www.python-lycee.com.</i><br>\n<i>Les activités partagées sur <a href=\"https://capytale2.ac-paris.fr/web/accueil\"><strong>Capytale</strong></a> sont sous licence <a href=\"https://creativecommons.org/licenses/by-sa/3.0/fr/\">Creative Commons</a>.</i>\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"},{"metadata":{},"cell_type":"markdown","source":"# <span style=\"color:#6C3483\">Chiffrement RSA\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](https://raw.githubusercontent.com/PythonLycee/PyLyc/master/img/Chiffrement_RSA.png)"},{"metadata":{},"cell_type":"markdown","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>"},{"metadata":{},"cell_type":"markdown","source":"## <span style=\"color:#8E44AD\" id=\"1\">1. Principe du chiffrement RSA</span>"},{"metadata":{},"cell_type":"markdown","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>\nDans 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>\nPour 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>"},{"metadata":{},"cell_type":"markdown","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"},{"metadata":{},"cell_type":"markdown","source":"Archibald fournit le couple $(n;c)$ à ses associés, et garde les valeurs $p$ et $q$ secrètes.<br><br>\nBalthazar, 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>\nPour 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>\nEnsuite, 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>\nExemple :<br>\nAvec les valeurs choisies précédemment, la lettre <strong>I</strong> correspond à la valeur $x=8$.<br>\nComme $x^9=8^9=134217728 \\equiv 216 [253]$, cette lettre se code avec la valeur $216$.\n"},{"metadata":{},"cell_type":"markdown","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."},{"metadata":{"trusted":false},"cell_type":"code","source":"#Utiliser si nécessaire cette zone pour les calculs en Python\n\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","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.__"},{"metadata":{"trusted":false},"cell_type":"code","source":"#Mise en mémoire de l'alphabet (+espace)\nAlphabet=\"ABCDEFGHIJKLMNOPQRSTUVWXYZ \"\n\ndef 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    \ndef 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        ","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"#Effectuer ici les appels aux fonctions chiffrage et chiffrement_RSA\n\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","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$\\;\\;\\;\\;\\;$__b. Déterminer cette valeur $d$ (on pourra commencer par appliquer l'algorithme d'Euclide).__<br>\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"},{"metadata":{"trusted":false},"cell_type":"code","source":"#Effectuer ici les calculs\n\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","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$\\;\\;\\;\\;\\;$__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."},{"metadata":{"trusted":false},"cell_type":"code","source":"#Utiliser si nécessaire cette zone pour les calculs en Python\n\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","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://notebook.basthon.fr/?from=https://raw.githubusercontent.com/PythonLycee/PyLyc/master/PGCD_Euclide_Bezout_vd.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.__"},{"metadata":{"trusted":false},"cell_type":"code","source":"import numpy as np\n\ndef 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","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"#Effectuer ici un appel à la fonction inv\n\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","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>"},{"metadata":{"trusted":false},"cell_type":"code","source":"#Écrire ici la fonction dechiffre_RSA\n\n\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","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.__"},{"metadata":{"trusted":false},"cell_type":"code","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","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"#Effectuer ici un appel à la fonction dechiffre_RSA\n\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"#Effectuer ici un appel à la fonction lettrage\n\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","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>"},{"metadata":{"trusted":false},"cell_type":"code","source":"#Effectuer ici un appel à la fonction dechiffre_RSA\n\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"#Effectuer ici un appel à la fonction lettrage\n\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## <span style=\"color:#8E44AD\" id=\"2\">2. Échanges sécurisés de message</span>\n<br><br>\nOn reprend dans cette partie les notations de la partie précédente."},{"metadata":{},"cell_type":"markdown","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"},{"metadata":{"trusted":false},"cell_type":"code","source":"from random import randint\n\ndef 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\ndef 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\ndef 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\np = premier() \n\n#génération d'un nombre premier q à 3 chiffres, distinct de p\nq = p\nwhile q == p : q = premier() \n\n#génération de c premier avec m\nm = (p-1)*(q-1)    \nc = 0\nwhile PGCD(c,m)!=1: c = randint(2,m-1) \n\n    \np,q,c","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"__2.2. Effectuer les saisies nécessaires pour calculer $n$.__"},{"metadata":{"trusted":false},"cell_type":"code","source":"#Effectuer ici les saisies pour le calcul de n\n\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","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"},{"metadata":{"trusted":false},"cell_type":"code","source":"\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Si C interceptait le message codé envoyé par B, pourrait-il le décoder ?...<br><br>\nPour 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>\nConnaissant $n$, C devrait retrouver la décomposition en facteurs premiers $n=pq$.<br><br>\nLa 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>\nPar ailleurs, le chiffrement RSA procède en réalité par codage par blocs et non par caractères."},{"metadata":{},"cell_type":"markdown","source":"## <span style=\"color:#8E44AD\" id=\"3\">3. Principe d'authentification</span>\n<br><br>\nOn reprend dans cette partie les notations des parties précédentes.<br><br>\n\nArchibald et Balthazar disposent chacun d'une clé publique et d'une clé privée pour le chiffrement RSA.<br><br>\n\nArchibald souhaite envoyer un message à Balthazar de telle sorte que celui-ci soit certain de l'origine du message.<br>\nMais toutes les personnes qui écrivent à Balthazar utilisent la même clé publique...<br><br>\n\nPour 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\nSupposons 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"},{"metadata":{},"cell_type":"markdown","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.__"},{"metadata":{"trusted":false},"cell_type":"code","source":"message = \"VOICI MON MESSAGE IMPORTANT\"    #message à envoyer\nmot_auth = message[:5]                     #partie du message pour l'authentification (ici le premier mot)\n\nmessage , mot_auth","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","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\n\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"#Effectuer ici les saisies pour obtenir les listes envoyées par Balthazar\n#(on pourra nommer ces listes code1 et code2)\n\n\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","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$\\quad\\;$__b. Effectuer les saisies Python correspondantes, et convertir les résultats en lettres.__"},{"metadata":{"trusted":false},"cell_type":"code","source":"#Effectuer les saisies pour interpréter code1 et code2\n\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"$\\quad\\;$__c. Qu'est ce qui assure à Balthazar que le message provient bien d'Archibald ?__\n"},{"metadata":{},"cell_type":"markdown","source":"## <span style=\"color:#8E44AD\" id=\"4\">4. Compléments arithmétiques</span>\n<br>\nOn 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>\nSoit $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\nOn 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\nLe but de cette partie est de démontrer le résultat qui a été admis dans la question 1.4.c. :<br>\nOn considère un entier positif $x$ et on souhaite démontrer que $x^{cd} \\equiv x \\;[n]$.<br>\n"},{"metadata":{},"cell_type":"markdown","source":"\n__4.0. a. Justifier qu'il existe un entier $k$ tel que $cd = km+1$.__<br>\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<br>\nNous allons maintenant procéder à la démonstration par disjonction des cas.<br>"},{"metadata":{},"cell_type":"markdown","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$\\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$\\quad\\;$__c. À l'aide des questions 4.0.a et 4.1.b, démontrer que $x^{cd} \\equiv x \\;[n]$.__\n"},{"metadata":{},"cell_type":"markdown","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"},{"metadata":{},"cell_type":"markdown","source":"__4.3. On suppose dans cette question que $PGCD(x,n)=p$.__<br>\n\n$\\quad\\;\\;$__a. Justifier que $p$ est un diviseur de $x^{cd}-x$.__<br>\n\n$\\quad\\;\\;$__b. Démontrer que $x^{cd} = (x^{q-1})^{k(p-1)}x$.__<br>\n\n$\\quad\\;\\;$__c. Justifier que $x^{q-1} \\equiv 1 \\;[q]$.__<br>\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$\\quad\\;\\;$__e. À l'aide des questions 4.3.a. et 4.3.d, justifier que $x^{cd} \\equiv x \\;[n]$.__\n\n\n__4.4. Conclure.__<br>\n\n\nRemarque : 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."},{"metadata":{},"cell_type":"markdown","source":"![RSA](https://raw.githubusercontent.com/PythonLycee/PyLyc/master/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>"},{"metadata":{},"cell_type":"markdown","source":"<i>© Copyright Franck CHEVRIER 2019-2022 https://www.python-lycee.com.</i><br>\n<i>Les activités partagées sur <a href=\"https://capytale2.ac-paris.fr/web/accueil\"><strong>Capytale</strong></a> sont sous licence <a href=\"https://creativecommons.org/licenses/by-sa/3.0/fr/\">Creative Commons</a>.</i><br>\n<span style=\"color:#8E44AD\">*Remerciements particuliers à Nicolas EHRSAM pour sa précieuse collaboration.*</span>\n<br><br>\n<span style=\"font-size:8px\">Dernière modification de l'activité : Juillet 2022</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}