13.5: The Hardness of Factoring N

As previously mentioned, the best known way to break the security of RSA as a trapdoor function (i.e., to compute the inverse RSA function given only the public information \(N\) and \(e\) ) involves factoring the RSA modulus.

Factoring integers (or, more specifically, factoring RSA moduli) is believed to be a hard problem for classical computers. In this section we show that some other problems related to RSA are "as hard as factoring." What does it mean for a computational problem to be "as hard as factoring?" More formally, in this section we will show the following:

Theorem \(13.12\)

Either all of the following problems can be solved in polynomial-time, or none of them can:

1. Given an RSA modulus \(N=p q\), compute its factors \(p\) and \(q\).
2. Given an RSA modulus \(N=p q\) compute \(\phi(N)=(p-1)(q-1)\).
3. Given an RSA modulus \(N=p q\) and value e, compute the corresponding \(d\) (satisfying \(e d \equiv \phi(N) 1)\)
4. Given an RSA modulus \(N=p q\), find any \(x \nexists_{N} \pm 1\) such that \(x^{2} \equiv_{N} 1\).

To prove the theorem, we will show:

• if there is an efficient algorithm for (1), then we can use it as a subroutine to construct an efficient algorithm for (2). This is straight-forward: if you have a subroutine factoring \(N\) into \(p\) and \(q\), then you can call the subroutine and then compute \((p-1)(q-1)\)
• if there is an efficient algorithm for (2), then we can use it as a subroutine to construct an efficient algorithm for (3). This is also straight-forward: if you have a subroutine computing \(\phi(N)\) given \(N\), then you can compute \(d\) exactly how it is computed in the key generation algorithm.
• if there is an efficient algorithm for (3), then we can use it as a subroutine to construct an efficient algorithm for (4).
• if there is an efficient algorithm for (4), then we can use it as a subroutine to construct an efficient algorithm for (1).

Below we focus on the final two implications.

Using square roots of unity to factor \(N\)

Problem (4) of Theorem \(13.12\) concerns a new concept known as square roots of unity:

Definition \(13.13)

\(x\) is a square root of unity modulo \(N\) if \(x^{2} \equiv_{N} 1\). If \(x \equiv_{N} 1\) and \(x \equiv_{N}-1\), then we say (Sqrt of unity) that \(x\) is a non-trivial square root of unity.

Since \((\pm 1)^{2}=1\) over the integers, it is also true that \((\pm 1)^{2} \equiv_{N}\). In other words, \(\pm 1\) are always square roots of unity modulo \(N\), for any \(N\). But some values of \(N\) have even more square roots of unity. If \(N\) is the product of distinct odd primes, then \(N\) has 4 square roots of unity: two trivial and two non-trivial ones (and you are asked to prove this fact in an exercise)

Claim \(13.14\)

Suppose there is an efficient algorithm for computing nontrivial square roots of unity modulo \(N\). Then there is an efficient algorithm for factoring \(N\). (This is the (4) \(\Rightarrow\) (1) step in Theorem 13.12.)

Proof

The reduction is rather simple. Suppose NTSRU is an algorithm that on input \(N\) returns a non-trivial square root of unity modulo \(N\). Then we can factor \(N\) with the following algorithm:

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

The algorithm is simple, but we must argue that it is correct. When \(x\) is a nontrivial square root of unity modulo \(N\), we have the following:

\[\begin{array}{lll} x^{2} \equiv_{p q} 1 & \Rightarrow p q \mid x^{2}-1 & \Rightarrow p q \mid(x+1)(x-1) \\ x \neq p q 1 & & \Rightarrow p q \nmid(x-1) \\ x \neq z_{p q}-1 & & \Rightarrow p q \nmid(x+1) \end{array}\]

The prime factorization of \((x+1)(x-1)\) contains a factor of \(p\) and a factor of \(q\). But neither \(x+1\) nor \(x-1\) contain factors of both \(p\) and \(q\). Hence \(x+1\) and \(x-1\) must each contain factors of exactly one of \(\{p, q\}\). In other words, \(\{\operatorname{gcd}(p q, x-1), \operatorname{gcd}(p q, x+1)\}=\{p, q\}\).

Finding square roots of unity

Claim \(13.15\)

If there is an efficient algorithm for computing \(d \equiv_{\phi(N)} e^{-1}\) given \(N\) and e, then there is an efficient algorithm for computing nontrivial square roots of unity modulo \(N\). (This is the (3) \(\Rightarrow\) (4) step in Theorem 13.12.)

Proof

Suppose we have an algorithm FIND_D that on input \((N, e)\) returns the corresponding exponent \(d\). Then consider the following algorithm which uses FIND_D as a subroutine:

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

There are several return statements in this algorithm, and it should be clear that all of them indeed return a square root of unity. Furthermore, the algorithm does eventually return within the main for-loop, because \(x\) takes on the sequence of values:

\[w^{r}, w^{2 r}, w^{4 r}, w^{8 r}, \ldots, w^{2^{s} r}\]

and the final value of that sequence satisfies

\[w^{2^{s} r}=w^{e d-1} \equiv_{N} w^{(e d-1) \% \phi(N)}=w^{1-1}=1 .\]

Although we don’t prove it here, it is possible to show that the algorithm returns a square root of unity chosen uniformly at random from among the four possible square roots of unity. So with probability \(1 / 2\) the output is a nontrivial square root. We can repeat this basic process \(n\) times, and eventually encounter a nontrivial square root of unity with probability \(1-2^{-n}\)