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) 2159 < q < 2160; that is, q is a 160-bit prime;
  • (ii) 2l~ 1 < p < 2L 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 < 264 to 160-bit hash-codes. Where required, an integer x in the range 0 < x < 29 whose binary representation is x = xg-i29 1 + xg_229-2 + • • • + хг22 + x2 + x0 should be converted to the <7-bit sequence (x9_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 29).
  • 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 29).
  • 4.2 For the integer W defined below, let X = W + 2L_1. (X is an L-bit integer.)

W = V0 + иг2100 + V22320 + • • ■ + К-гг[1] [2] [3] [4]*[5]"-[2]) + (Vn mod 2b)2160n.

  • 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 ij -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.
 
Source
< Prev   CONTENTS   Source   Next >