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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s