How to decrypt a RSA plaintext given a public exponent e and a RSA modulus n

user106260

1/15/24, 4:10 PM

I am doing a RSA cryptography task where I need to decrypt a ciphertext but I am only given the ciphertext ,c, a public exponent, e, and a RSA modulus, n, which has two prime factors p and q such that |p − q| < 10000.

I am unsure of how to do this but I am given the hint of using a low exponent attack (although the exponent is the usual 65537) and a binary search somewhere.

Could someone point me in the right direction? Thank you.

126

1 + 0

Score:0

Crypto

Don Freecs

1/15/24, 6:14 PM

since the distance between $p$ and $q$ is too short you can perform Fermat's Attack

in this link you'll get full explanation

+ 1

fgrieu

1/15/24, 8:12 PM

The question's _"I am given the hint of using a low exponent attack (although the exponent is the usual 65537) and a binary search somewhere"_ is at odds with this answer. Strictly speaking, _"$n$ has two prime factors $p$ and $q$ such that $|p−q|<10000$"_ does not imply that Fermat factorization will succeed. It's still entirely possible that $n$ has three prime factors, as allowed by [PKCS#1](https://pkcs1.grieu.fr). With the primes large enough and the third chosen independently of $p$ and $q$, no known method to factorize $n$ from the stated givens would succeed.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How to decrypt a RSA plaintext given a public exponent e and a RSA modulus n

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.