fermat primes and dnssec-keygen bug?

[Spain, Dr. Jeffry A.]

> I would recommend that dnssec-keygen starts ignoring the "-e" parameter that everyone has put in their scripts to prevent exponent 3 keys, who are not getting keys with exponent 4294967296 + 1 (F5)

> Alternatively, if this is done on purpose, I guess we should all migrate the 64 bit machines :)

As background, see the discussion of Fermat Numbers, e.g. F4 and F5, at http://en.wikipedia.org/wiki/Fermat_number. See also the role of the exponent in RSA public-key cryptography at http://en.wikipedia.org/wiki/RSA_(algorithm).

This is interesting, if I correctly understand your point, but it appears that dnssec-keygen computes F5 differently than you do in your example in http://code.google.com/p/go/issues/detail?can=2&start=0&num=100&q=&colspec=ID%20Status%20Stars%20Priority%20Owner%20Reporter%20Summary&groupby=&sort=&id=3161.

In your example:
	pubkey := new(rsa.PublicKey)
	pubkey.N = big.NewInt(0)
	pubkey.E = 4294967296 + 1
which results in 32-bit integer overflow.

In bind-9.9.0/lib/dns/opensslrsa_link.c, starting at line 750:
	if (exp == 0) {
		/* RSA_F4 0x10001 */
		BN_set_bit(e, 0);
		BN_set_bit(e, 16);
	} else {
		/* F5 0x100000001 */
		BN_set_bit(e, 0);
		BN_set_bit(e, 32);
	}
where exp is nonzero if option -e is set in the original call to dnssec-keygen and e is a BIGNUM pointer initialized as 'BIGNUM *e = BN_new();'. I would surmise that e is not subject to integer overflow in its representation of F5. The BIGNUM type is a component of OpenSSL. See http://www.openssl.org/docs/crypto/bn.html. According to this document it supports arbitrary precision integer arithmetic subject only to memory allocation limits with no indication of a dependency on 32-bit or 64-bit CPU architecture. If there is a problem, I think it would be with OpenSSL rather than dnssec-keygen.

Jeffry A. Spain
Network Administrator
Cincinnati Country Day School