ANSI ASC X9 X9.80-2005 Prime Number Generation Primality Testing and Primality Certificates.pdf

1、 American National Standard for Financial Services X9.802005 Prime Number Generation, Primality Testing, and Primality Certificates Accredited Standards Committee X9, Incorporated Financial Industry Standards Date Approved: August 15, 2005 American National Standards Institute American National Stan

2、dards, Technical Reports and Guides developed through the Accredited Standards Committee X9, Inc., are copyrighted. Copying these documents for personal or commercial use outside X9 membership agreements is prohibited without express written permission of the Accredited Standards Committee X9, Inc.

3、For additional information please contact ASC X9, Inc., P.O. Box 4035, Annapolis, Maryland 21403. ANS X9.802005 ii ASC X9, Inc. 2005 All rights reserved Foreword Approval of an American National Standard requires verification by ANSI that the requirements for due process, consensus, and other criter

4、ia for approval have been met by the standards developer. Consensus is established when, in the judgment of the ANSI Board of Standards Review, substantial agreement has been reached by directly and materially affected interests. Substantial agreement means much more than a simple majority, but not

5、necessarily unanimity. Consensus requires that all views and objections be considered, and that a concerted effort be made toward their resolution. The use of American National Standards is completely voluntary; their existence does not in any respect preclude anyone, whether he has approved the sta

6、ndards or not from manufacturing, marketing, purchasing, or using products, processes, or procedures not conforming to the standards. The American National Standards Institute does not develop standards and will in no circumstances give an interpretation of any American National Standard. Moreover,

7、no person shall have the right or authority to issue an interpretation of an American National Standard in the name of the American National Standards Institute. Requests for interpretations should be addressed to the secretariat or sponsor whose name appears on the title page of this standard. CAUT

8、ION NOTICE: This American National Standard may be revised or withdrawn at any time. The procedures of the American National Standards Institute require that action be taken to reaffirm, revise, or withdraw this standard no later than five years from the date of approval. Published by Accredited Sta

9、ndards Committee X9, Incorporated Financial Industry Standards P.O. Box 4035 Annapolis, MD 21403 USA X9 Online http:/www.x9.org Copyright 2005 ASC X9, Inc. All rights reserved. No part of this publication may be reproduced in any form, in an electronic retrieval system or otherwise, without prior wr

10、itten permission of the publisher. Printed in the United States of America. ANS X9.802005 ASC X9, Inc. 2005 All rights reserved iiiContents Forewordii Tables.v Introductionvi 1 Scope 1 2 Normative references2 3 Terms and definitions .2 4 Symbols and abbreviated terms 4 5 Prime Generation Methods.5 5

11、.1 General Discussion .5 5.2 Generation of Primes Using Random Integers.7 5.2.1 Generation of Random Primes with Sequential Search 7 5.2.2 Generation of Random Primes with Uniform Distribution 8 5.2.3 Testing Using Probabilistic Methods 8 5.2.4 Testing Using Deterministic Methods .11 5.3 Constructiv

12、e Methods.16 5.3.1 Shawe-Taylors Algorithm 16 5.3.2 Maurers Algorithm17 5.4 Side Conditions for Generating Primes using Random Integers .19 6 Candidate Prime Testing Methods.20 7 Tables of Parameters 21 7.1 Rounds Required for Miller-Rabin if Followed by Lucas.21 7.2 Rounds Required for Frobenius-Gr

13、antham 21 Annex A (normative).23 A.1 Modular Exponentiation23 A.2 Jacobi Symbol .23 A.3 Sieve Procedure.25 A.4 Algorithms for Polynomial Arithmetic.26 A.5 Lucas Sequence 28 Annex B (informative) 30 B.1 Discussion of General Prime Proving Methods .30 B.2 Discussion of the Distribution of Randomly Cho

14、sen Primes .30 Annex C Summary of Changes from ANS X9.802001 (informative)31 C.1 Introduction31 C.2 Technical changes.31 C.2.1 Search Range for primes 31 C.2.2 Errors in Jacobi symbol algorithm 31 C.2.3 Range of bases in Miller-Rabin test.32 C.2.4 Perfect squares in Lucas test.32 C.2.5 Discriminants

15、 with Jacobi symbol 0 in Lucas test 32 C.2.6 Boundary conditions in Shawe-Taylors algorithm .32 C.3 Editorial issues 33 C.3.1 Random bit generators .33 ANS X9.802005 iv ASC X9, Inc. 2005 All rights reserved C.3.2 Failure probability .33 C.3.3 Lucas-Lehmer vs. Lucas.33 C.3.4 Reference for combining M

16、iller-Rabin and Lucas tests33 C.3.5 Versions of Shawe-Taylor.33 C.3.6 Binary expansions.33 C.3.7 Modulo p division in Lucas sequence algorithm .33 C.3.8 Negative numbers in Lucas sequence example 33 C.3.9 Added Interval34 Bibliography35 ANS X9.802005 ASC X9, Inc. 2005 All rights reserved vTables Tab

17、le 1: An ECPP certificate for p = 377681287. 16 Table 2: Rounds Required for Miller-Rabin . 21 Table 3: Rounds Required for Frobenius-Grantham . 21 ANS X9.802005 vi ASC X9, Inc. 2005 All rights reserved Introduction NOTE The users attention is called to the possibility that compliance with this stan

18、dard may require use of an invention covered by patent rights. By publication of this standard, no position is taken with respect to the validity of this claim or of any patent rights in connection therewith. The patent holder has, however, filed a statement of willingness to grant a license under t

19、hese rights on reasonable and nondiscriminatory terms and conditions to applicants desiring to obtain such a license. Details may be obtained from the standards developer. Suggestions for the improvement or revision of this Standard are welcome. They should be sent to the X9 Committee Secretariat, A

20、ccredited Standards Committee X9, Inc., Financial Industry Standards, P.O. Box 4035, Annapolis, MD 21403 USA. This Standard was processed and approved for submittal to ANSI by the Accredited Standards Committee on Financial Services, X9. Committee approval of the Standard does not necessarily imply

21、that all the committee members voted for its approval. The X9 committee had the following members: Gene Kathol, X9 Chairman Vincent DeSantis, X9 Vice-Chairman Cynthia Fuller, Executive Director Isabel Bailey, Managing Director Organization Represented Representative ACI Worldwide Jim Shaffer America

22、n Bankers Association C. Diane Poole American Express Company Mike Jones American Financial Services Association Mark Zalewski Bank of America Daniel Welch Capital One Scott Sykes Certicom Corporation Daniel Brown Citigroup, Inc. Daniel Schutzer Deluxe Corporation John Fitzpatrick Diebold, Inc. Bruc

23、e Chapa Discover Financial Services Jennifer Schroeder Federal Reserve Bank Dexter Holt First Data Corporation Gene Kathol Fiserv Bud Beattie Hewlett Packard Larry Hines Hypercom Scott Spiker IBM Corporation Todd Arnold Ingenico John Sheets Intuit, Inc. Jana Hocker J.P. Morgan Chase not all non-prim

24、es may reach this bound, and the probability that a non-prime generated at random passes such a test is much lower. Accordingly, the 2100bound is considered appropriate independent of the size of the prime being generated and the intended security level of the cryptosystem in which the prime is to b

25、e employed. For high-assurance applications, however, the deterministic methods may nevertheless be preferable. ANS X9.802005 2 ASC X9, Inc. 2005 All rights reserved 2 Normative references The following referenced documents are indispensable for the application of this document. For dated references

26、, only the edition cited applies. Nevertheless, parties to agreements based on this document are encouraged to consider applying the most recent edition of the referenced documents indicated below. For undated references, the latest edition of the referenced document (including any amendments) appli

27、es. X9.62-1998, Public Key Cryptography for the Financial Services Industry The Elliptic Curve Digital Signature Algorithm (ECDSA). X9.63-2002, Public Key Cryptography for the Financial Services Industry Key Agreement and Transport Using Elliptic Curve Cryptography 3 Terms and definitions For the pu

28、rposes of this document, the following terms and definitions apply. 3.1 Composite An integer that has at least two prime factors (two or more may be identical). 3.2 ECPP Acronym for Elliptic Curve Primality Proving algorithm. 3.3 m-bit number A positive integer whose binary representation consists o

29、f m bits, where the high order bit, by definition, is always a “1”. In the case of an m-bit prime number, the low order bit is also a “1” except for the 2-bit prime number decimal 2, which has the binary value b10. For example, the two-byte hexadecimal prime number x01FD (decimal 509) is the 9-bit p

30、rime number b111111101. 3.4 Lehmer-Kraitchik Algorithm A deterministic algorithm that may be used to rigorously prove the primality of an integer. 3.5 Lucas Probable Prime1An integer that has been declared to be a prime number after applying the Lucas test. This number may, however, actually be comp

31、osite with low probability. 3.6 Miller-Rabin Probable Prime An integer that has been declared to be a prime number after applying the Miller-Rabin (M-R) test. This number may, however, actually be composite with low probability. 3.7 Monic Polynomial A polynomial whose lead coefficient is 1. 1Formerl

32、y called “Lucas-Lehmer Probable Prime” in ANS X9.802001. ANS X9.802005 ASC X9, Inc. 2005 All rights reserved 33.8 Polynomial Discriminant The squared product of the pairwise difference of roots of the polynomial. 3.9 Prime Certificate A certificate containing a small set of numbers associated with a

33、n integer that can be used to rigorously prove that the integer is prime. Certificates can be independently checked by other software. 3.10 Prime Number An integer that is greater than 1, and divisible only by 1 and itself. 3.11 Primitive Root An integer a is a primitive root with respect to a prime

34、 p if the smallest integer value of x, such that ax 1 (mod p), is x = p1. 3.12 Private Key In an asymmetric (public) key cryptosystem, that key of an entitys key pair which is known only by that entity. 3.13 Probable Prime An integer that has been declared prime via a probabilistic method. 3.14 Pseu

35、do-Random Number A single number taken as a sample from a sequence of numbers produced by a pseudo-random number generator. 3.15 Public Key In an asymmetric key system, that key of an entitys key pair which may be publicly known. 3.16 Public-Key Cryptography An asymmetric cryptographic algorithm tha

36、t uses two related keys, a public key and a private key; the two keys have the property that, given the public key, it is computationally infeasible to derive the private key. 3.17 Sharp Estimate An estimate for a variable or mathematical quantity is said to be sharp when the estimate is close to th

37、e true value of the quantity being estimated. 3.18 Sieve A computation technique that identifies integers in an arithmetic progression that have small prime factors. 3.19 Trial Division A procedure whereby an integer is tested to see if it is divisible by small primes by performing the actual divisi

38、on and seeing if the remainder is zero. ANS X9.802005 4 ASC X9, Inc. 2005 All rights reserved 3.20 Uniform Random Variable A real number x, lying within a pre-specified interval a, b such that the probability that x lies in a sub-interval c, d with c a and d b is equal to (dc)/(ba). 4 Symbols and ab

39、breviated terms 4.1 x Floor function of x; the largest integer x. For example, 5.3 = 5, and 1.5 = 2. 4.2 x Ceiling function of x; the smallest integer x. For example, 5.3 = 6 and 1.5 = 1. 4.3 x Square root of x. 4.4 anJacobi symbol of a with respect to n. See Annex A.2. 4.5 a|b Evenly divides; e.g.

40、a divides b evenly (with no remainder). 4.6 + Addition. 4.7 Congruence. A B (mod C) means that (AB) is divisible by C. 4.8 ab Exponentiation. a raised to the b thpower. 4.9 Multiplication. 4.10 x Absolute value of x; x is x if x 1), will be the ANS X9.802005 14 ASC X9, Inc. 2005 All rights reserved

41、most efficient for computation: 2, 3, 5, 6, 7, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 24, 26, 28, 29, 30, 31, 33, 34, 35, 37, . 1. Set a threshold k for stopping. Let n be the number of factors of p 1; i.e., denote the factors as q1, q2, , qn. Let j = 0 (to keep track of how many qihave

42、 been satisfied). Let a = 2. 2. If ap1 1 (mod p) then for each i for which an a has not been found for factor qi, if a(p 1)/qi / 1 (mod p) then, increment j, and print (or store) qi, a. 3. If a (p1/4+ 1)2. Then p is prime if q is prime; i.e., q becomes the candidate prime to be proved by the next le

43、vel. NOTE Verification does not use D, m, or the factors of m. Nevertheless, for a number of reasons they appear in certificates produced by many implementations of the ECPP algorithm. This standard includes them in the certificate definition in order to accommodate the use of such certificates. The

44、 method is illustrated in Table 1. Table 1: An ECPP certificate for p = 377681287. j p D (a, b) m factors of m S q 0 377681287 3 (0, 343) 377660188 2, 19, 97, 51229 (328938831, 132650121) 512291 51229 3 (0, 4) 50817 3, 13, 1303 (18245, 46776) 1303 2 1303 3 (0, 1) 1236 2, 3, 103 (1152, 1203) 103 3 10

45、3 3 (0, 22) 124 2, 31 (31, 47) 31 4 31 0 31 is a prime by trial division. NOTE This example could easily have been terminated at an earlier stage by appeal to trial division, but was continued as far as possible for the purpose of illustration. 5.3 Constructive Methods 5.3.1 Shawe-Taylors Algorithm4

46、The following algorithm generates guaranteed primes that need not be tested by any other algorithms. It is therefore intended for first party prime generation. This version of the algorithm cannot be used to test a prime given by a second party. This algorithm is recursive. To generate a prime of b

47、bits let the routine ST_Random_Prime(b) return a prime of b bits: 1. If b 2 rmax, then a. Select s uniformly at random in 0,1. b. Let r = 2s1. It suffices, in practice, to compute r to single precision. c. If rmax (b r b), go to 4a. Else set r = 0.5. 5. Set q = M_Random_Prime( r b + 1). 6. Set I = 2

48、b1/(2q) . 7. Set success = False. 8. While (success is False) a. Set R = a uniformly chosen random integer in I + 1, 2I. b. Set n = 2Rq + 1. c. Determine, by trial division, if n is divisible by a prime number 20, so proceed to Step 3. 3. Set B = 1680. 4. b 2 rmax, so set r = .5 and proceed to Step

49、5. 5. Set q = M_Random_Prime(21). This calls the procedure recursively. 1. Set c = 1.05 and rmax = 20. ANS X9.802005 ASC X9, Inc. 2005 All rights reserved 192. b 20, so proceed to Step 3. 3. Set B = 463.01 4. b 2 rmax, so set r = 0.5 and proceed to Step 5. 5. Set q = M_Random_Prime(10). This again calls the procedure recursively. 1. Set c = 1.05 and rmax = 20. 2. b 20, so randomly search for a 10-bit number that is