APPENDIX 2. GENERATION OF PRIMES FOR THE DSA
This appendix includes algorithms for generating the primes p and q used in the DSA. These algorithms require a random number generator (see Appendix 3), and an efficient modular exponentiation algorithm. Generation of p and q shall be performed as specified in this appendix, or using other FIPS approved security methods.
2.1. A PROBABILISTIC PRIMALITY TEST
In order to generate the primes p and q, a primality test is required.
There are several fast probabilistic algorithms available. The following algorithm is a simplified version of a procedure due to M.O. Rabin, based in part on ideas of Gary L. Miller. [See Knuth, The Art of Computer Programming, Vol. 2, Addison-Wesley, 1981, Algorithm P, page 379.] If this algorithm is iterated n times, it will produce a false prime with probability no greater than 1/4n. Therefore, n ≥ 50 will give an acceptable probability of error. To test whether an integer is prime:
- Step 1. Set i = 1 and n ≥ 50.
- Step 2. Set w = the integer to be tested, w = 1 + 2am, where m is odd and 2a is the largest power of 2 dividing w - 1.
- Step 3. Generate a random integer b in the range 1 < b < w.
- Step 4. Set j = 0 and z = bm mod w.
- Step 5. If j = 0 and z = 1, or if z = w - 1, go to step 9.
- Step 6. If j > 0 and z = 1, go to step 8.
- Step 7. j = j + 1. If j < a, set z = z2 mod w and go to step 5.
- Step 8. w is not prime. Stop.
- Step 9. If i < n, set i = i + 1 and go to step 3. Otherwise, w is probably prime.
2.2. GENERATION OF PRIMES
The DSA requires two primes, p and q, satisfying the following three conditions:
- 2159 < q < 2160
- 2L-1 < p < 2L for a specified L, where L = 512 + 64j for some 0 ≤ j ≤ 8
13
