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

[Mac Arthur]

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!

Alors la question est mal formulée…
La réponse est "jamais" et non "non"...


PS : J'ai pris le temps de lire et c'est super intéressant. Nombres premiers, factorisation, ça m'a rappelé plein de souvenirs. Quant à la règle à calcul…

Ce message a été modifié par Mac Arthur - 2 Aug 2025, 23:39.

[Paul Emploi]

Nombres premiers, factorisation, ça m'a rappelé plein de souvenirs. Quant à la règle à calcul…

Je fais parti de ces personnes qui à l'école primaire ont reçu en cadeau une belle règle à calcul de qualité, c'était cher, un très bel objet de précision.
Puis à 10 ans, en 6ème, reçu l'apogée de l'analogique grâce à mon oncle chez Air France: un vrai disque de navigation aérienne, le vrai des navigateurs d'Air France!!!
Putains de cadeaux!

[Mac Arthur]

Graphoplex 😘

PS. Modifie le titre, ou la réponse

[Paul Emploi]

Graphoplex 😘

PS. Modifie le titre, ou la réponse

Oui ça correspond.

Le plus fort est que la multiplication est simplement une addition sur une échelle logarithmique. La division une simple soustraction.
D'un coup ça fait voir les données et le monde différemment, je devais être en CM2!
Cette règle à calcul m'a ouvert des horizons, mathématiquement, mais aussi pour ma façon de comprendre le réel.

Non non pour le titre.
Je parle des articles avec une question posée, et en général la réponse est "non" dans l'article, leurs titres sont putaclique.
Et ma réponse n'est pas non si tu lis la fin, c'est "ça dépends"...
Une "simple" avancée mathématique et on est tous à poil avec nos données exposées à tous. Le plus probable, mais quand?!?

PS: ne nous engageons pas dans le (perfect) Forward Secrecy. Ça compliquerait

[Mac Arthur]

Merci pour ce moment
https://www.photocalcul.com/Calcul/Regles/G...#GRAPHO%20CLASS

[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.

[Paul Emploi]

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

Lis le papier de recherche...

Je te renverrais sur la page Wikipedia sur l'algorithme de Shor:
"L'algorithme de Shor fut utilisé en 2001 par un groupe d'IBM, qui factorisa 15 en 3 et 5, en utilisant un calculateur quantique de 7 qubits. Vingt cinq ans plus tard le record du plus grand entier factorisé en pratique par l'algorithme de Shor n'a pas été grandement amélioré et stagne toujours de l'ordre de 32."

Pour l'instant on en est à 35 qui a été factorisé avec presque succès par un ordinateur quantique: 5x7. 6 bits.
Je ne doute pas qu'on puisse en arriver bientôt à 77 (7x11), voire 143 (11x13) dans cette décennie, soit des nombres sur 7 bits et 8 bits.
On est très loin des 4096 bits nécessaires ad-minima, et 8192 pour ceux qui sont plus précautionneux.
À ce rythme on cassera du très vieux RSA 1024 bits dans 2 millénaires et l'actuel RSA 4096 bits de base dans 8 millénaires. Je dors tranquille!

L'algorithme de Shor n'est pas en cause. Ce qui est en cause est le coté réellement quantique des "ordinateurs quantiques" actuels.
Présenté autrement, l'enchevêtrement (entanglement) est-il vraiment obtenu sur des dizaines voire centaines de Qubits, et se maintient-il suffisamment longtemps pour obtenir un quelconque résultat utile? La réponse à ces deux questions semble être non, passé quelques Qubits.

Encore une fois, il ne faut pas croire les titres sensationnalistes ou alarmistes, ou la nécessité d'utiliser de la cryptographie post-quantique (PQC), en grande partie expérimentale, dont la sécurité réelle contre les attaques traditionnelles n'est pas connue, avec de nombreux algorithmes du NIST qui se sont révélés faibles ou pire.
Vous pouvez, vous aussi, dormir sur vos deux oreilles!

[Anibé]

Tsss… Je sens que le temps est proche où l'immense majorité des peuples de la Terre va ressentir la nécessité de se servir à nouveau de papier et de crayons pour transmettre ses pensées, ses recherches et ses sentiments (sans parler des rapports avec la Très-Sainte-Administration qui nous écrase de ses exigences ordinatoresques depuis des années, et à qui il va falloir faire comprendre que nous - ni Elle, d'ailleurs - n'avons plus les compétences pour utiliser ces objets magiques auxquels nous ne comprenons plus rien…)
Pardon, je ne voulais pas troller…

[dijee]

Entendu, mais alors pourquoi les administrations américaines doivent t'elles se préparer à la cryptographie post quantique dès maintenant? ( loi de 2022 )

Je veux bien qu'ils soient particulièrement prudents là bas, mais ils ont l'air de prendre le cassage de leur sécurité par un éventuel véritable ordinateur quantique, susceptible d'apparaitre un jour, comme sérieux.

Ou alors il ne s'agit pas de la meme cryptographie?

J'ai lu aussi tout et son contraire pour les cryptomonnaies par rapport à ce problème

Perso avec le peu de compréhension que j'ai de toutes ces choses je m'y perd complétement

[Paul Emploi]

Entendu, mais alors pourquoi les administrations américaines doivent t'elles se préparer à la cryptographie post quantique dès maintenant? ( loi de 2022 )

C'est extrêmement simple, soit les lois sont conçues par des chercheurs et des scientifiques de tous poils.
Soit elles sont conçues par des des personnes n'ayant (hors exception) aucune idée de ce dont elles parlent...

Un des avantages de cette loi Américaine a été de promouvoir des systèmes de chiffrement/authentification/hashing bien moins résistants aux attaques traditionnelles.
Bien sûr, seul un conspirationniste pourrait prétendre que ça arrange le gouvernement US de pouvoir casser la sécurité des échanges et stockages chiffrés.
Loin de moi cette idée, même si je me souvient de Clipper...

[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.

[Anibé]

Merci

Ce message a été modifié par Anibé - 4 Aug 2025, 09:13.

[DOMY]

Une émission sur ARTE que j'ai vu, il n'y a pas longtemps !

42 - La réponse à presque tout : Le chiffrement parfait existe-t-il ?
Nous l’avons toujours cherché, ce code parfait à même de sécuriser à 100 % nos informations personnelles.
Mais il y a un hic : même la clé le plus sécurisée ne le reste que jusqu’à son décryptage.
En la matière, l’ordinateur quantique est une source d’inquiétude majeure.
Car il pourrait bientôt décoder les systèmes actuels de chiffrement et rendre ainsi publiques toutes nos données numériques.



Ce message a été modifié par DOMY - 4 Aug 2025, 09:26.

[Stéphane33]

Je partage que la cryptographie asymétrique, comme RSA, révolutionne le sujet.
Par contre, je crois que les inventeurs ne sont pas les chercheurs ayant donné leurs noms au RSA.

La cryptographie asymétrique a été inventée en 1973 par James Ellis au Government Communications Headquarters (service de renseignements électronique du gouvernement britannique) et tenu secret jusqu’en 1997. D'ailleurs, il est mort avant que ce soit public.

[Benzebut]

"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.

La suprématie quantique n'est pas, simplement parce que cette nouvelle approche des qbits n'est pas maitrisée. Et que la puissance fournie est gaspillée par le code pour l'exploiter sur des simples problèmes proposés.

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.

C'est pourtant bien résumé et tout le cœur du problème. Il me faudra donc trouver cette conférence de Xavier Waintal. Mais qui n'est pas propre au quantique, mais bien au développement des techniques par l'optimisation et la maitrise des ressources. Actuellement c'est comme donner un Ferrari à un jeune conducteur en lui demandant de devenir champion du monde dès le premier grand prix...

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 ?

Il dirait probablement la même chose sur ces différents points. Depuis ce cher Vauban, il est admis que tout est prenable, c'est une simple question de temps et de moyens.
Ainsi, il est indispensable pour le système bancaire d'être sécurisé pour que ses utilisateurs aient confiance en lui. S'il ses codes sont contournables, il devient obsolète et perd sa raison d'être. Le système doit résister, même s'il ne sera jamais inviolable, comme les citadelles pour Vauban. Et tous les codes actuels ont été cassés, puis mis à jour et le seront encore. Mais si cela reste marginal et "contrôlé", c'est acceptable car ignoré par le plus grand nombre.
Toutes les organisations étudient les alternatives pour renforcer leurs sécurités, avec tout le drame des fantasmes, utopies et charlatans. Afin d'être plus en avance que les autres au cas où...