Rabin Cryptosystem: Chosen-Ciphertext Attack

I read in literature that Rabin Cryptosystem can be broken using chosen-ciphertext attack. It is described that after chosen ciphertext is decrypted attacker can factorize public key $n$ by using square root with probability of $1/2$. But in article it is not described how this factorization is done.

If somebody can give some example I would be grateful.

I'll assume this is not homework.

It's actually quite simple:

• Pick a random value $r$

• Compute $s = r^2 \bmod n$, and submit $s$ to the Rabin decryptor

• Since $s$ is a Quadratic Residue, the Rabin decryptor will return some value $t = \sqrt{s} \bmod n$.

• Now, $s$ has four square roots (assuming $n$ has two prime factors and you didn't happen to pick an $r$ that's not relatively prime to $n$); if you have $t = r$ or $t = n-r$, it didn't work. If it's one of the other two possible values, then we have $r^2 = t^2 \bmod n$, that is, $(r+t)(r-t) = kn$, for some integer $k$; however neither $r+t$ nor $r-t$ are multiples of $n$, hence $\gcd(r+t, n)$ is a nontrivial factor of $n$ (and $\gcd(r-t, n)$ is another nontrivial factor).

Because we selected $r$ at random, Rabin has no way of knowing which of the four possibilities we picked; it returns one of them, and so the probability that it happens to return one that gives us the factorization is $2/4 = 0.5$