L'algorithme de Shor résout en temps polynomial deux problèmes réputés difficiles : la factorisation d'un grand entier et le logarithme discret. Or ce sont exactement les deux problèmes sur lesquels reposent RSA, Diffie-Hellman et la cryptographie sur courbes elliptiques. Ce n'est donc pas une faiblesse d'implémentation que l'on corrigerait par un correctif : c'est la disparition du fondement mathématique.
Ce que Shor calcule vraiment
Une confusion fréquente consiste à imaginer un ordinateur quantique qui « essaierait toutes les clés plus vite ». Ce n'est pas le mécanisme.
Shor ramène la factorisation à un problème de recherche de période. Pour factoriser un entier N, on étudie la fonction qui à x associe a^x modulo N. Cette fonction est périodique, et connaître sa période permet de retrouver les facteurs par un calcul classique élémentaire. La partie quantique du travail se limite à déterminer cette période, à l'aide d'une transformée de Fourier quantique : les états qui ne correspondent pas à la bonne période interfèrent destructivement, celui qui correspond ressort avec une forte probabilité.
La même structure algorithmique s'applique au logarithme discret, ce qui condamne du même coup Diffie-Hellman, ECDH, ECDSA et EdDSA.
La conséquence pratique est brutale : augmenter la taille des clés ne sauve pas. Contre une attaque classique, doubler la taille d'une clé RSA augmente le coût de manière exponentielle. Contre Shor, le coût ne croît que de façon polynomiale. On déplace l'échéance de très peu, au prix d'une dégradation de performance immédiate et bien réelle.
Ce qui tombe et ce qui tient
| Famille | Fondement mathématique | Algorithme quantique concerné | Effet |
|---|---|---|---|
| RSA (chiffrement et signature) | factorisation | Shor | cassé |
| Diffie-Hellman, ECDH | logarithme discret | Shor | cassé |
| ECDSA, EdDSA | logarithme discret sur courbe | Shor | cassé |
| AES, ChaCha20 | recherche exhaustive de clé | Grover | sécurité effective réduite de moitié |
| SHA-2, SHA-3, HMAC | préimage et collision | Grover et variantes | affaibli, pas cassé |
La distinction est essentielle. Grover apporte une accélération quadratique sur une recherche non structurée : il ne fait pas disparaître le problème, il en divise le niveau de sécurité effectif par deux. C'est la raison pour laquelle AES-256 est considéré comme une cible raisonnable, alors qu'un AES-128 devient discutable pour des données à longue durée de confidentialité. Le détail du fonctionnement de Grover mérite d'être compris avant d'annoncer que « tout le chiffrement sera cassé » : c'est faux, et un RSSI le sait.
Où RSA et ECC se cachent réellement dans un système d'information
L'inventaire est presque toujours plus large que prévu, parce que l'asymétrique est enfoui dans des protocoles et des produits plutôt qu'exposé dans le code applicatif :
- TLS : établissement de clé et signature du certificat serveur, sur chaque flux HTTPS, chaque appel d'API, chaque connexion à une base de données.
- PKI interne : autorités de certification racines et intermédiaires, certificats machine, signature de code, horodatage.
- Accès distants : IKE/IPsec, clés SSH, certificats de VPN.
- Fédération d'identité : jetons signés en RS256 ou ES256, assertions SAML, jetons OIDC.
- Matériel : cartes à puce, modules de sécurité matériels, clés FIDO2 dont les assertions reposent sur des signatures elliptiques.
- Signature électronique et scellement : documents dont la valeur probante doit survivre des années, voire des décennies.
Cette liste illustre un point souvent négligé : la migration post-quantique n'est pas un sujet de chiffrement de flux. C'est aussi, et peut-être surtout, un sujet d'authentification et de confiance.
Deux régimes de risque à ne pas confondre
Il faut séparer la confidentialité de l'authenticité, car elles n'ont pas la même urgence.
Confidentialité : le risque est rétroactif. Un flux chiffré capté aujourd'hui peut être conservé et déchiffré plus tard. C'est la logique du « store now, decrypt later ». Toute donnée dont la confidentialité doit tenir longtemps est donc exposée dès maintenant, indépendamment de la date d'arrivée d'une machine capable d'exécuter Shor à l'échelle.
Authenticité : le risque est contemporain. Forger une signature exige de disposer de la capacité au moment de la fraude. Une signature émise aujourd'hui ne devient pas frauduleuse rétroactivement. Deux réserves importantes toutefois :
- les ancres de confiance de longue durée (autorités racines, clés de signature de firmware gravées dans du matériel) sont conçues pour rester valides très longtemps ;
- la valeur probante de documents signés doit parfois survivre au-delà de la durée de vie de l'algorithme, ce qui impose des mécanismes de resignature ou d'archivage sécurisé.
Cette distinction est un outil de priorisation : traiter d'abord les secrets à longue durée de confidentialité et les ancres de confiance difficiles à remplacer, avant les jetons de session dont la durée de vie se compte en minutes.
Ce que cela change pour l'authentification
Un facteur d'authentification qui repose sur une clé privée persistante hérite de la fragilité de l'algorithme qui la protège, et de la lourdeur de son cycle de renouvellement. À l'inverse, une preuve construite à partir de paramètres éphémères générés au moment de l'authentification, et de fonctions de hachage composées, ne laisse pas de secret durable à capter aujourd'hui pour l'exploiter demain. C'est la logique retenue par le 4ᵉ facteur cognitif : ce qui est vérifié n'est pas la détention d'une clé, mais la capacité à produire un résultat par une méthode personnelle jamais transmise.
FAQ
Augmenter la taille des clés RSA repousse-t-il vraiment la menace ?
Marginalement, et à un coût élevé. Le travail quantique croît polynomialement avec la taille de la clé, alors que le coût de calcul classique, lui, croît immédiatement pour vos serveurs. Le rapport bénéfice/effort est mauvais comparé à une migration vers des algorithmes post-quantiques.
L'algorithme de Shor a-t-il déjà été exécuté ?
Des démonstrations existent, mais sur des entiers minuscules et sans aucune portée cryptographique. Aucune conclusion sérieuse sur un calendrier ne peut en être tirée, ce qui est précisément pourquoi la planification doit reposer sur la durée de confidentialité exigée par vos données.
Faut-il abandonner AES et SHA-256 ?
Non. Le symétrique et le hachage sont affaiblis, pas cassés. Passer à AES-256 et privilégier des sorties de hachage longues constitue une réponse proportionnée et peu coûteuse.
Par quoi remplace-t-on concrètement RSA et ECC ?
Par les algorithmes standardisés par le NIST en 2024, en privilégiant une approche hybride associant un algorithme classique éprouvé et un algorithme post-quantique, comme le recommande l'ANSSI pendant la période de transition.
Aller plus loin : pilier : authentification cognitive · cryptographie post-quantique, vue d'ensemble · les standards du NIST · « store now, decrypt later »