# 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.

• Nov 16, 2021 at 21:22

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$$