[1487] in cryptography@c2.net mail archive
Re: Speeding up DH
daemon@ATHENA.MIT.EDU (Bill Frantz)
Mon Sep 15 14:22:40 1997
In-Reply-To: <m0x9oJa-000HRHC@laptop.ka9q.ampr.org>
Date: Sun, 14 Sep 1997 23:15:23 -0700
To: Phil Karn <karn@qualcomm.com>, colin@nyx.net
From: Bill Frantz <frantz@netcom.com>
Cc: cryptography@c2.net, stewarts@ix.netcom.com, karn@qualcomm.com
At 2:16 AM -0700 9/13/97, Phil Karn wrote:
>>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,
>
>The DH moduli I generated for Photuris a while back used random() to
>generate a random starting point, and then searched forward from that
>point using an overlaid sieve to find the first prime p for which
>(p-1)/2 was also prime. I suppose it would have been better to pick an
>"open" starting point, but I didn't know that it was possible to pick
>a "devious" DH moduli -- is it?
>
>I didn't manually set any bits, other than to make the msb and lsb both 1 :-).
I used Java's java.math.BigInteger function to get a 1023 bit prime. I
then doubled it, added one and checked the result for primality. I then
went looking for generators using the algorithm in Applied Cryptography. I
found that performance was 20-30% better with 2 as a generator than it was
with any of the odd numbers that Colin Plumb's big integer library handles
directly with ModExp. (Javasoft's BigInteger class uses Colin's library
"under the covers".)
It looks kind of like:
BigInteger factor = new BigInteger(1023, 100, new SecureRandom());
BigInteger modulus = factor.shiftleft(1);
modulus = modulus.add(new BigInteger("1");
if (modulus(isProbabalPrime(100))) ... etc.
-------------------------------------------------------------------------
Bill Frantz | The Internet was designed | Periwinkle -- Consulting
(408)356-8506 | to protect the free world | 16345 Englewood Ave.
frantz@netcom.com | from hostile governments. | Los Gatos, CA 95032, USA
