Anahtarlar
d nasıl bulunur: genişletilmiş Öklid algoritması
Her satır, üstündeki iki satırdan bölmeyle elde edilir. Kalanı 1 olan satırda son sütun d'dir (negatifse φ(n) ekleyin).
| Bölüm | Kalan | e'nin katsayısı |
|---|
Mesaj
Ağ üzerinden gönderilen
| Bit | Kare | m ile çarp |
|---|
Anahtarı kırmak
RSA şifreleme demosu
RSA, herkesin bir mesajı sizin açık anahtarınızla kilitlemesine olanak tanırken onu yalnızca sizin özel anahtarınızla açabilmenizi sağlar. Arkasında birkaç satırlık okul aritmetiği vardır: iki asal sayı, bir çarpma, bir kalan ve akıllıca bir ters. Seçtiğiniz asallardan bir anahtar çifti oluşturun, bir mesajı karakter karakter şifreleyip şifresini çözün, herkesin sizden geldiğini doğrulayabilmesi için imzalayın, ardından saldırganı oynayıp n'yi çarpanlarına ayırarak gerçek anahtarların neden yüzlerce basamak gerektirdiğini görün. İki asal sayı p ve q seçin ya da Yeni asallar'a basın. Uygulama açık anahtar (e, n) ile özel anahtar d'yi oluşturur ve genişletilmiş Öklid algoritmasının d'yi nasıl bulduğunu gösterir. Bir mesaj yazın: her karakter açık anahtarla şifrelenir ve özel anahtarla şifresi çözülür. Ardışık kare almayla hesaplanan kuvveti görmek için bir satıra tıklayın. Bunun yerine özel anahtarla imzalamak için İmzala'ya geçin ve küçük anahtarların ne kadar çabuk kırıldığını görmek için n'yi çarpanlara ayır'a basın.
Nasıl çalışır
- İki asal p ve q girin ya da bir boyut seçip Yeni asallar'a basın; uygulama n, φ(n), e ve d'yi hesaplar ve d'nin nasıl bulunduğunu gösterir.
- Bir mesaj yazın ve Şifrele ya da İmzala'yı seçin. Her karakter bir sayıya dönüştürülür ve mod n'de bir kuvvete yükseltilir; ardışık kare almayı görmek için bir satıra tıklayın.
- Eve'in n'yi iki asalına ayırıp özel anahtarı ele geçirmesi için n'yi çarpanlara ayır'a basın.
Anahtarlar nasıl çalışır
İki asalı çarpın: n = p × q. p = 61 ve q = 53 ile n = 3233 olur. φ(n) = (p − 1)(q − 1) = 3120 sayısı, n'den küçük olup n ile ortak çarpanı olmayan sayıları sayar ve yalnızca p ile q'yu bilen biri tarafından hesaplanabilir. 3120 ile ortak çarpanı olmayan e = 17'yi seçin ve e × d, φ(n)'nin bir katından 1 fazla olacak şekilde d'yi bulun: burada d = 2753, çünkü 17 × 2753 = 46801 = 15 × 3120 + 1. (e, n) çiftini yayımlayın ve d'yi saklayın. Bir m mesajı c = mᵉ mod n olur ve Euler teoremi cᵈ mod n'nin m'yi geri verdiğini garanti eder.
Neden kırılması zor
Bir saldırganın ihtiyaç duyduğu her şey n'nin çarpanlarında saklıdır. n = 3233 ile bu hiçbir koruma sağlamaz: tek bölenleri denemek, yaklaşık iki düzine denemeden sonra 53'ü bulur. Ama gereken çaba n'nin kareköküyle büyür. 2048 bitlik bir modül yaklaşık 617 basamaklıdır ve bilinen hiçbir yöntem, bugün var olan hiçbir bilgisayarda, onu makul bir sürede çarpanlarına ayıramaz. İmzalama RSA'yı tersine çalıştırır: s = mᵈ mod n yalnızca özel anahtarla üretilebilir ve herkes sᵉ mod n'nin m'yi geri verdiğini doğrulayabilir.
Sık sorulan sorular
Neden kimse açık anahtardan d'yi hesaplayamaz?
d'yi bulmak için φ(n) = (p − 1)(q − 1) gerekir, φ(n)'yi elde etmek için de p ve q gerekir. Bunları n'den geri elde etmek n'yi çarpanlarına ayırmak demektir ve yüzlerce basamaklı sayılar için bilinen hızlı bir yöntem yoktur. Demo, oyuncak anahtarları saniyenin çok küçük bir kesrinde çarpanlarına ayırmanıza izin verir; bu da gerçek anahtarların neden bu kadar büyük olduğunu tam olarak gösterir.
Mesaj neden her seferinde bir karakter şifreleniyor?
Çünkü oyuncak anahtarlar küçüktür: RSA yalnızca n'den küçük bir sayıyı şifreleyebilir. n = 3233 ile her karakter kodu sığar, ama bütün bir cümle sığmaz. Gerçek RSA 2048 bit veya daha büyük bir modül kullanır, aynı mesajın asla iki kez aynı şekilde şifrelenmemesi için mesajı rastgele baytlarla doldurur ve pratikte yalnızca AES gibi daha hızlı bir şifre için kısa bir anahtarı şifreler.
Ardışık kare alma ne işe yarar?
m²⁷⁵³ mod n gibi devasa kuvvetleri, devasa sayıyı hiç yazmadan hesaplar. Üssü ikili tabanda yazın, sonra bitlerini sırayla dolaşın: her bit için o ana kadarki sonucun karesini alın ve her 1 için m ile çarpın, her seferinde mod n'ye göre kalanı alın. 2048 bitlik bir üs yalnızca yaklaşık 2048 kare alma gerektirir.
Şifreleme ile imzalama arasındaki fark nedir?
Şifreleme alıcının açık anahtarını kullanır, böylece onu yalnızca alıcının özel anahtarı geri alabilir. İmzalama göndericinin özel anahtarını kullanır, böylece herkes onu göndericinin açık anahtarıyla doğrulayabilir ve mesajın o anahtarın sahibinden geldiğini ve değiştirilmediğini bilir.
Mesajım bir yere gönderiliyor mu?
Hayır. Her şey tarayıcınızda hesaplanır; asallarınız ve mesajınız bu tarayıcının yerel depolamasında kalır.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Editöre Git