Join Log in
Score:1
Manc avatar Crypto

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

in flag
Manc

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

329
1 + 2
rsa
Maarten Bodewes avatar
in flag
Maarten Bodewes
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/
1
Reply
Manc avatar
in flag
Manc
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
1
Reply
Score:1
avatar Crypto
pe flag
Samuel Neves

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

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.