CRYSTALS-Kyber: gitterbaserad KEM

CRYSTALS-Kyber (som NIST döpte om till ML-KEM i FIPS 203) är en Key Encapsulation Mechanism (KEM) baserad på Module-LWE. Den ersätter RSA och ECDH vid nyckelutbyte och ger kvantresistens med praktiskt användbara prestanda.

En KEM kapslar in en delad hemlighet: avsändaren genererar en slumpmässig nyckel K och krypterar den med mottagarens publika nyckel (inkapsulering), vilket ger en chiffertext C. Mottagaren dekapsulerar C med sin privata nyckel för att återfå K. Inget interaktivt nyckelutbyte behövs.

Kyber använder Module-LWE över ringen R_q = Z_q[x]/(x^256+1) med q=3329. Dimension k=2 (Kyber-512), k=3 (Kyber-768), k=4 (Kyber-1024). Säkerhetsnivåerna är cirka 128, cirka 192 respektive cirka 256 bitar. k=3 (Kyber-768) är det rekommenderade standardvalet.

Generera matrisen A ∈ R_q^{k×k} från seed ρ (expanderbart). Sampla den hemliga variabeln s och bruset e från en centrerad binomialfördelning (små koefficienter). Publik nyckel: (ρ, t=As+e). Privat nyckel: s. Bruset e är litet men förhindrar att s kan återställas från den publika nyckeln.

För att skicka en delad hemlighet till innehavaren av den publika nyckeln (ρ, t): sampla r, e1, e2 från brusfördelningen. Beräkna u = A^T r + e1, v = t^T r + e2 + round(q/2)*m där m är ett slumpmässigt 256-bitars meddelande. Delad hemlighet K = KDF(m). Chiffertext = (u, v).

Med den privata nyckeln s: beräkna m' = decompress(v - s^T u) = decompress(t^T r + e2 + round(q/2)*m - s^T(A^T r + e1)). Brustermerna tar ungefär ut varandra, så att m'≈m. Beräkna K = KDF(m'). Sannolikheten för dekapsuleringsfel: < 2^{-139}.

Kyber-768: publik nyckel 1184 byte, privat nyckel 2400 byte, chiffertext 1088 byte, delad hemlighet 32 byte. Jämför med ECDH-P256: publik nyckel på 65 byte, chiffertext på 32 byte. Kyber är cirka 15 gånger större men kvantsäkert. Det är fortfarande snabbt: inkapsulering och dekapsulering tar mindre än 1 ms på moderna processorer.

Polynomisk multiplikation i R_q = Z_q[x]/(x^256+1) använder Number Theoretic Transform (NTT) – den modulära aritmetikens motsvarighet till FFT. NTT minskar polynomisk multiplikation från O(n^2) till O(n log n). q=3329 valdes för att ge goda NTT-egenskaper för n=256.

Under migreringen till PQC används ett hybridnyckelutbyte: kombinera ECDH och Kyber. Delad hemlighet = KDF(ECDH_output || Kyber_output). Säkerheten kräver att båda bryts: klassiska angripare bryter inget av dem; kvantangripare bryter ECDH men inte Kyber. TLS 1.3-utkast (IETF RFC 8446) stöder hybrida KEM:er.

Kybers dekapsulering körs inte i konstant tid i naiva implementationer – steget med avvisningssampling läcker tidsinformation. Referensimplementeringen använder en konstanttidsbaserad NTT och jämförelse av komprimerad chiffertext. Använd referenskoden från NIST:s inlämning eller granskade biblioteksimplementationer.

NIST publicerade FIPS 203 (ML-KEM) i augusti 2024. Chrome lade till Kyber-stöd i TLS 1.3 under 2023. Cloudflare, Google och AWS distribuerar hybrida ECDH+Kyber-lösningar. OpenSSL 3.x lade till stöd för ML-KEM. Implementationer för LibSSH och WireGuard är under utveckling.

Kyber (ML-KEM) är en Module-LWE-baserad KEM som ersätter ECDH. Nycklarna är cirka 1 KB stora; NTT-aritmetiken är snabb; algoritmen är kvantresistent. Distribuera den som hybrid med ECDH under migreringen. Standardiserad som FIPS 203. Nästa steg: CRYSTALS-Dilithium och Falcons signaturscheman.