Algorithme de Shor
Qu'est-ce que Algorithme de Shor ?
Algorithme de ShorAlgorithme quantique qui factorise les grands entiers et calcule les logarithmes discrets en temps polynomial, cassant RSA, Diffie-Hellman et la cryptographie sur courbes elliptiques sur un ordinateur quantique suffisamment grand.
L'algorithme de Shor, publié par Peter Shor en 1994, résout les problèmes de factorisation d'entiers et de logarithme discret en temps polynomial sur un ordinateur quantique tolérant aux fautes. Or, ces deux problèmes fondent presque tous les systèmes à clé publique en production : RSA, Diffie-Hellman, DSA et ECDSA. Aucun matériel quantique actuel ne permet de factoriser des tailles de clés cryptographiquement pertinentes, mais on estime que quelques milliers de qubits logiques stables suffiraient à casser RSA-2048. Cette perspective justifie le processus de normalisation PQC du NIST et la crainte des attaques de type "collecter maintenant, déchiffrer plus tard".
● Exemples
- 01
Sert de base théorique pour estimer le calendrier de la menace quantique sur RSA-2048 et ECC P-256.
- 02
Justifie la migration des primitives asymétriques classiques vers des KEM à base de réseaux comme CRYSTALS-Kyber.
● Questions fréquentes
Qu'est-ce que Algorithme de Shor ?
Algorithme quantique qui factorise les grands entiers et calcule les logarithmes discrets en temps polynomial, cassant RSA, Diffie-Hellman et la cryptographie sur courbes elliptiques sur un ordinateur quantique suffisamment grand. Cette notion relève de la catégorie Cryptographie en cybersécurité.
Que signifie Algorithme de Shor ?
Algorithme quantique qui factorise les grands entiers et calcule les logarithmes discrets en temps polynomial, cassant RSA, Diffie-Hellman et la cryptographie sur courbes elliptiques sur un ordinateur quantique suffisamment grand.
Comment fonctionne Algorithme de Shor ?
L'algorithme de Shor, publié par Peter Shor en 1994, résout les problèmes de factorisation d'entiers et de logarithme discret en temps polynomial sur un ordinateur quantique tolérant aux fautes. Or, ces deux problèmes fondent presque tous les systèmes à clé publique en production : RSA, Diffie-Hellman, DSA et ECDSA. Aucun matériel quantique actuel ne permet de factoriser des tailles de clés cryptographiquement pertinentes, mais on estime que quelques milliers de qubits logiques stables suffiraient à casser RSA-2048. Cette perspective justifie le processus de normalisation PQC du NIST et la crainte des attaques de type "collecter maintenant, déchiffrer plus tard".
Comment se défendre contre Algorithme de Shor ?
Les défenses contre Algorithme de Shor combinent habituellement des contrôles techniques et des pratiques opérationnelles, comme détaillé dans la définition ci-dessus.
Quels sont les autres noms de Algorithme de Shor ?
Noms alternatifs courants : Algorithme de factorisation de Shor.
● Termes liés
- cryptography№ 846
Cryptographie post-quantique
Algorithmes cryptographiques classiques conçus pour rester sûrs face aux attaques d'ordinateurs classiques comme d'ordinateurs quantiques à grande échelle.
- cryptography№ 890
Cryptographie quantique
Cryptographie qui exploite des propriétés quantiques, généralement de photons, pour obtenir des garanties de sécurité impossibles à atteindre avec la seule communication classique.
- cryptography№ 951
Algorithme RSA
Algorithme à clé publique de Rivest, Shamir et Adleman (1977) dont la sécurité repose sur la difficulté de factoriser le produit de deux grands nombres premiers.
- cryptography№ 454
Algorithme de Grover
Algorithme quantique de recherche qui trouve un élément marqué dans une base non structurée de N entrées en environ sqrt(N) étapes, offrant une accélération quadratique contre les chiffrements symétriques et les fonctions de hachage.
- cryptography№ 732
Normalisation PQC du NIST
Processus pluriannuel du NIST qui sélectionne et normalise les algorithmes cryptographiques post-quantiques ; ses trois premières normes, FIPS 203, 204 et 205, ont été publiées en août 2024.
- cryptography№ 253
CRYSTALS-Kyber
Mécanisme d'encapsulation de clé fondé sur les réseaux euclidiens, normalisé par le NIST sous le nom FIPS 203 (ML-KEM) en août 2024 et destiné à remplacer les échanges de clés RSA et Diffie-Hellman dans un monde post-quantique.