Dacă RSA folosește $e$ cu $\gcd(e,\phi(N))\ne1$, dar $e$ este greu de factorizat, are un adversar încă un avantaj în găsirea $d$ pentru $m^{ed}\equiv m\mod N$?

De obicei, RSA folosește un exponent de criptare $e$ cu $\gcd(e,\phi(N))=1$.
Acest întrebare arată de ce trebuie să fie așa: Pentru $\ne1$ s-ar putea să nu existe exponent de decriptare $d$ pentru că altele $m'\ne m$ poate exista cu $m^e \equiv (m')^e \bmod N$.

Cu toate acestea, dacă ne producem $m$ ca: $$m = m_0^{e} \mod N$$ sau mai general $$m = m_0^{e^{r_1}\cdot r_2} \mod N \tag{I}$$

Putem întotdeauna (cu excepția unor cazuri speciale pe care le ignorăm aici) să găsim un exponent de decriptare $d$ pentru $c \equiv m^e \mod N$ $$d \equiv e^i \equiv e^{\phi(\phi(N))-1} \mod \phi(N)$$ cu $$c^d \equiv (m^{e})^d \equiv m^{\displaystyle e^1\cdot e^{{\phi(\phi(N))-1}}} \equiv m^ {\displaystyle e^{{\phi(\phi(N))}}} \equiv m \mod N$$

Desigur, acest mesaj $m$ nu a putut transmite o mare parte din informațiile țintă. Unele informații cu biți mici ar putea fi transmise prin generarea aleatorie $m$ până când primii biți poartă informațiile țintă. Nu este deloc eficient, dar asta nu este important aici.

Întrebarea este dacă ar fi (mult) mai ușor pentru un adversar să găsească exponentul de decriptare $d$ pentru așa $e$?

Dacă $\gcd(e,\phi(N))\gg 1$ este cunoscută factorizarea $N$ poate deveni mult mai ușor și cu această pauză securitatea RSA.
Î1: Dar ce se întâmplă dacă $\gcd(e,\phi(N))\gg 1$ este nu cunoscut? Pentru a ne asigura că alegem un $e$ care este greu de factorizat.
Are un adversar încă un mare avantaj de a ști $\gcd \ne1$ ?

Ar putea depinde în mare măsură de factorii aleși.
Presupunem aici (cazul de utilizare țintă) $$N = P \cdot Q$$ $$P = 2 \cdot p_s \cdot p_b +1$$ $$Q = 2 \cdot q_s \cdot q_b +1$$ $$\phi(N) = 2^2 \cdot p_s \cdot p_b \cdot q_s \cdot q_b$$ $$e = (2^2 \cdot p_b \cdot q_b) \cdot e_b > 2^{3000} \text{ (greu de factorizat)}$$ $$\gcd(e,\phi(N))=2^2\cdot p_b \cdot q_b = 2^2\cdot (2\cdot 3\cdot b_0+1) \cdot (2\cdot 3\cdot q_0 +1) = B$$ $$B > 2^{2000} \text{ (greu de factorizat)}$$ $$\phi(\phi(N)) = 2^3 \cdot 3^2 \cdot \phi(p_s) \cdot \phi(q_s) \cdot (q_0\cdot b_0)$$ $$\phi(p_s) \cdot \phi(q_s) /4= S \aproximativ 2^{200} \ll B$$ (în cazul de utilizare țintă $p_s,q_s$ au forma $p_s = 2\cdot p_1\cdot p_2 \cdot p_3+1$)
(toți factorii primi variabili sunt unici)

$e$ trebuie să fie un pătrat al unei rădăcini primitive modulo $p_s$ și $q_s$.
Cu asta putem produce $S$ valori diferite cu $m^{e^i} \bmod N$. În funcție de pornire $m$ obținem 4 seturi disjunse de acea dimensiune (plus câteva cazuri speciale mai mici pe care le ignorăm aici).
Factorul suplimentar $e_b$ este necesar pentru a ascunde relația cu $\phi(N)$ și $B$. Cu asta $e\gg N$ Aici.
Presupunem că și adversarul știe $S$ inclusiv factorizarea prime.

Î2: Întrebarea legată de cazul de utilizare permite și valori țintă $n\ne m$ dar generat ca $(\text{I})$ (si stiu ca exista o solutie):
Poate adversarul să găsească $i$ în $n\equiv m^{e^i} \bmod N$ cu cunoscut $e,n,m,N,S$ mai rapid decât $O(p_s + q_s) \aprox O(\sqrt{S})$?
Acest lucru se poate realiza prin găsirea unei soluții pentru $j,k$ în $n^{\displaystyle p_s} \equiv (m^{\displaystyle {p_s}})^{e^j} \bmod N$ și $n^{\displaystyle q_s} \equiv (m^{\displaystyle {q_s}})^{e^k} \bmod N$ cu testare pas cu pas. Pasul uriaș nu poate fi făcut ca $\phi(N)$ este necunoscută şi $e^{2^{50}}$ prea mare pentru a calcula fără el. Sau se poate face mai repede?

(jucărie)-Exemplu:
Aici $p_b,q_b < p_s,q_s$ sunt utilizate. În cazul de utilizare țintă, acestea vor fi $p_b,q_b \gg p_s,q_s$ (și toate valorile mult mai mari)

$N=P\cdot Q = 6565236619157488809896588016937$
$P = 2 \cdot p_s \cdot p_b +1 = 2500987802965403$
$Q = 2 \cdot q_s \cdot q_b +1 = 2625057431856779$
$p_b = 2 \cdot 3 \cdot p_0 = 2 \cdot 3 \cdot 4547= 27283$
$p_s = 2 \cdot p_1 \cdot p_2 \cdot p_3 + 1 = 2 \cdot 2579\cdot 2963\cdot 2999 + 1=45834178847$
$q_b = 2 \cdot 3 \cdot q_0 = 2 \cdot 3 \cdot 4007= 24043$
$q_s = 2 \cdot q_1 \cdot q_2 \cdot q_3 + 1 = 2 \cdot 2819\cdot 3023\cdot 3203 + 1=54590887823$
$\phi(N) = 2^2 \cdot p_s \cdot p_b \cdot q_s \cdot q_b = 6565236619157483683851353194756$ $\phi(\phi(N))=2^5\cdot3^2 \cdot p_0\cdot p_1\cdot p_2 \cdot p_3\cdot q_0\cdot q_1\cdot q_2\cdot q_3$
$\phi(\phi(N)) = 3282361465954844745126356151456$

Exponenți $e,d$ au doar un singur factor suplimentar mare pentru a face factorizarea dificilă. $e = 3681846424601561452716738001396 = 2^2 \cdot p_b \cdot q_b \cdot 1403217197574083942221 $
$d = 1568810657844451193145575929268 = 2^2 \cdot p_b \cdot q_b \cdot 597901661545558066493 $

Aici $B<S$ dar în cazul de utilizare țintă $B \gg S$ $S = p_1\cdot p_2\cdot p_3\cdot q_1\cdot q_2\cdot q_3 = 625532128948867853353$
$B = 2^2 \cdot p_b \cdot q_b = 2^2 \cdot 27283 \cdot 24043=2623860676$

Adversarul ar ști $N$,$e$,$S$ inclusiv factorizarea de $S$. Dar el nu cunoaște factorizarea $N,e,B$.