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
?
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
?
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.