Take the 2-minute tour ×
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.

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
    
crypto.stackexchange.com/a/9145/991 $\;$ –  Ricky Demer Nov 4 '13 at 16:56

2 Answers 2

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+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

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

Your Answer

 
discard

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.