Criptosistem Rabin: atac cu text cifrat ales

Am citit în literatură că Rabin Cryptosystem poate fi spart utilizând atacul cu text cifrat ales. Se descrie că, după decriptarea textului cifrat ales, atacatorul poate factoriza cheia publică $n$ folosind rădăcina pătrată cu probabilitate de $1/2$. Dar în articol nu este descris cum se face această factorizare.

Dacă cineva poate da un exemplu, aș fi recunoscător.

Presupun că asta nu este teme.

De fapt, este destul de simplu:

• Alegeți o valoare aleatorie $r$

• Calcula $s = r^2 \bmod n$, și trimiteți $s$ la decriptorul Rabin

• De cand $s$ este un reziduu patratic, decriptorul Rabin va returna o anumită valoare $t = \sqrt{s} \bmod n$.

• Acum, $s$ are patru rădăcini pătrate (presupunând $n$ are doi factori primi și nu s-a întâmplat să alegi un $r$ asta nu este relativ prim pentru $n$); daca ai $t = r$ sau $t = n-r$, nu a mers. Dacă este una dintre celelalte două valori posibile, atunci avem $r^2 = t^2 \bmod n$, acesta este, $(r+t)(r-t) = kn$, pentru un număr întreg $k$; cu toate acestea nici $r+t$ nici $r-t$ sunt multipli de $n$, prin urmare $\gcd(r+t, n)$ este un factor netrivial al $n$ (și $\gcd(r-t, n)$ este un alt factor netrivial).

Pentru că noi am ales $r$ la întâmplare, Rabin nu are de unde să știe care dintre cele patru posibilități am ales-o; returnează unul dintre ele, deci probabilitatea ca se întâmplă să returneze unul care ne oferă factorizarea este $2/4 = 0.5$