Se întreabă cum, în RSA, se găsește $e$ dat $d$ și $N$. Voi ignora cerința întrebării că $e$ este coprim cu $N$, care este foarte neobișnuit și nu are relevanță matematică. Voi presupune și eu $p\ne q$, pentru că este necesar pentru cele declarate $\varphi(N)=(p-1)\cdot(q-1)$ a tine.
Cu definiția RSA a întrebării, metoda de găsit $e$ merge
- Factor $N$ a găsi $p$ și $q$
- Calcula $\varphi=(p-1)\cdot(q-1)$
- Calcula $e$ știind $e\cdot d\bmod\varphi=1$ și $1<e<\varphi$. Acea $e$ este definit în mod unic și inversul modular al $d$ în grup multiplicativ de modul întreg $\varphi$. Pentru numere mici, o metodă de lucru este încercarea și eroarea de cotă mică $e>1$. O metodă mai constructivă este (jumătate)-algoritm euclidian extins, care calculează $e=d^{-1}\bmod \varphi$ direct. Pentru un algoritm practic care utilizează numai numere întregi nenegative:
- $a\gets d\bmod \varphi$ , $b\obține \varphi$ , $x\gets0$ și $y\gets1$
Notă: $a\cdot x+b\cdot y=\varphi$ va continua să țină
- dacă $a=1$, apoi ieșire „inversul dorit $e$ de $d$ modulo $\varphi$ este $y$" și opriți
- Dacă $a=0$, apoi ieșire „inversul dorit $e$ de $d$ modulo $\varphi$ nu exista" și opriți
- $r\gets\lfloor b/a\rfloor$
- $b\obține b-a\cdot r$ și $x\obține x+r\cdot y$
- dacă $b=1$, apoi ieșire „inversul dorit $e$ de $d$ modulo $\varphi$ este $\varphi-x$" și opriți
- Dacă $b=0$, apoi ieșire „inversul dorit $e$ de $d$ modulo $\varphi$ nu exista" și opriți
- $r\obține\lfloor a/b\rfloor$
- $a\obține a-b\cdot r$ și $y\obține y+r\cdot x$
- Continuați la 2
Aceeași metodă este de obicei folosită pentru a calcula $d$ din $e$, de cand $d$ și $e$ sunt simetrice în $e\cdot d\bmod\varphi=1$. Totuși, nu așa $d=11$ a fost calculat în întrebare; dintr-un motiv ciudat întrebarea cere $e<\varphi(N)$ dar nu $d<\varphi(N)$, sau mai obișnuit $d<N$ sau $d<\operatorname{lcm}(p-1,q-1)$.
Problemă serioasă cu această abordare pentru RSA așa cum este practicată (deci foarte mare $N$, cel puțin sute de cifre zecimale): nu va funcționa, pentru că $N$ va fi atât de mare încât nu poate fi luată în considerare, astfel $\varphi$ nu poate fi calculată în acest fel.
De asemenea, starea întrebării $e\cdot d\bmod\varphi(N)=1$ este o condiție suficientă, dar nu necesară pentru utilizarea manualului de criptare RSA $(e,N)$ pentru a fi anulat prin decriptarea RSA folosind $(d,N)$, si invers. Condiția necesară este $e\cdot d\bmod\lambda(N)=1$, Unde $\lambda(N)=\operatorname{lcm}(p-1,q-1)$. Această condiție este adesea folosită în practică: este permisă de PKCS#1, și mandatat de FIPS 186-4. Exemplu mic artificial: $N=341$, $e=7$, $d=13$ funcționează foarte bine pentru criptarea/decriptarea manuală RSA, încă $e\cdot d\bmod\varphi(N)=1$ nu se menține (în acest exemplu $p=11$, $q=31$, $\varphi(N)=300$, $\lambda(N)=30$ ).
Cu toate acestea, în RSA așa cum se practică, $e$ este mic, adesea suficient de mic încât $e$ pot fi găsite prin enumerare. Astfel, o metodă ar putea fi:
- calcula $c\gets2^d\bmod N$
- calcula $c_2\obține c^2\bmod N$
- a stabilit $e\gets1$
- repeta
- a stabilit $e\obține e+2$
- a stabilit $c\obține c\cdot c_2\bmod N$; înștiințare $c=2^{d\cdot e}\bmod N$
- dacă $c=2$
- pentru $m$ primele sute de numere prime impare (notă: pentru mici $N$, vrem să ne oprim de îndată ce $m^2>N$ )
- dacă $m^{e\cdot d}\bmod N\ne m$, continua la repeta de mai sus
- ieșire $e$ și opriți.
Este aproape sigur că dacă an $e$ este de ieșire, este valabil în sensul că manualul de criptare RSA folosește $(e,N)$ este anulat prin decriptarea RSA folosind $(d,N)$, și (echivalent) $e\cdot d\bmod\lambda(N)=1$. Nu este chiar sigur $e\cdot d\bmod\varphi(N)=1$, dar știind $e\cdot d$ și $N$ este posibil să factorizezi $N$ (folosind acest algoritm) și apoi calculați cel $e$ cu $e\cdot d\bmod\varphi(N)=1$ și $1<e<\varphi(N)$, dacă dintr-un motiv oarecare se dorește.
Adăugare: Cele de mai sus sunt departe de a fi optime. Când $\delta=\ln(e)/\ln(N)$ este sub un anumit prag, în ordinea lui $0.292$, există modalități de factor $N$ (și astfel rezolvați problema prin prima metodă discutată). Practic, schimbăm $d$ și $e$ în a lui Dan Boneh și Glenn Durfee Criptanaliză RSA cu cheie privată $d$ Mai puțin decât $N^{0,292}$, în procedurile Eurocrypt 1999. Vedea Acolo pentru mai mult.
