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