How to factor RSA modulus given the public and private exponent?

Question

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?

Answer 1

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.

Answer 2

You can use the open source tool I have developed in 2009 that converts RSA keys between the SFM format (n,e,d) and CRT format (p,q,dp,dq,u), and the other way around. It is on SourceForge : http://rsaconverter.sourceforge.net/

The algorithm I implemented is based on ideas presented by Dan Boneh, as described by the previous answer.

I hope this will be useful.

Mounir IDRASSI - IDRIX