L’algorithme de Shor casse la factorisation et le logarithme discret : RSA, DH sur corps finis, ECDH, ECDSA et EdDSA tombent tous face à un ordinateur quantique cryptographiquement pertinent. Les schémas post-quantiques reposent sur des problèmes sans raccourci quantique connu : réseaux euclidiens structurés (ML-KEM, ML-DSA, FN-DSA), fonctions de hachage (SLH-DSA, LMS, XMSS) et codes correcteurs d’erreurs (HQC, Classic McEliece). Les algorithmes de chiffrement symétriques et les fonctions de hachage ne subissent que l’accélération quadratique de Grover, si bien qu’AES-256, AES-128 et SHA-256 restent utilisables.
Le NIST a publié FIPS 203 (ML-KEM), FIPS 204 (ML-DSA) et FIPS 205 (SLH-DSA) le 13 août 2024 ; FN-DSA (FIPS 206, issu de Falcon) et HQC sont encore à l’état de projet. Le NIST IR 8547 (projet public initial) propose de déprécier les algorithmes classiques de 112 bits après 2030 et d’interdire tous les algorithmes à clé publique vulnérables au quantique après 2035 ; le CNSA 2.0 de la NSA fixe des dates plus précoces pour les systèmes de sécurité nationale.
Ordre de migration en pratique : d’abord l’échange de clés hybride, car le trafic enregistré peut être déchiffré plus tard (X25519MLKEM768 en TLS et mlkem768x25519-sha256 en SSH sont déjà des choix par défaut), puis les signatures et la PKI, où les tailles et la distribution de la confiance posent des problèmes plus difficiles. Le zoo des algorithmes PQC compare les tailles et les vitesses.