# NIST method for generating DSA primes

Some public-key schemes require primes satisfying various specific conditions. For example, the NIST Digital Signature Algorithm (DSA of §11.5.1) requires two primes p and *q *satisfying the following three conditions:

- (i) 2
^{159}<*q <*2^{160}; that is,*q*is a 160-bit prime; - (ii)
*2*^{l}~^{1}< p < 2^{L}for a specified*L,*where*L*= 512 + 64/ for some 0 < / < 8; and - (iii)
*q*divides p - 1.

This section presents an algorithm for generating such primes p and *q.* In the following, *H* denotes the SHA-1 hash function (Algorithm 9.53) which maps bitstrings of bitlength < 2^{64} to 160-bit hash-codes. Where required, an integer *x* in the range 0 < *x < 2** ^{9}* whose binary representation is

*x*=

*x*

_{g}-i*2*1 + x

^{9}_{g}_22

^{9-2}+ • • • + хг2

^{2}+

*x*

*2*

*+ x*

*should be converted to the <7-bit sequence (x*

_{0}_{9}_ix

_{(;}_2 • • •

*x^xixo),*and vice versa.

4.56 Algorithm NIST method for generating DSA primes INPUT: an integer *l,* 0 < *l* < 8.

OUTPUT: a 160-bit prime *q* and an L-bit prime *p,* where *L =* 512 + 64/ and *q(p* - 1).

- 1. Compute
*L =*512 + 64/. Using long division of (L - 1) by 160, find n,*b*such that*L —*1 = 160rc +*b,*where 0**160.** - 2. Repeat the following:
- 2.1 Choose a random seed
*s*(not necessarily secret) of bitlength*g >*160. - 2.2 Compute
*U = H(s)®H((s*+ 1) mod 2^{9}). - 2.3 Form
*q*from*U*by setting to 1 the most significant and least significant bits of*U.*(Note that*q*is a 160-bit odd integer.) - 2.4 Test
*q*for primality using MILLER-RABIN(g,f) for*t*> 18 (see Note 4.57). Until*q*is found to be a (probable) prime. - 3. Set
*ii*—0,*ji*—2. - 4. While
*i*< 4096 do the following: - 4.1 For
*к*from 0 to*n*do the following: set*Vk<—H((s*+*j + k)*mod 2^{9}). - 4.2 For the integer
*W*defined below, let*X = W*+ 2^{L_1}. (*X*is an L-bit integer.)

*
*

*W = V*_{0}* +* и_{г}2^{100} + *V** _{2}2^{320}* + • • ■ + К-гг

^{[1]}

^{[2]}

^{[3]}

^{[4]}*

^{[5]}"-

^{[2]}) +

*(V*mod 2

_{n}^{b})2

^{160n}.

- 4.3 Computec =
*X*mod*2q*and set*p*=*X -*(c—1). (Note that*p*= 1 (mod 2*q).)* - 4.4 If
*p > 2*^{[2]}~^{[2]}then do the following:

Test *p* for primality using MILLER-RABIN(p,f) for *t >* 5 (see Note 4.57). If *p* is a (probable) prime then return^,p).

- 4.5 Set
*ii—i*4- 1,*j i*—*j*-T*n*+ 1. - 5. Go to step 2.

- [1] 4.57 Note (choice of primality test in Algorithm 4.56)
- [2] The FIPS 186 document where Algorithm 4.56 was originally described only specifies that a robust primality test be used in steps 2.4 and 4.4, i.e., a primality test wherethe probability of a composite integer being declared prime is at most (|)80. If theheuristic assumption is made that q is a randomly chosen 160-bit integer then, by Table 4.4, MILLER-RABINL/,18) is a robust test for the primality of q. If p is assumedto be a randomly chosen L-bit integer, then by Table 4.4, MILLER-RABIN(p,5) isa robust test for the primality of p. Since the Miller-Rabin test is a probabilistic primality test, the output of Algorithm 4.56 is a probable prime.
- [3] (ii) To improve performance, candidate primes q and p should be subjected to trial division by all odd primes less than some bound В before invoking the Miller-Rabin test.See Note 4.45 for guidance on selecting B.
- [4] 4.58 Note (“weak” primes cannot be intentionally constructed) Algorithm 4.56 has the featurethat the random seed s is not input to the prime number generation portion of the algorithmitself, but rather to an unpredictable and uncontrollable randomization process (steps 2.2
- [5] and 4.1), the output of which is used as the actual random seed. This precludes manipulationof the input seed to the prime number generation. If the seed s and counter i are made public,then anyone can verify that q and p were generated using the approved method. This featureprevents a central authority who generates p and q as system-wide parameters for use in theDSA from intentionally constructing “weak” primes q and p which it could subsequentlyexploit to recover other entities’ private keys.
- [6] The FIPS 186 document where Algorithm 4.56 was originally described only specifies that a robust primality test be used in steps 2.4 and 4.4, i.e., a primality test wherethe probability of a composite integer being declared prime is at most (|)80. If theheuristic assumption is made that q is a randomly chosen 160-bit integer then, by Table 4.4, MILLER-RABINL/,18) is a robust test for the primality of q. If p is assumedto be a randomly chosen L-bit integer, then by Table 4.4, MILLER-RABIN(p,5) isa robust test for the primality of p. Since the Miller-Rabin test is a probabilistic primality test, the output of Algorithm 4.56 is a probable prime.
- [7] The FIPS 186 document where Algorithm 4.56 was originally described only specifies that a robust primality test be used in steps 2.4 and 4.4, i.e., a primality test wherethe probability of a composite integer being declared prime is at most (|)80. If theheuristic assumption is made that q is a randomly chosen 160-bit integer then, by Table 4.4, MILLER-RABINL/,18) is a robust test for the primality of q. If p is assumedto be a randomly chosen L-bit integer, then by Table 4.4, MILLER-RABIN(p,5) isa robust test for the primality of p. Since the Miller-Rabin test is a probabilistic primality test, the output of Algorithm 4.56 is a probable prime.
- [8] The FIPS 186 document where Algorithm 4.56 was originally described only specifies that a robust primality test be used in steps 2.4 and 4.4, i.e., a primality test wherethe probability of a composite integer being declared prime is at most (|)80. If theheuristic assumption is made that q is a randomly chosen 160-bit integer then, by Table 4.4, MILLER-RABINL/,18) is a robust test for the primality of q. If p is assumedto be a randomly chosen L-bit integer, then by Table 4.4, MILLER-RABIN(p,5) isa robust test for the primality of p. Since the Miller-Rabin test is a probabilistic primality test, the output of Algorithm 4.56 is a probable prime.