le système RSA

Le premier algorithme de chiffrement à clef publique a été développé par R.Merckle et M.Hellman en 1977. Il fut vite rendu obsolète grâce aux travaux de Shamir, Zippel et Herlestman, de célèbres cryptanalistes.

En 1978, l'algorithme à clé publique de Rivest, Shamir, et Adelman (d'où son nom RSA) apparaît. Cette algorithme sert encore en 2002 à protéger les codes nucléaires de l'armée américaine et russe...

fonctionnement de RSA

Le fonctionnement du cryptosystème RSA est basé sur la difficulté de factoriser de grands entiers.

Soit deux nombres premiers p et q, et d un entier tel que d soit premier avec (p-1)*(q-1)). Le triplet (p,q,d) constitue ainsi la clé privée.

La clé publique est alors le doublet (n,e) créé à l'aide de la clé privée par les transformations suivantes :

n = p * q

e = 1/d mod((p-1)(q-1))

Soit M, le message à envoyer. Il faut que le message M soit premier avec la clé n. En effet, le déchiffrement repose sur le théorème d'Euler stipulant que si M et n sont premiers entre eux, alors :

Mphi(n) = 1 mod(n)

Il est donc nécessaire que M ne soit pas un multiple de p, de q , ou de n. Une solution consiste à découper le message M en morceaux M_i tels que le nombre de chiffres de chaque M_i soit strictement inférieur à celui de p et de q. Cela suppose donc que p et q soient grand, ce qui est le cas en pratique puisque tout le principe de RSA réside dans la difficulté à trouver dans un temps raisonnable p et q connaissant n, ce qui suppose p et q grands.

En pratique...

Supposons qu'un utilisateur (nommé Bob) désire envoyer un message M à une personne (nommons-là Alice), il lui suffit de se procurer la clé publique (n,e) de cette dernière puis de calculer le message chiffré c :

c = Me mod(n)

Bob envoie ensuite le message chiffré c à Alice, qui est capable de le déchiffrer à l'aide de sa clé privée (p,q,d) :

M =  Me*d mod(n) = cd mod(n)