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.

Dans nos exemples, on pourra prendre par exemple : p = 50005987, et q = 74013803 (mais vous êtes libre d'en tester d'autres !)

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

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

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

>>> Kpu, Kpr = make_keys(50005987, 74013803)
>>> Kpu
(3701133270638561, 17)
>>> Kpr
(3701133270638561, 1088568572534933)

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

>>> Kpu, Kpr = make_keys(50005987, 74013803)
>>> chiffrer_int(45323453485635, Kpu)
73262112569103
>>> dechiffrer_int(73262112569103, Kpr)
45323453485635

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.

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 = 4503268953
>>> b = n.to_bytes(5, 'big')

>>> Kpu, Kpr = make_keys(50005987, 74013803)
>>> m = bytes
>>> chiffrer_int(45323453485635, Kpu)
73262112569103
>>> dechiffrer_int(73262112569103, Kpr)
45323453485635

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.

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

Vérifiez que vous obtenez bien la même chose.

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

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.

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.