Cryptographie post-quantique

La cryptographie post-quantique développe des schémas à clé publique dont la sécurité repose sur des problèmes réputés difficiles même pour les ordinateurs quantiques, remplaçant la cryptographie RSA et à courbe elliptique que l'algorithme de Shor pourrait casser.

Definition

La cryptographie post-quantique comprend des algorithmes cryptographiques classiques (non quantiques) conçus pour rester sécurisés face à des adversaires équipés d'ordinateurs quantiques à grande échelle, en s'appuyant sur des problèmes pour lesquels aucun algorithme quantique efficace n'est connu.

Scope

Ce sujet couvre la menace quantique (algorithmes de Shor et de Grover), les principales familles de schémas résistants aux attaques quantiques — basés sur les réseaux, basés sur les codes, basés sur les fonctions de hachage et multivariés —, l'effort de normalisation du NIST et ses algorithmes sélectionnés (ML-KEM, ML-DSA, SLH-DSA), ainsi que les préoccupations liées à la migration, telles que le concept de 'récolter maintenant, déchiffrer plus tard' et le déploiement hybride. Il exclut la cryptographie quantique proprement dite (distribution quantique de clés), qui utilise du matériel quantique plutôt que des algorithmes classiques.

Core questions

• Pourquoi les ordinateurs quantiques cassent-ils la cryptographie RSA et à courbe elliptique, mais pas aussi sévèrement les chiffrements symétriques ?
• Quels problèmes difficiles (réseaux, codes, fonctions de hachage) sont réputés résister aux attaques quantiques ?
• Quels schémas le NIST a-t-il sélectionnés pour la normalisation, et quels sont leurs compromis ?
• Qu'est-ce que la menace 'récolter maintenant, déchiffrer plus tard' et pourquoi crée-t-elle une urgence ?
• Comment les schémas post-quantiques et classiques sont-ils combinés dans les déploiements hybrides pendant la migration ?

Key concepts

• Algorithme de Shor
• Algorithme de Grover
• Cryptographie basée sur les réseaux (apprentissage avec erreurs)
• Cryptographie basée sur les codes
• Signatures basées sur les fonctions de hachage
• ML-KEM (Kyber) et ML-DSA (Dilithium)
• Récolter maintenant, déchiffrer plus tard
• Crypto-agilité
• Échange de clés hybride

Key theories

La menace quantique de l'algorithme de Shor

L'algorithme quantique de Shor factorise les entiers et calcule les logarithmes discrets en temps polynomial, cassant RSA, Diffie-Hellman et la cryptographie à courbe elliptique ; l'algorithme de Grover n'accélère la force brute que de manière quadratique, donc les clés symétriques n'ont besoin que d'être doublées.

Familles de problèmes résistants aux attaques quantiques

La sécurité post-quantique est recherchée dans des problèmes tels que l'apprentissage avec erreurs et les problèmes de vecteur le plus court dans les réseaux, le décodage de codes linéaires aléatoires, et la sécurité des fonctions de hachage — dont aucun n'a d'algorithme quantique efficace connu.

Mechanisms

Les schémas basés sur les réseaux, tels que ML-KEM (dérivé de CRYSTALS-Kyber), fondent l'encapsulation de clé sur la difficulté du problème d'apprentissage avec erreurs sur modules, ajoutant de petites 'erreurs' aléatoires que seule la clé privée peut supprimer. Les signatures basées sur les fonctions de hachage (SLH-DSA/SPHINCS+) construisent des signatures uniquement à partir de la sécurité d'une fonction de hachage. Les schémas basés sur les codes dissimulent une structure décodable dans un code linéaire d'apparence aléatoire. La migration utilise généralement des constructions hybrides qui combinent un schéma classique et un schéma post-quantique, de sorte que la sécurité est maintenue si l'un ou l'autre résiste.

Clinical relevance

La migration est déjà en cours dans les systèmes déployés : les principaux navigateurs et bibliothèques TLS ont activé l'échange de clés hybride ML-KEM, les applications de messagerie (PQXDH de Signal) et SSH ont ajouté des poignées de main post-quantiques, et les organismes de normalisation exhortent les organisations à inventorier leur cryptographie et à planifier les transitions. Le risque de 'récolter maintenant, déchiffrer plus tard' signifie que les données nécessitant une confidentialité à long terme devraient être protégées contre les attaques quantiques dès aujourd'hui.

Evidence & guidelines

Le NIST a finalisé ses premières normes post-quantiques en 2024 : FIPS 203 (ML-KEM) pour l'encapsulation de clé, FIPS 204 (ML-DSA) et FIPS 205 (SLH-DSA) pour les signatures. Les directives du NIST, de la NSA (CNSA 2.0) et des agences nationales établissent les calendriers de migration. La meilleure pratique pendant la transition privilégie les schémas hybrides combinant des algorithmes post-quantiques et classiques.

History

L'algorithme de Peter Shor en 1994 a montré que les ordinateurs quantiques pourraient casser les systèmes à clé publique dominants, motivant la recherche d'alternatives. La cryptographie basée sur les réseaux a progressé grâce aux résultats de dureté dans le pire des cas d'Ajtai et au problème d'apprentissage avec erreurs de Regev (2005). Le NIST a lancé un processus de normalisation public en 2016 ; après plusieurs tours, il a sélectionné CRYSTALS-Kyber et d'autres, publiant les premières normes (FIPS 203-205) en 2024.

Key figures

• Peter Shor
• Daniel J. Bernstein
• Tanja Lange
• Oded Regev
• Chris Peikert

Seminal works

• shor1997
• nist2024mlkem
• bernstein2017

Frequently asked questions

Existe-t-il déjà des ordinateurs quantiques capables de casser RSA ?

Non. Les ordinateurs quantiques actuels sont beaucoup trop petits et bruyants pour exécuter l'algorithme de Shor sur des tailles de clés réelles. La préoccupation concerne les machines futures, combinée au fait que les données chiffrées aujourd'hui pourraient être stockées et déchiffrées une fois que de telles machines existeront.

La cryptographie post-quantique nécessite-t-elle du matériel quantique ?

Non. Les schémas post-quantiques fonctionnent sur des ordinateurs classiques ordinaires ; ils reposent simplement sur des problèmes mathématiques réputés difficiles même pour les attaquants quantiques. La distribution quantique de clés, qui utilise du matériel quantique, est une approche distincte.