Digital Signature Standard (DSS)

Original publisher: Gaithersburg, MD: U.S. Dept. of Commerce, Technology Administration, Information Technology Laboratory, National Institute of Standards and Technology, [2000] OCLC Number: (OCoLC)73166668 Subject: Digital signatures. Excerpt: ... 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 n algorithm is iterated n times, it will produce a false prime with probability no greater than 1 / 4. 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. a a Step 2. Set w = the integer to be tested, w = 1 + 2 m, where m is odd and 2 is the largest power of 2 dividing w-1. Step 3. Generate a random integer b in the range 1 < b < w. m Step 4. Set j = 0 and z = b 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. 2 Step 7. j = j + 1. If j < a, set z = z 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: 159 160 a. 2 < q < 2 L-1 L b. 2 < p < 2 for a specified L, where L = 512 + 64j for some 0 ≤ j ≤ 8 13