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 ?


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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.