Les algorithmes de Shor et de Grover expliqués

Les ordinateurs quantiques ne se contentent pas d'exécuter plus rapidement les algorithmes classiques : ils exploitent la superposition et l'interférence quantiques pour résoudre certains problèmes de manière exponentiellement plus rapide. Deux algorithmes menacent la plupart des systèmes cryptographiques déployés : celui de Shor (qui casse RSA/ECC) et celui de Grover (qui affaiblit la cryptographie symétrique et les fonctions de hachage).

L'algorithme de Shor (1994) résout la factorisation des entiers et le logarithme discret en temps polynomial sur un ordinateur quantique. Il casse directement RSA (fondé sur la factorisation), Diffie-Hellman (logarithme discret modulo p) et ECDH/ECDSA (logarithme discret sur les courbes elliptiques).

L'ingrédient essentiel de l'algorithme de Shor est la transformée de Fourier quantique (QFT), une version quantique exponentiellement plus rapide de la DFT. Pour rechercher une période, la QFT identifie la période de f(x) = a^x mod N, à partir de laquelle les facteurs de N sont dérivés au moyen du GCD.

Pour factoriser N : (1) choisissez un a aléatoire tel que a < N et vérifiez que gcd(a,N)=1 ; (2) trouvez la période r de f(x)=a^x mod N au moyen de la QFT ; (3) avec une forte probabilité, gcd(a^{r/2}±1, N) fournit un facteur non trivial. L'étape classique est en O(log N) ; la recherche quantique de la période est en O((log N)^3), donc polynomiale.

Meilleure méthode classique de factorisation : GNFS — O(exp((64/9 log N)^{1/3} log log N)^{2/3})), sous-exponentielle. Sur un ordinateur quantique tolérant aux fautes, l'algorithme de Shor atteint un temps polynomial O((log N)^3). RSA-2048 nécessite environ 4000 qubits logiques et environ 10^9 opérations de portes. Les ordinateurs NISQ actuels disposent d'environ 1000 qubits bruités : ils ne représentent pas encore une menace.

L'algorithme de Grover (1996) fournit une accélération quadratique pour la recherche non structurée. Pour un espace de recherche de N éléments, les algorithmes classiques nécessitent O(N) requêtes ; celui de Grover n'en nécessite que O(√N). Appliqué à la cryptographie, il casse les clés symétriques de n bits en O(2^{n/2}) au lieu de O(2^n).

AES-128 : sécurité classique de 2^128, ramenée par Grover à 2^64 — non sécurisé contre un grand ordinateur quantique. AES-256 : 2^256 → 2^128 — toujours sécurisé. Solution : doubler la taille des clés symétriques. Résistance aux collisions de SHA-256 : 2^128 → 2^85 (paradoxe des anniversaires + Grover). Préimage de SHA-256 : 2^256 → 2^128 — OK.

Les ordinateurs quantiques NISQ actuels (IBM Heron : 133 qubits ; Google Sycamore : 70 qubits) sont trop petits et trop bruités pour effectuer des calculs pertinents en cryptographie. Les estimations situent le cassage de RSA-2048 entre 2035 et 2050 avec des ordinateurs quantiques tolérants aux fautes. Les attaques visant à collecter maintenant les données pour les déchiffrer plus tard représentent une menace actuelle.

Les adversaires collectent aujourd'hui le trafic chiffré et le stockent. Lorsqu'un ordinateur quantique sera disponible, ils le déchiffreront rétroactivement. Les secrets à longue durée de vie (données gouvernementales classifiées, dossiers médicaux) sont donc vulnérables dès aujourd'hui. La migration vers la PQC doit commencer maintenant pour ces données.

Problèmes de réseaux (LWE, SIS), problèmes fondés sur les codes (McEliece), signatures fondées sur les fonctions de hachage (SPHINCS+), problèmes multivariés : aucun algorithme quantique en temps polynomial n'est connu. Ces problèmes constituent le fondement des normes post-quantiques du NIST.

Les normes PQC du NIST (ML-KEM, ML-DSA, SLH-DSA) ont été finalisées en 2024. Les organisations doivent : recenser l'utilisation actuelle de la cryptographie, identifier les données à longue durée de vie et donner la priorité au déploiement de la PQC pour l'échange de clés (le plus urgent en raison des attaques visant à collecter maintenant les données pour les déchiffrer plus tard). Les signatures disposent de davantage de temps.

Quel est l'impact de l'algorithme de Grover sur AES-128 ?

L'algorithme de Shor (temps polynomial) casse RSA, DH et ECC. L'algorithme de Grover (accélération quadratique) réduit de moitié la robustesse des clés symétriques. Solution : migrer vers les normes PQC du NIST (fondées sur les réseaux). Ensuite : CRYSTALS-Kyber KEM.