问题:

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?

回答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.

回答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

回答3:

I posted a response on the crypto stack exchange answering the same question here. It uses the same approach as outlined in Boneh's paper, but does a lot more explanation as to how it actually works. I also try to assume a minimal amount of prior knowledge.

Hope this helps!