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