RSA - Var $e = d$ bir sorun?

Question

Üniversitede küçük RSA projesi üzerinde çalışıyorum. Şu anda bunu yaptım:

1. Seçilen aralıktan bir asal sayı dizisi oluşturulur.
2. $p$ ve $q$ bu diziden rastgele seçilmiş
3. $n$ hesaplandı
4. $\phi(n)$ hesaplandı
5. $e$ hesaplandı
6. $d$ hesaplandı

Ne hakkında düşünüyorsun $e$ ve $d$ bu durumda?

• $p = 29$
• $q = 53$
• $n = 1537$
• $\phi(n) = 1456$
• $e = 545$
• $d = 545$

Answer 1

Bir RSA anahtar oluşturma prosedürünün bitmesi için oldukça büyük bir olasılık olsaydı felaket olurdu $e=d$, çünkü bu durumda, genel anahtar, güvenlik açısından gizli olması gereken özel anahtarı ortaya çıkarır.

Fakat $e=d$ anahtar oluşturma prosedürünün 1. ve 2. adımlarında yatan daha büyük bir sorunun belirtisidir: RSA yalnızca $p$ ve $q$ faktoring olacak şekilde seçilir $n$ zordur ve bu demektir ki $p$ ve $q$büyük asal olmalıdır. Modern taban çizgisi$n$ nın-nin $2048$ bitler, yani $617$ ondalık basamaklar, değil $4$Ondalık basamak. Bunun için,$p$ ve $q$ yaklaşık olarak büyük bir asal alt kümesi arasından rastgele seçilir $309$rakamlar. Hakkında bitti$10^{305}$böylesi asal sayılar, böylece bunların hepsini üretir, sonra bunun içinde toplama olanaksızdır. Doğru prosedür, doğrudan$p$ ve $q$.

İle $p$ ve $q$ rastgele asallar bu kadar büyük ve rastgele bir seçim $e$ öyle ki $\gcd(e,\phi(n))=1$ (veya rastgele asal seçimi $p$ ve $q$ tek bağımlılıkla $e$ o $\gcd(e,p-1)=1$ ve $\gcd(e,q-1)=1$yaygın bir uygulama olduğu gibi), son derece olasılık dışı $d=e$veya daha genel olarak, bir veya birkaç yeniden şifreleme, şifre çözmeye yol açar. Bisiklete binme saldırısıyla ilgili şu soruları görün .

---

FIPS 186-4 ek B.3'te RSA anahtar oluşturma prosedürleri bulunmaktadır . Önerileni yoksayın$1024$-kullanılmayan bit anahtar boyutu. Önerilen$2048$ temeldir, $3072$ giderek yaygınlaşan $4096$mantıksız değil bit. Bu prosedürler, soruda kullanılanlardan birkaç noktadan farklıdır:

• Büyük asal üretimi $p$ ve $q$ önceden tahmin edilemeyen bir aralıkta $[2^{(k-1)/2},2^{k/2}]$, nerede $k$ istenen bit boyutudur $n$ (Örneğin $3072$)
• Garip $e$ ile $2^{16}<e<2^{256}$ (düşük RSA dolgu seçimlerine karşı bir koruma görevi gördüğü için daha düşük, birlikte çalışabilirlik için daha yüksek ve diğer bazı kötü seçimleri imkansız hale getirme)
• Kullanma $d=e^{-1}\bmod\lambda(n)$ (nerede $\lambda$olan Carmichael fonksiyonu ) yerine$d=e^{-1}\bmod\phi(n)$. Her ikisi de matematiksel olarak iyi, ancak$\lambda$ en küçük pozitif özel üssü üreten sigortalar $d$ verilen için çalışmak $(n,e)$.
• Minimum boyut gerektirir $d$ (çok daha büyük $2^{256}$, tesadüfen sigortalayan $d>e$), matematiksel zorunluluktan çok, hatalara karşı bir koruma olarak.