[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Proposal for new DH Groups 6, 7, and 8
Alexey Kirichenko writes:
> At 21:52 6.2.2000 +0200, Tero Kivinen wrote:
> >I think those primes should be generated in the same way the primes
> >currently in the IKE are generated, i.e to have format of
> >
> >p = 2^n - 2^(n-64) - 1 + (floor(Pi*2^(n-130)) + t)*2^64,
>
> What's so great about this format ? I'd love (but would be very
> surprised) to see any proofs/arguments of useful properties
> of primes generated in the specified way. References ?
The reason for that format is explained in the RFC 2412 Appendix E as
I said in my previous email. Here is cut & paste of the relevant
parts:
----------------------------------------------------------------------
Network Working Group H. Orman
Request for Comments: 2412 Department of Computer Science
Category: Informational University of Arizona
November 1998
The OAKLEY Key Determination Protocol
...
APPENDIX E The Well-Known Groups
The group identifiers:
0 No group (used as a placeholder and for non-DH exchanges)
1 A modular exponentiation group with a 768 bit modulus
2 A modular exponentiation group with a 1024 bit modulus
3 A modular exponentiation group with a 1536 bit modulus (TBD)
4 An elliptic curve group over GF[2^155]
5 An elliptic curve group over GF[2^185]
values 2^31 and higher are used for private group identifiers
Richard Schroeppel performed all the mathematical and computational
work for this appendix.
Classical Diffie-Hellman Modular Exponentiation Groups
The primes for groups 1 and 2 were 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.
Because both primes are based on pi, there is a large section of
overlap in the hexadecimal representations of the two primes. The
primes are chosen to be Sophie Germain primes (i.e., (P-1)/2 is also
prime), to have the maximum strength against the square-root attack
on the discrete logarithm problem.
The starting trial numbers were repeatedly incremented by 2^64 until
suitable primes were located.
Because these two primes are congruent to 7 (mod 8), 2 is a quadratic
residue of each prime. All powers of 2 will also be quadratic
residues. This prevents an opponent from learning the low order bit
of the Diffie-Hellman exponent (AKA the subgroup confinement
problem). 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.]
...
--
kivinen@iki.fi Work : +358-9-4354 3218
SSH Communications Security http://www.ssh.fi/
SSH IPSEC Toolkit http://www.ssh.fi/ipsec/
References: