2
$\begingroup$

I've heard that textbook RSA is insecure when decryption exponent $d$ is smaller than $N^{1/4}$ where $N$ is the public modulus. Why is it the case and what would be a simple explanation of the attack ?

$\endgroup$

1 Answer 1

2
$\begingroup$

RSA without proper padding using randomness (plain old RSA) is not to be used in practice, and the attacks on small exponents assume plain old RSA, or a means of getting past the padding, such as the so-called million message attack.

The original attack on plain old RSA using such small exponents was due to Wiener. There has been further work showing that an even larger $d$ than $d>N^{1/4}$ is required, such as work by Maitra and Sarkar.

In addition, please see the extensive discussion in the question RSA with small exponents.

$\endgroup$
1
  • 2
    $\begingroup$ Is it possible for you to briefly outline the Wiener attack ? $\endgroup$
    – SpiderRico
    Apr 16, 2017 at 8:05

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.