Let $n = pq$ where $p$ and $q$ are prime. We do not know $p$ and $q$. All we know is that $p \equiv q \equiv 3 \pmod 4$. From this we need to find a number $y$, in terms of $n$ and $x$, such that $y^2 \equiv x \pmod n$.

So $n \equiv 1 \pmod 4$ but I'm not sure that this is helpful at all. Is it possible to find $y$, and if so, how would I go about doing it?

  • $\begingroup$ The difficulty of taking square roots mod $pq$ is in fact the basis of the Rabin cryptographic system, which is provably as hard as factoring $n$ (a claim that not even the ubiquitous RSA can promise). @lulu's answer essentially shows how to factor $n$ given a method to extract square roots. $\endgroup$ – Erick Wong Apr 27 '16 at 2:31

Note: what follows is not an answer to the question. It shows how to extract the square root assuming you know $p$ and $q$. I am leaving it up because in the comments which follow the OP discuss, and clarify, the actual intent of the question (which is quite different that the stated question). The intended question was (to paraphrase): As an authenticity check, person $A$ has a number $n=pq$ on file. Person $B$, seeking to authenticate $A$ presents a quadratic residue $\pmod n$. Person $A$, knowing the factoring, extracts a square root and presents that to $B$ as proof. The problem asks if this is secure. The answer is: No...$A$ has a $50-50$ chance of giving $B$ the wrong square root, that is, the one $B$ does not already know. In that event, $B$ will be able to factor $n$ and permanently compromise the code.

Side note: how can $A$ produce a square root (knowing $p,q$).

If you have established that $x$ is a square, then we know that $x^{(p-1)/2}\equiv 1 \pmod p$ so $x^{1+(p-1)/2}\equiv x \pmod p$. But if $p=4k+3$ then $1+\frac {p-1}2=2k+2$ is even whence $y_p=x^{k+1}$ is a square root of $x\pmod p$. Similarly we can find $y_q$ and then use the Chinese Remainder theorem to find $y$ such that $y\equiv y_p\pmod p$ and $y\equiv y_q \pmod q$.

| cite | improve this answer | |
  • $\begingroup$ But doesn't the CRT depend on knowing what $p$ and $q$ are? $\endgroup$ – griest Apr 27 '16 at 0:05
  • $\begingroup$ Indeed it does. As does knowing the exponent. Sorry, I missed the part where you said $p,q$ were unknown. Let me think for a minute to see if this trick can be adapted to $pq$... $\endgroup$ – lulu Apr 27 '16 at 0:07
  • $\begingroup$ Nope...not seeing anything useful. Sorry. It is usually hard to extract square roots from composite moduli...do you have any reason to believe it is possible in this case? $\endgroup$ – lulu Apr 27 '16 at 0:12
  • $\begingroup$ Just to be clear: if you could find all $4$ square roots, then you can easily factor $n$....so extracting square roots is more or less the same as factoring the product. $\endgroup$ – lulu Apr 27 '16 at 0:18
  • $\begingroup$ I only need to find one of the 4 square roots. Here is some context. Presumably someone can impersonate Alice by finding a square root since it says that the scheme is insecure. $\endgroup$ – griest Apr 27 '16 at 0:37

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.