Nommé selon les initiales de ses inventeurs, en 1977 : Ronald Rivest, Adi Shamir et Leonard Adleman. Il s'agit d'un chiffre asymétrique, c'est à dire que la clé pour chiffrer est différente de la clé pour chiffrer.

Comme pour le chiffre de ElGamal, RSA exploite des propriétés arithmétiques des nombres premiers.

Nous allons utiliser des nombres premiers. Pour les démonstrations, des nombres premiers peuvent suffire. Vous en trouverez une liste 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 – 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.

• 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 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.
• Calculer $d$, inverse modulaire de $e \mod \varphi$.

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

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

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.

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

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

C'est très simple :

>>> b = bytes([18, 29, 36, 54, 201])
>>> n = int.from_bytes(b, 'big')

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 === C'est encore plus simple : <code python> >>> n = 4503268953 >>> b = n.to_bytes('big') </code> ===== Chiffrer ===== Soit un message ''mb'' de type ''bytes'' et la clé publique ''Kpu = (n, e)''. Il faut transformer ''mb'' dans le nombre entier ''m'' correspondant : <code python> >>> 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. **condition :** Il faut ''m < n''. Le calcul du message chiffré est tout simplement $m' \overset{n}{=}m^e$. > Pour le calcul $mc \overset{n}{=}m^e$ on utilisera l'exponentielle modulaire définie dans [[nsi:tds:cryptographie:exponentiation_modulaire]]. Il faut enfin transformé le message chiffré ''mc'' dans le type ''bytes''. On peut écrire : <code python> >>> s = octets_size(n) >>> mcb = mc.to_bytes(s, 'big') </code> <WRAP box> === À 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. </WRAP> ===== Déchiffrer ===== C'est exactement la même chose mais en utilisant $Kpr$ au lieu de $Kpu$. <WRAP box> === À faire === É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. </WRAP> ===== Test ===== Je vous propose de prendre ''p = 50005987'' et ''q = 74013803'', deux nombres premiers très grands. * La clé publique est alors ''Kpu = (3701133270638561, 17)'' * 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> >>> 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. <WRAP tip> 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 ===== 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$. ===== 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.