0
$\begingroup$

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?

| improve this question | | | | |
$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Henrick Hellström Nov 17 '14 at 14:42
  • $\begingroup$ 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. $\endgroup$ – fgrieu Nov 17 '14 at 16:09
1
$\begingroup$

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

| improve this answer | | | | |
$\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.