[1483] in cryptography@c2.net mail archive
Re: Speeding up DH
daemon@ATHENA.MIT.EDU (William Allen Simpson)
Mon Sep 15 13:43:47 1997
Date: Mon, 15 Sep 97 14:21:18 GMT
From: "William Allen Simpson" <wsimpson@greendragon.com>
To: cryptography@c2.net
> From: Phil Karn <karn@qualcomm.com>
> >The Photuris criteria (that's the one with the 64 msbs and lsbs set to
> >1, isn't it?) are nice, and I might have used them if I'd though of it,
> >but I wanted to have a few published criteria and then use a one-way
> >function to document the lack of hidden properties in the primes
> >chosen. The furthest out on a limb I went was to set the two msbs to 1,
>
> I didn't manually set any bits, other than to make the msb and lsb both 1 :-).
>
Originally, Photuris had specified well-known primes. But, a hew and
cry was raised that this gave a target for crackers. Now, Photuris uses
variable primes, which are generated by the operators. The implementors'
draft includes Karn's prime generation code so that everyone can
generate their own primes. And I'm working on a DHCP draft for dynamic
distribution of the primes to lesser endowed boxen.
The prime that the first writer (Colin Plumb) is thinking of was in "The
resolution of ISAKMP with Oakley":
Oakley implementations MUST support a MODP group with the following
prime and generator. This group is assigned id 1 (one).
The prime is: 2^768 - 2 ^704 - 1 + 2^64 * { [2^638 pi] + 149686 }
Its hexadecimal value is
FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
E485B576 625E7EC6 F44C42E9 A63A3620 FFFFFFFF FFFFFFFF
The generator is: 2.
other groups can be defined using Oakley New Group Mode. This default
group was generated by Richard Schroeppel at the University of
Arizona. Properties of this prime are described by the following
exerpt from [Orm96]:
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.]
[Comment from Simpson: the above text DOES NOT appear anywhere in Orm96,
so there is some fudging going on.... And the text is slightly wrong,
as this prime is "safe" and (p-1)/2 is "Sophie-Germain". Probably a
problem in translation from Schroeppel's French.]
WSimpson@UMich.edu
Key fingerprint = 17 40 5E 67 15 6F 31 26 DD 0D B9 9B 6A 15 2C 32
BSimpson@MorningStar.com
Key fingerprint = 2E 07 23 03 C5 62 70 D3 59 B1 4F 5E 1D C2 C1 A2
