We are given n (public modulus) where n=pq and e (encryption exponent). Then I was able to crack the private key d, using Wieners attack. So now, I have (n,e,d). My question is, is there a way to calculate p and q from this information? If so, any links and explanation would be much appreciated!
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
It's actually fairly easy to factor $n$ given $e$ and $d$. Here's the standard way to do this:
If you are familiar with the Miller-Rabin primality test, this will look familiar; the logic is the same (except that we use $ed-1$ rather than $n-1$ as the startign place for the exponent)
Generally, (n,e,d) is sufficient. Using these three it is possible to decrypt, encrypt, sign and verify any message or signature.
If you still need p and q: NIST SP 800-56B: Recommendation for Pair-Wise Key Establishment Schemes Using Integer Factorization Cryptography, Appendix C Prime Factor Recovery (Normative) contains formula for retrieving p and q, when you know (n,e,d). This formula is useful for instance to convert the private key in (n,e,d) format to CRT format.
Even a tool exists for the job: RSA CRT/SFM Converter.