Un cadenas ouvert pour tout le monde, une seule clé pour l'ouvrir

Cambridge, Massachusetts, avril 1977. Un séder de Pessah chez un étudiant, et trois jeunes enseignants du MIT à table : Ron Rivest, vingt-neuf ans, informaticien ; Adi Shamir, vingt-quatre ans, Israélien ; Leonard Adleman, trente et un ans, théoricien des nombres. On boit beaucoup de vin. On parle de cryptographie à clé publique : depuis l'automne, ces trois-là ne parlent que de ça. Vers minuit, chacun rentre chez soi. Rivest ne dort pas. Il s'allonge sur son canapé avec un manuel de mathématiques et retourne le problème qui leur résiste depuis cinq mois.

Puis il décroche et appelle Adleman. Il tient quelque chose.

Félicitations, Ron, ça devrait marcher.

Réponse d'Adleman, telle qu'il la racontera en 2003. Au matin, l'essentiel de l'article est écrit. Le mémo fera quinze pages. Quarante-neuf ans plus tard, ça marche toujours.

Le problème laissé ouvert par Diffie et Hellman

Tout commence en novembre 1976 avec un article de Whitfield Diffie et Martin Hellman dans les IEEE Transactions on Information Theory, « New Directions in Cryptography ». Jusque-là, chiffrer suppose un secret partagé, remis d'avance par un courrier de confiance. Diffie et Hellman proposent une clé pour fermer et une autre pour ouvrir, la première publiée au grand jour. Ils décrivent l'idée sans avoir la fonction mathématique qui réalise ce tour.

Rivest lit l'article dans son bureau quand Adleman passe la tête par la porte. Rivest s'enflamme, Adleman hausse les épaules : « On aurait dit qu'ils avaient résolu une sorte de problème d'ingénierie. » Shamir, lui, mord tout de suite. Une routine s'installe entre bureaux voisins : Rivest et Shamir proposent un schéma, Adleman le casse, souvent en quelques minutes. Sacs à dos, polynômes de permutation, un schéma à base de réseaux qui lui coûte une nuit blanche. Des mois de propositions mortes-nées, entre dîners et week-ends de ski dans le Vermont.

Un cadenas ouvert distribué à tout le monde

L'idée de cette nuit se raconte avec des cadenas. On fait fabriquer des milliers de cadenas ouverts, identiques, et on les distribue à qui en veut. N'importe qui peut en claquer un sur une boîte et l'expédier. Une seule clé les ouvre, et elle ne quitte jamais la poche de son propriétaire. Le cadenas, c'est la clé publique. La clé, c'est la clé privée.

En mathématiques, le cadenas est un nombre. On choisit deux grands nombres premiers, p et q, et on publie leur produit n avec un exposant e. Chiffrer un message, c'est le traiter comme un nombre, l'élever à la puissance e et garder le reste de la division par n. Déchiffrer demande un second exposant, d, calculable seulement par qui connaît p et q séparément. Multiplier p par q prend une fraction de seconde. Retrouver p et q à partir de n, c'est le mur. Pris à l'envers, le même calcul donne une signature que tout le monde peut vérifier avec le cadenas. Alice et Bob, que tous les manuels de cryptographie emploient depuis, y font leur première apparition.

Ce qui a fait tilt avec RSA, c'est qu'il ne semblait exister aucune autre façon de le casser que la factorisation.

Phrase d'Adleman. Le mémo MIT/LCS/TM-82 sort en avril 1977, et Rivest en envoie une copie à Martin Gardner, chroniqueur du Scientific American.

Quarante millions de milliards d'années

La chronique paraît en août 1977 sous le titre « A new kind of cipher that would take millions of years to break ». Gardner promet le mémo à quiconque écrira au 545 Technology Square avec une enveloppe timbrée à 35 cents ; environ 4 000 partiront, selon Rivest. Le MIT y joint un défi, un message chiffré avec un n de 129 chiffres et 100 dollars au premier qui le déchiffrera. S'y ajoute une estimation que Rivest qualifiera plus tard de tristement célèbre : avec les meilleurs algorithmes et machines de l'époque, factoriser un tel nombre prendrait « 40 quadrillion years », quarante millions de milliards d'années.

Dans le premier jet, Rivest range les auteurs dans l'ordre alphabétique : Adleman, Rivest, Shamir. Adleman proteste : il n'a rien construit, seulement démoli, et n'accepte de signer qu'en dernier. ARS devient RSA.

Je me souviens m'être dit que c'était probablement l'article le moins intéressant que j'écrirais jamais, que personne ne le lirait et qu'il paraîtrait dans une revue obscure.

L'article paraît en février 1978 dans les Communications of the ACM, volume 21, numéro 2, pages 120 à 126.

Le secret anglais de 1973

Les trois du MIT avaient quatre ans de retard, et ils l'ignoraient. Au GCHQ, le service britannique d'écoute, un jeune mathématicien nommé Clifford Cocks avait décrit le même système dans une note interne datée du 20 novembre 1973, à partir d'une idée de son collègue James Ellis. Le GCHQ n'a pas su quoi en faire, l'a classé secret, et Cocks n'a pu en parler en public que le 18 décembre 1997. Les trois du MIT n'ont rien volé : ils ont trouvé seuls ce qu'un autre avait trouvé seul avant eux, et rangé dans un tiroir.

Le brevet arrive dans le mauvais ordre. Le MIT le dépose le 14 décembre 1977, quatre mois après la chronique de Gardner, et l'obtient le 20 septembre 1983 sous le numéro 4 405 829, valable aux États-Unis seulement : ailleurs, la publication préalable le rend impossible. Le 6 septembre 2000, deux semaines avant son expiration, RSA Security place l'algorithme dans le domaine public.

RSA Security, justement. Les trois inventeurs fondent RSA Data Security en 1982. En juillet 1996, Security Dynamics, fabricant des porte-clés d'authentification SecurID, la rachète et finira par prendre son nom. Le jeton gris en haut de cette page, photographié en 2008, est un SecurID : un code à six chiffres renouvelé toutes les soixante secondes à partir d'une graine secrète partagée avec un serveur. Une horloge et un secret remis d'avance, la vieille méthode du courrier de confiance, sous le nom de ceux qui l'avaient rendue facultative.

Les mots magiques, dix-sept ans plus tard

Les quarante millions de milliards d'années ont duré dix-sept ans. En avril 1994, une équipe coordonnée par Derek Atkins, Michael Graff, Arjen Lenstra et Paul Leyland factorise le nombre de Gardner avec environ 600 volontaires et plus de 1 600 machines reliées par Internet, en plus de six mois. Le message : « The Magic Words are Squeamish Ossifrage ». Rivest s'était trompé sur les algorithmes et les machines à venir, pas sur le principe.

Le mur recule, lentement. RSA-250, 829 bits, tombe en février 2020 après 2 700 années-cœur de calcul ; RSA-260, 862 bits, le 3 septembre 2026 chez Cognition, pour environ 4 900 jours de GPU, soit 400 000 dollars. Les clés d'aujourd'hui font 2 048 bits au minimum, 617 chiffres, et l'auteur de ce record écrit lui-même qu'il ne les menace pas : RSA-2048 reste de l'ordre d'un milliard de fois plus dur que RSA-1024.

Le cadenas dans la barre d'adresse

Chaque connexion HTTPS s'ouvre encore par un échange à clé publique : le navigateur vérifie la signature d'un certificat et négocie une clé de session, puis le chiffrement classique prend le relais. Let's Encrypt, qui servait 762 millions de sites fin 2025, fait reposer sa racine historique, ISRG Root X1, sur une clé RSA de 4 096 bits. La puce des cartes bancaires s'en sert aussi : depuis le milieu des années 1990, la norme EMV utilise RSA pour que le terminal de paiement vérifie les signatures de la carte, de la banque qui l'a émise et du réseau de paiement. Elle accepte aussi, depuis 2021, les courbes elliptiques, aux clés plus courtes.

Le mur a maintenant une date. En 1994, Peter Shor a montré qu'un ordinateur quantique assez grand, qui n'existe pas encore, le traverserait. Le NIST a publié le 13 août 2024 trois standards de remplacement, FIPS 203, 204 et 205, et son projet de calendrier de novembre 2024 déclasse RSA à 2 048 bits après 2030 et l'interdit, à toute taille de clé, après 2035.

Rivest, Shamir et Adleman ont reçu le prix Turing 2002. Adleman, qui voulait retirer son nom, trouve aujourd'hui que « ARS » sonne de mieux en mieux. Le prochain cadenas ne sera plus un produit de deux nombres premiers. Celui-là aura tenu de 1977 à 2035, cinquante-huit ans, d'un canapé de la banlieue de Boston au petit cadenas longtemps dessiné à gauche de l'adresse dans les navigateurs. Pas mal, pour une idée venue après le vin de Pessah et vérifiée par téléphone vers minuit.