Key generation in Digital Signature Algorithm

In DSA, one needs to generate two primes $p$ and $q$ such that $q$ is $256$-bit and $p$ is $3072$-bit and $p-1$ is a multiple of $q$.

Question: How to generate such $p$ and $q$.

Attempt: First, use a random number generator to generate $256$-bit number, say $q$. Then test whether it is a prime. If it is not, generate again until a prime is obtained.

After that, generate a random number $\alpha$ such that $\alpha$ is $(3072-256)=2816$ bits and $\alpha q +1$. Test whether $\alpha q+1$ is prime. If it is not, then generate $\alpha$ again. If yes, then we are done as we have two primes $p$ and $q$ which satisfy the conditions above.

Does the key generation above work?

• The exact algorithm for generating the primes is specified in the DSS NIST FIPS 186-4 nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf – Henrick Hellström Nov 17 '14 at 14:42
• One issue with the proposed algorithm is that the $p$ generated will often be $3071$- bit rather than $3072$-bit, a stated requirement. Also, as pointed by Henrick Hellström, if you want DSA per the U.S. Department of Commerce's book, then appendix A.1 is a must; also, following that procedure ensures the parameters are not cooked in some way; $p$ and $q$ essentially become nothing-up-my-sleeve. – fgrieu Nov 17 '14 at 16:09

1 Answer

As the comments are quite spot-on, I shall just reproduce them and say that you should just follow the relevant standard which is FIPS 186-4 appendix A.1, which expands upon your intuition.

The exact algorithm for generating the primes is specified in the DSS NIST FIPS 186-4 [(PDF)] – Henrick Hellström

and

One issue with the proposed algorithm is that the p generated will often be 3071- bit rather than 3072-bit, a stated requirement. Also, as pointed by Henrick Hellström, if you want DSA per the U.S. Department of Commerce's book, then appendix A.1 [(PDF)] is a must; also, following that procedure ensures the parameters are not cooked in some way; p and q essentially become nothing-up-my-sleeve. – fgrieu