Qu'est-ce que l'algorithme de Shor et pourquoi menace-t-il Bitcoin ?

Qu'est-ce que l'algorithme de Shor ?

Un algorithme quantique capable de transformer de grands nombres en facteurs premiers et de résoudre le problème du logarithme discret en quelques secondes. Une grande partie de la cryptographie asymétrique moderne (à clé publique) repose sur la complexité de ces deux problèmes : RSA, Protocole Diffie-HellmanSignatures ECDSA et Schnorr.

Pour un ordinateur classique, ces problèmes sont pratiquement insolubles si la clé est suffisamment longue. La meilleure méthode traditionnelle est méthode de tamisage à champ numérique – les revendications temps sous-exponentiel. Par exemple, déchiffrer une clé RSA-2048 prendrait des milliards d'années, mais l'algorithme de Shor résout le même problème dans temps polynomial. L’algorithme est devenu l’un des résultats clés des débuts de l’informatique quantique. Il a montré qu’une machine quantique suffisamment puissante pourrait résoudre efficacement les problèmes sur lesquels reposent les systèmes cryptographiques largement utilisés.

Qui l'a inventé et quand ?

Le mathématicien Peter Shor de Laboratoires Bell en 1994. Avant cela, l'informatique quantique existait déjà en tant que direction théorique, mais elle n'avait pas d'application aussi convaincante pour résoudre un problème pratiquement important. Les travaux de Shor ont montré qu'un ordinateur quantique suffisamment puissant serait capable de briser une gamme de systèmes cryptographiques à clé publique, notamment le RSA et la cryptographie à courbe elliptique. Cela est devenu l’une des principales incitations au développement de l’informatique quantique et, par la suite, à la création d’une cryptographie post-quantique résistante à de telles attaques.

Comment fonctionne l'algorithme de Shor ?

Le problème de la factorisation (factorisation d'un nombre) revient à trouver la période d'une fonction spéciale. Un ordinateur classique passe trop de temps sur cette recherche. Un ordinateur quantique crée une superposition de nombreux états possibles et utilise ensuite ingérence Et transformée de Fourier quantique met en évidence la structure périodique de la fonction. Après mesure et traitement classique, vous pouvez en obtenir les facteurs d'un nombre ou résoudre le problème du logarithme discret.

Le flux de travail ressemble à ceci :

1. Préparation (PC ordinaire) : formule le problème et sélectionne un nombre aléatoire pour commencer.
2. Noyau quantique (PC quantique) : Trouve la période cachée d'une fonction en un seul passage.
3. Finale (PC standard) : utilise la période pour calculer instantanément les multiplicateurs.

Un ordinateur quantique produit des résultats avec une certaine probabilité. Si la tentative échoue, l’algorithme est relancé. Pour les courbes elliptiques qui protègent le réseau de la première cryptomonnaie, une modification de l'algorithme de Shor est utilisée : il résout le problème du logarithme discret et permet de calculer la clé privée à partir de la clé publique.

Pourquoi les ordinateurs quantiques menacent-ils spécifiquement Bitcoin ?

La plupart des sorties Bitcoin sont contrôlées par des clés de courbe elliptique privées et publiques. secp256k1. Le premier est nécessaire pour créer une signature, le second est nécessaire pour la vérifier. Trouver une clé privée à partir d'une clé publique est impossible sur un ordinateur classique : les meilleurs algorithmes nécessitent environ 2¹²⁸ étapes de calcul.

L'algorithme de Shor résout efficacement le problème du logarithme discret sur une courbe en temps polynomial, réduisant ainsi le processus de piratage. Une attaque quantique devient possible après la révélation de la clé publique. Pour certains types de sorties, il est publié dès la création de la sortie, pour d'autres, uniquement lorsque les fonds sont dépensés pour la première fois. Les signatures ECDSA et les signatures Schnorr modernes sont menacées par l'algorithme de Shor.

En même temps, fonction d'exploitation minière et de hachage SHA-256 bien mieux protégé. L'algorithme quantique de Grover ne leur donne qu'une accélération quadratique. La complexité de la recherche tombe à 2¹²⁸ opérations, ce qui reste sûr et peut être facilement nivelé en passant à des hachages plus longs à l'avenir.

Menace quantique pour Bitcoin : combien de qubits sont nécessaires ?

Il est important de faire ici la distinction entre les qubits physiques et logiques. Les qubits physiques sont instables et sujets au bruit. Pour obtenir un qubit logique fiable, des dizaines ou des centaines de qubits physiques sont nécessaires, combinés à des algorithmes de correction d’erreurs. Lorsque les chercheurs parlent d’une véritable attaque, ils évaluent les qubits physiques d’une machine tolérante aux pannes.

Les estimations des ressources nécessaires à une attaque quantique contre la cryptographie blockchain sont en chute libre. Les premiers travaux théoriques sur les systèmes ioniques nécessitaient des millions de qubits physiques, mais en 2026, la situation a changé :

1. Google Quantum AI, en collaboration avec la Fondation Ethereum et l'Université de Stanford, a publié une étude selon laquelle moins de 500 000 qubits physiques suffisent pour déchiffrer une clé de 256 bits sur une architecture supraconductrice. C'est 20 fois moins que les estimations précédentes. La mise en œuvre pratique est encore inaccessible, mais le seuil théorique a été considérablement réduit.
2. IonQ a présenté le premier schéma d'ingénierie complet pour attaquer la courbe secp256k1. Selon les calculs des ingénieurs, sur la dernière architecture Walking Cat, un ordinateur ionique ne nécessitera que 19 397 qubits physiques (1 457 logiques). Dans ce cas, une sélection de clé prendra environ 25,7 jours.

La variation des effectifs s'explique par le type d'équipement. Les pièges à ions IonQ effectuent des opérations avec beaucoup plus de précision que les puces supraconductrices de Google et nécessitent donc beaucoup moins de qubits pour la correction des erreurs. Il faut payer cela à temps : les machines ioniques fonctionnent beaucoup plus lentement – donc près d'un mois pour générer une clé au lieu de quelques minutes pour les supraconducteurs.

Que signifie le score IonQ en pratique ?

Réservons tout de suite : il s'agit d'un calcul mathématique, pas d'une véritable expérience. La société a spécifiquement souligné qu’une machine capable de mener une telle attaque n’existe pas aujourd’hui : pas un seul portefeuille cryptographique ou clé privée n’a été compromis.

La valeur de la recherche est ailleurs. Pour la première fois, l'algorithme de Shor est décrit dans les moindres détails – jusqu'à des portes de correction d'erreurs spécifiques avec une probabilité de succès prouvée plutôt qu'hypothèse. Il s’agit essentiellement d’un plan détaillé pour les futurs appareils.

Pour comprendre l'ampleur : les plus grands processeurs quantiques opérationnels (tels que ceux d'IBM) ne contiennent aujourd'hui qu'environ 1 100 à 1 200 qubits physiques, fonctionnant sans correction d'erreur complète. L’écart entre un millier de qubits bruyants et les 20 000 qubits requis dans une machine tolérante aux pannes est encore énorme.

Quelqu'un a-t-il déjà craqué des clés en utilisant l'algorithme de Shor ?

Jusqu’à présent, les succès se limitent aux échelles « jouets ». En 2001, le système de RMN liquide à 7 qubits d'IBM a implémenté avec succès pour la première fois l'algorithme de Shor, prenant en compte le nombre 15 en facteurs premiers. En 2012, les chercheurs ont élevé la barre à 21, mais ce record et les suivants ont été obtenus grâce à des circuits quantiques « compilés » et simplifiés par les mathématiciens à l’avance, avant même le début des calculs.

Dans le segment de la courbe elliptique, les progrès semblent plus dynamiques, mais non sans réserves importantes. Le 24 avril 2026, le chercheur indépendant Giancarlo Lelli a prouvé le piratage d'une clé de 15 bits à l'aide d'une solution quantique accessible au public d'IBM (en recevant pour cela une récompense de 1 BTC du Projet Eleven). L'espace de recherche a été multiplié par 512 par rapport au précédent enregistrement de 6 bits.

Cependant, les développeurs de blockchain ont accueilli la nouvelle avec scepticisme : 15 bits ne génèrent que 32 768 combinaisons, qu'un PC ordinaire trie en une fraction de seconde, et les résultats de la génération quantique due à un bruit matériel à une telle échelle sont difficiles à distinguer d'une substitution aléatoire.

La véritable clé du réseau Bitcoin (256 bits) est encore loin. L'écart entre l'expérience 15 bits et secp256k1 est énorme, mais pas parce que les ressources de l'algorithme de Shor augmentent de façon exponentielle avec chaque bit. Le principal problème est la nécessité d’exécuter un très long circuit quantique sur des centaines ou des milliers de qubits logiques avec correction d’erreurs. Cela nécessite des appareils bien plus grands et plus fiables que ceux qui existent aujourd’hui.

Quelles pièces sont les plus à risque ?

L'algorithme de Shor nécessite une clé publique. Dans Bitcoin, ce n’est pas toujours révélé :

1. Formater les adresses P2PK (les premières pièces, y compris celles qui appartiendraient à Satoshi Nakamoto) contiennent la clé publique directement sur la blockchain.
2. Portefeuilles réutilisables : si à partir d'un tel compte (par exemple, P2PKH) ont déjà envoyé des transactions, la clé publique a été révélée lors de la signature. L'utilisation répétée d'une telle adresse rend le solde vulnérable.
3. Format réseau Racine pivotante (P2TR) : la clé publique est directement présente dans la blockchain dès la création UTXO. Par conséquent, si une machine quantique suffisamment puissante apparaît, ces fonds seront vulnérables avant même d’être dépensés.

Les adresses à partir desquelles les fonds n'ont jamais été dépensés (par exemple, P2PKH « propre », P2WPKH) cachent la clé derrière un hachage cryptographique. Ils ne peuvent être attaqués que dans une courte fenêtre, lorsque la transaction est dans le mempool : l'attaquant dispose de quelques minutes pour calculer la clé et « tuer » la transaction avec la sienne. L'estimation actuelle d'IonQ de 26 jours par clé exclut complètement une telle attaque. Selon diverses estimations, les adresses dont les clés ont déjà été divulguées contiennent désormais environ un quart de tous les bitcoins existants.

Comment le secteur se prépare-t-il ?

En août 2024 NIST a approuvé les trois premières normes post-quantiques : ML-KEM pour l'échange de clés, ainsi que ML-DSA et SLH-DSA pour les signatures numériques. En mars 2025, l’algorithme de repli HQC a été ajouté, dont la norme définitive est attendue d’ici 2027.

Selon le projet NIST IR 8547, les courbes RSA et elliptiques classiques devraient être obsolètes après 2030, et d'ici 2035, leur utilisation dans le secteur public américain sera totalement interdite.

La communauté Bitcoin discute activement du projet de proposition BIP-361. L'initiative, présentée par le développeur Jameson Lopp et un groupe d'experts, consiste à geler les pièces vulnérables aux ordinateurs quantiques.

Ethereum considère l'abstraction de compte comme l'un des outils clés qui, après une mise à jour appropriée du protocole, permettront aux comptes d'utiliser différents schémas de vérification de signature, y compris post-quantiques.

Quand est le Jour Q ?

Il n’y a pas de consensus. Après les publications de mars 2026, Google, Microsoft et Cloudflare ont désigné 2029 comme référence – non pas pour la création d'un supercalculateur, mais pour une transition complète vers des algorithmes de chiffrement post-quantique. Les experts s’attendent à l’émergence d’un ordinateur quantique cryptographiquement dangereux à l’approche des années 2030. Dans le même temps, les sceptiques rappellent qu'au cours des 30 années écoulées depuis la publication de l'algorithme de Shor, seul le nombre 21 a été résolu sur du matériel réel.

Cependant, des recherches portant sur 2026 montrent que les besoins en matériel diminueront plus rapidement qu’on ne le pensait auparavant. En six mois, l'estimation théorique des systèmes basés sur des atomes neutres est passée de millions de qubits à 10 000-20 000.

Que doit faire un détenteur de cryptomonnaie ?

1. Ne réutilisez pas les adresses. Chaque nouvelle transaction signifie une nouvelle adresse.
2. Transférez des fonds depuis d'anciennes adresses P2PK et des adresses avec une clé révélée vers de nouvelles.
3. Surveillez les mises à jour du portefeuille : la migration vers les signatures post-quantiques nécessitera une action de l'utilisateur.
4. Ne faites pas confiance aux projets qui promettent une « protection quantique » sans audit du code ouvert.

La chose la plus dangereuse pour un réseau n’est pas un piratage soudain, mais le chaos lors d’une migration précipitée. Plus tôt la communauté s’accordera sur une norme, plus la transition se fera en douceur.