# How does knowing the factorization of N help to obtain the secret?

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

• 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). – fgrieu Feb 27 '15 at 7:25
• 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? – Sam I Am Feb 27 '15 at 21:06
• 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$. – fgrieu Feb 28 '15 at 8:52
• 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. – Robert NACIRI Mar 1 '15 at 15:51

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.