Shor ve Grover Algoritmaları Açıklanıyor

Kuantum bilgisayarlar yalnızca klasik algoritmaları daha hızlı çalıştırmaz; belirli problemleri üstel olarak daha hızlı çözmek için kuantum süperpozisyonundan ve girişiminden yararlanır. Kullanımdaki kriptografinin çoğunu tehdit eden iki algoritma vardır: Shor algoritması (RSA/ECC'yi kırar) ve Grover algoritması (simetrik algoritmaları/özetleri zayıflatır).

Shor algoritması (1994), bir kuantum bilgisayarında tamsayıları çarpanlara ayırma ve ayrık logaritma problemlerini polinom zamanda çözer. Bu durum RSA'yı (çarpanlara ayırmaya dayanır), Diffie-Hellman'ı (p modunda ayrık logaritmaya dayanır) ve ECDH/ECDSA'yı (eliptik eğri ayrık logaritmasına dayanır) doğrudan kırar.

Shor algoritmasının temel bileşeni, DFT'nin üstel olarak daha hızlı kuantum sürümü olan Kuantum Fourier Dönüşümüdür (QFT). Periyot bulma işleminde QFT, f(x) = a^x mod N fonksiyonunun periyodunu belirler; N'nin çarpanları da buradan GCD aracılığıyla elde edilir.

N'yi çarpanlara ayırmak için: (1) N'den küçük rastgele bir a seçin ve gcd(a,N)=1 olduğunu denetleyin. (2) QFT kullanarak f(x)=a^x mod N fonksiyonunun r periyodunu bulun. (3) Yüksek olasılıkla gcd(a^{r/2}±1, N), önemsiz olmayan bir çarpan verir. Klasik adım O(log N); kuantum periyot bulma işlemi O((log N)^3) — polinom zamandadır.

Klasik çarpanlara ayırmada en iyi yöntem: GNFS — alt üstel O(exp((64/9 log N)^{1/3} log log N)^{2/3})). Hata toleranslı bir kuantum bilgisayarında Shor algoritması: polinom zamanlı O((log N)^3). RSA-2048 için yaklaşık 4000 mantıksal kübit ve yaklaşık 10^9 kapı işlemi gerekir. Günümüzün NISQ bilgisayarlarında yaklaşık 1000 gürültülü kübit bulunur; dolayısıyla henüz tehdit oluşturmamaktadırlar.

Grover algoritması (1996), yapısal olmayan aramalarda karesel hızlanma sağlar. N öğeden oluşan bir arama uzayı için klasik algoritmalar O(N) sorguya ihtiyaç duyar; Grover algoritması ise O(√N) sorgu gerektirir. Kriptografiye uygulandığında, n bitlik simetrik anahtarları O(2^{n/2}) zamanda kırar; klasik yöntemde bu süre O(2^n)'dir.

AES-128: klasik güvenlik düzeyi 2^128'dir; Grover algoritması bunu 2^64'e düşürür ve büyük bir kuantum bilgisayarına karşı güvensiz hâle getirir. AES-256: 2^256 → 2^128 — hâlâ güvenlidir. Çözüm: simetrik anahtar boyutlarını iki katına çıkarın. SHA-256 çakışma direnci: 2^128 → 2^85 (doğum günü paradoksu + Grover). SHA-256 ön görüntü direnci: 2^256 → 2^128 — OK.

Günümüzün NISQ kuantum bilgisayarları (IBM Heron: 133 kübit, Google Sycamore: 70 kübit), kriptografik açıdan anlamlı hesaplamalar için çok küçük ve çok gürültülüdür. RSA-2048'in kırılmasına ilişkin tahminler, hata toleranslı kuantum bilgisayarları için 2035-2050 aralığındadır. Şimdi topla, sonra şifresini çöz saldırıları güncel bir tehdittir.

Saldırganlar bugün şifrelenmiş trafiği toplar ve saklar. Bir kuantum bilgisayarı kullanılabilir hâle geldiğinde bu trafiğin şifresini geriye dönük olarak çözerler. Bu nedenle uzun süre geçerli sırlar (gizli hükümet verileri, tıbbi kayıtlar) bugün savunmasızdır. Bu tür veriler için PQC geçişi hemen başlatılmalıdır.

Kafes problemleri (LWE, SIS), kod tabanlı problemler (McEliece), özet tabanlı imzalar (SPHINCS+), çok değişkenli problemler — bilinen hiçbir polinom zamanlı kuantum algoritması bunları çözememektedir. Bunlar, NIST'in kuantum sonrası standartlarının temelini oluşturur.

NIST PQC standartları (ML-KEM, ML-DSA, SLH-DSA) 2024'te kesinleştirildi. Kuruluşlar şunları yapmalıdır: mevcut kriptografi kullanımını envanterleyin, uzun süre geçerli verileri belirleyin ve anahtar değişimi için PQC kullanımına öncelik verin (şimdi topla, sonra şifresini çöz saldırıları nedeniyle en acil konu budur). İmzalar için daha fazla zaman vardır.

Grover algoritmasının AES-128 üzerindeki etkisi nedir?

Shor algoritması (polinom zamanlı) RSA'yı, DH'yi ve ECC'yi kırar. Grover algoritması (karesel hızlanma) simetrik anahtarların gücünü yarıya indirir. Çözüm: NIST PQC standartlarına (kafes tabanlı) geçiş yapın. Sırada: CRYSTALS-Kyber KEM.