Thursday, March 17, 2005

RFC 2409, RFC 3526, and "bad" generators

The two RFCs specify 2 as a generator for the prime Diffie-Hellman fields. However, 2 is not a generator: for example:

RFC 2409 - The Internet Key Exchange (IKE)

6.1 First Oakley Default Group

FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A63A3620FFFFFFFFFFFFFFFF

? p=2^768-2^704-1+2^64*(floor(2^638*pi)+149686)
%41 = 1552518092300708935130918131258481755631334049434514313202351194902966239949102107258669453876591642442910007680288864229150803718918046342632727613031282983744380820890196288509170691316593175367469551763119843371637221007210577919
? isprime(p)
%42 = 1
? j=2;
? (p-1)%j
%44 = 0
? q=(p-1)/j;
? isprime(q)
%46 = 1
? Mod(2,p)^q
%47 = Mod(1, 1552518092300708935130918131258481755631334049434514313202351194902966239949102107258669453876591642442910007680288864229150803718918046342632727613031282983744380820890196288509170691316593175367469551763119843371637221007210577919)
? znprimroot(p)
%48 = Mod(7, 1552518092300708935130918131258481755631334049434514313202351194902966239949102107258669453876591642442910007680288864229150803718918046342632727613031282983744380820890196288509170691316593175367469551763119843371637221007210577919)

The reason is buried Appendix E of RFC 2412 (uncited): " Using 2 as a generator is efficient for some modular exponentiation algorithms. [Note that 2 is technically not a generator in the number theory sense, because it omits half of the possible residues mod P. From a cryptographic viewpoint, this is a virtue.]"

One wonders why they didn't use a multiplier (instead of 149686) for which 2 really is a number-theoretic generator.

No comments :