Problem: Given a pair of public and private RSA keys, factor N into p and q.
Some basic facts you need to know:
- Euler’s totient is multiplicative: if p and q are coprime then .
- Euler’s theorem: if a and N are coprime then . Therefore we have .
- In the RSA cryptosystem, the public key is (N,e) and private key is d such that , where N is the product of two large primes p and q meaning .
- Chinese remainder theorem: 1 has 4 square roots modulo pq: 1, -1, x, -x where and and . x and -x are the nontrivial square roots of 1 modulo pq.
We begin with the fact that , which means , meaning ed-1 is a multiple of , meaning 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 with r odd. We know from the evenness of p-1 and q-1 that t > 1.
Thus we now have . Now we try to find a non-trivial square root of unity of N by the following algorithm:
- Pick a random 1<a<N that is coprime to N (very important).
- Reduce t by 1. If t is -1, goto 1. Else obtain x = .
- If x is 1 goto 2. If x is -1 goto 1.
- 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 , 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 i.e .
Since x is a nontrivial square root of 1 mod pq, that means and . 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).
This blog post is based on the Yale CS lecture Cryptography and Computer Security Lecture 11