# Factor N given e and d

Problem: Given a pair of public and private RSA keys, factor N into p and q.

Some basic facts you need to know:

1. Euler’s totient is multiplicative: if p and q are coprime then $\phi(pq) = (p-1)(q-1)$.
2. Euler’s theorem: if a and N are coprime then $a^{\phi(N)} = 1 \bmod N$. Therefore we have $a^{k\cdot \phi(N)} = (a^{\phi(N)})^k = 1^k = 1 \bmod N$.
3. In the RSA cryptosystem, the public key is (N,e) and private key is d such that $e\cdot d = 1\bmod \phi(N)$, where N is the product of two large primes p and q meaning $\phi(N) = (p-1)(q-1)$.
4. Chinese remainder theorem: 1 has 4 square roots modulo pq: 1, -1, x, -x where $x = 1 \bmod p$ and $x = -1 \bmod q$ and $x \neq \pm 1 \bmod pq$. x and -x are the nontrivial square roots of 1 modulo pq.

We begin with the fact that $e\cdot d = 1\bmod \phi(N)$, which means $e\cdot d - 1 = 0\bmod \phi(N)$, meaning ed-1 is a multiple of $\phi(N)$, meaning $e\cdot d - 1 = k \cdot (p-1)(q-1)$ where k is an integer.

Since p and q are primes, they are both odd, hence p-1 and q-1 are both even, therefore (p-1)(q-1) is even as well. Therefore write $(p-1)(q-1) = 2^t\cdot r$ with r odd. We know from the evenness of p-1 and q-1 that t > 1.

Thus we now have $a^{r\cdot 2^t} = 1 \bmod N$. Now we try to find a non-trivial square root of unity of N by the following algorithm:

1. Pick a random 1<a<N that is coprime to N (very important).
2. Reduce t by 1. If t is -1, goto 1. Else obtain x = $a^{r\cdot 2^t} \bmod N$.
3. If x is 1 goto 2. If x is -1 goto 1.
4. x is a nontrivial square root of 1 mod N.

What this algorithm does is, it picks a random 1<a<N and starts with $a^{r\cdot 2^t} = 1 \bmod N$, then square roots it. If the square root obtained is 1, then take the square root of that too. Keep going until we get a square root of 1 that isn’t 1. Then check if it’s -1 or nontrivial. If it’s -1 then start over. If it’s nontrivial then we’re done.

Now we have x, a nontrivial square root of 1 mod pq, i.e $(x+1)(x-1) = x^2 - 1 = 1 - 1 = 0 \bmod pq$ i.e $(x+1)(x-1) = k\cdot pq$.

Since x is a nontrivial square root of 1 mod pq, that means $(x+1) \neq 0 \bmod pq \implies pq \nmid (x+1)$ and $(x-1) \neq 0 \bmod pq \implies pq \nmid (x-1)$. In other words pq is neither a factor of (x+1) nor (x-1). Since we know that pq is a factor of (x+1)(x-1) the only possibility is that one of p and q is a factor of (x-1) and the other is a factor of (x+1).

Thus, given a nontrivial square root of 1 mod pq x, we can find p and q by simply doing gcd(x-1, pq). Since pq has exactly one factor in common with x-1 then we get either p or q and we get the other by simply dividing pq by what we got from gcd(x-1, pq).

My implementation in Python

This blog post is based on the Yale CS lecture Cryptography and Computer Security Lecture 11