Search code examples
primesdsa

DSA: How to generate the subprime?

Lately I did a bit of research about the Digital Signature Algorithm and how it works. My question according to this is of no practical matter for me but of pure interest.

However, I'm curious how to generate the subprime in DSA: Somewhere during the generation of the parameters for the algorithm one chooses a 1024-bit prime p. The next step is to find a 160-bit prime q which is a divisor of p-1. That's where I get stuck. I have no idea how to find that subprime q in time, without having to wait forever. I also couldn't find any documentation about that particular part of DSA on the internet and all the example implementations I've found use library functions to create the parameters.

Does anyone know more about that subprime generation or can lead me to a place where I can read about it?

Thanks in advance.

Solution

  • As suggested by Zoredache: The algorithm to create the pair of primes p and q for DSA, found in the Digital Signature Standard.

    Let L-1 = 160*n + b, where b,n ∈ ℕ and 0 ≤ b < 160

    1. Choose a random number seed > 2¹⁶⁰. Let g be the length of seed in bits.
    2. U = sha(seed) XOR sha(seed+1 mod 2^g) (where sha is the Secure Hash Algorithm)
    3. q = U OR 2¹⁵⁹ OR 1
    4. Test if q is prime, if not go to step 1.
    5. counter = 0, offset = 2
    6. For k = 0,...,n: V_k = sha((seed + offset + k) mod 2^g)
    7. W = V_0 + V_1 * 2^160 + ... + V_(n-1) * 2^((n-1)*160) + (V_n mod 2^b) * 2^(n*160)
    8. X = W + 2^(L-1)
    9. c = X mod 2*q
    10. p = X - (c-1)
    11. If p < 2^(L-1) go to step 13.
    12. Test if p is prime, if so go to step 15.
    13. counter = counter + 1, offset = offset + n + 1
    14. If counter >= 4096 go to step 1, if not go to step 7.
    15. We have now p and q so that q is a divisor of p-1.

    I hope I did not get anything wrong. I didn't understand everything completely yet but the major trick is to calculate p out of q instead of trying the opposite thing.