Différences

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

--- nsi:terminales:securite:rsa [2023/03/31 11:13] – goupillwiki
+++ nsi:terminales:securite:rsa [2023/04/11 15:02] (Version actuelle) – goupillwiki
@@ Ligne 147: / 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 ===
@@ Ligne 166: / Ligne 167: @@
 <code python>
 >>> Kpu, Kpr = make_keys(50005987, 74013803)
->>> m = bytes
+>>> mb = bytes([41, 56, 176, 88, 82, 67])
->>> chiffrer_int(45323453485635, Kpu)
+>>> mcb = chiffrer_bytes(mb, Kpu)
-73262112569103
+>>>list(mcb)
->>> dechiffrer_int(73262112569103, Kpr)
+[66, 161, 170, 49, 247, 15]
-45323453485635
+>>> mb2 = dechiffrer_bytes(mcb, Kpr)
+>>> list(mb2)
+[41, 56, 176, 88, 82, 67]
 </code>
+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>
+===== 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é.
+<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>
+=== Amélioration : le bourrage  ===
+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.
+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.
+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.
-<WRAP box>
+Mais si on fait cela, à la réception, comment démêlera-t-on la partie bourrage de la partie message ?
-=== À faire ===
-É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.
+On choisit donc :
-</WRAP>
+  * 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
-===== Déchiffrer =====
+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 :
-C'est exactement la même chose mais en utilisant $Kpr$ au lieu de $Kpu$.
+''%%<4><hasard><hasard><hasard><mb>%%''.
+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')
->>> mcb = chiffrer(mb, Kpu)
->>> list(mcb)
-[2, 127, 116, 114, 183, 42, 173]
->>> dechiffrer(mcb, Kpr)
-b'\x00\x00chien'
-</code>
-Vérifiez que vous obtenez bien la même chose.
+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é.
-<WRAP tip>
+Il faudra alors découper le message en morceaux et chiffrer ces morceaux indépendamment.
-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.
+=== Choix ===
+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 ===
+  * 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.
+Utilisez un fichier quelconque, par exemple une image, et vérifiez le bon fonctionnement.
 </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 237: / 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>