L'algorithme de Shor est un algorithme quantique qui résout en temps polynomial deux problèmes sur lesquels repose la cryptographie asymétrique actuelle : la factorisation des grands entiers et le logarithme discret. Exécuté sur un calculateur quantique suffisamment grand et corrigé des erreurs, il casse RSA, Diffie-Hellman et la cryptographie sur courbes elliptiques (ECC).
Pourquoi la taille de clé ne sauve rien
La sécurité de RSA repose sur le fait qu'aucun algorithme classique connu ne factorise efficacement un module de 2 048 ou 4 096 bits. Shor supprime cette difficulté : le coût passe d'exponentiel à polynomial. Doubler la taille de clé augmente marginalement le nombre de qubits nécessaires, mais ne rétablit aucune barrière durable. La seule réponse est de changer de famille mathématique, d'où les standards post-quantiques publiés par le NIST en 2024 : FIPS 203 (ML-KEM), FIPS 204 (ML-DSA) et FIPS 205 (SLH-DSA).
Une échéance à anticiper dès aujourd'hui
Aucune machine publique ne casse aujourd'hui RSA-2048. Le risque est néanmoins actuel pour deux raisons. D'abord la stratégie « store now, decrypt later » : des flux chiffrés captés aujourd'hui peuvent être déchiffrés plus tard. Ensuite la durée de vie des infrastructures, des certificats et des documents signés, souvent supérieure à dix ans. L'ANSSI recommande l'hybridation — combiner un schéma classique et un schéma post-quantique — pendant la période de transition.
Aller plus loin : pourquoi RSA et ECC tombent · les standards PQC du NIST · définition de l'algorithme de Grover · l'approche cognitive de HIAsecure