CRYSTALS-Kyber: KEM oparty na kratach

CRYSTALS-Kyber (przemianowany przez NIST na ML-KEM w dokumencie FIPS 203) to mechanizm enkapsulacji klucza (KEM) oparty na Module-LWE. Zastępuje RSA i ECDH podczas wymiany kluczy, zapewniając odporność na obliczenia kwantowe przy praktycznej wydajności.

KEM enkapsuluje wspólny sekret: nadawca generuje losowy klucz K i szyfruje go kluczem publicznym odbiorcy (enkapsulacja), uzyskując szyfrogram C. Odbiorca dekapsuluje C swoim kluczem prywatnym, aby odzyskać K. Interaktywna wymiana klucza nie jest potrzebna.

Kyber wykorzystuje Module-LWE nad pierścieniem R_q = Z_q[x]/(x^256+1), gdzie q=3329. Wymiar k=2 (Kyber-512), k=3 (Kyber-768), k=4 (Kyber-1024). Poziom bezpieczeństwa wynosi odpowiednio ~128, ~192 i ~256 bitów. k=3 (Kyber-768) jest zalecaną wartością domyślną.

Należy wygenerować macierz A ∈ R_q^{k×k} na podstawie ziarna ρ (rozwijalnego). Następnie należy wylosować sekret s i szum e z centrowanego rozkładu dwumianowego (małe współczynniki). Klucz publiczny: (ρ, t=As+e). Klucz prywatny: s. Szum e jest mały, ale uniemożliwia odzyskanie s na podstawie klucza publicznego.

Aby wysłać wspólny sekret posiadaczowi klucza publicznego (ρ, t), należy wylosować r, e1, e2 z rozkładu szumu. Następnie należy obliczyć u = A^T r + e1, v = t^T r + e2 + round(q/2)*m, gdzie m jest losową wiadomością 256-bitową. Wspólny sekret K = KDF(m). Szyfrogram = (u, v).

Mając klucz prywatny s, należy obliczyć m' = decompress(v - s^T u) = decompress(t^T r + e2 + round(q/2)*m - s^T(A^T r + e1)). Składniki szumu w przybliżeniu się znoszą, pozostawiając m'≈m. Następnie należy obliczyć K = KDF(m'). Prawdopodobieństwo niepowodzenia dekapsulacji: < 2^{-139}.

Kyber-768: klucz publiczny 1184 bajty, klucz prywatny 2400 bajtów, szyfrogram 1088 bajtów, wspólny sekret 32 bajty. Dla porównania ECDH-P256: klucz publiczny 65 bajtów, szyfrogram 32 bajty. Kyber jest około 15 razy większy, ale odporny na ataki kwantowe. Nadal działa szybko: enkapsulacja i dekapsulacja trwają poniżej 1 ms na nowoczesnych procesorach.

Mnożenie wielomianów w R_q = Z_q[x]/(x^256+1) wykorzystuje transformatę teoretyczno-liczbową (NTT) — modularny odpowiednik FFT. NTT zmniejsza złożoność mnożenia wielomianów z O(n^2) do O(n log n). Wartość q=3329 wybrano ze względu na dobre właściwości NTT dla n=256.

Podczas migracji do PQC należy stosować hybrydową wymianę klucza: połączyć ECDH i Kyber. Wspólny sekret = KDF(ECDH_output || Kyber_output). Bezpieczeństwo wymaga złamania obu mechanizmów: przeciwnicy klasyczni nie łamią żadnego z nich, a przeciwnicy kwantowi łamią ECDH, ale nie Kyber. Szkice TLS 1.3 (IETF RFC 8446) obsługują hybrydowe KEM-y.

Dekapsulacja Kybera nie ma stałego czasu wykonania w naiwnych implementacjach — etap próbkowania z odrzucaniem ujawnia informacje poprzez czas wykonania. Implementacja referencyjna wykorzystuje stałoczasowe NTT i porównanie skompresowanego szyfrogramu. Należy używać kodu referencyjnego z dokumentu zgłoszeniowego NIST lub poddanych audytowi implementacji bibliotek.

NIST opublikował FIPS 203 (ML-KEM) w sierpniu 2024 roku. Chrome dodał obsługę Kybera w TLS 1.3 w 2023 roku. Cloudflare, Google i AWS wdrażają hybrydowe ECDH+Kyber. OpenSSL 3.x dodał obsługę ML-KEM. Implementacje LibSSH i WireGuard są w trakcie tworzenia.

Kyber (ML-KEM) to KEM oparty na Module-LWE, zastępujący ECDH. Rozmiary kluczy wynoszą około 1 KB; szybka arytmetyka NTT; odporność na obliczenia kwantowe. Podczas migracji należy wdrażać go hybrydowo z ECDH. Standaryzowany jako FIPS 203. Dalej: schematy podpisu CRYSTALS-Dilithium i Falcon.