Différences

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

--- nsi:terminales:securite:rsa [2022/03/28 13:28] – ↷ Liens modifiés en raison d'un déplacement. 193.51.53.161
+++ nsi:terminales:securite:rsa [2023/04/11 15:02] (Version actuelle) – goupillwiki
@@ Ligne 1: / Ligne 1: @@
 ====== Chiffrement RSA ======
-Nommé selon les initiales de ses inventeurs, en 1977 : **Ronald Rivest**, **Adi Shamir** et **Leonard Adleman**. Il s'agit d'un [[nsi:terminales:chiffrement_symetrique_asymetrique|chiffre asymétrique]], c'est à dire que la clé pour chiffrer est différente de la clé pour chiffrer.
+Nommé selon les initiales de ses inventeurs, en 1977 : **Ronald Rivest**, **Adi Shamir** et **Leonard Adleman**. Il s'agit d'un [[nsi:terminales:securite:chiffrement_symetrique_asymetrique|chiffre asymétrique]], c'est à dire que la clé pour chiffrer est différente de la clé pour chiffrer.
 Comme pour le [[nsi:tds:cryptographie:elgamal|chiffre de ElGamal]], RSA exploite des propriétés arithmétiques des nombres premiers.
@@ 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>
-===== Chiffrer =====
+===== Chiffrer / Déchiffrer avec des int =====
-On veut chiffrer l'entier $K$ connaissant $Kpu = (n,e)$
+Nous commençons par une version très simple où on ne s'embarrasse pas avec les ''bytes''.
-=== Découper en blocs ===
+Pour chiffrer le message $m$, un entier, avec la clé $Kpu = (n, e)$, il suffit de calculer :
+$$m_c \overset{n}{=}m^e$$
-En binaire, on découpe $K$ en blocs $B$ dont les valeurs doivent être plus petites que $n$.
+Pour déchiffrer le message $m'$ avec la clé $Kpr = (n, d)$, il suffit de calculer :
+$$m \overset{n}{=}m_c^d$$
-Par exemple, si $n > 255$,
+**Précondition :** il faut $m < n$. On aura alors automatiquement $m_c < n$.
-  * on pourra découper $K$ en octets (chaque octet sera $<n$)
-  * Avec $n= 1\,763$ et $K = 12\,596$, $K$ s'écrit en binaire $11000100110100_b$.
-  * $K$ utilise 14 bits, on complète par des $0$ à gauche :\\ $K = 00110001\,\, 00110100_b$ ce qui produit deux blocs $00110001$ et $00110100$.
-  * Soit $B$ l'un des blocs. On a donc $0 \leqslant B < n$.
-Notre clé sera un ''bytes'' obtenu directement par lecture de fichier. Le découpage sera donc déjà fait.
+<WRAP box>
+=== Implémenter ===
-=== Exponentiation modulaire ===
+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.
-> Vous utiliserez la fonction ''exponentiation_mod'' définie dans [[nsi:tds:cryptographie:exponentiation_modulaire]].
+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>
-Pour chaque bloc $B$, on calcule $C \overset{n}{=} B^e$.
+===== Utiliser des bytes =====
-On prend soin d'écrire $C$ en binaire en utilisant la taille d'un bloc.
+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.
-C'est à dire que si $C = 17 = 10001_b$ et que l'on a choisi des blocs de taille 8, il faudra écrire $C = 00010001_b$.
+=== Déterminer la taille en octets d'un nombre ===
-=== Regroupement ===
+On cherche d'abord à calculer combien d'octets, au minimum, sont nécessaires pour stocker un nombre ''n''. Je vous propose la fonction suivante :
-On joint les blocs dans un tableau.
+<code python>
+def octets_size(n):
+    """
+    n: entier positif
+    renvoie le nombre d'octets nécessaires pour écrire n.
+    """
+    s = 0
+    while n > 0:
+        n = n //256
+        s += 1
+    return s
+</code>
 <WRAP box>
-=== À faire ===
+Ajoutez la fonction à votre programme.
+</WRAP>
-Écrivez une fonction ''chiffrer_RSA(K, Kpu)'' où ''K'' est déjà découpée et qui renvoie la version chiffrée de ''K'' en ayant chiffré l'un après l'autre chaque constituant de ''K''.
+=== De bytes à int ===
-Pour simplifier, on souhaite que ''n > 255'' et alors ''K'' est de type ''bytes''.
+C'est très simple :
 <code python>
->>> K = bytes([13, 151, 12])
+>>> b = bytes([18, 29, 36, 54, 201])
->>> Kpu = (8383, 17)
+>>> n = int.from_bytes(b, 'big')
->>> chiffrer_RSA(K, Kpu)
-, 4984, 5986
 </code>
+Voyons à quoi correspond l'argument ''%%'big'%%''. Supposons que ''b = bytes([1, 0])''. Cela signifie que ''b'' est composé de deux octets : l'octet de valeur 1 et l'octet de valeur 0. On pourrait les écrire en binaire ''0b00000001'' et ''0b00000000''.
-<WRAP important>
+On souhaite former un grand nombre en collant ces deux nombres bout à bout. **Mais dans quel sens ?**
-Si ''K'' est de type ''bytes'', alors ''K'' est comme un découpage en octets. Si ''n > 255'', on est tranquilles.
-C'est plus compliqué pour le résultat : Suite au calcul $C \overset{n}{=} B^e$, même si $0 \leqslant B  < 256$, on ne peut rien affirmer sur $C$, seulement que $C < n$. Donc $C$ ne tient pas forcément sur un octet. Par exemple :
+  * ''%%'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.
-<code python>
+On pourra choisir ''%%'big'%%'' à chaque fois.
->>> K = bytes([13, 151, 12])
->>> Kpu = (8383, 17)
->>> chiffrer_RSA(K, Kpu)
-[7854, 4984, 5986]
-</code>
-Mais on voudrait que la réponse soit de type ''bytes''. Il suffit pour cela de prévoir le nombre d'octets suffisant pour chaque morceau de réponse. Ici, ''n = 8383'' tient sur 2 octets. On prévoit donc 2 octets pour chaque élément de la réponse. Par exemple
+=== De int à bytes ===
-<code python>
+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.
->>> n, e = Kpu
->>> B = 13
->>> C = B**e % n # C = 7854
->>> C.to_bytes(2,'big')
-b'\x1e\xae'  # c'est à dire, écrit en décimal, bytes([30, 174])
-</code>
-De sorte qu'avec ce choix :
 <code python>
->>> K = bytes([13, 151, 12])
+>>> n = 4503268953
->>> Kpu = (8383, 17)
+>>> b = n.to_bytes(5, 'big')
->>> chiffrer_RSA(K, Kpu)
-b'\x1e\xae\x13x\x17b' # soit bytes([30, 174, 19, 120, 23, 98])
 </code>
-Puisque ''K'' comptait 3 octets et que chacun de ces octets en a produit 2, on obtient 6 octets dans la réponse.
+<WRAP box>
-Idéalement, il faudrait que le nombre d'octets de la réponse s'adapte automatiquement à la valeur de ''n''.
+=== Adapter les fonctions ===
-</WRAP>
-</WRAP>
-===== Déchiffrer =====
+Implémenter les fonctions suivantes :
-C'est exactement la même chose mais en utilisant $Kpr$ au lieu de $Kpu$.
+  * ''%%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%%'' .
-Mais il faut tenir compte du problème de taille évoqué dans le cadre ci-dessus.
-Prenons un exemple :
+Vérifiez que l'on a bien :
 <code python>
->>> Kc = bytes([30, 174, 19, 120, 23, 98]) # K chiffré
+>>> Kpu, Kpr = make_keys(50005987, 74013803)
->>> Kpr = (8383, 6753) # Kpr = n, d
+>>> mb = bytes([41, 56, 176, 88, 82, 67])
->>> chiffrer_RSA(Kc, Kpr)
+>>> mcb = chiffrer_bytes(mb, Kpu)
-b'\r\x97\x0c' # c'est à dire bytes([13, 151, 12])
+>>>list(mcb)
+[66, 161, 170, 49, 247, 15]
+>>> mb2 = dechiffrer_bytes(mcb, Kpr)
+>>> list(mb2)
+[41, 56, 176, 88, 82, 67]
 </code>
-Nous sommes allés dans le sens contraire du cas précédent : d'éléments ''C'' sur 2 octets, nous obtenons des éléments ''B = C**d % n'' sur un seul octet. Donc de ''Kc'' sur 6 octets, nous retrouvons ''K'' sur 3 octets.
+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>
-Lors de la lecture de ''Kc'', vous devez donc prendre les octets 2 par 2.
+===== Bourrage =====
-<WRAP important>
+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é.
-Encore une fois, 2 n'est qu'un exemple pour notre ''n = 8383'', mais pour un ''n'' plus grand il pourrait falloir 3 octets, ou 4, ou... 128 !
+<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>
-Pour ce faire, voici une manipulation possible :
+=== Amélioration : le bourrage  ===
-<code python>
->>> Kc = bytes([30, 174, 19, 120, 23, 98])
->>> int.from_bytes(Kc[2:4],'big')
-</code>
-Ici ''%%Kc[2:4]%%'' permet de récupérer les octets d'indices 2 et 3 dans ''Kc''. La fonction ''int.from_bytes'' permet d'assembler ces deux octets pour former un entier.
+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.
+Mais si on fait cela, à la réception, comment démêlera-t-on la partie bourrage de la partie message ?
+On choisit donc :
+  * 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
+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 :
+''%%<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 ===
+Implémentez les fonctions ''%%chiffrer_pad(mb:bytes, Kpu) -> bytes%%'' et ''%%dechiffrer_pad(mcb:bytes, Kpr) -> bytes%%'' mettant en œuvre le bourrage.
+//padding = bourrage//
+</WRAP>
+===== Avec découpage =====
+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.
+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é.
+Il faudra alors découper le message en morceaux et chiffrer ces morceaux indépendamment.
+=== 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.
-  * Écrire une fonction ''dechiffrer_RSA(Kc, Kpr)''
+Utilisez un fichier quelconque, par exemple une image, et vérifiez le bon fonctionnement.
-  * Placer un texte quelconque dans un fichier ''cle.txt''
-  * ''K'' est obtenu en lisant le contenu de ''cle.txt'' en mode binaire.
-  * Choisissez ''Kpu'' et ''Kpr'' de sorte que ''255 < n < 65536''\\ //Vous pourrez faire plus grand si cela fonctionne.//
-  * Calculez ''Kc = chiffrer_RSA(K, Kpu)''
-  * Vérifiez : ''assert dechiffrer_RSA(Kc, Kpr) == K''.
 </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$.