question about rsa encryption

[Whyte, William]

> That brings on another amateur question. In that article it says,
> "If the public exponent is less than a quarter of the modulus, RSA
> can be insecure."
> 
> Well, the public exponents I've seen range from 17 to 65537. What
> gives? Is this just one of the many weaknesses mitigated by proper
> padding?

This should probably refer to the private exponent. Weiner's
continued fraction attack (from
http://www3.sympatico.ca/wienerfamily/Michael/MichaelPapers/ShortSecretExpon
ents.pdf)
recovers the private exponent if it's known to be less than
a quarter the length of the modulus (if the factors of the
modulus are approximately the same size and other reasonable
conditions are met).

More recently, Dan Boneh and Glenn Durfee described a lattice
attack: to prevent this, the length of the private exponent must 
be at least (1 - sqrt(2)) times the length of the modulus.
http://crypto.stanford.edu/~dabo/abstracts/lowRSAexp.html
Nick Howgrave-Graham gave some arguments at CaLC 2001 as to why
this attack probably isn't going to get any better.

There's a really good survey of attacks on the RSA cryptosystem
at http://crypto.stanford.edu/~dabo/abstracts/RSAattack-survey.html
which should help too.

Cheers,

William

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com