Re: [TLS] MODP group modulus derivation [was: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups?]

[Peter Gutmann <pgut001%cs.auckland.ac.nz@localhost>]

Daniel Kahn Gillmor <dkg%fifthhorseman.net@localhost> writes:

>More colloquially, this is: 64 bits of 0xFF, followed by (k-128) bits of pi,
>followed by 64 more bits of 0xFF.  I don't know why this sequence was
>selected.  Does anyone have any pointers to reasons you might want the
>modulus structured this way?

    The prime for this group was selected to have certain properties.  The high
    order 64 bits are forced to 1.  This helps the classical remainder
    algorithm, because the trial quotient digit can always be taken as the high
    order word of the dividend, possibly +1.  The low order 64 bits are forced
    to 1.  This helps the Montgomery-style remainder algorithms, because the
    multiplier digit can always be taken to be the low order word of the
    dividend.  The middle bits are taken from the binary expansion of pi.  This
    guarantees that they are effectively random, while avoiding any suspicion
    that the primes have secretly been selected to be weak.

    The prime is chosen to be a Sophie-Germain prime (i.e., (P-1)/2 is also
    prime), to have the maximum strength against the square-root attack.  The
    starting trial numbers were repeatedly incremented by 2^64 until suitable
    primes were located.

    Because this prime is congruent to 7 (mod 8), 2 is a quadratic residue.
    All powers of 2 will also be quadratic residues. This prevents an opponent
    from learning the low order bit of the Diffie-Hellman exponent.  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.]

This is from an early Oakley draft draft-ietf-ipsec-isakmp-oakley-03.txt that
references another Oakley draft draft-ietf-ipsec-oakley-01.txt which, however,
doesn't actually contain the text quoted above.  So I guess the reference
would be [Citation needed ^ 2] or [Apocryphal ^ 2].

(Oh, and if anyone feels like confirming the SHA-1 hashes of the primes I
posted last week....).

Peter.