CRYSTALS-Kyber: KEM Berbasis Kisi

CRYSTALS-Kyber (berganti nama menjadi ML-KEM oleh NIST dalam FIPS 203) adalah Mekanisme Enkapsulasi Kunci (KEM) yang berbasis Module-LWE. Algoritma ini menggantikan RSA dan ECDH untuk pertukaran kunci, serta memberikan ketahanan terhadap kuantum dengan tingkat kinerja yang praktis.

KEM melakukan enkapsulasi rahasia bersama: pengirim menghasilkan kunci acak K, mengenkripsinya dengan kunci publik penerima (enkapsulasi), lalu menghasilkan teks sandi C. Penerima melakukan dekapsulasi terhadap C dengan kunci privatnya untuk memulihkan K. Pertukaran kunci interaktif tidak diperlukan.

Kyber menggunakan Module-LWE pada gelang R_q = Z_q[x]/(x^256+1) dengan q=3329. Dimensi k=2 (Kyber-512), k=3 (Kyber-768), k=4 (Kyber-1024). Tingkat keamanan masing-masing sekitar 128, 192, dan 256 bit. k=3 (Kyber-768) merupakan bawaan yang disarankan.

Hasilkan matriks A ∈ R_q^{k×k} dari benih ρ (dapat diperluas). Ambil sampel rahasia s dan derau e dari distribusi binomial berpusat (koefisien kecil). Kunci publik: (ρ, t=As+e). Kunci privat: s. Derau e berukuran kecil, tetapi mencegah pemulihan s dari kunci publik.

Untuk mengirim rahasia bersama kepada pemilik kunci publik (ρ, t): ambil sampel r, e1, e2 dari distribusi derau. Hitung u = A^T r + e1, v = t^T r + e2 + round(q/2)*m, dengan m sebagai pesan acak 256-bit. Rahasia bersama K = KDF(m). Teks sandi = (u, v).

Dengan kunci privat s: hitung m' = decompress(v - s^T u) = decompress(t^T r + e2 + round(q/2)*m - s^T(A^T r + e1)). Suku-suku derau saling meniadakan secara mendekati sehingga tersisa m'≈m. Hitung K = KDF(m'). Probabilitas kegagalan dekapsulasi: < 2^{-139}.

Kyber-768: kunci publik 1184 bita, kunci privat 2400 bita, teks sandi 1088 bita, rahasia bersama 32 bita. Bandingkan dengan ECDH-P256: kunci publik 65 bita, teks sandi 32 bita. Kyber sekitar 15 kali lebih besar, tetapi aman terhadap kuantum. Tetap cepat: enkapsulasi+dekapsulasi < 1 md pada CPU modern.

Perkalian polinomial dalam R_q = Z_q[x]/(x^256+1) menggunakan Transformasi Teoretis Bilangan (NTT) — analog aritmetika modular dari FFT. NTT mengurangi kompleksitas perkalian polinomial dari O(n^2) menjadi O(n log n). q=3329 dipilih karena memiliki sifat NTT yang baik untuk n=256.

Selama migrasi PQC, gunakan pertukaran kunci hibrida: gabungkan ECDH dan Kyber. Rahasia bersama = KDF(ECDH_output || Kyber_output). Keamanan memerlukan pemecahan keduanya: penyerang klasik tidak dapat memecahkan salah satunya; penyerang kuantum dapat memecahkan ECDH tetapi tidak Kyber. Draf TLS 1.3 (IETF RFC 8446) mendukung KEM hibrida.

Dekapsulasi Kyber tidak berjalan dalam waktu-konstan pada implementasi naif — langkah pengambilan sampel dengan penolakan membocorkan informasi pewaktuan. Implementasi rujukan menggunakan NTT waktu-konstan dan perbandingan teks sandi terkompresi. Gunakan kode rujukan dari pengajuan NIST atau implementasi pustaka yang telah diaudit.

NIST menerbitkan FIPS 203 (ML-KEM) pada Agustus 2024. Chrome menambahkan dukungan Kyber dalam TLS 1.3 pada 2023. Cloudflare, Google, dan AWS menerapkan ECDH+Kyber hibrida. OpenSSL 3.x menambahkan dukungan ML-KEM. Implementasi LibSSH dan WireGuard sedang dikerjakan.

Dokumen standar NIST apa yang menstandardisasi CRYSTALS-Kyber?

Kyber (ML-KEM) adalah KEM berbasis Module-LWE yang menggantikan ECDH. Ukuran kunci sekitar 1 KB; aritmetika NTT cepat; tahan terhadap kuantum. Terapkan sebagai hibrida dengan ECDH selama migrasi. Distandardisasi sebagai FIPS 203. Berikutnya: skema tanda tangan CRYSTALS-Dilithium dan Falcon.