3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are you effectively asking why the hash function is used instead of an arbitrary source of random numbers? $\endgroup$ – otus Jul 28 '16 at 6:43
  • 3
    $\begingroup$ 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. $\endgroup$ – SEJPM Jul 28 '16 at 9:47
  • $\begingroup$ @otus - that is correct. $\endgroup$ – neubert Jul 28 '16 at 14:08
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.