RSA açıklaması
Bir tarayıcı her asma kilit gösterdiğinde, bir mesaj imzalandığında ya da bir yazılım bir güncellemeyi doğruladığında açık anahtarlı kriptografi iş başındadır ve RSA onun en bilinen biçimidir. Fikri şudur: bir mesajı kilitleyen anahtar yayımlanabilirken onu açan anahtar gizli kalır. Dikkat çekici biçimde, bütün sistem okulda öğretilen aritmetiğe dayanır: asal sayılar, çarpma ve kalanlar.
RSA'nın çözdüğü problem
Sezar'ın kaydırma şifresinden modern AES'e kadar geleneksel şifreler kilitlemek ve açmak için aynı anahtarı kullanır; bu yüzden iki tarafın önce gizli bir anahtarı baş başa paylaşması gerekir. Açık anahtarlı kriptografi bu adımı ortadan kaldırır. Her kişinin iki anahtarı vardır: herkesin ona mesaj şifrelemek için kullanabileceği bir açık anahtar ve yalnızca kendisinde bulunan, şifreyi tek başına çözebilen bir özel anahtar. Whitfield Diffie ve Martin Hellman fikri 1976'da tanımladı; bir yıl sonra MIT'den Ron Rivest, Adi Shamir ve Leonard Adleman bunu gerçekleştirmenin bir yolunu buldu ve yöntem, adlarının baş harflerinden dolayı RSA olarak adlandırıldı.
Anahtarları oluşturmak
İki büyük asal, p ve q seçin ve bunları çarpın: n = p × q. n'den küçük olup n ile ortak çarpanı olmayan sayıları sayan Euler totient fonksiyonunu, φ(n) = (p − 1)(q − 1), hesaplayın. φ(n) ile ortak çarpanı olmayan bir açık üs e seçin; olağan seçim 65537'dir. Ardından e × d, φ(n)'ye bölündüğünde 1 kalanını verecek şekilde özel üs d'yi bulun. Genişletilmiş Öklid algoritması bunu hızla yapar. Açık anahtar (e, n) çiftidir; özel anahtar d'dir. p = 61 ve q = 53 ile bu, n = 3233, φ(n) = 3120, e = 17 ve d = 2753 verir.
Şifreleme ve şifre çözme
Bir mesaj önce n'den küçük bir m sayısına dönüştürülür. Onu şifrelemek için c = mᵉ mod n, yani mᵉ'nin n'ye bölümünden kalan hesaplanır. Şifreyi çözmek için cᵈ mod n hesaplanır. Euler teoremi bunun m'yi geri verdiğini garanti eder, çünkü e × d, φ(n)'nin bir katından bir fazladır. Yukarıdaki anahtarlarla kodu 65 olan A harfi 65¹⁷ mod 3233 = 2790 olur ve 2790²⁷⁵³ mod 3233 yeniden 65'tir. Bu kadar büyük kuvvetler asla tam olarak yazılmaz: ardışık kare alma onları üssün her biti için bir kare alma yaparak ve her adımda kalanı alarak hesaplar.
Dijital imzalar
RSA tersine de çalışır. Bir mesajı özel üsse yükseltmek, s = mᵈ mod n, yalnızca anahtarın sahibinin üretebileceği bir imza ortaya çıkarır. Herkes onu açık anahtarla doğrulayabilir: sᵉ mod n m'yi geri veriyorsa mesaj d'nin sahibinden gelmiştir ve yolda değiştirilmemiştir. Pratikte imzalanan, mesajın kendisi değil, mesajın kısa bir özetidir (hash). Bu tür imzalar yazılım güncellemelerini, güvenli web sitelerini ve elektronik belgeleri korur.
Neden güvenli
Herkes n ve e'yi görebilir. d'yi bulmak için saldırganın φ(n)'ye, φ(n)'yi bulmak için de p ve q'ya ihtiyacı vardır; yani RSA'yı kırmak n'yi çarpanlarına ayırmaya indirgenir. İki asalı çarpmak bir bilgisayar için bir mikrosaniyenin küçük bir kesri kadar sürer; çarpımı yeniden onlara ayırmanın ise son derece zor olduğuna inanılır. Şimdiye kadar çarpanlarına ayrılmış en büyük RSA meydan okuma sayısı olan, 2020'deki RSA-250, 829 bittir ve yaklaşık 2700 yıllık bilgisayar zamanı gerektirmiştir. Bugün kullanılan anahtarlar en az 2048 bit, yani yaklaşık 617 basamaktır.
İki kez keşfedilen bir sır
RSA'dan dört yıl önce, 1973'te İngiliz matematikçi Clifford Cocks, istihbarat kurumu GCHQ'da çalışırken meslektaşı James Ellis'in bir fikrinden yola çıkarak aynı şemayı buldu. Çalışma gizli tutuldu ve ancak 1997'de kamuoyuna açıklandı. RSA'nın kendisi 1983'te Amerika Birleşik Devletleri'nde patentlendi; patent, algoritmanın kamu malı olarak serbest bırakılmasından iki hafta sonra, Eylül 2000'de sona erdi.
Uygulamada RSA
Gerçek RSA metni asla doğrudan şifrelemez. Mesaj, aynı mesajın her seferinde farklı şifrelenmesi ve desenlerin sızmaması için OAEP gibi bir şemayla rastgele baytlarla doldurulur. RSA yavaş olduğundan çoğunlukla AES gibi hızlı bir simetrik şifre için kısa bir anahtarı değiş tokuş etmek veya korumak ya da imzalamak için kullanılır. Yeterince büyük kuantum bilgisayarlar, 1994 tarihli Shor algoritmasıyla n'yi hızla çarpanlarına ayırabilir; bu yüzden RSA'nın yanında yeni kuantum sonrası yöntemler devreye alınıyor.
Keşfedin
Kendi asallarınızdan ya da 2 ile 8 basamak arası rastgele asallardan anahtarlar oluşturmak, genişletilmiş Öklid algoritmasının d'yi satır satır buluşunu görmek, bir mesajı karakter karakter şifrelemek ya da imzalamak ve herhangi bir karakter için ardışık kare almayı izlemek için RSA şifreleme demosunu açın. Ardından Eve'in n'yi çarpanlarına ayırmasına izin verin ve ihtiyaç duyduğu sürenin asalların boyutuyla nasıl büyüdüğünü izleyin.
Sık sorulan sorular
RSA neden asal sayılara ihtiyaç duyar?
Çünkü φ(n), ancak n'nin asallara nasıl ayrıldığını bildiğinizde kolayca hesaplanır. p ve q asal olmak üzere n = p × q için φ(n) = (p − 1)(q − 1). Asallar ayrıca n'yi, büyüklüğüne göre çarpanlarına ayrılması olabildiğince zor bir sayı yapar, çünkü hiç küçük çarpanı yoktur.
e neden çoğu zaman 65537'dir?
65537 = 2¹⁶ + 1 asaldır ve ikili tabanda yalnızca iki tane 1 içerir; bu yüzden onunla şifrelemek yalnızca 16 kare alma ve bir çarpma gerektirir. Ayrıca 3 gibi çok küçük üslerin zayıflıklarından kaçınacak kadar büyüktür.
RSA ile Diffie–Hellman arasındaki fark nedir?
Diffie–Hellman iki kişinin açık bir kanal üzerinden ortak bir gizli anahtarda anlaşmasını sağlar; kendi başına hiçbir şeyi şifrelemez veya imzalamaz. RSA bir anahtar çiftiyle doğrudan şifreler ve imzalar. İkisi de bir yönde kolay, diğer yönde zor olan problemlere dayanır: RSA için çarpanlara ayırma, Diffie–Hellman için ayrık logaritma.
Demonun anahtarları gerçek şifreleme için kullanılabilir mi?
Hayır. Asalları en fazla on iki basamaklıdır, bu yüzden ürettiği herhangi bir anahtar saniyeler içinde ya da daha kısa sürede çarpanlarına ayrılabilir ve her karakteri dolgu olmadan tek başına şifreler. RSA'nın nasıl çalıştığını görmek için tasarlanmıştır, bir şeyi korumak için değil.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
RSA şifreleme demosunu açın