Samedi sécurité : quand les ordinateurs quantiques casseront-ils le RSA 2048 bits ?, Réactions à la publication du 02/08/2025

[Paul Emploi]

Image ChatGPT, manque d'imagination Philippe


TL;DR

Comme la plupart des titres posant une question, la réponse est "non"...
Ça va être un peu plus technique après.
Mais retenez-le: non, les ordinateurs quantiques ne casseront pas le RSA, enfin pas à ce rythme et de notre vivant!


RSA en 1977, une avancée cryptographique incroyable

Commençons par le commencement, la sécurité par la paire de clé publique/privée RSA, amené en 1977 par Ron Rivast, Adi Shamir et Leonard Adleman, et qui a changé le monde! Ces trois chercheurs ont changé la face de la sécurité informatique via les chiffrements asymétriques, et pour longtemps!

Il faut noter que par extension ça a changé aussi les chiffrements symétriques, par transfert de la clé de chiffrement symétrique elle-même chiffrée par la clé publique et donc uniquement déchiffrable par la clé privée.
Mais aussi de l'authentification par la clé privée, via un hash chiffré par celle-ci, vérifiable par tous ceux ayant la clé publique. La signature électronique.

Je ne saurais trop dire à quel point leur impact est essentiel aujourd'hui, énormément de choses dérivent de leur travail, que j'avais découvert dans Science & Vie qui était à l'époque une revue de vulgarisation scientifique. (ils ont gardé le vulgaire dans différents sens, pas le scientifique)

Comment le RSA fonctionne

La sécurité RSA fonctionne comme une boîte fermée avec une clé spéciale : tout le monde peut la fermer avec une clé publique, mais seul celui qui a la clé privée peut l’ouvrir.
Cette sécurité repose sur un secret mathématique : la clé est créée à partir du produit deux grands nombres premiers.

Multiplier ces nombres est facile, mais les retrouver à partir du résultat (les factoriser) est très difficile, même pour les ordinateurs. C’est cette difficulté qui protège le message.
Aujourd'hui le minimum est 4096 bits typiquement, avec nombre d'entre nous utilisant du 8192 bits.


Pourquoi la force-brute ne sert à rien

On considère qu'un supercalculateur d'aujourd'hui peut casser une seule clé RSA 1024 bits en un an. Soit plus que l'âge de l'univers pour du vieux 2048 bits.

Ou à l'inverse un supercalculateur dans deux millénaires devrait être capable de casser un seule clé RSA 2048 bits en 1 an si la Loi de Moore n'est pas cassée entre-temps (elle le sera) et si deux fois plus de transistors amènent à deux fois plus de performances (ça n'est pas le cas).

Bref, la force-brute ne fonctionne absolument pas, et c'est un point-clé du RSA.

Pour donner un facteur d'échelle, créer une clé RSA de 1024 bits par le produit de deux grands nombres premiers (connus) pour un Commodore C64 prend quelques secondes, contre une année pour la casser pour les meilleurs supercalculateurs d'aujourd'hui, qui est l'opération inverse!

C'est cette asymétrie de puissance de calcul qui est essentielle...

La "suprématie quantique"

La "suprématie quantique" est la supériorité des ordinateurs quantiques face aux superordinateurs traditionnels, résolvant en théorie certains problèmes bien plus rapidement, et plus le problème étant complexe plus l'écart augmentant.


Un nouvelle technologie éclatant l'ancienne.


Mais ça n'a été observé jusqu'à présent que pour des problèmes qui ne concernent pas grande-monde... Et quasiment aucun intérêt réel.
En général, à chaque bond en avant, des chercheurs ont obtenus les mêmes résultats et des fois bien plus rapidement, avec des superordinateurs traditionnels!

Les fausses prétentions des ordinateurs quantiques

On nous annonce l'apocalypse chaque fois qu'on peut avec des progrès apparents de factorisation de grands nombres premiers par des ordinateurs quantiques.
Ça vend bien, tant dans les parutions de papiers de recherche que pour les médias.

Sauf que rien de tout cela est vrai, le plus grand nombre factorisé par un ordinateur quantique à ce jour semble être 35. Pas un nombre à 35 chiffres en notation décimale, pas un nombre sur 35 bits (des microsecondes sur un Mac), mais bien "35" (trente cinq) soit 5x7, un nombre codé sur 6 bits, pas 4096 bits! Si vous avez plus de 8 ans vous savez le faire de tête!

C'est ce qu'explique un papier passionnant des chercheurs Peter Gutmann et Stephan Neuhaus, ainsi qu'un petit PDF amusant "bollocks" utilisé lors d'une présentation par Peter Gutmann. Tout est en Anglais, mais permettez-moi de résumer...

Essentiellement les seuls essais fiables et vérifiables de factorisation de nombres premiers par des ordinateurs quantiques ont été sur de très petits nombres, comme 15, 21 ou 35.
Le reste est constitué d'arnaques, de tours de magie informatiques ou mathématiques, de nombres "magiques", de nombres (résultats) préalablement connus, d'usages de "compilateurs" connaissant le résultat, des arnaques! Trop relayées!

Quand certains prétendent casser des clés RSA de 892 bits avec un ordinateur quantique, ça n'est pas de la force brute, mais de la farce brute...

On est tous des suprémacistes quantiques

L'auteur, facétieux, a choisi de reproduire les expériences de factorisation quantiques réussies, grâce à un chien qui malheureusement nous a depuis quitté, ainsi qu'un boulier et un Commodore C64 (émulé certes).

Plaçant ces trois dispositifs au même niveau que les meilleurs ordinateurs quantiques!


Je n'ai pu reproduire toute l'expérience car ayant des chats, qui bien qu'étant l'animal le plus quantique depuis Schrödinger tient plus du générateur aléatoire quantique coté miaulement, sauf quand il est activé en continu quand il a faim.
Par rapport aux chiens, il y a ce qu'on nomme dans notre jargon informatique une "inversion de contrôle" (IoC) qui peut s'associer à une injection de dépendance pour les personnes seules.


Mais je pourrais prétendre factoriser un nombre premier de 4096 bits si le produit d'un nombre premier de 4095 bits et d'un second qui serait "2" (deux) techniquement sur 2 bits. Un Commodore C64 de base ferait ça les doigts dans le nez. Et moi sur une feuille de papier avec un crayon en moins d'une heure... Je suis la suprématie quantique!


Au pire je peux utiliser une grande règle à calcul. Un outil de suprématie quantique.

Les recommandations des auteurs

Outre les critiques justifiées, les auteurs font des propositions constructives pour pouvoir valider les futures expériences de factorisation de grands nombres (en leur deux facteurs premiers) par un ordinateur quantique.

La plus importante étant la fourniture par un tiers indépendant d'une dizaine de ces nombres (produits de paires de grands nombres premiers non proches), sans évidemment fournir ceux ayant permis de les générer et même en les éliminant de leurs systèmes: aucun besoin des deux facteurs premiers si l'expérience quantique fonctionne!


En conclusion

En utilisant les seuls points de données fiables en terme de factorisation de nombres issus du produit de deux nombres premiers, la courbe pointe sur l'année 4000 plus ou moins un siècle, pour du RSA 1024 bits, au rythme observé actuellement en informatique quantique.
Donc vers l'an 10 000 pour les actuels RSA 4096 bits.

Même si on est pas à l'abri d'une découverte, probablement mathématique, on est en sécurité pour longtemps. Tout comme César était immortel, pour longtemps...
Ça rassure non?!?


Lien vers le billet original

[minounet]

tu as entendu parler de l'algorithme de Shor ?
Sinon ok avec les ordi quantique actuel pas cassable ou pliseurs milliers d'années comme tu dis
mais avec un traitant pusieurs million,s oui d'ici 2050


Ce message a été modifié par minounet - 3 Aug 2025, 12:24.

[linus]

Pour ma part j'ai assisté a deux conférences d'un chercheur français appelé Xavier Waintal.
ATTENTION, je suis incompétent dans ce domaine alors ce que j'en dit ci-après c'est ce qu'un naîf a pu en saisir.

En 2022, il avait donné cette conférence :
"Quantum computers: What are they? What are they supposed to do? Will they work? The point of view of a skeptic"
ou
"Calculateurs quantiques : qu'est ce que c'est ? Qu'est ce qu'ils sont supposés savoir faire ? Marcheront ils un jour ? Le point de vue d'un sceptique"
Je ne m'en souviens pas assez bien pour la résumer.
Je me rappelle juste que, peu après l'annonce de Google d'avoir atteint la suprématie quantique, Xavier Waintal avait écrit un programme faisant le même calcul sur un simple laptop en assez peu de temps.

En revanche, j'avais rédigé le résumé ci-après de la conférence de 2020 pour un collègue et ami :

Je n’ai pas tout compris mais le coeur de l’exposé était que, d’un côté il y a la physique des qbits (qui progresse), de l’autre l’informatique quantique (qui progresse) mais ces 2 communautés ne se parlent pas et, entre les deux, il y a un no-man’s land où personne ne va et où se cache un problème redoutable.
Du coup, la partie mathématique et informatique du calcul quantique part sur des hypothèses actuellement intenables par la physique et de très loin, du moins pour le type d'applications visées. Et la réciproque est vraie pour la partie physique.
Xavier WAINTAL est bien d’accord que tout le travail fait a et aura des retombées dans des tas de domaines mais il a expliqué en détail pourquoi (comme Alain Aspect) il pense que les algorithmes de correction d’erreur ne solutionnent pas le problème crucial de décohérence et cela pour 20 ordres de grandeurs (si j’ai bien compris). Il a dit qu’il a lu la quasi totalité de la littérature et qu’aucun article n’aborde ce problème de front. Ils disent tous “when we will reach the threshold…” sans préciser qu’on n’a pas actuellement de piste en ce sens. Selon lui l’analyse mathématique du problème semble indiquer que ce n’est pas possible.
Bon, j’explique mal mais c’était intéressant.
Apparemment il a eu bien du mal à publier son article (pas trouvé) et, selon lui, les referee étaient d’accord avec son analyse mais lui opposaient le fait que, si son papier venait à être publié, il désespérerait toute une communauté. Aucun ne voulait en prendre le risque !!!

Par ailleurs, il y a quelques années, j'ai assisté à des exposés d'un chercheur en cryptographie. Selon lui, dans le monde entier, des labos sont financés par les banques pour trouver de nouveaux algorithmes de cryptapge. Il expliquait que la plupart des nouveaux algorithmes "inviolables", peu après leur publication, se trouvaient cassés par les labos concurrents. Dur, dur !!!!
Et si je me souviens bien, il a glissé dans un de ses baratins que le RSA est bien plus facile à casser qu'on ne le croit mais qu'il y a trop intérêts en jeu pour que cela soit sur la place publique... faute d'une alternative fiable, d'où le financement de la recherche par les banques. Qu'en dirait il maintenant ?

Ce message a été modifié par linus - 3 Aug 2025, 23:03.