CRYSTALS-Kyber: KEM basato su reticoli

CRYSTALS-Kyber (rinominato ML-KEM da NIST in FIPS 203) è un Meccanismo di incapsulamento delle chiavi (KEM) basato su Module-LWE. Sostituisce RSA ed ECDH nello scambio di chiavi, offrendo resistenza ai computer quantistici con prestazioni pratiche.

Un KEM incapsula un segreto condiviso: il mittente genera una chiave casuale K e la cifra con la chiave pubblica del destinatario (incapsulamento), producendo un testo cifrato C. Il destinatario decapsula C con la propria chiave privata per recuperare K. Non è necessario alcuno scambio interattivo di chiavi.

Kyber usa Module-LWE sull'anello R_q = Z_q[x]/(x^256+1) con q=3329. Dimensione k=2 (Kyber-512), k=3 (Kyber-768), k=4 (Kyber-1024). Livello di sicurezza: rispettivamente ~128, ~192, ~256 bit. k=3 (Kyber-768) è il valore predefinito consigliato.

Generi la matrice A ∈ R_q^{k×k} dal seed ρ (espandibile). Campioni il segreto s e il rumore e da una distribuzione binomiale centrata (con coefficienti piccoli). Chiave pubblica: (ρ, t=As+e). Chiave privata: s. Il rumore e è piccolo, ma impedisce di recuperare s dalla chiave pubblica.

Per inviare un segreto condiviso al titolare della chiave pubblica (ρ, t): campioni r, e1, e2 dalla distribuzione del rumore. Calcoli u = A^T r + e1, v = t^T r + e2 + round(q/2)*m, dove m è un messaggio casuale di 256 bit. Segreto condiviso K = KDF(m). Testo cifrato = (u, v).

Con la chiave privata s: calcoli m' = decompress(v - s^T u) = decompress(t^T r + e2 + round(q/2)*m - s^T(A^T r + e1)). I termini di rumore si annullano approssimativamente, lasciando m'≈m. Calcoli K = KDF(m'). Probabilità di errore del decapsulamento: < 2^{-139}.

Kyber-768: chiave pubblica di 1184 byte, chiave privata di 2400 byte, testo cifrato di 1088 byte, segreto condiviso di 32 byte. A confronto, ECDH-P256: chiave pubblica di 65 byte, testo cifrato di 32 byte. Kyber è circa 15 volte più grande, ma è sicuro contro i computer quantistici. È comunque veloce: incapsulamento e decapsulamento richiedono meno di 1 ms sulle CPU moderne.

La moltiplicazione di polinomi in R_q = Z_q[x]/(x^256+1) usa la Number Theoretic Transform (NTT), l'analogo aritmetico modulare della FFT. La NTT riduce la moltiplicazione di polinomi da O(n^2) a O(n log n). q=3329 è stato scelto perché offre buone proprietà NTT per n=256.

Durante la migrazione alla PQC, utilizzi uno scambio ibrido di chiavi: combini ECDH e Kyber. Segreto condiviso = KDF(ECDH_output || Kyber_output). La sicurezza richiede di compromettere entrambi: gli avversari classici non compromettono nessuno dei due; gli avversari quantistici compromettono ECDH ma non Kyber. Le bozze di TLS 1.3 (IETF RFC 8446) supportano KEM ibridi.

Il decapsulamento di Kyber non è a tempo costante nelle implementazioni ingenue: il passaggio di rejection sampling può causare perdite di informazioni sui tempi di esecuzione. L'implementazione di riferimento usa una NTT a tempo costante e il confronto a tempo costante del testo cifrato compresso. Utilizzi il codice di riferimento della submission NIST oppure implementazioni di librerie sottoposte ad audit.

NIST ha pubblicato FIPS 203 (ML-KEM) nell'agosto 2024. Chrome ha aggiunto il supporto a Kyber in TLS 1.3 nel 2023. Cloudflare, Google e AWS stanno distribuendo soluzioni ibride ECDH+Kyber. OpenSSL 3.x ha aggiunto il supporto a ML-KEM. Le implementazioni per LibSSH e WireGuard sono in corso.

Quale documento standard NIST definisce lo standard CRYSTALS-Kyber?

Kyber (ML-KEM) è un KEM basato su Module-LWE che sostituisce ECDH. Chiavi di circa 1 KB; aritmetica NTT veloce; resistenza ai computer quantistici. Durante la migrazione, lo distribuisca in modalità ibrida con ECDH. Standardizzato come FIPS 203. Prossimo argomento: gli schemi di firma CRYSTALS-Dilithium e Falcon.