[374] in cryptography@c2.net mail archive
Comments wanted Re: DSA parameter generation
daemon@ATHENA.MIT.EDU (Colin Plumb)
Mon Mar 17 23:33:56 1997
Date: Mon, 17 Mar 97 19:01:59 MST
From: colin@nyx.net (Colin Plumb)
To: cryptography@c2.net
Cc: colin@nyx.net
I'm implementing a DSA system which allows the use of precomputed
prime parameters for fast key generation. Obviously, those parameters
must be generated in a way that is beyond reproach.
Now, the standard way is David Kravitz' "Kosherizer", but that
technique does not obviously generalize to subprimes q over
160 bits, which are required if you support key sizes p over
1024 bits.
(The argument for going over 1024 bits when SHA is only 80 bits secure
is that, in practice, a fully free collision attack is not practical,
so you have less than 80 bits on one side of the birthday attack and thus
SHA is, in practice, more like 160 than 80 bits secure.)
Now, it's important that such a technique be simple, so there are
few strange arbitrary parameters in the process which might be
manipulated to control the output.
The technique I'm thinking of is:
- Use Kravitz' technique for converting a seed string to a number
unmodified. This technique is:
If you consider 0 <= SHA(string) < 2^160, then to generate k bits,
generate as much of the infinite series SHA(seed) + SHA(seed+1) * 2^160 +
SHA(seed+2) * 2^320 + ... as is needed and take the result mod 2^k.
If the number has to be exactly k bits long, then set bit k-1 to make sure
that 2^(k-1) <= n < 2^k - 1.
I interpret the string as a big-endian number, to be consistent with
SHA, due to lack of guidance.
Kravitz' original technique generates q from SHA(seed) XOR SHA(seed+1)
and then uses seed+2 to generate q. this XOR business doesn't work so
well when generating a 170-bit q or whatever. Therefore, I propose:
- Generate q0 of the appropriate length using "seed". One option
I'm considering is to set additional high bits of q0 to make hash
collision attacks (finding X and Y so SHA(X) mod q = SHA(Y) mod q,
which is easier than finding SHA(x) = SHA(y) as long as y < 2^160)
more difficult.
- Let q be the next prime >= q0.
- Generate p0 using the same seed. Then let p be the next prime
congruent to 1 mod 2*q which is >= p0 - (p0 mod 2*q).
Kravitz keeps retrying with different seeds until he generates a prime,
whereas I find linear search easier to explain and I don't think it
introduces any weaknesses.
Note that the low-order bits of p0 and q0 are the same. This
is for simplicity of generation, and I believe it's defensible
on the grounds that ignoring (p0 mod 2*q) ignores those bits of
q0 anyway, so it doesn't matter that they're the same.
Um... does anyone have any comments or criticisms? Cryptographers are
exactly the folks this is intended to placate. I want a publicly documented
parameter-generation scheme that "obviously" prevents anyone,
particularly the generator, from generating any parameters with
any undocumented properties.
Oh, one minor esthetic problem with the Kravitz technique is that you
have to iterate trying seeds until you get a prime q. This means that
you can't choose a nice quotation as the seed and have it work.
The proposed seed is the same one that's been used before,
Whatever you do will be insignificant, but it is very important that you do it.
I have rambled, but I think everything important is in there.
Would anyone like to comment?
--
-Colin
