Différences

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

--- nsi:terminales:securite:rsa [2023/03/31 10:53] – goupillwiki
+++ nsi:terminales:securite:rsa [2023/04/11 15:02] (Version actuelle) – goupillwiki
@@ Ligne 40: / Ligne 40: @@
 <WRAP box>
-==== À faire ====
 === Quelques questions ===
@@ Ligne 66: / Ligne 64: @@
 >>> Kpu, Kpr = make_keys(50005987, 74013803)
 >>> Kpu
+(3701133270638561, 17)
 >>> Kpr
+(3701133270638561, 1088568572534933)
 </code>
 </WRAP>
@@ Ligne 73: / Ligne 73: @@
 </WRAP>
-=== Tests
+===== Chiffrer / Déchiffrer avec des int =====
+Nous commençons par une version très simple où on ne s'embarrasse pas avec les ''bytes''.
-===== Conversions int - bytes, taille en octets =====
+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 121: / 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 216: / 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>