# Decrypt RSA with known public key and modulus and the range of dp

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})$$

• 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/ Jul 31, 2021 at 11:27
• 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
– Manc
Jul 31, 2021 at 11:45

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$$.