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

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

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 veut taille_mb ⇐ taille_n - 4
  (on veut s'assurer un minimum d'octets de bourrage pour bien embrouiller)
  on peut prendre l'exemple de taille_m = 2
• puisque taille_mb est assez petit, on doit compléter. Il reste taille_bourrage = taille_n - taille_mb - 1 octets à compléter.
  dans l'exemple, cela donne 7 - 2 - 1 = 4.
• Le premiers des octets de bourrage contiendra l'octet taille_bourrage.
  Dans l'exemple : 4.
• Les autres octets de bourrages contiendront un octet aléatoire.

Dans l'exemple, avec taille_n = 7, taille_mb = 2, taille_bourrage = 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.

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.

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.

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