|
 |
|
 |
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...
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)Phi(n) étant l'indicateur d'euler, et valant dans le cas présent (p-1)*(q-1). 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 Mi tels que le nombre de chiffres de chaque Mi 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.
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)
|
