CRYSTALS-Kyber: gitterbasierter KEM

CRYSTALS-Kyber (von NIST in FIPS 203 in ML-KEM umbenannt) ist ein auf Module-LWE basierendes Key Encapsulation Mechanism (KEM). Es ersetzt RSA und ECDH beim Schlüsselaustausch und bietet Quantenresistenz bei praxisgerechter Leistung.

Ein KEM kapselt ein gemeinsames Geheimnis: Der Sender erzeugt einen zufälligen Schlüssel K und verschlüsselt ihn mit dem öffentlichen Schlüssel des Empfängers (Kapselung), wodurch ein Chiffretext C entsteht. Der Empfänger entkapselt C mit seinem privaten Schlüssel, um K wiederherzustellen. Ein interaktiver Schlüsselaustausch ist nicht erforderlich.

Kyber verwendet Module-LWE über dem Ring R_q = Z_q[x]/(x^256+1) mit q=3329. Die Dimension beträgt k=2 (Kyber-512), k=3 (Kyber-768) beziehungsweise k=4 (Kyber-1024). Die Sicherheitsstufen betragen jeweils etwa 128, 192 und 256 Bit. k=3 (Kyber-768) ist die empfohlene Standardeinstellung.

Erzeugen Sie aus dem Seed ρ (erweiterbar) die Matrix A ∈ R_q^{k×k}. Ziehen Sie das Geheimnis s und das Rauschen e aus einer zentrierten Binomialverteilung (mit kleinen Koeffizienten). Öffentlicher Schlüssel: (ρ, t=As+e). Privater Schlüssel: s. Das Rauschen e ist klein, verhindert aber, dass s aus dem öffentlichen Schlüssel rekonstruiert werden kann.

Um dem Inhaber des öffentlichen Schlüssels (ρ, t) ein gemeinsames Geheimnis zu senden: Ziehen Sie r, e1 und e2 aus der Rauschverteilung. Berechnen Sie u = A^T r + e1 sowie v = t^T r + e2 + round(q/2)*m, wobei m eine zufällige 256-Bit-Nachricht ist. Gemeinsames Geheimnis K = KDF(m). Chiffretext = (u, v).

Mit dem privaten Schlüssel s: Berechnen Sie m' = decompress(v - s^T u) = decompress(t^T r + e2 + round(q/2)*m - s^T(A^T r + e1)). Die Rauschanteile heben sich annähernd auf, sodass m'≈m verbleibt. Berechnen Sie K = KDF(m'). Die Wahrscheinlichkeit eines Fehlschlags bei der Entkapselung beträgt < 2^{-139}.

Kyber-768: öffentlicher Schlüssel 1184 Byte, privater Schlüssel 2400 Byte, Chiffretext 1088 Byte, gemeinsames Geheimnis 32 Byte. Zum Vergleich: ECDH-P256: öffentlicher Schlüssel 65 Byte, Chiffretext 32 Byte. Kyber ist etwa 15-mal größer, aber quantensicher. Trotzdem ist es schnell: Kapselung und Entkapselung dauern auf modernen CPUs zusammen weniger als 1 ms.

Die Polynom-Multiplikation in R_q = Z_q[x]/(x^256+1) verwendet die Number Theoretic Transform (NTT) – das Analogon der FFT für modulare Arithmetik. Die NTT reduziert die Komplexität der Polynom-Multiplikation von O(n^2) auf O(n log n). q=3329 wurde gewählt, weil dieser Wert gute NTT-Eigenschaften für n=256 besitzt.

Verwenden Sie während der PQC-Migration einen hybriden Schlüsselaustausch: Kombinieren Sie ECDH und Kyber. Gemeinsames Geheimnis = KDF(ECDH_output || Kyber_output). Für einen erfolgreichen Angriff müssen beide Verfahren gebrochen werden: Klassische Angreifer brechen keines von beiden; Quantenangreifer brechen ECDH, aber nicht Kyber. Entwürfe zu TLS 1.3 (IETF RFC 8446) unterstützen hybride KEMs.

Die Kyber-Entkapselung läuft in naiven Implementierungen nicht in konstanter Zeit ab – der Schritt des Rejection Sampling kann Zeitinformationen preisgeben. Die Referenzimplementierung verwendet eine NTT in konstanter Zeit und einen Vergleich komprimierter Chiffretexte in konstanter Zeit. Verwenden Sie den Referenzcode der NIST-Einreichung oder geprüfte Bibliotheksimplementierungen.

Das NIST veröffentlichte FIPS 203 (ML-KEM) im August 2024. Chrome fügte 2023 Unterstützung für Kyber in TLS 1.3 hinzu. Cloudflare, Google und AWS stellen hybride ECDH+Kyber-Verfahren bereit. OpenSSL 3.x unterstützt inzwischen ML-KEM. Implementierungen für LibSSH und WireGuard befinden sich in Arbeit.

Welches NIST-Standarddokument standardisiert CRYSTALS-Kyber?

Kyber (ML-KEM) ist ein auf Module-LWE basierendes KEM, das ECDH ersetzt. Schlüsselgrößen von etwa 1 KB; schnelle NTT-Arithmetik; quantenresistent. Stellen Sie Kyber während der Migration als Hybrid mit ECDH bereit. Standardisiert in FIPS 203. Als Nächstes: die Signaturschemata CRYSTALS-Dilithium und Falcon.