ANSI 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. Copyright American National Standards Institute Provided by IHS under license with ANSINot for ResaleNo reproduction or networking permitted without license from IHS-,-,-ANS X9.802005 ii ASC X9, Inc. 20

4、05 All rights reserved Foreword Approval of an American National Standard requires verification by ANSI that the requirements for due process, consensus, and other criteria for approval have been met by the standards developer. Consensus is established when, in the judgment of the ANSI Board of Stan

5、dards Review, substantial agreement has been reached by directly and materially affected interests. Substantial agreement means much more than a simple majority, but not necessarily unanimity. Consensus requires that all views and objections be considered, and that a concerted effort be made toward

6、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 standards or not from manufacturing, marketing, purchasing, or using products, processes, or procedures not conforming to the standar

7、ds. The American National Standards Institute does not develop standards and will in no circumstances give an interpretation of any American National Standard. Moreover, no person shall have the right or authority to issue an interpretation of an American National Standard in the name of the America

8、n National Standards Institute. Requests for interpretations should be addressed to the secretariat or sponsor whose name appears on the title page of this standard. CAUTION NOTICE: This American National Standard may be revised or withdrawn at any time. The procedures of the American National Stand

9、ards 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 Standards Committee X9, Incorporated Financial Industry Standards P.O. Box 4035 Annapolis, MD 21403 USA X9 Online http:/www.x9.org Co

10、pyright 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 written permission of the publisher. Printed in the United States of America. Copyright American National Standards Institute Provid

11、ed by IHS under license with ANSINot for ResaleNo reproduction or networking permitted without license from IHS-,-,-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 abbreviate

12、d terms 4 5 Prime Generation Methods.5 5.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 D

13、eterministic Methods .11 5.3 Constructive 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

14、.21 7.2 Rounds Required for Frobenius-Grantham 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 Discus

15、sion of the Distribution of Randomly Chosen 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 squa

16、res in Lucas test.32 C.2.5 Discriminants 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 Copyright American National Standards Institute Provided by IHS under license with ANSINot for ResaleNo repr

17、oduction or networking permitted without license from IHS-,-,-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 Miller-Rabin and Lucas tests33 C.3.5 Versions of Shawe-Taylor.33 C.3.6 Binary expansions.33

18、 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 Copyright American National Standards Institute Provided by IHS under license with ANSINot for ResaleNo reproduction or networking permitted without lice

19、nse from IHS-,-,-ANS X9.802005 ASC X9, Inc. 2005 All rights reserved vTables Table 1: An ECPP certificate for p = 377681287. 16 Table 2: Rounds Required for Miller-Rabin . 21 Table 3: Rounds Required for Frobenius-Grantham . 21 Copyright American National Standards Institute Provided by IHS under li

20、cense with ANSINot for ResaleNo reproduction or networking permitted without license from IHS-,-,-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 standard may require use of an invention covered by pa

21、tent 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 these rights on reasonable and nondiscriminatory te

22、rms 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, Accredited Standards Committee X9, Inc., Financial

23、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 that all the committee members voted for its appro

24、val. 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 American Bankers Association C. Diane Poole American Expr

25、ess 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. Bruce Chapa Discover Financial Services Jennifer Schro

26、eder 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-primes may reach this bound, and the probability that

27、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 be employed. For high-assurance applications, howev

28、er, the deterministic methods may nevertheless be preferable. Copyright American National Standards Institute Provided by IHS under license with ANSINot for ResaleNo reproduction or networking permitted without license from IHS-,-,-ANS X9.802005 2 ASC X9, Inc. 2005 All rights reserved 2 Normative re

29、ferences The following referenced documents are indispensable for the application of this document. For dated references, 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

30、 indicated below. For undated references, the latest edition of the referenced document (including any amendments) applies. 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 Fina

31、ncial Services Industry Key Agreement and Transport Using Elliptic Curve Cryptography 3 Terms and definitions For the purposes 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 fo

32、r Elliptic Curve Primality Proving algorithm. 3.3 m-bit number A positive integer whose binary representation consists of 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

33、2, which has the binary value b10. For example, the two-byte hexadecimal prime number x01FD (decimal 509) is the 9-bit prime 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 integ

34、er that has been declared to be a prime number after applying the Lucas test. This number may, however, actually be composite 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, howe

35、ver, actually be composite with low probability. 3.7 Monic Polynomial A polynomial whose lead coefficient is 1. 1Formerly called “Lucas-Lehmer Probable Prime” in ANS X9.802001. Copyright American National Standards Institute Provided by IHS under license with ANSINot for ResaleNo reproduction or net

36、working permitted without license from IHS-,-,-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 an integer

37、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 p if the

38、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 Pseudo-Random

39、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 that uses two

40、 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 the true val

41、ue 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 division and see

42、ing if the remainder is zero. Copyright American National Standards Institute Provided by IHS under license with ANSINot for ResaleNo reproduction or networking permitted without license from IHS-,-,-ANS X9.802005 4 ASC X9, Inc. 2005 All rights reserved 3.20 Uniform Random Variable A real number x,

43、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 abbreviated 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 smalle

44、st 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. 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

45、. 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 Copyright American National Standards Institute Provided by IHS under license with ANSINot for ResaleNo reproduction or networking permitted without license from IHS-,-,-ANS X9.802005 14 ASC X9,

46、Inc. 2005 All rights reserved 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

47、 keep track of how many qihave 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 pri

48、me to be proved by the next level. 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 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 (1