[1471] in cryptography@c2.net mail archive
Re: Speeding up DH
daemon@ATHENA.MIT.EDU (Colin Plumb)
Fri Sep 12 12:47:20 1997
Date: Fri, 12 Sep 1997 04:23:57 -0600 (MDT)
From: Colin Plumb <colin@nyx.net>
To: cryptography@c2.net, stewarts@ix.netcom.com
> At 08:33 PM 9/9/97 -0600, Colin Plumb wrote:
>> If you look in PGP 5, you'll see some precomputed primes with (p-1)/2
>> prime, and some on-the-fly code that generates p-1/2 = k*q for k "as
>> small as possible" while still ensuring that a multiple of q in the
>> right range will be prime. This bounds k small enough that the leakage
>> is contained within the paranoia padding, so we don't worry about
>> generator or not.
and Bill Stewart <stewarts@ix.netcom.com> replied:
> Is there any way to bully the user interface into making these visible?
> There are some primes that the Photuris people picked, for several
> useful sizes.
Well, you can generate the keys and look at them. Or read the source
code. They are not the Photuris keys, but generated by a documented
technique. Do you want me to post the bits here?
First, from the DSS key generation suggestion, using an SHA-based
n->m bit one-way function, by hashing the input to get the least significant
160 bits, incrementing it (as a big-endian array of bytes, propagating
carry), and hashing again to get the next-most significant 160 bits, etc.
I.e. for m bits seeded with x, form the number
SHA(x) + 2^160 * SHA(x+1) + 2^320 * SHA(x+2) + ...
and take it mod 2^m.
Then we set the two msbs, used that as a starting value p0, and the
first prime >= p0 which also had (p-1)/2 prime is the value chosen.
The seed "x" was the 79 ASCII bytes of the phrase:
Whatever you do will be insignificant, but it is very important that you do it.
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,
thinking of making attacks more difficult. I didn't consider the
modular reduction speedups.
> How fast is the calculation on a typical machine, compared to the
> rest of the calculations performed? Is 4x enough to be critical?
No, not critical, just nice. Timings for various modular exponentiations
with a 1024-bit modulus on a P5-133:
2^<1024> mod <1024> bits AVERAGE: 0.208 s
<1024>^<1024> mod <1024> bits AVERAGE: 0.248 s
<1024>^<1024> * <1024>^<1024> mod <1024> bits AVERAGE: 0.290 s
2^<240> mod <1024> bits AVERAGE: 0.047 s
<1024>^<240> mod <1024> bits AVERAGE: 0.062 s
<1024>^<240> * <1024>^<240> mod <1024> bits AVERAGE: 0.075 s
It makes things more pleasat to use. And sometimes people build servers
that need to do this a *lot*. (And then they go and design protocols
like SET to run on them and wonder why Intel stock goes up...)
Um, what other calculations? There ain't much more to the public-key
part, and the rest is dependent on the size of the message, so it
varies. The data compression is quite expensive.
--
-Colin
