Assuming $x=a^2 \pmod n$ and knowing $x$, $p$, $q$ how is it possible to obtain $a$?

  • 7
    $\begingroup$ I won't deprive you from the benefit of doing your homework. $\;$ Hint: establish that if $N$ is prime, it is possible to solve $x=a^2\bmod N$ for $a$ (that's the modular square root problem). Now, assume the factorization of $N$ is available, and use the Chineese Remainder Theorem (at first, handle the case of $N$ not divisible by the square of a prime). $\endgroup$ – fgrieu Feb 27 '15 at 7:25
  • $\begingroup$ Thanks for not depriving me from such benefit xD Would it be possible to set up two equations, such as x=a^2 mod p and x=a^2 mod q and use CRT to solve for a? $\endgroup$ – Sam I Am Feb 27 '15 at 21:06
  • 3
    $\begingroup$ The CRT (and the appropriate conditions on $p$, $q$: that $p$ divides $N$, $q$ divides $N$, $\gcd(p,q)=1$) gives you that $x=a^2\bmod N$ if and only if $x=a^2\bmod p$ and $x=a^2\bmod q$. Now you need to solve these two equations, and walk back to $N$. $\endgroup$ – fgrieu Feb 28 '15 at 8:52
  • $\begingroup$ As fgrieu mentioned, this is equivalent to extracting square root over $F_p$. When prime p is of "special form" the algorithm is deterministic, otherwise it's probabilistic. This is a nice brainstorming problem. $\endgroup$ – Robert NACIRI Mar 1 '15 at 15:51

Your question is related to the well known RABIN Cryptosystem which is similar to RSA, except the public exponent is 2.

As fgrieu mentioned, decipherment can be easily processed by the CRT algorithm, but some precautions must beforehand be observed during the key generation. In fact the solution of the equation gives 4 roots, which means that the solution of the initial problem when they exist (... $x \in QR(p\cdot q)$) is not unique. And asking which of one of four solution to return is a security problem, and without knowing these constraints, the probability of divulging the factorization of modulus is $0.5$. The determination of the right and secure solution must be carefully studied regarding the form of the factor p & q, and the properties of special integer called "Blum integers".

When restricting to correct message space, there is a unified inversion formula which runs on $\mathbb{Z}/n \mathbb{Z}$. I know it because it was specified in an early draft of SC27-ISO9796 at the end of the $80^{th}$. Unfortunately I don't remember it. Probably Fgrieu can confirm and search for it.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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