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

L'algorithme de Shor, publié par le mathématicien Peter Shor en 1994, est un algorithme quantique qui résout efficacement les problèmes de factorisation entière et de logarithme discret. Ces problèmes mathématiques constituent le fondement de la sécurité des cryptographies RSA, Diffie-Hellman et ECDSA, y compris les signatures protégeant pratiquement toutes les crypto-monnaies actuelles.

Les ordinateurs classiques nécessitent un temps exponentiel pour factoriser de grands nombres ou calculer des logarithmes discrets. Une clé RSA de 2 048 bits mettrait plus de temps à briser les ordinateurs classiques que l’âge de l’univers. L'algorithme de Shor réduit cela au temps polynomial, ce qui rend ces opérations réalisables sur des ordinateurs quantiques suffisamment puissants.

Pour les cryptomonnaies, la menace est spécifique : l'algorithme de Shor peut dériver les clés privées de ECDSA à partir de clés publiques. Bitcoin, Ethereum et la plupart des crypto-monnaies utilisent ECDSA avec la courbe secp256k1. Une fois les clés publiques exposées (ce qui se produit lorsque les adresses sont dépensées), les ordinateurs quantiques exécutant l'algorithme de Shor peuvent calculer les clés privées correspondantes.

L'exécution de l'algorithme de Shor sur ECDSA 256 bits prend 1 200 à 1 450 qubits logiques, rentre à l'intérieur moins de 500 000 qubits physiques, et se termine en minutes — le benchmark de mars 2026 de Google Quantum AI, en collaboration avec la Fondation Ethereum et Stanford. Cela représente environ la moitié des 2 330 qubits logiques estimés précédemment. Une analyse indépendante Caltech/Oratomic atteint la même rupture avec environ 26 000 qubits physiques sur du matériel à atomes neutres sur une dizaine de jours. La factorisation RSA-2048 prend désormais moins d’un million de qubits bruyants et moins d’une semaine (Gidney, mai 2025), contre 20 millions de qubits en 2019 – mais RSA n’est pas la cible la plus proche, car l’ECDSA-256 est moins cher.

Le meilleur matériel public d'aujourd'hui est à peu près 2 500 qubits physiques, aucun de ces éléments n'est tolérant aux pannes à grande échelle. La machine qui comble l'écart est la Blue Jay d'IBM en 2033, avec plus de 2 000 qubits logiques sur environ 100 000 physiques — précédé par Starling en 2029 à ~200 logiques. La fenêtre d'arrivée est 2029-2033.

La cryptographie post-quantique répond à cette menace en utilisant des problèmes mathématiques que l'algorithme de Shor ne peut pas résoudre efficacement. La cryptographie basée sur le réseau (Kyber) et les signatures basées sur le hachage (SPHINCS+) ne connaissent aucune attaque quantique efficace connue.

SynX implémente les algorithmes Kyber-768 et SPHINCS+ spécifiquement parce que l'algorithme de Shor n'offre aucun avantage contre eux. Cela protège les avoirs en cryptomonnaies contre les progrès inévitables de la technologie informatique quantique.