Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|improve this question $\;$ – Ricky Demer Nov 4 '13 at 16:56

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)

share|improve this answer
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}$? – hhel uilop Nov 4 '13 at 17:09
@hheluilop: $f = 2^s \times g$; keep on dividing $f$ by two until you get an odd number. – poncho Nov 4 '13 at 17:16
There is no such value as $\gcd(n+1)$. Did you mean $\gcd(n,b+1)$? – cpast May 10 '15 at 19:33
@cpast: yes, of course – 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.

share|improve this answer
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? – hhel uilop Nov 4 '13 at 17:24
If my memory serves me right, it'll handle any usual lengths. – user4982 Nov 4 '13 at 17:45
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? – Duncan Feb 3 '15 at 8:36
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. – user4982 Feb 3 '15 at 17:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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