Dans l’épisode précédent, nous avons découvert qu’un ordinateur quantique ne deviendrait vraiment utile qu’en résolvant un problème qui compte. Parmi les destinations promises, l’une inquiète déjà le monde numérique : RSA-2048. RSA apparaît à la fin des années 1970 pour répondre à un problème étonnant : comment échanger un secret avec quelqu’un que vous n’avez jamais rencontré… sans lui transmettre discrètement la clé ?

La solution utilise deux clés. 🔓 Une clé publique que chacun peut connaître. 🔐 Une clé privée que son propriétaire ne révèle jamais. Dans le cas du chiffrement, tout le monde peut utiliser la première pour fermer le cadenas, mais seule la seconde permet de l’ouvrir. Son cœur mathématique repose sur une asymétrie très simple.

Choisissez deux nombres premiers. 53 × 59 = 3 127 La multiplication est immédiate. Mais si je vous donne seulement 3 127, retrouver les deux nombres d’origine demande déjà plus de travail. RSA réalise la même opération… dans des proportions vertigineuses. Le système choisit secrètement deux nombres premiers d’environ 300 chiffres, puis les multiplie pour former un nombre gigantesque appelé le module.

Le résultat peut être publié. Ses deux facteurs restent secrets et permettent de construire la clé privée. Et contrairement à ce que son nom laisse croire, RSA-2048 ne contient pas 2 048 chiffres. Le nombre occupe 2 048 positions en langage binaire, soit environ 617 chiffres décimaux. Un ordinateur peut très rapidement multiplier ses deux facteurs.

Mais partir du résultat et les retrouver est un problème radicalement différent : la factorisation. Les meilleurs algorithmes classiques sont bien plus ingénieux qu’une succession d’essais. Pourtant, leur coût augmente si brutalement qu’une clé RSA-2048 correctement créée demeure hors de portée pratique.

En 2020, des chercheurs ont établi un record général en factorisant un nombre RSA de 250 chiffres, soit 829 bits. Le calcul a représenté environ 2 700 années-cœur, réparties entre des milliers de processeurs pendant plusieurs mois. RSA-2048 en compte 617. Et passer de 250 à 617 chiffres ne rend pas le problème simplement deux ou trois fois plus difficile.

Le fossé devient colossal. Voilà la propriété fascinante de cette serrure : son mécanisme peut être entièrement public sans que sa clé secrète le soit. L’attaquant connaît le nombre et l’algorithme. Il sait exactement quel problème résoudre. Mais aucun ordinateur classique ne sait aujourd’hui le faire assez efficacement à cette échelle.

Cela ne rend pas tout système RSA invulnérable : une mauvaise génération, un logiciel défaillant ou une clé volée peuvent permettre de contourner les mathématiques. Mais le cœur d’une clé RSA-2048 bien construite n’a pas été brisé publiquement par factorisation. Il résiste non parce que son mécanisme est caché… mais parce que le chemin du retour est extraordinairement difficile.

Aucun ordinateur quantique actuel ne peut davantage le faire. Puis, en 1994, Peter Shor a découvert qu’une machine quantique suffisamment puissante pourrait emprunter un autre chemin. Pas en essayant davantage de facteurs. Pas en testant toutes les réponses à la fois. Mais en transformant cette immense serrure en un problème de rythme caché.

🤔 Comment trouver un rythme peut-il faire céder un nombre de 617 chiffres ? C’est ce que nous découvrirons dans le prochain épisode. 🚁 Curiosity First. Learning together. 🔎 Sources : article fondateur du RSA · record de factorisation · NIST