Voi aborda cazul $e=2$; dacă $\gcd(e, \phi(n)) = 2$, atunci acest lucru este suficient (deoarece ar fi suficient să găsiți rădăcina pătrată a $c$ (textul cifrat), apoi luați $e/2$rădăcina asta.
Deci, ni se dă $c$ și doriți să găsiți valorile $m$ Sf. $m^2 = c \pmod {p^2}$.
Începem prin a găsi valorile $m'$ Sf. $m'^2 = c \pmod p$; aceasta este o rădăcină pătrată modulară și există algoritmi cunoscuți pentru aceasta. Cel mai simplu se aplică dacă $p \equiv 3 \pmod 4$; in acest caz, $m' = \pm c^{(p+1)/4} \bmod p$. The $p \equiv 1 \pmod 4$ cazul este de asemenea fezabil, dar este mai mult de lucru.
Având în vedere aceste valori, le convertim în valori modulo $p^2$. Asta se dovedește a fi și mai ușor, pentru că dacă avem $m = m' + xp$ (și $m$ va fi întotdeauna echivalent cu unul dintre $m'$ valori modulo $p$), atunci noi avem:
$$m^2 = (m' + xp)^2 = m'^2 + 2m'xp = c \pmod {p^2}$$
Și, de când $c-m'^2$ este un multiplu al $p$, putem reduce acest lucru la:
$2m'x = (c - m'^2)/p \pmod p$, sau $x = (2m')^{-1} (c - m'^2)/p \pmod p$
Și, $m = m' + px$ vă oferă valorile $m$ (și amintiți-vă, există două valori posibile ale $m'$ și deci două valori posibile ale $m$).
De asemenea, rețineți că, deoarece am reușit să facem fără nicio informație privată, aceasta nu funcționează ca „criptare cu cheie publică”
