Résumé
Kyber est un Key Encapsulation Mechanism (KEM), pas un schéma de chiffrement asymétrique général. Un KEM permet à deux parties de convenir d'une clé symétrique partagée sans l'échanger explicitement. Pour chiffrer des données, on utilise la clé dérivée avec un chiffrement symétrique (AES, ChaCha).
Composants
Un KEM a trois opérations :
G = KeyGen() → (pk, sk)
E = Encaps(pk) → (ct, K)
D = Decaps(sk, ct) → K
KeyGen — Génération de Clés
1. Générer une graine aléatoire d (32 bytes)
2. Dériver A ∈ R_q^{k×k} de d en utilisant SHAKE-128 (échantillonnage déterministe)
3. Échantillonner s ∈ R_q^{k} de la distribution CBD(η)
4. Échantillonner e ∈ R_q^{k} de la distribution CBD(η)
5. Calculer pk = A·s + e (codé comme byte array)
6. Stocker sk = (s, pk) (ou une forme hash pour désencapsulation plus rapide)
7. Retourner (pk, sk)
Notable : La matrice A est générée de façon déterministe à partir d'une graine. Cela signifie que A n'a pas besoin d'être stockée ni transmise — quiconque connaît la graine peut la reconstruire.
Encaps — Encapsulation
Input : pk
1. Générer une monnaie aléatoire m (32 bytes)
2. Dériver (K, r) = G(m || H(pk)) en utilisant SHA3-256/SHAKE256
où G est un hash, H est un autre hash
3. Calculer t = H(m) (engagement implicite)
4. Chiffrer m en utilisant pk et l'aléatoire r :
a. Échantillonner s' ∈ R_q^{k} de CBD(η) en utilisant r
b. Échantillonner e1 ∈ R_q^{k} de CBD(η)
c. Échantillonner e2 ∈ R_q de CBD(η)
d. Calculer u = NTT^{-1}(·NTT(s')) + e1
e. Calculer v = NTT^{-1}(t^T·NTT(s')) + e2 + Decompress_q(m, 1)
5. Retourner ct = (u, v) et K
Decaps — Désencapsulation
Input : sk, ct = (u, v)
1. Déchiffrer :
a. m' = Compress_q(v - s^T·u, 1)
2. Retraiter :
a. (K', r') = G(m' || H(pk))
b. Ré-exécuter Encaps en utilisant m' et r'
c. Comparer le résultat avec ct reçu
3. Si ça correspond : retourner K'
Si ça ne correspond pas : retourner une clé pseudo-aléatoire dérivée de (sk, ct)
L'étape de retraitement et comparaison (transformation Fujisaki-Okamoto) est ce qui rend Kyber CCA-sécurisé. Sans elle, le KEM serait vulnérable aux attaques par texte chiffré adaptatif.
Le Flux Complet
Alice Bob
| |
|--- (pk = A·s + e) --------->| (KeyGen d'Alice)
| |
|<--- (ct = (u,v), K) --------| (Encaps en utilisant pk d'Alice)
| |
|--- déchiffre ct avec s -----| (Decaps : récupère K)
| |
|--- (utilise K pour AES/ChaCha) -| (communication chiffrée)
Important : Contrairement à RSA ou ECDH, dans Kyber, le récepteur génère la paire de clés et l'émetteur génère le ciphertext et la clé. C'est asymétrique dans les directions : l'encapsulation va toujours de l'émetteur vers le récepteur.
Pourquoi KEM et pas chiffrement direct ?
La décision du NIST de standardiser des KEM plutôt que des PKE (chiffrement asymétrique direct) répond à :
- Simplicité : Un KEM a une interface plus petite et moins de modes de défaillance.
- Hybride naturel : Kyber + AES/ChaCha = chiffrement hybride, qui est la pratique recommandée même avec RSA/ECC.
- FO transform gérable : La transformation de Fujisaki-Okamoto d'un PKE à un KEM CCA-sécurisé est plus facile à analyser et vérifier qu'un PKE CCA-sécurisé direct.
Pour le chiffrement asymétrique d'usage général, on utilise HPKE (Hybrid Public Key Encryption, RFC 9180), qui définit comment combiner un KEM avec un AEAD. HPKE avec Kyber est déjà en cours de standardisation.
Références
- Fujisaki, E. & Okamoto, T. (1999). "Secure Integration of Asymmetric and Symmetric Encryption Schemes." CRYPTO 1999.
- Hofheinz, D., Hövelmanns, K. & Kiltz, E. (2017). "A Modular Analysis of the Fujisaki-Okamoto Transformation." TCC 2017.
- RFC 9180 — Hybrid Public Key Encryption (HPKE).