RSA : Rivest Shamir et Adleman 1978
RSA esr fondé sur la difficulté de factoriser des grands nombres qui sont le produit de deux grands nombres premiers.
Cryptographiquement parlant, on peut dire que multiplier deux grands nombres premiers est une fonction à sens unique: Il est facile de multiplier deux nombres pour obtenir un produit, mais difficile de factoriser ce produit et de retrouver les deux grands nombres premiers.
Initialisation
-
Choisir deux nombres premiers, p et q, les deux étant plus grands que 10100.
-
Calculer n = p · q (n est le modulus)
-
Choisir e aléatoire tel que e et ((p - 1) · (q - 1)) n'aient aucun facteur commun excepté 1
-
Trouver d tel que : ed = 1 mod((p - 1)(q - 1)).
-
Clé publique : (n,e).
-
Clé privée : (n,d) ou (p,q,d) si on désire garder p et q.
Chiffrement/Déchiffrement
-
L'expéditeur crée le texte chiffré c à partir du message m : c = me mod(n), où (n,e) est la clé publique du destinataire
-
Le destinataire reçoit c et effectue le déchiffrement : m = cd mod(n), où (n,d) est la clé privée du destinataire.
Ce qui est connus est la clé publique (e,n)
Pour déchiffrer un message m, il faut connaître d tel que ed=1 mod(p-1)(q-1)
Pour calculer d il faut donc connaître p et q
Or on sait que n=pq et on connaît n
Il faut donc factoriser n en ses facteurs premiers p et q
Or personne n'a pus le faire en un temps raisonnable.
