ANSI INCITS ISO IEC 18032-2005 Information technology Security techniques Prime number generation.pdf

1、INCITS/ISO/IEC 18032-2005 (ISO/IEC 18032:2005, IDT) Information technology Security techniques Prime numbergenerationIINCITS/ISO/IEC 18032-2005 (ISO/IEC 18032:2005, IDT)INCITS/ISO/IEC 18032-2005ii ITIC 2005 All rights reserved PDF disclaimer This PDF file may contain embedded typefaces. In accordanc

2、e with Adobes licensing policy, this file may be printed or viewed but shall not be edited unless the typefaces which are embedded are licensed to and installed on the computer performing the editing. In downloading this file, parties accept therein the responsibility of not infringing Adobes licens

3、ing policy. The ISO Central Secretariat accepts no liability in this area. Adobe is a trademark of Adobe Systems Incorporated. Details of the software products used to create this PDF file can be found in the General Info relative to the file; the PDF-creation parameters were optimized for printing.

4、 Every care has been taken to ensure that the file is suitable for use by ISO member bodies. In the unlikely event that a problem relating to it is found, please inform the Central Secretariat at the address given below. Adopted by INCITS (InterNational Committee for Information Technology Standards

5、) as an American National Standard. Date of ANSI Approval: 8/29/2005 Published by American National Standards Institute, 25 West 43rd Street, New York, New York 10036 Copyright 2005 by Information Technology Industry Council (ITI). All rights reserved. These materials are subject to copyright claims

6、 of International Standardization Organization (ISO), International Electrotechnical Commission (IEC), American National Standards Institute (ANSI), and Information Technology Industry Council (ITI). Not for resale. No part of this publication may be reproduced in any form, including an electronic r

7、etrieval system, without the prior written permission of ITI. All requests pertaining to this standard should be submitted to ITI, 1250 Eye Street NW, Washington, DC 20005. Printed in the United States of America INCITS/ISO/IEC 18032-2005 ITIC 2005 All rights reserved iii Contents Page Foreword . iv

8、 1 Scope . 1 2 Normative references 1 3 Terms and definitions . 2 4 Symbols . 2 5 Trial division 3 6 Probabilistic primality tests 4 6.1 Miller-Rabin primality test . 4 6.2 Frobenius-Grantham primality test. 5 6.3 Lehmann primality test . 5 7 Deterministic primality verification methods . 6 7.1 Elli

9、ptic curve primality certificate . 6 7.2 Primality certificate based on Maurers algorithm . 7 8 Prime number generation . 8 8.1 Requirements 8 8.2 Using probabilistic tests . 9 8.3 Using deterministic methods 10 9 Candidate prime testing 11 Annex A (informative) Error probabilities 13 Annex B (infor

10、mative) Generating primes with side conditions . 16 Bibliography . 18 INCITS/ISO/IEC 18032-2005 iv ITIC 2005 All rights reserved Foreword ISO (the International Organization for Standardization) and IEC (the International Electrotechnical Commission) form the specialized system for worldwide standar

11、dization. National bodies that are members of ISO or IEC participate in the development of International Standards through technical committees established by the respective organization to deal with particular fields of technical activity. ISO and IEC technical committees collaborate in fields of m

12、utual interest. Other international organizations, governmental and non-governmental, in liaison with ISO and IEC, also take part in the work. In the field of information technology, ISO and IEC have established a joint technical committee, ISO/IEC JTC 1. International Standards are drafted in accor

13、dance with the rules given in the ISO/IEC Directives, Part 2. The main task of the joint technical committee is to prepare International Standards. Draft International Standards adopted by the joint technical committee are circulated to national bodies for voting. Publication as an International Sta

14、ndard requires approval by at least 75 % of the national bodies casting a vote. Attention is drawn to the possibility that some of the elements of this document may be the subject of patent rights. ISO and IEC shall not be held responsible for identifying any or all such patent rights. ISO/IEC 18032

15、 was prepared by Joint Technical Committee ISO/IEC JTC 1, Information technology, Subcommittee SC 27, IT Security techniques. AMERICAN NATIONAL STANDARD INCITS/ISO/IEC 18032-2005 ITIC 2005 All rights reserved 1 Information technology Security techniques Prime number generation 1 Scope This Internati

16、onal Standard specifies methods for generating and testing prime numbers as required in cryptographic protocols and algorithms. Firstly, this International Standard specifies methods for testing whether a given number is prime. The testing methods included in this International Standard can be divid

17、ed into two groups: Probabilistic primality tests, which have a small error probability. All probabilistic tests described here may declare a composite to be a prime. One test described here may declare a prime to be composite. Deterministic methods, which are guaranteed to give the right verdict. T

18、hese methods use so-called primality certificates. Secondly, this International Standard specifies methods to generate prime numbers. Again, both probabilistic and deterministic methods are presented. NOTE Readers with a background in algorithm theory may have had previous encounters with probabilis

19、tic and deterministic algorithms. We stress that the deterministic methods in this International Standard internally still make use of random bits, and “deterministic” only refers to the fact that the output is correct with probability one. Annex B describes variants of the methods for generating pr

20、imes so that particular cryptographic requirements can be met. The methods for generating, proving and verifying primality defined by this International Standard are applicable to cryptographic systems based on the properties of the primes. NOTE The specifications of the tests given in this Internat

21、ional Standard define the properties to be tested in the simplest possible form. Following these specifications directly will not necessarily produce the most efficient implementations. This is especially the case for the Frobenius-Grantham test. 2 Normative references The following referenced docum

22、ents are indispensable for the application of this document. For dated references, only the edition cited applies. For undated references, the latest edition of the referenced document (including any amendments) applies. ISO/IEC 9796-2:2002, Information technology Security techniques Digital signatu

23、re schemes giving message recovery Part 2: Integer factorization based mechanisms ISO/IEC 15946-1:2002, Information technology Security techniques Cryptographic techniques based on elliptic curves Part 1: General INCITS/ISO/IEC 18032-2005 2 ITIC 2005 All rights reserved 3 Terms and definitions For t

24、he purposes of this document, the following terms and definitions apply. 3.1 composite number composite Integer N 1 is composite if it is not prime, i.e. there exist divisors of N that are not trivial divisors. 3.2 entropy Total amount of information yielded by a set of bits. It is representative of

25、 the work effort required for an adversary to be able to reproduce the same set of bits. 3.3 Jacobi symbol Jacobi symbol of a with respect to an odd number n is the product of the Legendre symbols of a with respect to the prime factors of n (repeating the Legendre symbols for repeated prime factors)

26、. NOTE Defined in Annex A of ISO/IEC 9796-2. 3.4 Legendre symbol Let p be an odd prime, and let a be a positive integer. The Legendre symbol of a with respect to p is defined as a(p - 1)/2 mod p. NOTE Defined in Annex A of ISO/IEC 9796-2. 3.5 primality certificate Mathematical proof that a given num

27、ber is indeed a prime. For small numbers primality is most efficiently proven by trial division. In these cases, the primality certificate may therefore be empty. 3.6 prime number prime Integer N 1 is prime if the only divisors of N are trivial divisors. 3.7 pseudo-random bit generator Deterministic

28、 algorithm which when given some form of a bit sequence of length k outputs a sequence of bits of length l k, computationally infeasible to distinguish from true random bits. 3.8 trial division Trial division of a number N means checking all prime numbers smaller than or equal to N to see if they di

29、vide N. 3.9 trivial divisor Any integer N is always divisible by 1, -1, N and N. These numbers are the trivial divisors of N. 4 Symbols a mod n for integers a and n, (a mod n) denotes the (non-negative) remainder obtained when a is divided by n. C a primality certificate C(N) primality certificate o

30、f the number N. INCITS/ISO/IEC 18032-2005 ITIC 2005 All rights reserved 3 C0(N) the empty primality certificate. It indicates that trial division should be used to verify that N is a prime. gcd greatest common divisor g(x) mod (N,f(x) the remainder when the polynomial g(x) is divided by the polynomi

31、al f(x), calculating coefficients modulo the integer N k number of bits in N L limit below which primality is verified by trial division logb(a) the logarithm of a with respect to base b ln() the natural logarithm (i.e., with respect to the number e) M a lower bound on the size of an interval in whi

32、ch a prime number has to be found mina,b the minimum of the numbers a and b N candidate number to be tested for primality, where N is always a positive, odd number. n0 a starting point in an incremental search for a prime nmax an end point in an incremental search for a prime T a (probabilistic) tes

33、t for primality ZN the set of the integer numbers 0, 1, 2, ., N-1, representing the ring of integers modulo N. ZN* the subset of ZN containing the numbers that have a multiplicative inverse modulo N (i.e., if N is prime: the integer numbers 1, 2, ., N-1) ZNx/f(x) the ring of polynomials modulo f(x)

34、with coefficients in ZN x the largest integer smaller than or equal to x. a parameter which determines the lower bound of the entropy of the output of a prime generation algorithm the maximal number of steps in an incremental search for a prime 5 Trial division The primality of an integer N can be p

35、roven by means of trial division. This is done in the following way: 1. For all primes p N a. If N mod p = 0 then return “reject” 2. Return “accept” For small integers N, trial division is less computationally expensive than other primality tests. Implementations of any primality test described in t

36、his standard may define a trial division bound L, below which trial division is used in order to prove the primality of integers. This International Standard sets no value for L. NOTE It is assumed that the set of prime numbers below a certain size are already known. One practical way to implement t

37、he test may be to have a pre-computed table of the first few primes, do trial division by these, and then simply trial divide by all odd integers up to the square root. INCITS/ISO/IEC 18032-2005 4 ITIC 2005 All rights reserved NOTE The size of integers for which trial division is less computationall

38、y expensive than another primality test, depends on the test and its implementation. A typical value for L might be L = 103. 6 Probabilistic primality tests A probabilistic primality test takes a positive, odd number N as input and returns “accept” or “reject”. If N is a composite number, the tests

39、described in this clause output “reject”, except with some error probability depending on the test being used. The probability that a composite number is accepted is not negligible. If N is a prime number, the Miller-Rabin test and the Frobenius-Grantham test always output “accept”. The Lehmann test

40、 rejects a prime number with a probability that is not negligible. In order to reduce the probability of errors, one usually makes several iterations with the same input (and different choices for the random values). 6.1 Miller-Rabin primality test On input of a candidate number, N, the Miller-Rabin

41、 test starts with the following initialisation step: 1. Determine positive integers t and s such that N-1 = 2ts, where s is odd. Subsequently, the Miller-Rabin test proceeds with one or more iterations of the following algorithm, which takes inputs t, s, N and outputs “accept” or “reject”. For each

42、iteration, a different base b must be selected, with 2 b N-2. NOTE One iteration of the algorithm is called testing N for primality with respect to the base b. 1. Choose a random integer b such that 2 b N-2. 2. Let y = bs mod N 3. if y 1 and y N-1 then do a. i = 1 b. while i 1 is prime if and only i

43、f a ZN*: a(N-1)/2 = 1 mod N and a ZN*: a(N-1)/2 = -1 mod N. The Lehmann primality test takes as input a candidate number N and a parameter t indicating the maximum number of iterations to be executed. The test executes the following algorithm. 1. Set f = “false”. 2. Do t times INCITS/ISO/IEC 18032-2

44、005 6 ITIC 2005 All rights reserved a. Choose a random integer b such that 2 b N-2. b. Let y = b(N-1)/2 mod N. c. If y 1 and y N-1 then return “reject”. d. If y = N-1, then set f = “true”. 3. If f = “true” then return “accept”, else return “reject”. NOTE Informative Annex A contains information on t

45、he error probability of this test depending on the number of iterations. 7 Deterministic primality verification methods Deterministic primality verification methods use primality certificates in order to verify the primality of a given number. This clause specifies the content of two types of primal

46、ity certificates: Primality certificates based on elliptic curves Primality certificates for primes generated by Maurers algorithm (see Clause 8.3.1) A primality certificate contains information that enables efficient verification that a given number is a prime. For both types of certificates descri

47、bed in this International Standard, small numbers (i.e. numbers smaller than the trial division bound L) are most efficiently verified to be primes by trial division. Let C0 denote the empty primality certificate for such numbers. An elliptic curve primality certificate can be computed given any pri

48、me. Hence, the method for computing this certificate can in effect also be used to verify primality. The primality certificate obtained through Maurers algorithm is generated as part of generating a prime, and it cannot in general be efficiently computed for an arbitrary prime (after the prime has b

49、een generated). 7.1 Elliptic curve primality certificate Information regarding elliptic curves can be found in ISO/IEC 15946-1. NOTE The method is based on the following fact: Let gcd(N,6) = 1 and let r be a prime such that r (N1/4+1)2. If there exists a (non-singular) elliptic curve y2 = x3+ax+b modulo N and a point P 0 on this curve with order r, then N is prime. To prove that a number is prime the method is used recursively. The recursi