[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: ietf-openpgp@xxxxxxx*Subject*: Re: Bigger DSA keys*From*: hal@xxxxxxxxxx ("Hal Finney")*Date*: Mon, 19 Sep 2005 18:44:29 -0700 (PDT)*List-archive*: <http://www.imc.org/ietf-openpgp/mail-archive/>*List-id*: <ietf-openpgp.imc.org>*List-unsubscribe*: <mailto:ietf-openpgp-request@imc.org?body=unsubscribe>*Sender*: owner-ietf-openpgp@xxxxxxxxxxxx

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

**Follow-Ups**:**Re: Bigger DSA keys***From:*Adam Back

**Re: Bigger DSA keys***From:*Ben Laurie

- Prev by Date:
**Interop grill-off** - Next by Date:
**Problems with v4 key packet format** - Previous by thread:
**Re: Bigger DSA keys** - Next by thread:
**Re: Bigger DSA keys** - Index(es):