Algoritma Shor & Grover Dijelaskan

Komputer kuantum tidak sekadar menjalankan algoritma klasik dengan lebih cepat — komputer ini memanfaatkan superposisi dan interferensi kuantum untuk menyelesaikan masalah tertentu secara eksponensial lebih cepat. Dua algoritma mengancam sebagian besar kriptografi yang digunakan: Shor (memecahkan RSA/ECC) dan Grover (melemahkan kriptografi simetris/fungsi hash).

Algoritma Shor (1994) menyelesaikan pemfaktoran bilangan bulat dan logaritma diskret dalam waktu polinomial pada komputer kuantum. Algoritma ini secara langsung memecahkan RSA (berbasis pemfaktoran), Diffie-Hellman (logaritma diskret modulo p), serta ECDH/ECDSA (logaritma diskret kurva eliptik).

Komponen utama dalam algoritma Shor adalah Transformasi Fourier Kuantum (QFT) — versi kuantum dari DFT yang jauh lebih cepat secara eksponensial. Untuk pencarian periode, QFT mengidentifikasi periode f(x) = a^x mod N, yang darinya faktor-faktor N diturunkan melalui GCD.

Untuk memfaktorkan N: (1) Pilih a acak dengan a < N, lalu periksa gcd(a,N)=1. (2) Temukan periode r dari f(x)=a^x mod N menggunakan QFT. (3) Dengan probabilitas tinggi, gcd(a^{r/2}±1, N) menghasilkan faktor nontrivial. Langkah klasik memerlukan O(log N); pencarian periode kuantum memerlukan O((log N)^3) — waktu polinomial.

Pemfaktoran klasik terbaik: GNFS — O(exp((64/9 log N)^{1/3} log log N)^{2/3})) subeksponensial. Algoritma Shor pada komputer kuantum yang toleran terhadap kesalahan: O((log N)^3) polinomial. RSA-2048 memerlukan sekitar 4000 qubit logis + sekitar 10^9 operasi gerbang. Komputer NISQ saat ini memiliki sekitar 1000 qubit yang bising — belum menjadi ancaman.

Algoritma Grover (1996) memberikan percepatan kuadratik untuk pencarian tak terstruktur. Untuk ruang pencarian yang terdiri dari N item, algoritma klasik memerlukan O(N) kueri; algoritma Grover memerlukan O(√N). Jika diterapkan pada kriptografi, algoritma ini memecahkan kunci simetris n-bit dalam O(2^{n/2}), bukan O(2^n).

AES-128: keamanan klasik 2^128, dikurangi oleh Grover menjadi 2^64 — tidak aman terhadap komputer kuantum besar. AES-256: 2^256 → 2^128 — masih aman. Solusi: gandakan ukuran kunci simetris. Ketahanan tabrakan SHA-256: 2^128 → 2^85 (serangan ulang tahun+Grover). Pracitra SHA-256: 2^256 → 2^128 — OK.

Komputer kuantum NISQ saat ini (IBM Heron: 133 qubit, Google Sycamore: 70 qubit) terlalu kecil dan terlalu bising untuk komputasi yang relevan bagi kriptografi. Perkiraan pemecahan RSA-2048 adalah pada 2035–2050 dengan komputer kuantum toleran terhadap kesalahan. Serangan kumpulkan-sekarang-dekripsi-nanti merupakan ancaman saat ini.

Penyerang mengumpulkan lalu menyimpan lalu lintas terenkripsi hari ini. Ketika komputer kuantum tersedia, mereka mendekripsinya secara retrospektif. Hal ini membuat rahasia jangka panjang (data pemerintah terklasifikasi, rekam medis) rentan sejak sekarang. Migrasi PQC untuk data semacam itu harus dimulai sekarang.

Masalah kisi (LWE, SIS), masalah berbasis kode (McEliece), tanda tangan berbasis hash (SPHINCS+), serta masalah multivariat — belum memiliki algoritma kuantum waktu polinomial yang diketahui. Semua ini menjadi dasar standar pascakuantum NIST.

Standar PQC NIST (ML-KEM, ML-DSA, SLH-DSA) difinalisasi pada 2024. Organisasi sebaiknya: menginventarisasi penggunaan kriptografi saat ini, mengidentifikasi data berumur panjang, dan memprioritaskan penerapan PQC untuk pertukaran kunci (yang paling mendesak karena serangan kumpulkan-sekarang-dekripsi-nanti). Tanda tangan memiliki lebih banyak waktu.

Apa dampak algoritma Grover terhadap AES-128?

Algoritma Shor (waktu polinomial) memecahkan RSA, DH, dan ECC. Algoritma Grover (percepatan kuadratik) mengurangi separuh kekuatan kunci simetris. Solusi: bermigrasi ke standar PQC NIST (berbasis kisi). Berikutnya: KEM CRYSTALS-Kyber.