RSA ve Tam Sayı Çarpanlara Ayırma
RSA, güvenliği iki büyük asal sayının çarpımını çarpanlara ayırmanın zorluğuna dayanan, şifreleme ve dijital imzalar sağlayan en yaygın bilinen açık anahtarlı şifreleme sistemidir.
Tanım
RSA, genel bir modül n'nin iki gizli asal sayının çarpımı olduğu bir açık anahtarlı şifreleme sistemidir; şifreleme, mesajı genel bir üs ile n modülüne göre yükseltir ve şifre çözme, yalnızca n'nin çarpanlara ayrılmasından türetilebilen özel bir üs kullanır.
Kapsam
Bu konu, RSA algoritmasını — anahtar üretimi, şifreleme, şifre çözme ve modüler üs alma yoluyla imzalama — yanı sıra dayandığı tam sayı çarpanlara ayırma problemini, onu tehdit eden çarpanlara ayırma algoritmalarını ve pratik uygulamada ders kitabı RSA'yı güvenli kılan dolgu şemalarını (OAEP, PSS) kapsamaktadır. Anahtar boyutu önerilerini ve zamanlama ve hata saldırıları gibi uygulama saldırılarını ele almaktadır. Ayrık logaritma tabanlı şemaları ve eliptik eğri kriptografisini hariç tutar; bunlar ayrı olarak ele alınmaktadır.
Temel sorular
- RSA genel ve özel üsleri, modüler aritmetiğin yapısından nasıl ortaya çıkmaktadır?
- RSA'nın güvenliği neden modülün çarpanlara ayrılmasının zorluğuna bağlıdır?
- Büyük tam sayılar ne kadar hızlı çarpanlara ayrılabilir ve bu, anahtar boyutları için ne anlama gelmektedir?
- Ders kitabı RSA neden güvensizdir ve OAEP ve PSS gibi dolgu şemaları bunu nasıl düzeltmektedir?
- Uygulama düzeyindeki hangi saldırılar (zamanlama, hata, zayıf rastgelelik) RSA'yı pratikte tehdit etmektedir?
Anahtar kavramlar
- modüler üs alma
- genel ve özel üsler
- Euler'in totient ve Carmichael fonksiyonu
- çarpanlara ayırma problemi
- genel sayı alanı eleği
- OAEP dolgusu
- PSS imza dolgusu
- anahtar boyutu ve güvenlik seviyesi
Temel kuramlar
- RSA tuzak kapısı permütasyonu
- RSA, bir tuzak kapısı tek yönlü permütasyon tanımlar: genel üs ile n modülüne göre yükseltmek kolaydır, ancak bunu tersine çevirmek, yalnızca n'nin asal çarpanlara ayrılmasından hesaplanabilen özel üssü gerektirir — yani tuzak kapısını.
- Çarpanlara ayırma varsayımı ve anahtar boyutu
- RSA'nın pratik güvenliği, en iyi çarpanlara ayırma algoritmalarını (şu anda modül uzunluğunda subeksponansiyel olan genel sayı alanı eleği) takip eder; bunlara direnmek, modern RSA'nın neden 2048-bit veya daha büyük modüller kullanmasının nedenidir.
Mekanizmalar
Anahtar üretimi, iki büyük rastgele asal sayı p ve q seçer, n = p*q olarak ayarlar, (p-1)(q-1) ile aralarında asal bir genel üs e seçer ve özel üs d'yi e'nin modüler tersi olarak hesaplar. Şifreleme c = m^e mod n'yi hesaplar; şifre çözme m = c^d mod n'yi geri getirir. Doğruluk Euler teoremini takip eder. Güvenli dağıtım, şifreleme için düz metni OAEP dolgusu ile sarar ve imzalar için PSS kullanır, çünkü ham 'ders kitabı' RSA esnek ve deterministiktir.
Klinik önem
RSA, onlarca yıldır kullanılan altyapıyı güvence altına almaktadır: TLS sunucu sertifikaları, kod imzalama, SSH anahtarları, PGP/S-MIME e-postaları, akıllı kartlar ve belge imzalama. Eliptik eğri şemaları, daha küçük anahtarlar nedeniyle yeni sistemler için giderek daha fazla tercih edilse de, RSA sertifikalarda ve eski protokollerde yaygınlığını korumaktadır ve onu anlamak, gerçek dünyadaki kriptografik riski değerlendirmek için elzemdir.
Kanıt ve kılavuzlar
RSA, OAEP ve PSS'yi belirten PKCS #1 (RFC 8017) ile standartlaştırılmıştır. NIST (SP 800-57), daha yüksek güvenlik seviyeleri için 3072-bit ile minimum 2048-bit modül önermektedir. Önemli başarısızlıklar (Debian zayıf anahtar hatası, Infineon anahtar üretimindeki ROCA kusuru ve FREAK'in 512-bit ihracat RSA'ya düşürülmesi) doğru anahtar üretimi ve parametre boyutlarının önemini vurgulamaktadır.
Tarihçe
RSA, 1977-1978 yıllarında MIT'de Rivest, Shamir ve Adleman tarafından yayımlanmıştır; bu, Diffie ve Hellman tarafından önerilen açık anahtar kavramının ilk pratik gerçekleşmesidir. (Clifford Cocks, 1973'te GCHQ'da gizlice eşdeğer bir şema keşfetmişti.) Çarpanlara ayırmadaki gelişmeler — 1980'ler-1990'larda kuadratik elek ve ardından sayı alanı eleği — güvenli anahtar boyutunu kademeli olarak artırmış ve RSA Çarpanlara Ayırma Yarışmaları pratik ilerlemeyi takip etmiştir.
Öne çıkan isimler
- Ronald Rivest
- Adi Shamir
- Leonard Adleman
- Carl Pomerance
- Arjen Lenstra
İlgili konular
Temel eserler
- rivest1978
- katz2020
- menezes1996
Sıkça sorulan sorular
- RSA bozuldu mu?
- Yeterince büyük bir modül (2048 bit veya daha fazla) ile düzgün bir şekilde uygulanan RSA'yı hiçbir klasik saldırı bozmamaktadır. Gerçek dünyadaki RSA başarısızlıkları, algoritmanın kendisinin bozulmasından değil, çok küçük anahtarlardan, zayıf rastgele sayı üretiminden veya eksik/yanlış dolgudan kaynaklanmaktadır. Ancak, büyük bir kuantum bilgisayar, Shor algoritması aracılığıyla RSA'yı bozacaktır.
- Neden doğrudan RSA fonksiyonuyla şifreleme yapamıyorum?
- Ham 'ders kitabı' RSA deterministik ve esnektir, bilgi sızdırır ve şifreli metin manipülasyonuna izin verir. Güvenli kullanım, şifreleme için OAEP ve imzalar için PSS gibi rastgele dolgu gerektirir, bu nedenle standartlar bu şemaları zorunlu kılmaktadır.