# Why does FIPS 186-4 seem to have an excessively complex q generation?

So in DSA you have two primes - p and q. q is N bits long (let's assume 160 bits) and p is L bits long (let's assume 1024 bits).

Here's what FIPS 186-4 says about generating the q parameter for DSA:

1. Get an arbitrary sequence of seedlen bits as the domain_parameter_seed.
2. U = Hash (domain_parameter_seed) mod 2$^{N-1}$.
3. q = 2$^{N-1}$ + U + 1 – ( U mod 2).
4. Test whether or not q is prime as specified in Appendix C.3.
5. If q is not a prime, then go to step 5.

outlen is the length of the Hash output, in bits, and seedlen is any number > N.

What I'm wondering is... why not just replace steps 5, 6 and 7 with "get an arbitrary sequence of N bits as the q" and "make the least significant bit 1"?

2$^{N-1}$ gives you the lower bound on an N-sized variable. U adds the trailing N bytes of Hash(domain_parameter_seed) to 2$^{N-1}$ and "1 - (U mod 2)" makes the final number odd. So it seems like a poor-man's randomPrime(n-bits) function call.

• Are you effectively asking why the hash function is used instead of an arbitrary source of random numbers?
– otus
Jul 28 '16 at 6:43
• Possible explanation: The authors of the standard didn't want to trust the user's RNGs too much to give proper uniform randomness and thus used their trusted hash function to ensure uniform distribution.
– SEJPM
Jul 28 '16 at 9:47
• @otus - that is correct. Jul 28 '16 at 14:08

This is meant to allow domain_parameter_seed to be longer than 160 bits and to allow for the "verifiable canonical generation" of domain parameters described in Appendix A of the document you linked. See A.1.1.2 and A.2.3 in particular.

A truly random seed would be acceptable to use without hashing, but using a chosen number directly would be suspicious at least. Possibility of poor RNG may also be a consideration.