[1459] in cryptography@c2.net mail archive
Re: Speeding up DH
daemon@ATHENA.MIT.EDU (Colin Plumb)
Wed Sep 10 14:12:02 1997
Date: Wed, 10 Sep 1997 11:06:51 -0600 (MDT)
From: Colin Plumb <colin@nyx.net>
To: colin@nyx.net, cryptography@c2.net, dpj@world.std.com,
frantz@communities.com
I wrote:
>> If p-1 is divisible by k, for any small factor k, then x mod k is
>> revealed, assuming g is a generator. Choosing g not a generator is
>> equivalent to choosing x a multiple of k (for some divisors k),
>> so it renders the leak useless. ...
And David Jablon clarified:
> Choosing g as "not a generator" of the full group
> may be insufficient to stop all leaks;
> g must specifically be of order (p-1)/k.
> A simple way to get one is to use g=g_0^k
> for any g_0, as long as g <> 1.
That's what I meant, but the meaning was buried in the parenthetical
comment "(for some divisors k)". Thanks, David, for clarifying.
The other thing that was confusing was my reference to PGP5 using an
exponent length of 3*80=240 bits. That's based on a value of 80 bits
as the work factor of breaking a 1024-bit exponent, which is
approximately correct. The actual code knows the "correct"
exponent length to balance the attack difficulty with the modulus size,
and it actually uses one 1.5 times as long for paranoia's sake.
It's not hard-coded at 240 bits!
--
-Colin
