GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== 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: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.

<WRAP info>Cette technique avait déjà été découverte à Bletchley Park lors de la seconde guerre mondiale. Il s'agit du centre de renseignement où a été créé le fameux [[https://fr.wikipedia.org/wiki/Colossus_(ordinateur)|Colossus]], calculateur destiné à casser le code [[https://fr.wikipedia.org/wiki/Enigma_(machine)|Enigma]] utilisé par l'armée allemande. Mais cette invention, couverte par le secret défense, n'a pu être revendiquée par les Britanniques.</WRAP>

===== Création des clés publique et privée =====

==== Nombres premiers ====

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}$.

À cette échelle, les nombres premiers sont trop nombreux pour être catalogués ou même recherchés de faaçon systématique. On se contente d'en choisir au hasard -- [[nsi:tds:cryptographie:get_n_bits_prime|voir cet exercice]]. 

L'idée est de choisir aléatoirement un nombre de 512 bits et de faire une série de tests pour savoir s'il est premier. La série de tests pour chaque essai est suffisamment rapide et on sait qu'on a aux alentours de $\frac{1}{300}$ chance de trouver un premier dans cet zone. On trouve donc un premier assez vite au hasard.

Ces premiers étant très nombreux, la probabilité que deux personnes trouvent une même paire de premiers est négligeable.

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.\\ **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 ===

La paire $(n,e)$ constitue la **clé publique**.

=== Clé privée ===

La paire $(n,d)$ constitue la **clé privée**.

<WRAP box>
=== Quelques questions ===

  - Si je vous donne $(n, e) = (143, 17)$,
    * trouvez $p$ et $q$,
    * déduisez-en $\varphi$,
    * déduisez-en $d$.
  - Si je vous donne $(n,e) = (261\,589, 17)$, même question.

Vous voyez que c'est beaucoup plus long dans le second cas. Ce serait infaisable avec un $n$ de grande taille comme ce qu'on utilise avec RSA.

=== 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>

<WRAP tip>**Optionnel :** Pour aller plus loin, vous pouvez utiliser [[nsi:tds:cryptographie:get_n_bits_prime|cet exercice]] pour produire des premiers de taille voulue et écrire ''%%make_keys(nbits)%%'' où ''nbits'' est un entier pair, par exemple ''100''. Dans cette version, on génère 2 premiers de ''%%nbits//2%%'' bits puis on produit les paires ''Kpu'' et ''Kpr''. Vous pouvez toujours choisir ''e'' parmi 3, 17, 65537 selon la taille des premiers considérés.
</WRAP>

===== 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.

=== Déterminer la taille en octets d'un nombre ===

On cherche d'abord à calculer combien d'octets, au minimum, sont nécessaires pour stocker un nombre ''n''. Je vous propose la fonction suivante :

<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>
Ajoutez la fonction à votre programme.
</WRAP>

=== De bytes à int ===

C'est très simple :

<code python>
>>> b = bytes([18, 29, 36, 54, 201])
>>> n = int.from_bytes(b, 'big')
</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''.

On souhaite former un grand nombre en collant ces deux nombres bout à bout. **Mais dans quel sens ?**

  * ''%%'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.

On pourra choisir ''%%'big'%%'' à chaque fois.

=== De int à bytes ===

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(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>

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.

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>
=== 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.

Utilisez un fichier quelconque, par exemple une image, et vérifiez le bon fonctionnement.
</WRAP>

===== 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$.

Donc, prenons $B$ un élément de $K$.
  * $C \overset{n}{\equiv} B^e$
  * donc $C^d \overset{n}{\equiv} \left(B^e\right)^d = B^{e\cdot d}$
  * on sait que $e\cdot d \overset{(p-1)(q-1)}{\equiv} 1$ donc $e\cdot d = 1 + k\cdot(p-1)(q-1)$ pour un certain $k$ (dont la valeur n'a pas d'importance)
  * donc $C^d \overset{n}{\equiv} B^{1 + k\cdot(p-1)(q-1)}$
  * Supposons que $B$ n'est pas divisible par $q$, on aura\\ $B^{q-1} \overset{q}{\equiv} 1$ et donc $B^{1 + k\cdot(p-1)(q-1)} = B\cdot \left(B^{q-1}\right)^{k\cdot (p-1)} \overset{q}{\equiv} B \cdot 1 = B$
  * De même si $B$ n'est pas divisible par $p$, $B^{1 + k\cdot(p-1)(q-1)}  \overset{p}{\equiv} B \cdot B$
  * On peut raisonner dans le cas où $B$ serait multiple de $p$ ou $q$, je ne le fais pas ici.
  * On déduit que $C^d \overset{q}{\equiv} B$ et $C^d \overset{p}{\equiv} B$, ce qui signifie que $C^d - B$ est multiple de $p$ et $q$, donc de $n = pq$ et donc $C^d - B \overset{n}{\equiv} 0$
  * On conclut que $C^d \overset{n}{\equiv} = B$.