Zusammenfassung
Kyber ist ein Key Encapsulation Mechanism (KEM), kein allgemeines asymmetrisches Verschlüsselungsschema. Ein KEM ermöglicht es zwei Parteien, einen gemeinsamen symmetrischen Schlüssel zu vereinbaren, ohne ihn explizit auszutauschen. Zum Verschlüsseln von Daten wird der abgeleitete Schlüssel mit einer symmetrischen Verschlüsselung (AES, ChaCha) verwendet.
Komponenten
Ein KEM hat drei Operationen:
G = KeyGen() → (pk, sk)
E = Encaps(pk) → (ct, K)
D = Decaps(sk, ct) → K
KeyGen — Schlüsselgenerierung
1. Zufälligen Seed d erzeugen (32 Bytes)
2. A ∈ R_q^{k×k} aus d mit SHAKE-128 ableiten (deterministisches Sampling)
3. s ∈ R_q^{k} aus der CBD(η)-Verteilung abtasten
4. e ∈ R_q^{k} aus der CBD(η)-Verteilung abtasten
5. pk = A·s + e berechnen (als Byte-Array codiert)
6. sk = (s, pk) speichern (oder eine Hash-Form für schnellere Entkapselung)
7. (pk, sk) zurückgeben
Bemerkenswert: Die Matrix A wird deterministisch aus einem Seed erzeugt. Das bedeutet, dass A weder gespeichert noch übertragen werden muss — jeder, der den Seed kennt, kann sie rekonstruieren.
Encaps — Einkapselung
Input: pk
1. Eine zufällige Münze m erzeugen (32 Bytes)
2. (K, r) = G(m || H(pk)) ableiten mit SHA3-256/SHAKE256
wobei G ein Hash ist, H ein anderer Hash
3. t = H(m) berechnen (implizites Commitment)
4. m mit pk und der Zufälligkeit r verschlüsseln:
a. s' ∈ R_q^{k} aus CBD(η) mit r abtasten
b. e1 ∈ R_q^{k} aus CBD(η) abtasten
c. e2 ∈ R_q aus CBD(η) abtasten
d. u = NTT^{-1}(·NTT(s')) + e1 berechnen
e. v = NTT^{-1}(t^T·NTT(s')) + e2 + Decompress_q(m, 1) berechnen
5. ct = (u, v) und K zurückgeben
Decaps — Entkapselung
Input: sk, ct = (u, v)
1. Entschlüsseln:
a. m' = Compress_q(v - s^T·u, 1)
2. Neuverarbeiten:
a. (K', r') = G(m' || H(pk))
b. Encaps mit m' und r' erneut ausführen
c. Ergebnis mit empfangenem ct vergleichen
3. Bei Übereinstimmung: K' zurückgeben
Bei Nichtübereinstimmung: pseudozufälligen Schlüssel aus (sk, ct) zurückgeben
Der Schritt der Neuverarbeitung und des Vergleichs (Fujisaki-Okamoto-Transform) macht Kyber CCA-sicher. Ohne ihn wäre der KEM anfällig für adaptive Ciphertext-Angriffe.
Der vollständige Ablauf
Alice Bob
| |
|--- (pk = A·s + e) --------->| (KeyGen von Alice)
| |
|<--- (ct = (u,v), K) --------| (Encaps mit Alices pk)
| |
|--- entschlüsselt ct mit s --| (Decaps: stellt K wieder her)
| |
|--- (verwendet K für AES/ChaCha) (verschlüsselte Kommunikation)
Wichtig: Anders als bei RSA oder ECDH erzeugt bei Kyber der Empfänger das Schlüsselpaar und der Sender erzeugt den Ciphertext und den Schlüssel. Es ist in den Richtungen asymmetrisch: Die Einkapselung geht immer vom Sender zum Empfänger.
Warum KEM und nicht direkte Verschlüsselung?
Die Entscheidung des NIST, KEMs anstelle von PKE (direkte asymmetrische Verschlüsselung) zu standardisieren, liegt begründet in:
- Einfachheit: Ein KEM hat eine kleinere Schnittstelle und weniger Fehlermodi.
- Natürlicher Hybrid: Kyber + AES/ChaCha = hybride Verschlüsselung, die auch mit RSA/ECC die empfohlene Praxis ist.
- Handhabbarer FO-Transform: Die Fujisaki-Okamoto-Transformation von einem PKE zu einem CCA-sicheren KEM ist einfacher zu analysieren und zu verifizieren als ein direktes CCA-sicheres PKE.
Für allgemeine asymmetrische Verschlüsselung wird HPKE (Hybrid Public Key Encryption, RFC 9180) verwendet, das definiert, wie ein KEM mit einem AEAD kombiniert wird. HPKE mit Kyber wird bereits standardisiert.
Referenzen
- 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).