Este ușor de arătat că în RSA, când e = 3 există 4 mesaje m pentru care textul cifrat este egal cu textul simplu și gcd(m, n) = 1
Ei bine dacă $m^3 = m \pmod n$ (și presupunând $n$ este un modul RSA convențional, adică este $n = pq$, pentru $p, q$ numere prime impare distincte), aceasta este echivalentă cu ambele de mai jos care dețin simultan:
$$m^3 = m \pmod p$$
$$m^3 = m \pmod q$$
Dacă $p, q$ sunt prime, acestea sunt ecuații cubice în câmpuri; astfel de ecuații cubice au (cel mult) 3 soluții. Un moment de reflecție (sau un pic de algebră) dă soluțiile $m = 0, 1, -1$ (cu cea mai târziu echivalentă cu $p-1, q-1$) - deoarece există cel mult 3 soluții, acestea trebuie să fie toate.
Acum, $m=0$ (în ambele cazuri) este în contradicție cu $\gcd(m, n)=1$, prin urmare putem renunța la acele soluții; asta da solutiile $m = 1, -1 \pmod p$ și $m = 1, -1 \bmod q$. Prin teorema chineză a restului (și faptul că $p, q$ sunt relativ prime), toate cele patru combinații posibile corespund unei singure $m$ în intervalul $(0, n-1)$.
Combinatia $m = 1 \pmod p$ și $m = 1 \pmod q$ dă valoarea $m = 1$; la fel combinația $m = -1 \pmod p$ și $m = -1 \pmod q$ dă valoarea $m = n-1$ (citatul arată asta ca $-1$, cu toate acestea, aceasta nu este în interval, iar modular cubing nu va returna niciodată valoarea -1); acestea sunt cele două soluții banale.
Celelalte două combinații, ambele $m = 1 \bmod p$ și $m = -1 \pmod q$, și $m = -1 \bmod p$ și $m = 1 \pmod q$ sunt soluțiile netriviale.
Această logică arată că nu există alte posibilități.
De asemenea, cum să găsesc celelalte 2 mesaje când nu există niciun indiciu despre n,p,q?
Chiar dacă ți s-a dat valoarea de $n$, cunoașterea uneia dintre cele două valori netriviale duce imediat la o factorizare a $n$, de exemplu, prin calcul $\gcd(m-1, n)$, deci nu există o cale ușoară (fără a cunoaște factorizatoin apriori).
