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.

Si je transmet le message m, un entier, il doit être inférieur à n. Le message chiffré mc sera lui aussi inférieur à n.

Comme m et mc seront à un moment écrits sous forme d'octets bytes, il pourra être utile de connaître la taille de n quand il est écrit sous la forme bytes.

On écrit donc une fonction pour trouver la taille de n.

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

Soit un message mb de type bytes et la clé publique Kpu = (n, e).

Il faut transformer mb dans le nombre entier m correspondant :

>>> m = int.from_bytes(mb, 'big')

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

Il faut enfin transformé le message chiffré mc dans le type bytes. On peut écrire :

>>> s = octets_size(n)
>>> mcb = mc.to_bytes(s, 'big')

C'est exactement la même chose mais en utilisant $Kpr$ au lieu de $Kpu$.

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.

  Le résultat à l'air satisfaisant mais on a un petit problème : le message de départ était "chien" c 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.

  ===== Justification ===== D'après le 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.

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

  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.