CRYSTALS-Kyber : KEM fondé sur les réseaux euclidiens

CRYSTALS-Kyber (renommé ML-KEM par le NIST dans FIPS 203) est un mécanisme d'encapsulation de clé (KEM) fondé sur le LWE modulaire. Il remplace RSA et ECDH pour l'échange de clés et fournit une résistance quantique avec des performances pratiques.

Un KEM encapsule un secret partagé : l'expéditeur génère une clé aléatoire K et la chiffre avec la clé publique du destinataire (encapsulation), ce qui produit un texte chiffré C. Le destinataire désencapsule C avec sa clé privée pour récupérer K. Aucun échange de clés interactif n'est nécessaire.

Kyber utilise le LWE modulaire sur l'anneau R_q = Z_q[x]/(x^256+1), avec q=3329. Dimension k=2 (Kyber-512), k=3 (Kyber-768), k=4 (Kyber-1024). Niveau de sécurité : environ 128, 192 et 256 bits, respectivement. k=3 (Kyber-768) est la valeur par défaut recommandée.

Générez la matrice A ∈ R_q^{k×k} à partir de la graine ρ (extensible). Échantillonnez le secret s et le bruit e selon une distribution binomiale centrée (petits coefficients). Clé publique : (ρ, t=As+e). Clé privée : s. Le bruit e est faible, mais il empêche de retrouver s à partir de la clé publique.

Pour envoyer un secret partagé au détenteur de la clé publique (ρ, t), échantillonnez r, e1 et e2 selon la distribution du bruit. Calculez u = A^T r + e1, v = t^T r + e2 + round(q/2)*m, où m est un message aléatoire de 256 bits. Secret partagé K = KDF(m). Texte chiffré = (u, v).

Avec la clé privée s, calculez m' = decompress(v - s^T u) = decompress(t^T r + e2 + round(q/2)*m - s^T(A^T r + e1)). Les termes de bruit s'annulent approximativement, ce qui laisse m'≈m. Calculez K = KDF(m'). Probabilité d'échec de la désencapsulation : < 2^{-139}.

Kyber-768 : clé publique de 1184 octets, clé privée de 2400 octets, texte chiffré de 1088 octets, secret partagé de 32 octets. À titre de comparaison, ECDH-P256 utilise une clé publique de 65 octets et un texte chiffré de 32 octets. Kyber est environ 15 fois plus volumineux, mais résiste aux attaques quantiques. Il reste rapide : encapsulation et désencapsulation prennent moins d'une milliseconde sur les processeurs modernes.

La multiplication polynomiale dans R_q = Z_q[x]/(x^256+1) utilise la transformée de nombres théoriques (NTT), l'analogue arithmétique modulaire de la FFT. La NTT réduit la multiplication polynomiale de O(n^2) à O(n log n). q=3329 a été choisi pour offrir de bonnes propriétés de NTT avec n=256.

Lors de la migration vers la PQC, utilisez un échange de clés hybride : combinez ECDH et Kyber. Secret partagé = KDF(ECDH_output || Kyber_output). La sécurité exige de casser les deux : les adversaires classiques ne cassent ni l'un ni l'autre ; les adversaires quantiques cassent ECDH, mais pas Kyber. Les projets de TLS 1.3 (RFC 8446 de l'IETF) prennent en charge les KEM hybrides.

La désencapsulation de Kyber n'est pas en temps constant dans les implémentations naïves : l'étape d'échantillonnage par rejet révèle des informations par le temps d'exécution. L'implémentation de référence utilise une NTT en temps constant et une comparaison en temps constant des textes chiffrés compressés. Utilisez le code de référence de la soumission au NIST ou des implémentations de bibliothèques auditées.

Le NIST a publié FIPS 203 (ML-KEM) en août 2024. Chrome a ajouté la prise en charge de Kyber dans TLS 1.3 en 2023. Cloudflare, Google et AWS déploient des solutions hybrides ECDH+Kyber. OpenSSL 3.x a ajouté la prise en charge de ML-KEM. Les implémentations de LibSSH et WireGuard sont en cours.

Quel document normatif du NIST définit CRYSTALS-Kyber ?

Kyber (ML-KEM) est un KEM fondé sur le LWE modulaire qui remplace ECDH. Taille des clés : environ 1 Ko ; calculs NTT rapides ; résistance quantique. Déployez-le en mode hybride avec ECDH pendant la migration. Normalisé dans FIPS 203. Ensuite : les schémas de signature CRYSTALS-Dilithium et Falcon.