0
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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

in this link you'll get full explanation

$\endgroup$
1
  • 1
    $\begingroup$ 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. 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. $\endgroup$
    – fgrieu
    Jan 15, 2023 at 20:12

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.