Comment chiffrer (et déchiffrer) avec RSA

Il y a une série de 5 articles sur RSA :

RSA, c’est «juste» un peu d’arithmétique pendulaire

Nous disposons de 2 clés. La clé publique et la clé privée sont toutes les deux composées de deux nombres. La clé publique est formée de l’exposant $e$ (nombre souvent premier) et le module $n$ (nombre très grand, plusieurs centaines de chiffres, qui est le produit de 2 nombres premiers $p$ et $q$ ). La clé privée est formée d’un autre exposant, $d$ , et du même module $n$ .

Nous n’allons pas ici détailler la théorie arithmétique qui fait que RSA fonctionne. Vous trouverez un point de départ sur le sujet sur la page Wikipédia sur le chiffrement RSA. Nous allons juste voir comment faire fonctionner le chiffrement/déchiffrement en pratique.

RSA est un chiffrement par bloc. Chaque bloc à chiffrer est un nombre, qui doit être plus petit que $n$. Si le module $n$ fait 1024 bits, on chiffre donc des blocs (c’est à dire des nombres) de moins de 1024 bits (les blocs sont généralement construits en utilisant des blocs de données plus petits, puis en faisant du padding – par exemple de l'OAEP). Pour la suite, nous avons simplement besoin de voir comment un nombre $M$ plus petit que $n$ est chiffré/déchiffré. On ne s’interessera pas aux techniques de padding ici.

L’opération de chiffrement du bloc (du nombre donc) $M$ est le calcul du bloc (du nombre) chiffré $C=M^e [n]$ . Ce calcul est très «simple». On élève $M$ à la puissance $e$ , et on cherche le résultat modulo $n$ (le reste de la division entière de $M^e$ par $n$ ).

Voyons ce que cela donne sur de petits nombres. Supposons que $n=1147$ (les vrais nombres $n$ sont beaucoup plus grands) et $e=7$ . Si on doit chiffrer le nombre $632$ , il suffit de calculer : $632^7[1147]=40273516138141319168 [1147]=892$ . Si on chiffre 632 avec la clé $(e,n) = (7,1147)$ , on obtient donc 892. La dernière opération consiste à prendre le reste de la division entière de 40273516138141319168 par 1147. En Python :

In [1]: 632 ** 7
Out[1]: 40273516138141319168

In [2]: 40273516138141319168 % 1147
Out[2]: 892

Le nombre intermédiaire 40273516138141319168 peut devenir très grand… surtout si $n$ est grand (et donc potentiellement $M$ ) ou si $e$ est grand. Plutôt que calculer $M^e$ et ensuite prendre le reste de la division entière on garde uniquement le reste après chaque multiplication.

In [1]: 632 % 1147
Out[1]: 632 # = 632 ** 1 [1147]
In [2]: (632 * 632) % 1147
Out[2]: 268 # = 632 ** 2 [1147]
In [3]: (268 * 632) % 1147
Out[3]: 767 # = 632 ** 3 [1147]
In [4]: (767 * 632) % 1147
Out[4]: 710 # = 632 ** 4 [1147]
In [5]: (710 * 632) % 1147
Out[5]: 243 # = 632 ** 5 [1147]
In [6]: (243* 632) % 1147
Out[6]: 1025 # = 632 ** 6 [1147]
In [7]: (1025* 632) % 1147
Out[7]: 892 # = 632 ** 7 [1147]

Il n’est pas très difficile d’écrire une petite fonction qui fait cette exponentiation modulaire :

def expo_mod(m, e, n):
    """ 
        calcule (m ** e) % n
    """
    # On laisse ça en exercice hein :)

Pour plus d’efficacité, on pourra utiliser le fait que $M^{2a} = (M^a)^2$ . Ainsi, pour calculer $M^{65537}\, [n]$ , on n’aura pas 65536 multiplications à faire mais seulement 16 environ. Quoi qu’il en soit, même une méthode qui ne serait pas très optimisée en temps d’exécution, si elle ne convient pas à une implémentation industrielle de RSA, convient tout à fait pour la résolution des problèmes sur Pydéfis. Un fois cette fonction écrite, le chiffrement d’un bloc est un simple appel de fonction :

In [1]: expo_mod(632, 7, 1147)
Out[1]: 892

On obtient 892, qui est le résultat du chiffrement de 632 par la clé $(e,n)=(7, 1147)$ .

Et le déchiffrement ?

Et pour le déchiffrement…. c’est la même chose. Il suffit d’utiliser l’exposant $d$ à la place de $e$ . Dans le cas qui précède, la clé privée associée à $(7, 1147)$ est $(463, 1147)$ (On voit un peu plus loin comment calculer cette valeur de 463). On déchiffre alors en faisant :

In [1]: expo_mod(892, 463, 1147)
Out[1]: 632

Le chiffrement et le déchiffrement sont complètement symétriques. On chiffre avec $e$ et on déchiffre avec $d$ . Mais on peut faire l’inverse : si on chiffre avec $d$ , on déchiffrera avec $e$ .

Naturellement, tout réside dans l’exposant $d$ qui permet de déchiffrer ce qui est chiffré avec $e$ . La création de la paire clé privé / clé publique se fait ainsi (regardez sur le net, ceci est expliqué des centaines de fois, par exemple Algorithme d’Euclide étendu et application à RSA sur Bibmath) :

on choisit 2 nombres premiers $p$ et $q$ (par exemple 31 et 37)
le produit $pq$ donne le module $n$ (et donc $n=31\times37=1147$ )
calculer $z=(p-1)(q-1)$ (ici $z=30\times 36=1080$ )
choisir un nombre $e$ premier avec $z$ (on prend généralement $e$ premier, ici $e=7$ , mais il faut bien vérifier qu’il soit premier avec $z$ , $e=3$ ou $e=5$ ne conviennent pas, par exemple)
calculer $d$ , inverse de $e$ modulo $z$ , c’est à dire le nombre inférieur à $z$ tel que le reste de la division de $e\times d$ par $z$ soit égal à 1 (le calcul de $d$ peut être réalisé avec l’algorithme d’Euclide étendu, voir la référence plus haut), on trouve ici 463. En effet : (7 * 463) % 1080 donne 1.

La sécurité de RSA réside dans le fait qu’on ne peut pas calculer $d$ connaissant $e$ et $n$ . Si on ne peut pas faire ce calcul c’est parce qu’on a besoin de $z$ pour calculer $d$ . Or pour calculer $z$ , il faut connaître $p$ et $q$ . Et $p$ et $q$ sont calculables à partir de $n$ si on arrive à faire sa décomposition en facteurs premiers. La sécurité de RSA repose donc sur la difficulté de trouver les 2 facteurs premiers de $n$ . Ce problème est en apparence simple, et il l’est effectivement si $n$ est petit (par exemple 1147). Mais il devient difficile (à cause du temps de calcul) si $n$ fait plusieurs centaines de chiffres, ce qui est le cas en pratique.

J’insiste sur le fait que pour $n=1147$ , il n’y a pas de difficulté à trouver les facteurs premiers de $n$ et donc calculer $z$ et donc inverser $e$ . Une boucle toute simple qui teste tous les entiers impairs (même pas les seuls nombres premiers) trouve la décomposition en une fraction de seconde. Par contre si $n$ fait 600 chiffres (en base 10), alors le problème devient trop compliqué (comprenez trop long) à résoudre.

Vers les faiblesses de RSA

Il existe plusieurs faiblesses de RSA, qui apparaissent si on fait les mauvais choix pour $p$ , $q$ , ou $e$ par exemple (dans le cas où les bons choix sont faits, RSA est a priori un algorihtme de chiffrement très sûr). Les défis proposés sur Pydéfis utilisent ces faiblesses, qui seront explicitées (mais pas trop) dans de prochains billets.