fermat primes and dnssec-keygen bug?

[Spain, Dr. Jeffry A.]

> There's quite a bit about choosing e in this presentation:
> http://www.esiea-recherche.eu/Slides09/slides_iAWACS09_Erra-Grenier_How-to-compute-RSA-keys.pdf

> However, I don't understand the math, so I can't say whether any of the advice is reasonable :(

Interesting document, although I'm not a mathematician either. Slide 15 is the key, I think, saying in essence that there's no way to be certain that any given RSA key is secure. To be less uncertain about one's RSA keys, it suggests among other things reviewing recommendations from various national agencies. On slide 21 are some recommendations for the public key exponent: an odd integer not less than 65537 (Fermat number 4) and less than 2^256 (Fermat number 8 minus 1). Slide 23 describes a minor flaw when the exponent is greater than F4, but indicates that it is not a serious threat. Based on this document I don't see any reason to believe that exponent F4 (dnssec-keygen default) is any more or less secure than F5 (dnssec-keygen -e). Signature verification with exponent F5 would take more CPU time, but we don't have any benchmarking data to indicate whether or not this is significant.

Other posts have alluded to the Debian openssl flaw reported in May 2008 (http://www.debian.org/security/2008/dsa-1571). This led to predictable random primes being used to generate RSA moduli, and was not related to any specific public key exponent. It affected openssl version 0.9.8c-1, but only the Debian version.

Regards, Jeff.