RSA private key d knowing e,n

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 ?

• 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).
– tylo
Jun 12, 2015 at 10:24
• the numbers work, just tested it with $m=20$ and $m=5001$. Jun 12, 2015 at 10:29
• You can also just factor $N$... Jun 12, 2015 at 11:18

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.

• No need for the quadratic sieve, the prime factors are so close that Fermat's attack actually works. Jun 12, 2015 at 11:13
• Factoring this modulus takes less than a second here on PARI/GP or Sage (and no, I'm not on a supercomputer). Jun 12, 2015 at 11:23
• @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. Jun 12, 2015 at 11:23
• @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. Jun 12, 2015 at 11:25