nist关于rsa中p,q的要求

NIST.FIPS.186-4

美国国家标准与技术研究院（National Institute of Standards and Technology，NIST）

FIPS,美国联邦信息处理标准（Federal Information Processing Standard）

Criteria for IFC Key Pairs

B.3.1 Criteria for IFC Key Pairs

Key pairs for IFC consist of a public key ( n , e ), and a private key ( n , d ), where n is the modulus

and is the product of two prime numbers p and q . The security of IFC depends on the quality and

secrecy of these primes and the private exponent d . The primes p and q shall be generated using 51

one of the following methods:

A. Both p and q are randomly generated prime numbers (Random Primes), where p and q

shall both be either :

1. Provable primes (see Appendix B.3.2), or

2. Probable primes (see Appendix B.3.3).

Using methods 1 and 2, p and q with lengths of 1024 or 1536 bits may be generated; p

and q with lengths of 512 bits shall not be generated using these methods. Instead, p

and q with lengths of 512 bits shall be generated using the conditions based on auxiliary

primes (see Appendices B.3.4, B.3.5, or B.3.6).

B. Both p and q are randomly generated prime numbers that satisfy the following additional

conditions (Primes with Conditions):

• ( p –1) has a prime factor p 1

• ( p +1) has a prime factor p 2

• ( q –1) has a prime factor q 1

• ( q +1) has a prime factor q 2

where p 1 , p 2 , q 1 and q 2 are called auxiliary primes of p and q .

Using this method, one of the following cases shall apply:

1. The primes p 1 , p 2 , q 1 , q 2 , p and q shall all be provable primes (see Appendix

B.3.4),

2. The primes p 1 , p 2 , q 1 and q 2 shall be provable primes, and the primes p and q

shall be probable primes (see Appendix B.3.5), or

3 The primes p 1 , p 2 , q 1 , q 2 , p and q shall all be probable primes (see Appendix

B.3.6).

The minimum lengths for each of the auxiliary primes p 1 , p 2 , q 1 and q 2 are dependent on

nlen , where nlen is the length of the modulus n in bits. Note that nlen is also called the

key size. The lengths of the auxiliary primes may be fixed or randomly chosen, subject to

the restrictions in Table B.1. The maximum length is determined by nlen (the sum of the

length of each auxiliary prime pair) and whether the primes p and q are probable primes

or provable primes (e.g., for the auxiliary prime pair p 1 and p 2 , len ( p 1 ) + len ( p 2 ) shall be

less than a value determined by nlen , whether p 1 and p 2 are generated to be probable or

provable primes) 3 .

3

In addition, all IFC keys shall meet the following criteria in order to conform to FIPS 186-4:

1. The public exponent e shall be selected with the following constraints:

(a) The public verification exponent e shall be selected prior to generating the primes

p and q , and the private signature exponent d .

(b) The exponent e shall be an odd positive integer such that:

2 16 < e < 2 256 .

Note that the value of e may be any value that meets constraint 1(b), i.e., e may be

either a fixed value or a random value.

2. The primes p and q shall be selected with the following constraints:

(a) ( p –1) and ( q –1) shall be relatively prime to the public exponent e .

(b) The private prime factor p shall be selected randomly and shall satisfy

and len ( q ). In each case, len ( p ) = len ( q ) = nlen /2. 53

( 2 )(2 ( nlen / 2) – 1 ) ≤ p ≤ (2 nlen / 2 – 1), where nlen is the appropriate length for the

desired security_strength .

(c) The private prime factor q shall be selected randomly and shall satisfy

( 2 )(2 ( nlen / 2) – 1 ) ≤ q ≤ (2 nlen / 2 – 1), where nlen is the appropriate length for the

desired security_strength .

(d) | p – q | > 2 ( nlen / 2) – 100 .

3. The private signature exponent d shall be selected with the following constraints after the

generation of p and q :

(a) The exponent d shall be a positive integer value such that

2 nlen / 2 < d < LCM( p –1, q –1), and

(b) d = e^  –1 mod (LCM( p –1, q –1)).

That is, the inequality in (a) holds, and 1 ≡ ( ed ) (mod LCM( p –1, q –1)).

In the extremely rare event that d ≤ 2 nlen / 2 , then new values for p , q and d shall be

determined. A different value of e may be used, although this is not required.

Any hash function used during the generation of the key pair shall be approved (i.e., specified in

FIPS 180).

 1,

• ( p –1) has a prime factor p 1

• ( p +1) has a prime factor p 2

• ( q –1) has a prime factor q 1

• ( q +1) has a prime factor q 2

这些数都应含有大的素因子以对抗光滑数分解(Pollard's p-1,Williams's p+1)。

2， | p – q | > 2 ( nlen / 2) – 100 .p和q具有足够的距离以对抗费马分解。

3，计算逆元的模用的LCM( p –1, q –1)，并非常见的n的欧拉函数。

4，2 nlen / 2 < d < LCM( p –1, q –1)，也规定了d的范围，一般来说d是接近的n的，很难被爆破。