ISO/IEC 18032:2005
(Main)Information technology — Security techniques — Prime number generation
Information technology — Security techniques — Prime number generation
ISO/IEC 18032:2005 specifies methods for generating and testing prime numbers. Prime numbers are used in various cryptographic algorithms, mainly in asymmetric encryption algorithms and digital signature algorithms. Firstly, ISO/IEC 18032:2005 specifies methods for testing whether a given number is prime. The testing methods included in ISO/IEC 18032:2005 can be divided 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. These methods use so-called primality certificates. Secondly, ISO/IEC 18032:2005 specifies methods to generate prime numbers. Again, both probabilistic and deterministic methods are presented.
Technologies de l'information — Techniques de sécurité — Génération de nombres premiers
General Information
Relations
Standards Content (Sample)
INTERNATIONAL ISO/IEC
STANDARD 18032
First edition
2005-01-15
Information technology — Security
techniques — Prime number generation
Technologies de l'information — Techniques de sécurité — Génération
de nombres premiers
Reference number
ISO/IEC 18032:2005(E)
©
ISO/IEC 2005
---------------------- Page: 1 ----------------------
ISO/IEC 18032:2005(E)
PDF disclaimer
This PDF file may contain embedded typefaces. In accordance with Adobe's 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 Adobe's licensing 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. 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.
© ISO/IEC 2005
All rights reserved. Unless otherwise specified, no part of this publication may be reproduced or utilized in any form or by any means,
electronic or mechanical, including photocopying and microfilm, without permission in writing from either ISO at the address below or
ISO's member body in the country of the requester.
ISO copyright office
Case postale 56 • CH-1211 Geneva 20
Tel. + 41 22 749 01 11
Fax + 41 22 749 09 47
E-mail copyright@iso.org
Web www.iso.org
Published in Switzerland
ii © ISO/IEC 2005 – All rights reserved
---------------------- Page: 2 ----------------------
ISO/IEC 18032:2005(E)
Contents Page
Foreword. iv
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 Elliptic curve primality certificate. 6
7.2 Primality certificate based on Maurer’s 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 (informative) Generating primes with side conditions. 16
Bibliography . 18
© ISO/IEC 2005 – All rights reserved iii
---------------------- Page: 3 ----------------------
ISO/IEC 18032:2005(E)
Foreword
ISO (the International Organization for Standardization) and IEC (the International Electrotechnical
Commission) form the specialized system for worldwide standardization. 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 mutual 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 accordance 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 Standard 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 was prepared by Joint Technical Committee ISO/IEC JTC 1, Information technology,
Subcommittee SC 27, IT Security techniques.
iv © ISO/IEC 2005 – All rights reserved
---------------------- Page: 4 ----------------------
INTERNATIONAL STANDARD ISO/IEC 18032:2005(E)
Information technology — Security techniques — Prime number
generation
1 Scope
This International 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 divided 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. These 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 probabilistic 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 primes 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 International 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 documents 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 signature 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
© ISO/IEC 2005 – All rights reserved 1
---------------------- Page: 5 ----------------------
ISO/IEC 18032:2005(E)
3 Terms and definitions
For the 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 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).
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
(p - 1)/2
as a mod p.
NOTE Defined in Annex A of ISO/IEC 9796-2.
3.5
primality certificate
Mathematical proof that a given number 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 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
divide 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 of the number N.
2 © ISO/IEC 2005 – All rights reserved
---------------------- Page: 6 ----------------------
ISO/IEC 18032:2005(E)
C (N) – the empty primality certificate. It indicates that trial division should be used to verify that N is a prime.
0
gcd – greatest common divisor
g(x) mod (N,f(x)) – the remainder when the polynomial g(x) is divided by the polynomial f(x), calculating
coefficients modulo the integer N
k – number of bits in N
L − limit below which primality is verified by trial division
log (a) − the logarithm of a with respect to base b
b
ln() – the natural logarithm (i.e., with respect to the number e)
M – a lower bound on the size of an interval in which a prime number has to be found
min{a,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.
n – a starting point in an incremental search for a prime
0
n – an end point in an incremental search for a prime
max
T – a (probabilistic) test for primality
Z – the set of the integer numbers 0, 1, 2, ., N-1, representing the ring of integers modulo N.
N
Z * – the subset of Z containing the numbers that have a multiplicative inverse modulo N (i.e., if N is prime:
N N
the integer numbers 1, 2, ., N-1)
Z [x]/f(x) – the ring of polynomials modulo f(x) with coefficients in Z
N N
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 proven 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 this 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 the 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.
© ISO/IEC 2005 – All rights reserved 3
---------------------- Page: 7 ----------------------
ISO/IEC 18032:2005(E)
NOTE The size of integers for which trial division is less computationally expensive than another primality test,
3
depends on the test and its implementation. A typical value for L might be L = 10 .
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 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 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 test starts with the following initialisation step:
t
1. Determine positive integers t and s such that N-1 = 2 s, 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 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.
s
2. Let y = b mod N
3. if y ≠ 1 and y ≠ N-1 then do
a. i = 1
b. while i < t and y ≠ N-1 do
2
i. y = y mod N
ii. if y = 1 then return “reject”
iii. i = i + 1
c. if y ≠ N-1 then return “reject”
4. return “accept”
A test for primality does not need to use exactly the same algorithm to be compliant with this International
Standard. A test for primality is compliant with this International Standard if one iteration outputs “accept” if
and only if one of the following requirements is satisfied for the chosen base:
s
• b mod N equals 1
s
• b mod N equals N-1
i
s 2
• For some i (0
4 © ISO/IEC 2005 – All rights reserved
---------------------- Page: 8 ----------------------
ISO/IEC 18032:2005(E)
The test only accepts the candidate if all iterations accept. Therefore the test may be stopped as soon as a
base not leading to acceptance has been found.
NOTE Informative Annex A contains estimates of the error probability of this test depending on the number of
iterations.
6.2 Frobenius-Grantham primality test
This test uses arithmetic in the ring Z [x]/(f(x)), where f(x) is some polynomial of degree 2. The test is as
N
follows.
On input of an odd number N, the Frobenius-Grantham primality test starts with the following initialisation
steps:
1. Test N for divisibility by primes less than or equal to min{50000, √N} (trial division).
2. Test if N is a square. If yes, reject N and stop.
r 2
3. Determine positive integers r and s such that 2 s= N -1 and s is odd.
Subsequently, the test proceeds with one or more iterations of the following algorithm, which takes inputs r, s,
N and outputs “accept” or “reject”. In each iteration, different values for b and c must be selected.
1. Choose random b,c∈Z until one of the following is true:
N
2
• Either gcd(b +4c,N) or gcd(c,N) is a non-trivial divisor of N.
2
• The Jacobi symbol of b +4c with respect to N is -1 mod N and the Jacobi symbol of –c with
respect to N is 1 mod N.
In the first case, reject N and stop. In the second case continue with the next step.
(N+1)/2 2
2. Test if the polynomial x mod (N, x -bx-c) has degree 0, or equivalently, is in Z . If not, reject N
N
and stop.
N+1 2
3. Test if x mod (N, x -bx-c) = -c. If not, reject N and stop.
j
s 2 2 s 2
4. Test if either x mod (N, x -bx-c) = 1 or j (0 ≤ j ≤ r-2) exists such that x mod (N, x -bx-c) = -1. If not,
reject N and stop, otherwise accept N.
NOTE The Jacobi symbol with respect to N may be efficiently computed without knowledge of the prime factors of N [16].
NOTE A more detailed description of the test can be found in [9]. In the same document, it is proven that an iteration of
the test can be implemented in such a way that its running time is approximately equal to 3 times the running time of one
iteration of the Miller-Rabin test.
NOTE Information regarding the error probability of this test can be found in Annex A.
6.3 Lehmann primality test
(N-1)/2
NOTE The Lehmann test is based on the following fact: An odd integer N > 1 is prime if and only if ∀ a ∈ Z *: a
N
(N-1)/2
= ±1 mod N and ∃ a ∈ Z *: a = -1 mod N.
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
© ISO/IEC 2005 – All rights reserved 5
---------------------- Page: 9 ----------------------
ISO/IEC 18032:2005(E)
a. Choose a random integer b such that 2 ≤ b ≤ N-2.
(N-1)/2
b. Let y = b 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 the 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 primality certificates:
• Primality certificates based on elliptic curves
• Primality certificates for primes generated by Maurer’s 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 described 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 C denote the empty
0
primality certificate for such numbers.
An elliptic curve primality certificate can be computed given any prime. Hence, the method for computing this
certificate can in effect also be used to verify primality. The primality certificate obtained through Maurer’s
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 been generated).
7.1 Elliptic curve primality certificate
Information regarding elliptic curves can be found in ISO/IEC 15946-1.
1/4 2
NOTE The method is based on the following fact: Let gcd(N,6) = 1 and let r be a prime such that r > (N +1) . If there
2 3
exists a (non-singular) elliptic curve y = x +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 recursion parameter is denoted by r. The
total collection of data generated by the method is organised in a primality certificate. Checking the certificate,
and thereby proving that N is prime, is considerably faster than generating the certificate.
NOTE If the number N is not prime, then the method will search for an elliptic curve that doesn't exist. Hence, the
method will run indefinitely, unless precautions are taken. If the method is stopped before it produces a primality certificate
(e.g. after a predetermined amount of time), the number N cannot be judged to be prime or composite.
7.1.1 Elliptic curve primality certificate generation
On input of an integer number N with gcd(N,6) = 1, the elliptic curve primality certificate generation starts with
the following initialisations:
1. Let C = {}
2. Let j = 0
3. Let r = N
6 © ISO/IEC 2005 – All rights reserved
---------------------- Page: 10 ----------------------
ISO/IEC 18032:2005(E)
Subsequently the following steps are executed for decreasing values of r, until r ≤ L:
1. j = j + 1.
4 2
2. t = ( √r+1) .
min
3. Determine integers t, a, b and a point P such that the following conditions are satisfied:
a. t is a probable prime and t ≥ t
min
2 3
b. The order of the elliptic curve E: y = x + ax + b mod r is a multiple of t.
c. P is a point on E with order t.
4. Let C = (r,t,a,b,P).
j
5. Append C to C.
j
6. r = t.
When r ≤ L, the primality of r is proven by means of trial division. The output of the algorithm is the sequence C.
NOTE Algorithms to implement step 3.b. efficiently are described e.g. in [2].
7.1.2 Elliptic curve primality certificate verification
For a number N with gcd(N,6) = 1, an elliptic curve primality certificate is a sequence C = {C , C , …, C },
1 2 k
where:
C = (p ,r , a, b , P)
i i i i i i
such that:
• p = N.
1
• r is a prime less than L.
k
and for all i = 1, 2, …, k:
1. gcd(p,6) = 1.
i
2 3
2. P is a point on the elliptic curve E: y = x + a x + b mod p ,
i i i i
3. P has order r .
i i
4. p = r for 1 ≤ i < k.
i+1 i
1/4 2
5. r > (p +1) .
i i
The number N is prime if it has such a certificate.
7.2 Primality certificate based on Maurer’s algorithm
This type of primality certificate can be computed only during the generation process of the prime number,
which is described in Clause 8.3.1.
© ISO/IEC 2005 – All rights reserved 7
---------------------- Page: 11 ----------------------
ISO/IEC 18032:2005(E)
NOTE Maurer's algorithm is based on the following fact. Let N = 1 + 2Rq, where q is an odd prime and q > R. If an
N-1 2R
integer a exists satisfying a = 1 mod N and gcd(a -1,N) = 1, then N is prime.
The proof that an odd number, N ≥ L, is prime has the following structure:
Proof(N) = (N, q, a)
This tuple is a proof of primality if the following conditions are fulfilled:
• q is an odd prime such that:
o q is a divisor of N-1.
2
o q > (N-1)/2.
• a is an integer such that 1< a < N and
N-1
o a (mod N) = 1.
(N-1)/q
o gcd(a -1, N) = 1.
The primality certificate, C(N), for the integer N is as follows:
• If N ≤ L then C(N) = C (N).
0
• If N > L then C(N) = “Proof(N), C(q)”, where Proof(N) = (N, q, a).
8 Prime number generation
This clause specifies two different ways of generating a prime. The first type of method is based on
probabilistic primality tests. The primes generated by these methods may optionally be certified by
subsequently generating an elliptic curve certificate. The second type of method is based on deterministic
generating methods. It includes Maurer’s algorithm, which generates a prime number together with a primality
certificate for that number.
8.1 Requirements
In order for a prime number generation algorithm to be compliant with this International Standard, the
algorithm must be capable of generating output numbers of a given bit length k. Secondly, it must ensure that
-100
the error probability is at most 2 . Thirdly, the entropy of the output number should be at least B bits and
1/3
also at least βk bits. The absolute bound B and the relative bound β. can be set depending on the security
requirements of the application.
NOTE For applications where the primes generated need to be kept secret, it is recommended to set B=100 and
β =12. This ensures that it will be infeasible for an adversary to predict the output of the algorithm with any significant
1/3
k
β
probability. The condition is true, for instance, if the output is chosen at random from a set of at least 2 k-bit primes.
Furthermore, as primes are often generated using a pseudo random number generator based on a seed of a certain
length, the uncertainty of the primes cannot be larger than that of the seed. In particular it is not harder to guess the
primes (e.g., in the case of RSA) than to guess the seed. The bound on the entropy increases asymptotically in the same
way as the expected complexity for factoring a modulus of size 2k by means of the number field sieve algorithm increases
[13]. Using β = 12, the fixed bound meets the variable bound for k ≈ 512 (i.e., for primes of 512 bits).
NOTE Annex A contains more information on how the properties of the algorithms can be established. With current
mathematical state of the art, it is only possible to rigorously prove some of the properties. The rest can be shown based
on well-established conjectures that have been extensively verified heuristically.
8 © ISO/IEC 2005 – All rights reserved
---------------------- Page: 12 ----------------------
ISO/IEC 18032:2005(E)
8.2 Using probabilistic tests
Let T denote any of the probabilistic primality tests given in Clause 6. The error probability of T depends on
the number of iterations of the test.
NOTE Recommended values for the number of iterations for each of the probabilistic tests described in this
International Standard are listed in Annex A.
The following subclauses describe two algorithms that meet the demands of Clause 8.1. It is not necessary to
follow the example algorithms exactly in order to be in compliance with this International Standard; it is only
necessary to implement an algorithm that is functionally equivalent to those algorithms given here.
8.2.1 Random Choice of Candidates
The following algorithm can be used assuming the test T is chosen appropriately:
k-1 k
1. Choose at random an odd number N such that 2 < N <2 .
2. If N passes T, output N and stop. Otherwise, go to step 1.
To estimate the probability that this algorithm outputs a composite, one must analyse how the test T behaves
on randomly chosen inputs. This may not be the same as the maximal probability that T accepts a composite.
NOTE For instance, this worst-case probability is as mentioned in Annex A, ¼ for one iteration of the Miller-Rabin
test, but in fact the probability is typically much smaller, i.e., a typical composite is accepted with much smaller probability
than ¼. Thus the number of iterations depends on such an average-case analysis. Annex A contains information on how
to choose the number of iterations.
NOTE The algorithm is guaranteed to produce uniformly chosen k-bit primes and therefore satisfies the general
requirement on the output distribution.
8.2.2 Incremental search
The following algorithm may be used. Let µ denote a parameter limiting the number of increments when
searching for a prime. The procedure is based on a different way of choosing the candidate primes and has
some efficiency advantages in practice compared to the method based on random choices of candidates
(Clause 8.2.1), when combined with test division:
k-1 k k
1. Choose at random odd n such that 2 < n <2 . Set N = n and n = min(2 , n +2µ). Execute the
0 0 0 max 0
following procedure:
2. If N passes the test T, output N and stop.
3. Set N = N+2. If N > n go to Step 1 else go to Step 2.
max
This algorithm chooses at random n and then tests n , n +2,.,n +2µ for primality. If no prime is found, a new
0 0 0 0
random starting point n is chosen and the procedure is repeated.
0
NOTE The error probability of this algorithm can be estimated using the same methods as for the algorithm choosing
random candidates. The estimates will not be identical - they will depend both on the choice of T and µ. It is worth
mentioning that due to the fact that the candidates in incremental search are not independent, error estimates tend to be
weaker for this method. Note that a trade-off is involved in the choice of µ: a larger value of µ will decrease the probability
that an execution of the inner loop outputs “fail”, and this tends to make the algorithm faster. On the other hand, the error
estimates tend to be weaker for larger µ.
k
It is recommended to use the parameter µ = 10ln(2 ). This results in a high probability of finding a prime in the
first interval and, still, the distribution of the found prime is almost uniform.
NOTE This algorithm does not choose primes with exactly the uniform distribution among k-bits numbers. Due to the
fact that primes are not regularly distributed; some primes will have larger probability of being chosen th
...
Questions, Comments and Discussion
Ask us and Technical Secretary will try to provide an answer. You can facilitate discussion about the standard in here.