so in rabin decryption, we get 4 answers due to the square root and one of them is the correct one although I've seen the correct result multiple times sometimes i.e. 2 out of the 4 square roots. Is this normal?

  • 2
    $\begingroup$ How do you count answers (hint: multiplicity of roots of a polynomial)? How is it possible to obtain what you claim you have seen? Can you show us? What is the probability that it happens by chance? What are the ways an adversary could increase this probability? Is this an issue? You understood it, we are not so keen about homework dump without display of efforts to solve it, and the best you should hope is hints. $\endgroup$ – fgrieu Oct 23 '17 at 6:04
  • $\begingroup$ @fgrieu this is not a homework. I'm just trying to understand why is this the case as I'm not so good with math. I know I should get the inverse but I wasn't expecting to see the same result. 2 out of the 4 results were the same. $\endgroup$ – rullzing Oct 23 '17 at 22:00

Rabin decryption (or rather, one step of that before selection of the solution then padding removal) is solving the equation $c=m^2\bmod(p\;q)$, searching for $0\le m<p\;q$ given $c$ and distinct large primes $p$ and $q$ (often it is taken $p\equiv q\equiv3\mod 4$).

This is done by

  • Solving $c\bmod p={m_p}^2\bmod p$ with $0\le m_p<p$, with either one solution $m_p=0$ when $c\bmod p=0$; or 2 solutions $m_p\ne0$ and $p-m_p$ otherwise (when $p\equiv3\mod 4$, a solution is $(c\bmod p)^{p+1}/4\bmod p$, and the other follows)
  • same modulo $q$, giving also one or two solutions.
  • combining the solutions by the CRT. The usual ways is to take one of the pair $(m_p,m_q)$ and compute
    • $q_\text{Inv}=q^{-1}\bmod p$
    • $m_0=(((m_p-m_q)\;q_\text{Inv})\bmod p)\;q+m_q$
    • $m_1=(-m_0)\bmod(p\;q)$
    • $m_2=((((m_p+m_q)\;q_\text{Inv})\bmod p)\;q-m_q)\bmod(p\;q)$
    • $m_3=(-m_2)\bmod(p\;q)$

There is either 1, 2 or 4 distinct solutions $m_i$ thus computed, never 3 (proof: two solutions can be equal only if they are equal both modulo $p$ and modulo $q$, and we can count the cases; 1 solution occurs for $c=0$, 2 solutions when another $c$ is such that $c\bmod p=0$ or $c\bmod q=0$, 4 solutions otherwise).

In practice, only 1 or 4 solutions ever arise unless the holder of the private key goofs. That's because exhibiting $c$ (or $m$) for which there are 2 solutions immediately leads to factorization, because $\gcd(c,\;p\;q)$ is one of $p$ or $q$ . The 1 solution case only occurs for forged ciphertext (which can easily be made to arise by an active adversary, or goof).


Not the answer you're looking for? Browse other questions tagged or ask your own question.