1
$\begingroup$

How to decrypt RSA while given $e$,$n$ and the range of $dp$ ?

e=2953544268002866703872076551930953722572317122777861299293407053391808199220655289235983088986372630141821049118015752017412642148934113723174855236142887
n=6006128121276172470274143101473619963750725942458450119252491144009018469845917986523007748831362674341219814935241703026024431390531323127620970750816983

while $dp$ is in the range of $(1,2^{20})$

$\endgroup$
2
  • 1
    $\begingroup$ That seems small enough to factor, what have you tried? Note that homework / assignments are off topic, but we may give hints in comments if enough effort has been shown/ $\endgroup$
    – Maarten Bodewes
    Jul 31, 2021 at 11:27
  • 1
    $\begingroup$ I traversaled the range of dp and tried to calculate p with i in range(1,e) then p=((dp*e-1)/i)+1 but the public exponent is too large to traversale $\endgroup$
    – Manc
    Jul 31, 2021 at 11:45

1 Answer 1

1
$\begingroup$

Presumably $d_p$ is the quantity $d \bmod (p-1) = e^{-1} \bmod (p-1)$, from which we get the core property $$ e\cdot d_p \equiv 1 \pmod{p-1}\,. $$ For a small $d_p$ we can easily, by bruteforce, find the quantity $e\cdot d_p -1 = k\cdot (p-1)$ for some large unknown integer $k$.

Here we can take a hint from the Pollard $p-1$ factorization method—we have $2^{k(p-1)} = 1 \pmod{p}$, and thus $\gcd(n, 2^{e\cdot d_p - 1} - 1 \bmod n)$ will be $p$ for the right $d_p$.

In your example $d_p = 915155$.

$\endgroup$

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.