How to factor RSA modulus given the public and private exponent?
encryption, rsa
Solution
Yes -- once you know the modulus N, and public/private exponents d and e, it is not too difficult to obtain p and q such that N=pq.
This paper by Dan Boneh describes an algorithm for doing so. It relies on the fact that, by definition,
de = 1 mod phi(N).
For any randomly chosen "witness" in (2,N), there is about a 50% chance of being able to use it to find a nontrivial square root of 1 mod N (call it x). Then gcd(x-1,N) gives one of the factors.
Problem
I have a RSA private key with modulus `m`, public exponent `e` and private exponent `d`, but the program I am using needs the modulus's prime factors `p` and `q`. Is it possible to use `e` and `d` to get `p` and `q`?