Comment RSA fait-il de deux nombres premiers un cadenas que tout le monde peut fermer, mais que toi seul peux ouvrir ?

RSA fonctionne parce que certains calculs sont faciles dans un sens et terriblement durs dans l'autre. Ta clé privée est une paire de grands nombres premiers tirés au hasard et gardés secrets. Ta clé publique est construite à partir de leur produit. Multiplier deux nombres premiers ne prend aucun temps à un ordinateur, mais les retrouver à partir du produit, c'est le « problème de la factorisation », et la sécurité de RSA est liée à sa difficulté.

Le cadenas lui-même, c'est l'arithmétique de l'horloge. Sur une horloge de 12 heures, 8 heures après 7 heures, il est 3 heures, pas 15 : les nombres font le tour. RSA fait pareil avec une horloge géante de taille n, le produit des deux nombres premiers. Pour verrouiller un message, on le transforme en nombre et on l'élève à une puissance publique e, en ne gardant que le reste sur l'horloge. Pour le déverrouiller, on élève le résultat à une puissance secrète d, et le nombre de départ revient. Tout le monde peut faire la première étape. Sans d, la défaire est impraticable.

Et d ne se calcule facilement que si l'on connaît les deux nombres premiers. Dans un exemple de manuel, les nombres 61 et 53 donnent n = 3233, la puissance publique vaut 17 et la secrète 413. Le message 65 se verrouille en 2790, et 2790 se déverrouille en 65. Avec des nombres aussi petits, n'importe qui pourrait factoriser 3233 et voler la clé. Les vraies clés utilisent des nombres de plusieurs centaines de chiffres : factoriser un nombre RSA de 250 chiffres a demandé, en 2020, environ 2 700 années de calcul processeur.

L'idée a été rendue publique en 1977 par Ron Rivest, Adi Shamir et Leonard Adleman, après une nuit blanche au cours de laquelle Rivest a rédigé une bonne partie de l'article avant l'aube. La garantie repose sur un pari : on ne connaît aucun moyen rapide de factoriser de grands nombres, mais personne n'a prouvé qu'il n'en existe pas.