Différences

Ci-dessous, les différences entre deux révisions de la page.

--- nsi:terminales:securite:rsa [2023/03/31 10:44] – goupillwiki
+++ nsi:terminales:securite:rsa [2023/04/11 15:02] (Version actuelle) – goupillwiki
@@ Ligne 11: / Ligne 11: @@
 ==== Nombres premiers ====
-Nous allons utiliser des nombres premiers. Pour les démonstrations, des nombres premiers peuvent suffire. Vous en trouverez une liste [[https://fr.numere-prime.ro/1-1000-liste-tous-nombres-premiers-du-premier-2-dernier-997.php|ici]].
+Nous allons utiliser des nombres premiers. Pour les démonstrations, des nombres premiers peuvent suffire. Vous en trouverez une liste [[http://compoasso.free.fr/primelistweb/page/prime/liste_online.php|ici]].
 Mais la solidité de RSA est garantie par l'utilisation de nombres premiers très grands : de l'ordre de 500 à 1000 bits. $2^{1000} \approx 1000^{100} = 1\overbrace{000\cdots0}^{300\times}$.
@@ Ligne 21: / Ligne 21: @@
 Ces premiers étant très nombreux, la probabilité que deux personnes trouvent une même paire de premiers est négligeable.
-==== Méthode ====
+Dans nos exemples, on pourra prendre par exemple : ''p = 50005987'', et ''q = 74013803'' (mais vous êtes libre d'en tester d'autres !)
+=== Méthode ===
   * Choisir $p$ et $q$ deux premiers.\\ Il existe quelques conditions pour que le chiffrement reste solide et évite certaines techniques de déchiffrement. Nous n'entrerons pas dans ces détails mais si vous êtes curieux, voir sur [[https://fr.wikipedia.org/wiki/Chiffrement_RSA#Engendrer_les_clefs|Wikipedia]].
   * Calculer $n = p\times q$.
   * Calculer $\varphi = (p-1)\times(q-1)$.
-  * Choisir $e$ premier avec $\varphi$ et inférieur.\\ On peut choisir $e$ premier, ce qui garantit que $e$ sera premier avec $\varphi$.\\ Pour faciliter les calculs, on préfère un $e$ dont l'écriture binaire n'ait pas trop de ''1''. On peut choisir 3, 17 -- pour les expérimentations -- ou encore 65537.
+  * Choisir $e$ premier avec $\varphi$ et inférieur.\\ On peut choisir $e$ premier, ce qui garantit que $e$ sera premier avec $\varphi$.\\ Pour faciliter les calculs, on préfère un $e$ dont l'écriture binaire n'ait pas trop de ''1''. On peut choisir 3, 17 -- pour les expérimentations -- ou encore 65537.\\ **Attention :**Même avec $e$ premier, on a le risque que $e$ divise $\varphi$. Il faut donc s'assurer que ça n'arrive pas.
   * Calculer $d$, [[nsi:tds:cryptographie:inverse_modulaire|inverse modulaire]] de $e \mod \varphi$.
-==== Clé publique ====
+=== Clé publique ===
 La paire $(n,e)$ constitue la **clé publique**.
-==== Clé privée ====
+=== Clé privée ===
 La paire $(n,d)$ constitue la **clé privée**.
 <WRAP box>
-==== À faire ====
 === Quelques questions ===
@@ Ligne 51: / Ligne 51: @@
 === Implémentation ===
+On choisit $e = 17$ dans tous les cas.
 Écrivez une fonction Python ''%%make_keys(p, q)%%'' qui reçoit les premiers ''p'' et ''q'' et renvoie  ''Kpu = (n,e)'' et ''Kpr = (n,d)''.
+**précondition :** $e$ ne doit pas diviser $\varphi$.
+Vous pouvez vérifier que l'on obtient bien :
+<code python>
+>>> Kpu, Kpr = make_keys(50005987, 74013803)
+>>> Kpu
+(3701133270638561, 17)
+>>> Kpr
+(3701133270638561, 1088568572534933)
+</code>
 </WRAP>
@@ Ligne 58: / Ligne 73: @@
 </WRAP>
-===== Conversions int - bytes, taille en octets =====
+===== Chiffrer / Déchiffrer avec des int =====
+Nous commençons par une version très simple où on ne s'embarrasse pas avec les ''bytes''.
+Pour chiffrer le message $m$, un entier, avec la clé $Kpu = (n, e)$, il suffit de calculer :
+$$m_c \overset{n}{=}m^e$$
+Pour déchiffrer le message $m'$ avec la clé $Kpr = (n, d)$, il suffit de calculer :
+$$m \overset{n}{=}m_c^d$$
+**Précondition :** il faut $m < n$. On aura alors automatiquement $m_c < n$.
+<WRAP box>
+=== Implémenter ===
+Faites l'implémentation des fonctions :
+  * ''%%chiffrer_int(m:int, Kpu) -> int%%'' qui reçoit le message à chiffrer (entier ''m'') et la clé publique. La fonction renvoie le message chiffré sous forme d'un entier.
+  * ''%%dechiffrer_int(mc:int, Kpr) -> int%%'' qui reçoit le message à déchiffrer (entier ''mc'') et la clé privée. La fonction renvoie le message déchiffré sous forme d'un entier.
+Vérifiez que l'on a bien :
+<code python>
+>>> Kpu, Kpr = make_keys(50005987, 74013803)
+>>> chiffrer_int(45323453485635, Kpu)
+73262112569103
+>>> dechiffrer_int(73262112569103, Kpr)
+45323453485635
+</code>
+</WRAP>
+===== Utiliser des bytes =====
 L'algorithme de chiffrement implique des calculs sur de grands nombres qui doivent être de type ''int''. Mais il peut arriver que ces nombres doivent être disponibles sous une forme ''bytes''. Par exemple, on pourrait vouloir stocker ces nombres dans un fichier et le format ''bytes'' sera plus commode pour cela.
@@ Ligne 97: / Ligne 141: @@
   * ''%%'big'%%'' signifie qu'on les collera dans l'ordre où ils arrivent, c'est à dire :\\ ''0b 00000001 00000000'', soit le nombre 256.
-  * ''%'little'%%'' signifie qu'on les colle en sens inverse, c'est à dire :\\''0b 00000000 00000001'', soit le nombre 1.
+  * ''%%'little'%%'' signifie qu'on les colle en sens inverse, c'est à dire :\\''0b 00000000 00000001'', soit le nombre 1.
 On pourra choisir ''%%'big'%%'' à chaque fois.
@@ Ligne 103: / Ligne 147: @@
 === De int à bytes ===
-C'est encore plus simple :
+Il faut connaître le nombre d'octets désiré. Par exemple, si ''n = 4503268953'', il faut au minimum 5 octets. Mais on pourrait en prendre 6 ou 7 ou plus.
 <code python>
 >>> n = 4503268953
->>> b = n.to_bytes('big')
+>>> b = n.to_bytes(5, 'big')
 </code>
+<WRAP box>
+=== Adapter les fonctions ===
+Implémenter les fonctions suivantes :
+  * ''%%chiffrer_bytes(mb:bytes, Kpu) -> bytes%%'' qui reçoit le message à chiffrer sous la forme ''bytes''. La fonction doit reconstituer l'entier ''m'' à partir de ''mb'', puis faire le chiffrement comme précédemment, puis enfin convertir le message chiffré ''mc'' au format ''bytes''.
+  * ''%%dechiffrer_bytes(mcb:bytes, Kpr) -> bytes%%'' qui reçoit le message à déchiffrer sous la forme ''bytes'' et renvoie le message déchiffré sous la forme ''bytes''. Même principe que pour ''%%chiffrer_bytes%%'' .
+Vérifiez que l'on a bien :
+<code python>
+>>> Kpu, Kpr = make_keys(50005987, 74013803)
+>>> mb = bytes([41, 56, 176, 88, 82, 67])
+>>> mcb = chiffrer_bytes(mb, Kpu)
+>>>list(mcb)
+[66, 161, 170, 49, 247, 15]
+>>> mb2 = dechiffrer_bytes(mcb, Kpr)
+>>> list(mb2)
+[41, 56, 176, 88, 82, 67]
+</code>
-===== Chiffrer =====
+Remarquez que j'écris ''list'' à certains endroits pour éviter l'écriture standard de Python dans le cas des ''bytes''. L'écriture de Python qui ressemble à une chaîne de caractères est difficile à comprendre. Je préfère une liste de nombres qui montre bien les octets.
+</WRAP>
-Soit un message ''mb'' de type ''bytes'' et la clé publique ''Kpu = (n, e)''.
+===== Bourrage =====
+La clé ''n'' est est très grande, mais le message à transmettre ne l'est pas forcément. Si on échangeait beaucoup de messages avec un message petit, on aurait des risques de sécurité.
-Il faut transformer ''mb'' dans le nombre entier ''m'' correspondant :
+<WRAP box>
+=== À faire ===
-<code python>
+Pour vous en convaincre, imaginez que Alice veuille transmettre à Bob le message ''mb'', très simple, de seulement un octet. Alice chiffre avec ''Kpu'' et obtient ''mcb'' qu'elle envoie sur internet. Eve intercepte ''mcb''. Bien sûr, Eve connaît ''Kpu'' qui est publique.
->>> m = int.from_bytes(mb, 'big')
-</code>
-L'argument ''%%'big'%%'' indique dans quel ordre est écrit le nombre. Mais cela n'a pas d'importance tant qu'on utilise le même ordre au chiffrement et au déchiffrement.
+Comment Eve peut-elle retrouver ''mb''. Elle exploite le fait que ''mb'' est court.
+</WRAP>
-**condition :** Il faut ''m < n''.
+=== Amélioration : le bourrage  ===
-Le calcul du message chiffré est tout simplement $m' \overset{n}{=}m^e$.
+Puisque ''mb'' est petit, on est libre de compléter ''mb'' avec une partie aléatoire ce qui va embrouiller le message et rendre beaucoup plus difficile toute tentative de déchiffrement.
-> Pour le calcul $mc \overset{n}{=}m^e$ on utilisera l'exponentielle modulaire définie dans [[nsi:tds:cryptographie:exponentiation_modulaire]].
+Prenons un **exemple** : notre ''n = 3701133270638561'' s'écrit avec 7 octets. On a le droit de transmettre un message ''mb'' plus petit que ''n''. On peut donc transmettre n'importe quel message ''mb'' de 6 octets.
-Il faut enfin transformé le message chiffré ''mc'' dans le type ''bytes''. On peut écrire :
+Supposons que ''mb'' ne soit constitué que de deux octets. Il reste donc 4 octets que l'on peut bourrer librement avec des octets au hasard.
-<code python>
+Mais si on fait cela, à la réception, comment démêlera-t-on la partie bourrage de la partie message ?
->>> s = octets_size(n)
->>> mcb = mc.to_bytes(s, 'big')
-</code>
-<WRAP box>
+On choisit donc :
-=== À faire ===
+  * on détermine la taille de ''n''. Ici ''taille_n = 7'' ;
+  * on détermine la taille ''taille_mb'' de ''mb'' ;
+  * on calcule le nombre d'octets restants : ''rb = taille_n - taille_mb - 1''.\\ Par exemple, pour notre ''n'' de 7 octets et ''m'' sur 2 octets, on aurait ''rb = 7 - 2 - 1 = 4''.
+  * nous disposons donc de ''rb'' octets de bourrage.\\ Au déchiffrement, il faudra enlever le bourrage. Il faudra donc connaître le nombre d'octets de bourrage. on consacre donc le premier octet de bourrage à cela.\\ il faut donc que ''rb >= 1''
+  * les autres octets de bourrage seront aléatoires
-Écrivez une fonction ''chiffrer_RSA(mb, Kpu)'' où ''mb'' est le message de type ''bytes'', ''Kpu'' est la clé publique, et qui renvoie le message chiffré sous la forme bytes.
+Dans l'exemple, avec ''taille_n = 7'', ''taille_mb = 2'', ''rb = 4'', on devra produire 3 octets aléatoires et on complètera ''mb'' de la façon suivante :
-</WRAP>
-===== Déchiffrer =====
+''%%<4><hasard><hasard><hasard><mb>%%''.
-C'est exactement la même chose mais en utilisant $Kpr$ au lieu de $Kpu$.
+Une fois ''mb'' augmenté, on peut chiffrer.
+Au déchiffrement, il faudra commencé par déchiffrer, ce qui nous donnera la version augmentée de ''mb''. Puis il faudra lire le premier octet non nul, correspondant à ''taille_bourrage'', ce qui nous permettra de supprimer le bourrage afin de ne renvoyer que le message ''mb'' d'origine.
 <WRAP box>
-=== À faire ===
+=== Implémentation ===
-Écrivez une fonction ''dechiffrer_RSA(mcb, Kpr)'' où ''mcb'' est le message chiffré de type ''bytes'', ''Kpr'' est la clé privée, et qui renvoie le message déchiffré sous la forme bytes.
+Implémentez les fonctions ''%%chiffrer_pad(mb:bytes, Kpu) -> bytes%%'' et ''%%dechiffrer_pad(mcb:bytes, Kpr) -> bytes%%'' mettant en œuvre le bourrage.
-</WRAP>
-===== Test =====
+//padding = bourrage//
+</WRAP>
-Je vous propose de prendre ''p = 50005987'' et ''q = 74013803'', deux nombres premiers très grands.
-  * La clé publique est alors ''Kpu = (3701133270638561, 17)''
+===== Avec découpage =====
-  * La clé privée est ''Kpr = (3701133270638561, 1088568572534933)''
-  * Le nombre ''n = 3701133270638561'' s'écrit avec 7 octets. On pourra donc sans problème envoyer n'importe quel message de 6 octets ou moins.
-  * Choisissons le message ''%%mb = "chien".encode('utf8')%%''. C'est un message de 5 octets.
-<code python>
+Nos fonctions nécessitent que le message soit plus court que ''n''. En général ce n'est pas un problème car on n'utilise pas l'algorithme RSA pour un chiffrement complet. RSA est utilisé pour transmettre une clé pour poursuivre l'échange avec un chiffrement symétrique classique, plus efficace.
->>> Kpu = make_keys(50005987, 74013803)
->>> mb = "chien".encode('utf8')
+Néanmoins, on pourrait désirer chiffrer tout un fichier avec RSA. Dans ce cas on sera coincé par le fait que le fichier sera probablement plus grand que la clé.
->>> mcb = chiffrer(mb, Kpu)
->>> list(mcb)
+Il faudra alors découper le message en morceaux et chiffrer ces morceaux indépendamment.
-[2, 127, 116, 114, 183, 42, 173]
->>> dechiffrer(mcb, Kpr)
+=== Choix ===
-b'\x00\x00chien'
-</code>
+Soit ''%%taille_n%%'' la taille de la clé. On décide qu'un morceau ne pourra pas faire plus que ''%%taille_n - 4%%''. Le bloc chiffré devra toujours compter ''taille_n'' bytes.
+Au chiffrement, il faudra couper le message en autant de blocs que nécessaires. Le message chiffrer comptera autant de blocs, tous de même tailles, mis bout à bout.
+Au déchiffrement, on devra découper le message à déchiffrer en connaissant la taille des blocs. Il ne restera qu'à mettre bout à bout les blocs déchiffrés.
+<WRAP box>
+=== Implémentation ===
-Vérifiez que vous obtenez bien la même chose.
+  * Implémentez les fonctions ''%%chiffrer(mb:bytes, Kpu) -> bytes%%'' et ''%%dechiffrer(mcb:bytes, Kpr) -> bytes%%'' réalisant le chiffrement et le déchiffrement selon cette méthode.
+  * Implémentez les fonctions ''%%chiffrer_file(source:str, cible:str, Kpu)%%'' et ''%%dechiffrer(source:str, cible:str, Kpr)%%'' réalisant le chiffrement et le déchiffrement à partir de fichiers.
-<WRAP tip>
+Utilisez un fichier quelconque, par exemple une image, et vérifiez le bon fonctionnement.
-Le résultat à l'air satisfaisant mais on a un petit problème : le message de départ était ''%%"chien"%%'' ce qui une fois encodé donne ''%%b'chien'%%''. Alors d'où viennent ces ''%%\x00%%'' du message déchiffré ? Cela vient du fait que nos fonctions produisent des ''bytes'' de taille fixe. Puisque ''n'' fait 7 octets, le message chiffré et le message déchiffré doivent faire 7 octets, quitte à bourré en ajoutant des 0 à gauche.
 </WRAP>
-===== Justification =====
+===== Justification de l'algo RSA =====
 D'après le [[https://fr.wikipedia.org/wiki/Petit_th%C3%A9or%C3%A8me_de_Fermat|petit théorème de Fermat]], on sait que si $q$ premier, pour $a$ non divisible par $q$, alors $a^{q-1} \overset{q}{\equiv} 1$.
@@ Ligne 198: / Ligne 265: @@
   * On conclut que $C^d \overset{n}{\equiv} = B$.
-===== Amélioration =====
-Le chiffrement est déterministe si bien qu'un même message de départ produit toujours le même résultat chiffré. Si les messages à transmettre sont courts, cela peut occasionner une fragilité du chiffrement.
-<WRAP box>
-=== À faire ===
-Pour vous en convaincre, imaginez que Alice veuille transmettre à Bob le message ''mb'', très simple, de seulement un octet. Alice chiffre avec ''Kpu'' et obtient ''mcb'' qu'elle envoie sur internet. Eve intercepte ''mcb''. Bien sûr, Eve connaît ''Kpu'' qui est publique.
-Comment Eve peut-elle retrouver ''mb''. Elle exploite le fait que ''mb'' est court.
-</WRAP>
-Une façon de contourner ce problème est d'imposer un remplissage.
-Par exemple, avec la clé ''n'' testée plus haut faisait 7 octets. On peut donc transmettre 6 octets. Supposons que l'on fasse ceci :
-  * on veut chiffrer ''mb'' qui est petit. par exemple 1 ou 2 ou 3 octets.
-  * on commence par calculer ''s'', la taille de ''mb'' en octets.
-  * on produit la suite ''B'' d'octets suivante ''%%<s><hasard>...<hasard><mb>%%'' en faisant en sorte que cette suite face exactement un octet de moins que ''n'' (donc 6 aussi).
-Par exemple, si ''mb'' ne fait que 2 octets, alors ''s = 2'' et la suite d'octet serait ''%%<1><hasard><hasard><hasard><mb>%%''. Les octets ''%%<hasard>%%'' sont tous différents et choisis au hasard.
-Quand on déchiffre et qu'on rétrouve ''B'', on est certain que le premier octet non nul correspond à ''s'' et ''s'' permet de savoir quels octets sont vraiment importants. Par exemple, si ''s = 2'' on sait que seuls les 2 derniers octets de ''B'' sont importants.
-<WRAP box>
-=== À faire ===
-Faites la modification. Vérifiez que si on chiffre un message de un seul octet, le message chiffré change à chaque fois de sorte qu'il devient impossible d'utiliser la technique décrite précédemment.
-</WRAP>