Exponent 3 damage spreads...

[Steven M. Bellovin]

On Thu, 21 Sep 2006 07:00:03 -0400, "Whyte, William" <WWhyte at ntru.com>
wrote:

> > Similarly, the thousands of words of nitpicking standards, bashing ASN.1, and
> > so on ad nauseum, can be eliminated entirely by following one simple rule:
> > 
> >   Don't use e=3
> 
> I'd extend it to "don't use e <= 17". The PKCS#1 attack will work with
> e = 17, SHA-512 and RSA-15360, and someone's bound to implement RSA-15360
> somewhere to claim 256-bit security.


NIST's draft revision of FIPS 186-3 says

   (b) The exponent e shall be an odd positive integer such that
           65,537 <= e < 2**(nlen - 2*security_strength)
       where nlen is the length of the modulus n in bits.

The security_strength is the work factor for brute force attack on the
corresponding symmetric cipher or hash function, i.e., 128 for SHA-256.


		--Steven M. Bellovin, http://www.cs.columbia.edu/~smb

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