5
$\begingroup$

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!

$\endgroup$
1

2 Answers 2

11
$\begingroup$

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)

$\endgroup$
4
  • $\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, 2013 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, 2013 at 17:16
  • $\begingroup$ There is no such value as $\gcd(n+1)$. Did you mean $\gcd(n,b+1)$? $\endgroup$
    – cpast
    May 10, 2015 at 19:33
  • $\begingroup$ @cpast: yes, of course $\endgroup$
    – poncho
    May 11, 2015 at 21:16
1
$\begingroup$

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.

$\endgroup$
5
  • $\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, 2013 at 17:24
  • $\begingroup$ If my memory serves me right, it'll handle any usual lengths. $\endgroup$
    – user4982
    Nov 4, 2013 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$ Feb 3, 2015 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, 2015 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$ Jun 19, 2019 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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