RSA - jest $e = d$ problem?

Question

Pracuję nad małym projektem RSA na uniwersytecie. W tej chwili zrobiłem to:

1. Tablica liczb pierwszych jest generowana z wybranego zakresu.
2. $p$ i $q$ wybrane losowo z tej tablicy
3. $n$ obliczony
4. $\phi(n)$ obliczony
5. $e$ obliczony
6. $d$ obliczony

Co myślisz o $e$ i $d$ w tym wypadku?

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

Answer 1

Byłoby katastrofalne, gdyby procedura generowania klucza RSA miała spore prawdopodobieństwo zakończenia $e=d$, ponieważ w tym przypadku klucz publiczny ujawnia klucz prywatny, który musi być tajny z punktu widzenia bezpieczeństwa.

Ale $e=d$ jest symptomem większego problemu leżącego w krokach 1 i 2 procedury generowania klucza: RSA może być bezpieczny tylko wtedy, gdy $p$ i $q$ są dobierane w taki sposób, że faktoring $n$ jest trudne, a to oznacza $p$ i $q$powinny być dużymi liczbami pierwszymi. Nowoczesna podstawa to$n$ z $2048$ to znaczy bity $617$ cyfry dziesiętne, nie $4$cyfry dziesiętne. Dla tego,$p$ i $q$ są wybierane losowo spośród pokaźnego podzbioru liczb pierwszych około $309$cyfry. Jest ich ponad$10^{305}$takie liczby pierwsze, generując je wszystkie, a następnie wybieranie wewnątrz tego, co jest niewykonalne. Właściwa procedura to bezpośrednie generowanie$p$ i $q$.

Z $p$ i $q$ losowe liczby pierwsze tak duże i losowy wybór $e$ takie że $\gcd(e,\phi(n))=1$ (lub losowy wybór liczb pierwszych $p$ i $q$ z jedyną zależnością od $e$ że $\gcd(e,p-1)=1$ i $\gcd(e,q-1)=1$, co jest powszechną praktyką), jest to nieskończenie mało prawdopodobne $d=e$lub bardziej ogólnie, że jedno lub kilka ponownego szyfrowania prowadzi do odszyfrowania. Zobacz te pytania dotyczące ataku rowerowego .

---

Istnieją procedury generowania klucza RSA w FIPS 186-4 dodatek B.3 . Zignoruj ​​proponowane$1024$-bitowy rozmiar klucza, który jest przestarzały. Zaproponowany$2048$ jest linią bazową, $3072$ coraz częściej, rozszerzając się na $4096$-bit nie jest nierozsądne. Procedury te różnią się od zastosowanych w pytaniu kilkoma punktami, w tym:

• Generowanie dużych liczb pierwszych $p$ i $q$ nieprzewidywalnie w wyznaczonych odstępach czasu $[2^{(k-1)/2},2^{k/2}]$, gdzie $k$ to żądany rozmiar bitu $n$ (na przykład $3072$)
• Wymagające dziwne $e$ z $2^{16}<e<2^{256}$ (im niższy, ponieważ działa jako zabezpieczenie przed złym wyborem wypełnienia RSA, tym wyższy dla interoperacyjności i uniemożliwiający inne złe wybory)
• Za pomocą $d=e^{-1}\bmod\lambda(n)$ (gdzie $\lambda$jest funkcją Carmichaela ), a nie$d=e^{-1}\bmod\phi(n)$. Oba są matematycznie dobre, ale używają$\lambda$ zapewnia generowanie najmniejszego dodatniego wykładnika prywatnego $d$ praca dla danego $(n,e)$.
• Wymaganie minimalnego rozmiaru $d$ (znacznie większy niż $2^{256}$, który incydentalnie ubezpiecza $d>e$), bardziej jako zabezpieczenie przed błędami niż z matematycznej konieczności.