3
$\begingroup$

I need to find RSA private key $(d, N)$ knowing $(e, N)$. It's "own" RSA implementation. As i know
$p$ is random 70 bit number, then $q$ is $p-2^{10} < q < p+2^{10}$
$d$ is max 16 bit long with low number of ones in binary representation.

$e= 4223234360740816682261885795416553301541344119$

$N = 5074772291286459206774040208059072021046562917$

I tried to use Wiener's_attack with implementation from GitHub.

It gives me $d = 1031$. Is it the answer ? How to check if is it valid ?

What are the right ways to find d ?

| improve this question | |
$\endgroup$
  • $\begingroup$ How about trying out the $d$ value and see if you get the correct output? With those characteristics of $p$ and $q$, Fermat's factoring method would probably be quite fast (both prime factors close together). $\endgroup$ – tylo Jun 12 '15 at 10:24
  • $\begingroup$ the numbers work, just tested it with $m=20$ and $m=5001$. $\endgroup$ – SEJPM♦ Jun 12 '15 at 10:29
  • $\begingroup$ You can also just factor $N$... $\endgroup$ – fkraiem Jun 12 '15 at 11:18
4
$\begingroup$

Yes, in your specific case, $d=1031$ is the answer.

You can check it in the following ways:

  • Just try it out. Select some arbitrary messages, exponentiate with $e$, apply the modulus and exponentiate them with $d$. If this yields your original message number (like 20 or 5001) you know it's the correct $d$.
  • Factor $N$ using the exponent. You may want to use one of these algorithms for this. If you can factor this you can be sure to have the correct exponent. Note for the link: $m=e*d$

Now to the other ways there are for your case to find $d$.

  • Wiener's attack. $d$ is small meaning, Wiener's attack applies. You've used this fact successfully.
  • Brute-force. The parameters look so weak, that you can even just try out the $2^{16}$ values for $d$.
  • Factoring $n$. Using the quadratic sieve or a similar algorithm (provided by msieve or even non-dedicated tools) you can factor your 140-bit ($\approx 45$ digits) modulus within a relatively short time (seconds). After having factored $N$ you simply use the factorization to obtain $d$ from $e$.
  • As the distance between your primes isn't that large ($<2^{10}$) you can as well use Fermat's factoring method, which should yield the parameters $p$ and $q$ reasonaly fast. You proceed as above then.

So you see these parameters are extremely weak, so you shouldn't even think about using them in practice. But as they are so weak I'd guess this is some sort of homework, so it shouldn't be that much of a problem.

| improve this answer | |
$\endgroup$
  • $\begingroup$ No need for the quadratic sieve, the prime factors are so close that Fermat's attack actually works. $\endgroup$ – Thomas Jun 12 '15 at 11:13
  • $\begingroup$ Factoring this modulus takes less than a second here on PARI/GP or Sage (and no, I'm not on a supercomputer). $\endgroup$ – fkraiem Jun 12 '15 at 11:23
  • $\begingroup$ @Thomas, the QS is in here because it's an "off-the-shelf" algorithm that you just need to download and execute. It's also here to show that even if you don't know / mind about Fermat's method (which is also included :) ) that you can still factor $N$ in a reasonable amount of time. $\endgroup$ – SEJPM♦ Jun 12 '15 at 11:23
  • $\begingroup$ @fkraiem, thank you for this. I didn't have any idea how long it was gonna take (just reproduced your results). I'll edit the answer to reflect this. $\endgroup$ – SEJPM♦ Jun 12 '15 at 11:25

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.