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.

On veut chiffrer l'entier $K$ connaissant $Kpu = (n,e)$

En binaire, on découpe $K$ en blocs $B$ dont les valeurs doivent être plus petites que $n$.

Par exemple, si $n > 255$,

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

Vous utiliserez la fonction exponentiation_mod définie dans exponentiation_modulaire.

Pour chaque bloc $B$, on calcule $C \overset{n}{=} B^e$.

On prend soin d'écrire $C$ en binaire en utilisant la taille d'un bloc.

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

On joint les blocs dans un tableau.

>>> K = bytes([13, 151, 12])
>>> Kpu = (8383, 17)
>>> chiffrer_RSA(K, Kpu)
 7854, 4984, 5986

>>> K = bytes([13, 151, 12])
>>> Kpu = (8383, 17)
>>> chiffrer_RSA(K, Kpu)
[7854, 4984, 5986]

>>> 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])

>>> K = bytes([13, 151, 12])
>>> Kpu = (8383, 17)
>>> chiffrer_RSA(K, Kpu)
b'\x1e\xae\x13x\x17b' # soit bytes([30, 174, 19, 120, 23, 98])

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

Mais il faut tenir compte du problème de taille évoqué dans le cadre ci-dessus.

Prenons un exemple :

>>> Kc = bytes([30, 174, 19, 120, 23, 98]) # K chiffré
>>> Kpr = (8383, 6753) # Kpr = n, d
>>> chiffrer_RSA(Kc, Kpr)
b'\r\x97\x0c' # c'est à dire bytes([13, 151, 12])

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.

Lors de la lecture de Kc, vous devez donc prendre les octets 2 par 2.

Pour ce faire, voici une manipulation possible :

>>> Kc = bytes([30, 174, 19, 120, 23, 98])
>>> int.from_bytes(Kc[2:4],'big')
4984

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.

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