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!


It's actually fairly easy to factor $n$ given $e$ and $d$. Here's the standard way to do this:

  • Compute $f = ed - 1$. What's interesting about $f$ is that $x^f \equiv 1\ (\bmod n)$ for (almost) any $x$.

  • Write $f$ as $2^s g$ for an odd value $g$.

  • Select a random value $a$, and compute $b = a^g \bmod n$.

  • If $b = 1 $ or $-1$, then go back and select another random value of $a$

  • Repeatedly (in practice, up to $s$ times):

    • compute $c = b^2 \bmod n$.

    • If $c = 1$ then the factors for $n$ are $gcd(n, b-1)$ and $gcd(n, b+1)$

    • If $c = -1$, then go back and select another random value of $a$

    • Otherwise, set $b = c$, and go through another iteration of the loop.

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)

| improve this answer | |
  • $\begingroup$ Just to clarify, so when we write $f$ as $2^s g$, do you mean $f=2^s g$? Also, is it $2^s g$ or $2^{s g}$? $\endgroup$ – hhel uilop Nov 4 '13 at 17:09
  • $\begingroup$ @hheluilop: $f = 2^s \times g$; keep on dividing $f$ by two until you get an odd number. $\endgroup$ – poncho Nov 4 '13 at 17:16
  • $\begingroup$ There is no such value as $\gcd(n+1)$. Did you mean $\gcd(n,b+1)$? $\endgroup$ – cpast May 10 '15 at 19:33
  • $\begingroup$ @cpast: yes, of course $\endgroup$ – poncho May 11 '15 at 21:16

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.

| improve this answer | |
  • $\begingroup$ I will definitely check out the tool later. Do you know if the tool can handle 115-135 digit long integers for n and maybe 30-50 for d? $\endgroup$ – hhel uilop Nov 4 '13 at 17:24
  • $\begingroup$ If my memory serves me right, it'll handle any usual lengths. $\endgroup$ – user4982 Nov 4 '13 at 17:45
  • $\begingroup$ The algorithm in the NIST document is clear to me except for step 2. How does one calculate $r$? Is brute force the only option? $\endgroup$ – Duncan Jones Feb 3 '15 at 8:36
  • $\begingroup$ This step is fast to calculate because the other value ($2^t$) is multiple of 2. In fact, t is the number of zero bits on the least significant bits of k. An easy way to calculate r in many big number packages is to shift k right t steps. Either calculate the zeroes or shift one bit a time as long as the value is even. $\endgroup$ – user4982 Feb 3 '15 at 17:47
  • $\begingroup$ While seeing formulas is great, sometimes I need to see it in code. Found an implementation in Python that helped me understand it better: github.com/truongkma/ctf-tools/blob/master/… $\endgroup$ – Demonslay335 Jun 19 '19 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.