Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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$
