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!
$\begingroup$
$\endgroup$
1
-
$\begingroup$ crypto.stackexchange.com/a/9145/991 $\;$ $\endgroup$– user991Commented Nov 4, 2013 at 16:56
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
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)
-
$\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$ Commented 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$– ponchoCommented Nov 4, 2013 at 17:16
-
$\begingroup$ There is no such value as $\gcd(n+1)$. Did you mean $\gcd(n,b+1)$? $\endgroup$– cpastCommented May 10, 2015 at 19:33
-
$\begingroup$
$\endgroup$
5
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.
-
$\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$ Commented Nov 4, 2013 at 17:24
-
$\begingroup$ If my memory serves me right, it'll handle any usual lengths. $\endgroup$– user4982Commented 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$ Commented 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$– user4982Commented 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$ Commented Jun 19, 2019 at 19:59