Subject: Re: Bigger DSA keys

From: [email-masked] ("Hal Finney")
Date: Mon, 19 Sep 2005 18:44:29 -0700 (PDT)

As far as the issue of generating large DSA keys, a good algorithm to
use is the following.  First generate an appropriately sized subgroup
prime q (160, 224, or 256 bits respectively).  Then search for a prime
modulus p of the required size (1024, 2048 or 3072 bits) such that p is
one more than a multiple of q.

The trick is to make that second search fast.  Typically a fast prime
search is done in two phases: first sieving out multiples of small primes
to identify prime candidates, then a slower probabilistic primality test
to find a good prime.  The key for DSA keys is that sieving can still
be used even when looking for primes which are of the form qk+1.

Usually when sieving is done, the method already takes into consideration
that the prime must be odd.  So it already adjusts for the fact that the
number is of the form 2k+1.  The same basic approach works for primes
of the form qk+1 as well.  Since q is relatively prime to all of the
primes being sieved by, for a prime "j" we will eliminate every jth item.
The only question is where is the starting point for eliminating such
items in the sieve.  This comes down to computing q mod j.  Doing this
one extra step for each prime j being sieved by, allows the basic sieve
concept to still be used.

This method allows DSA primes to be found about as quickly as ordinary
primes of the same size.  The extra time to find the q prime is small,
and the sieve can run about as fast.  So generating such large primes
is not particularly costly or difficult.

In contrast, finding "strong" primes p such that (p-1)/2 is also prime
does tend to be slow.  I think there is a trick to do it using a double
sieve but it is still much slower than finding regular primes.  DSA
primes do not suffer from this deficiency.

Hal

---

From: Adam Back <[email-masked]>
Date: Tue, 20 Sep 2005 04:34:38 -0400

Could one not use the Lim Lee safe prime generation method for DSA?

It has significant speed advantages.

Adam

---

From: [email-masked] (Daniel A. Nagy)
Date: Tue, 20 Sep 2005 10:54:32 +0200

> It has significant speed advantages.

DSS explicitly specifies how to generate primes for DSA keys. It can be
easily generalized for larger keys and other hash functions, and its
reasonable to assume that the new DSS will do that.

My estimates were based on that specification.

-- 
Daniel

---

From: Werner Koch <[email-masked]>
Date: Tue, 20 Sep 2005 11:34:16 +0200

> reasonable to assume that the new DSS will do that.

FWIW, the Lim & Lee algorithm is newer than DSS.  It was published in
Crypto 97 whereas FIPS 186 was published in 1994.

Salam-Shalom,

   Werner

---

From: Ben Laurie <[email-masked]>
Date: Wed, 21 Sep 2005 13:24:20 +0100

Hal Finney wrote:
> sieve but it is still much slower than finding regular primes.

There is - Geoff Thorpe and I planned to implement it for OpenSSL, but 
never got around to it.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

---

From: Ben Laurie <[email-masked]>
Date: Wed, 21 Sep 2005 13:48:24 +0100

> My estimates were based on that specification.

You only have to follow DSS if you want FIPS-140 and the like, of course.