ISO/IEC 15946-5:2009

INTERNATIONAL ISO/IEC
STANDARD 15946-5
First edition
2009-12-15
Information technology — Security
techniques — Cryptographic techniques
based on elliptic curves —
Part 5:
Elliptic curve generation
Technologies de l'information — Techniques de sécurité — Techniques
cryptographiques fondées sur les courbes elliptiques —
Partie 5: Génération de courbes elliptiques

Reference number
©
ISO/IEC 2009
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 2009
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 2009 – All rights reserved

Contents Page
Foreword .iv
Introduction.v
1 Scope.1
2 Normative reference(s) .1
3 Terms and definitions .1
4 Notation and conversion functions .2
4.1 Notation .2
4.2 Conversion functions.3
5 Framework for elliptic curve generation.3
5.1 Types of trusted elliptic curve .3
5.2 Overview of elliptic curve generation.4
6 Verifiably Pseudo-Random Elliptic curve generation.4
6.1 Constructing Verifiably Pseudo-Random Elliptic Curves (prime case).4
6.1.1 Construction algorithm.4
6.1.2 Test for Near Primality .5
6.1.3 Finding a Point of Large Prime Order .6
6.1.4 Verification of Elliptic Curve Pseudo-Randomness .6
6.2 Constructing Verifiably Pseudo-Random Elliptic Curves (binary case).7
6.2.1 Construction algorithm.7
6.2.2 Verification of Elliptic Curve Pseudo-Randomness .8
7 Constructing Elliptic Curves by Complex Multiplication .9
7.1 General Construction (prime case) .9
7.2 MNT curve (Miyaji-Nakabayashi-Takano curve).10
7.3 BN curve (Barreto-Naehrig curve) .11
7.4 F curve (Freeman curve).12
7.5 CP curve (Cocks-Pinch curve) .13
8 Constructing Elliptic Curves by Lifting.14
Annex A (informative) Background information on elliptic curves .16
Annex B (informative) Background Information on elliptic curve cryptosystems.18
Annex C (informative) Numerical examples.21
Annex D (informative) Summary of properties of Elliptic Curves generated by a Complex
Multiplication method .29
Bibliography.30

© ISO/IEC 2009 – All rights reserved iii

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 15946-5 was prepared by Joint Technical Committee ISO/IEC JTC 1, Information technology,
Subcommittee SC 27, IT Security techniques.
ISO/IEC 15946 consists of the following parts, under the general title Information technology — Security
techniques ― Cryptographic techniques based on elliptic curves:
⎯ Part 1: General
⎯ Part 5: Elliptic curve generation
iv © ISO/IEC 2009 – All rights reserved

Introduction
Some of the most interesting alternatives to the RSA and F(p) based systems are cryptosystems based on
elliptic curves defined over finite fields. The concept of an elliptic curve based public-key cryptosystem is
rather simple:
⎯ Every elliptic curve over a finite field is endowed with an addition operation “+”, under which it forms a
finite abelian group.
⎯ The group law on elliptic curves extends in a natural way to a “discrete exponentiation” on the point group
of the elliptic curve.
⎯ Based on the discrete exponentiation on an elliptic curve, one can easily derive elliptic curve analogues of
the well-known public-key schemes of Diffie-Hellman and ElGamal type.
The security of such a public-key system depends on the difficulty of determining discrete logarithms in the
group of points of an elliptic curve. This problem is — with current knowledge — much harder than the
factorization of integers or the computation of discrete logarithms in a finite field. Indeed, since Miller and
Koblitz in 1985 independently suggested the use of elliptic curves for public-key cryptographic systems, the
elliptic curve discrete logarithm problem has only been shown to be solvable in certain specific, and easily
recognizable, cases. There has been no substantial progress in finding an efficient method for solving the
elliptic curve discrete logarithm problem on arbitrary elliptic curves. Thus, it is possible for elliptic curve based
public-key systems to use much shorter parameters than the RSA system or the classical discrete logarithm
based systems that make use of the multiplicative group of a finite field. This yields significantly shorter digital
signatures and system parameters.
This part of ISO/IEC 15946 describes elliptic curve generation techniques useful for implementing the elliptic
curve based mechanisms defined in ISO/IEC 9796-3, ISO/IEC 11770-3, ISO/IEC 14888-3, and
ISO/IEC 18033-2.
It is the purpose of this part of ISO/IEC 15946 to meet the increasing interest in elliptic curve based public-key
technology by describing elliptic curve generation methods to support key-exchange, key-transport and digital
signatures based on an elliptic curve.

© ISO/IEC 2009 – All rights reserved v

INTERNATIONAL STANDARD ISO/IEC 15946-5:2009(E)

Information technology — Security techniques —
Cryptographic techniques based on elliptic curves —
Part 5:
Elliptic curve generation
1 Scope
ISO/IEC 15946 specifies public-key cryptographic techniques based on elliptic curves.
This part of ISO/IEC 15946 defines elliptic curve generation techniques useful for implementing the elliptic
curve based mechanisms defined in ISO/IEC 9796-3, ISO/IEC 11770-3, ISO/IEC 14888-3 and
ISO/IEC 18033-2.
The scope of this part of ISO/IEC 15946 is restricted to cryptographic techniques based on elliptic curves
defined over finite fields of prime power order (including the special cases of prime order and characteristic
two). The representation of elements of the underlying finite field (i.e. which basis is used) is outside the scope
of this part of ISO/IEC 15946.
ISO/IEC 15946 does not specify the implementation of the techniques it defines. Interoperability of products
complying with ISO/IEC 15946 will not be guaranteed.
2 Normative reference(s)
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 15946-1, Information technology — Security techniques — Cryptographic techniques based on
elliptic curves — Part 1: General
3 Terms and definitions
For the purposes of this document, the following terms and definitions apply.
3.1
definition field of an elliptic curve
field that includes all the coefficients of the equation describing an elliptic curve
3.2
elliptic curve
cubic curve without a singular point
NOTE 1 A definition of a cubic curve is given in [29].
© ISO/IEC 2009 – All rights reserved 1

NOTE 2 The set of points of E under a certain addition law forms an abelian group. In this part of ISO/IEC 15946, we
only deal with finite fields F as the definition field. When we describe the definition field F of an elliptic curve E explicitly, we
denote the curve as E/F.
NOTE 3 A detailed definition of an elliptic curve is given in Clause 4.
[ISO/IEC 15946-1:2008]
3.3
finite field
field containing a finite number of elements
NOTE 1 A definition of field is given in [29].
m
NOTE 2 For any positive integer m and a prime p, there exists a finite field containing exactly p elements. This field is
m m
unique up to isomorphism and is denoted by F(p ), where p is called the characteristic of F(p ).
[ISO/IEC 15946-1:2008]
3.4
hash-function
function which maps strings of bits to fixed-length strings of bits, satisfying the following two properties:
⎯ for a given output, it is computationally infeasible to find an input which maps to this output;
⎯ for a given input, it is computationally infeasible to find a second input which maps to the same output.
[ISO/IEC 10118-1]
NOTE 1 Computational feasibility depends on the specific security requirements and environment.
NOTE 2 For the purposes of this document, the recommended hash-functions are those defined in ISO/IEC 10118-2
and ISO/IEC 10118-3.
3.5
nearly prime number
positive integer n = m⋅r, where m is a large prime number and r is a small smooth integer
NOTE The meaning of the terms large and small prime numbers is dependent on the application, and is based on
bounds determined by the designer.
3.6
order of an elliptic curve E(F)
number of points on an elliptic curve E defined over a finite field F
3.7
smooth integer
integer r whose prime factors are all small (i.e. less than some defined bound)
4 Notation and conversion functions
4.1 Notation
In this part of ISO/IEC 15946, the following notation is used to describe public-key systems based on elliptic
curve technology.
B
B An embedding degree, the smallest B such that #E(F(q)) | q -1.
2 © ISO/IEC 2009 – All rights reserved

2 3 m
E An elliptic curve, given by an equation of the form Y = X + aX + b over the field F(p ) for
2 3 2 m
p>3, by an equation of the form Y + XY = X + aX + b over the field F(2 ), or by an
2 3 2 m
equation of the form Y = X + aX + b over the field F(3 ), together with an extra point O
E
m m
referred to as the point at infinity. The elliptic curve is denoted by E/F(p ), E/F(2 ), or
m
E/F(3 ), respectively.
m
NOTE 1 In applications not based on a pairing, E/F(p) or E/F(2 ) is preferable from an efficiency
m
point of view. In applications that use a pairing, E/F(p) or E/F(3 ) is preferable from an efficiency point
of view.
#E(F(q)) The order (or cardinality) of E(F(q)).
n A prime divisor of #E(F(q)).
N The number of points on an elliptic curve E over F(q), #E(F(q)).
r The cofactor, that is #E(F(q)) = rn.
4.2 Conversion functions
For the purposes of this part of ISO/IEC 15946, the following conversion functions, defined in
ISO/IEC 15946-1:2008, are used.
BS2IP The bit string to integer conversion primitive
BS2OSP The bit string to octet string conversion primitive
EC2OSP The elliptic curve point to octet string conversion primitive
E
FE2IP The finite field element to integer conversion primitive
F
FE2OSP The finite field element to octet string conversion primitive
F
I2BSP The integer to bit string conversion primitive
I2OSP The integer to octet string conversion primitive
I2ECP The integer to elliptic curve conversion primitive
OS2BSP The octet string to bit string conversion primitive
OS2FEP The octet string to finite field element conversion primitive
F
OS2ECP The octet string to elliptic curve point conversion primitive
E
OS2IP The octet string to integer conversion primitive
5 Framework for elliptic curve generation
5.1 Types of trusted elliptic curve
There are a number of ways in which a user can obtain trust in the provenance of an elliptic curve, including
the following.
⎯ The curve may be obtained from an impartial trusted source (e.g. an international or national standard).
⎯ The curve may be generated and/or verified by a trusted third party.
© ISO/IEC 2009 – All rights reserved 3

⎯ The curve may be generated and/or verified by the user.
5.2 Overview of elliptic curve generation
There are three main ways to generate elliptic curves.
⎯ Generate an elliptic curve by applying the order counting algorithms to a (pseudo-)randomly chosen
elliptic curve. Such a technique is specified in Clause 6.
⎯ Generate an elliptic curve by applying the complex multiplication method. Such a technique is specified in
Clause 7.
⎯ Generate an elliptic curve by lifting an elliptic curve over a small finite field to that over a reasonably large
field. Such a technique is specified in Clause 8.
6 Verifiably Pseudo-Random Elliptic curve generation
6.1 Constructing Verifiably Pseudo-Random Elliptic Curves (prime case)
6.1.1 Construction algorithm
The following algorithm produces a set of elliptic curve parameters over a field F(p) selected
(pseudo-)randomly from the curves of appropriate order, along with sufficient information for others to verify
that the curve was indeed chosen pseudo-randomly.
NOTE 1 The algorithm is consistent with [16].
It is assumed that the following quantities have been chosen:
⎯ lower bound n for the order of the base point.
min
⎯ a cryptographic hash function H with output length L bits.
Hash
⎯ the bit length L of inputs to H, satisfying L ≥ L .
Hash
The following notation is adopted below:
⎯ v = ⎡log p⎤,
⎯ s = ⎣(v - 1)/L ⎦,
Hash
⎯ w = v - sL - 1.
Hash
Input: a prime number p; lower bound n for n; a trial division bound l .
min max
Output: a bit string X; EC parameters a, b, n, and G.
a) Choose an arbitrary bit string X of bit length L.
b) Compute h = H (X).
c) Let W be the bit string obtained by taking the w rightmost bits of h.
d) Convert X to an integer Z = BS2IP(X).
4 © ISO/IEC 2009 – All rights reserved

e) For i from 1 to s do:
L
1) Convert the integer (Z + i) mod 2 to a length-L bit string X using I2BSP.
i
2) Compute W = H (X ).
i i
f) Let W be the bit string obtained by the concatenation of W , W , …, W as follows:
0 1 s
W = W || W || … || W .
0 1 s
g) Convert W to a finite field element c = OS2FEP (BS2OSP (W)).
h) If c = 0 or 4c + 27 = 0 , then go to Step a).
F F
2 3
i) Choose finite field elements a, b ∈ F(p) such that b ≠ 0 and cb - a = 0 .
F F
NOTE 2 The simplest choice is a = c and b = c. However, an implementer may want to choose differently for
performance reasons.
2 3
j) Compute the order #E(F(p)) of the elliptic curve E over F(p) given by y = x + ax + b.
k) Test whether #E(F(p)) is a nearly prime number using the algorithm specified in 6.1.2. If so, the output of
the algorithm specified in 6.1.2 consists of the integers r, n. If not, then go to Step a).
l) Check E(F(p)) satisfies the MOV-condition specified in B.2.3, that is the smallest integer B such that n
B
divides q - 1 ensures the desirable security level. If not, then go to Step a).
m) Test whether #E(F(p)) ≠ p in order to be secure against the attack specified in B.2.2. If not, then go to
Step a).
n) Test whether the prime divisor n satisfies the condition described in B.2.4 for cryptosystems based on
ECDLP, ECDHP, or BDHP with auxiliary inputs as in B.1.5. If not, then go to Step a).
o) Generate a point G on E of order n using the algorithm specified in 6.1.3.
p) Output X, a, b, n, G.
NOTE 3 The necessity of near primality is described in B.2.2.
NOTE 4 Methods to compute the order #E(F(p)) are described in [5], [26] and [29].
6.1.2 Test for Near Primality
Given a lower bound n and a trial division bound l , the following procedures test N = #E(F(p)) for near
min max
primality.
Input: positive integers N, l , and n .
max min
Output: if N is nearly prime, output a prime n with n ≤ n and a smooth integer r such that N = rn. If N is not
min
nearly prime, output the message “not nearly prime”.
a) Set n = N, r = 1.
b) For l from 2 to l do
max
1) If l is composite then go to Step 3).
2) While (l divides n)
© ISO/IEC 2009 – All rights reserved 5

⎯ Set n = n/l and r = rl.
⎯ If n < n then output “not nearly prime” and stop.
min
3) Next l.
c) Test n for primality.
d) If n is prime then output r and n and stop.
e) Output “not nearly prime”.
NOTE Methods to test for primality are described in [3] and [4].
6.1.3 Finding a Point of Large Prime Order
If the order #E(F(q)) of an elliptic curve E is nearly prime, the following algorithm efficiently produces a random
point in E(F(q)) whose order is the large prime factor n of #E(F(q)) = rn.
Input: an elliptic curve E over the field F(q), a prime n, and a positive integer r not divisible by n.
Output: if #E(F(q)) = rn, a point G on E of order n; if not, the message “wrong order.”
a) Generate a random point P (not O ) on E.
E
b) Set G = rP.
c) If G = O then go to Step a).
E
d) Set Q = nG.
e) If Q ≠ O then output “wrong order” and stop.
E
f) Output G.
6.1.4 Verification of Elliptic Curve Pseudo-Randomness
The following algorithm determines whether an elliptic curve over F(p) was generated using the method of
6.1.1. The quantities L , L, v, s, and w, and the hash function H, are as in 6.1.1.
Hash
Input: a bit string X of length L, EC parameters q = p, a, b, n, and G = (x , y ), and a positive integer n .
G G min
Output: “True” or “False”.
a) Compute h = H (X).
b) Let W be the bit string obtained by taking the w rightmost bits of h.
c) Convert X to an integer Z = BS2IP(X).
d) For i from 1 to s do:
L
1) Compute Z = Z + i mod 2 .
L
2) Convert Z mod (2 ) to a bit string X = I2BSP(Z).
i
3) Compute W = H (X ).
i i
6 © ISO/IEC 2009 – All rights reserved

e) Let W be the bit string obtained by the concatenation of W , W , …, W as follows:
0 1 s
W = W || W || … || W .
0 1 s
f) Convert W to a finite field element c = OS2FEP (BS2OSP (W)).
g) Verify the following conditions.
⎯ n ≥ n
min
⎯ n is a prime.
⎯ c ≠ 0
F
⎯ 4c + 27 ≠ 0 .
F
⎯ b ≠ 0
F
2 3
⎯ cb - a = 0 .
F
⎯ G ≠ O
E
2 3
⎯ y = x + ax + b.
G G G
⎯ nG = O
E
h) If all the conditions in Step g) hold, then output “True”; otherwise output “False”.
6.2 Constructing Verifiably Pseudo-Random Elliptic Curves (binary case)
6.2.1 Construction algorithm
The following algorithm produces a set of elliptic curve parameters for a pseudo-random curve over a field
m
F(2 ), along with sufficient information for others to verify that the curve was indeed chosen pseudo-randomly.
NOTE 1 The algorithm is consistent with [16].
It is assumed that the following quantities have been chosen:
m
⎯ a field F(2 )
⎯ a lower bound n for the order of the base point
min
⎯ a cryptographic hash function H with output length L bits
Hash
⎯ the bit length L of inputs to H, satisfying L ≥ L .
Hash
The following notation is adopted below:
⎯ s = ⎣(m - 1)/ L ⎦,
Hash
⎯ w = m - sL .
Hash
m
Input: a field F(2 ); a lower bound n for n; a trial division bound l .
min max
Output: a bit string X; EC parameters a, b, n, and G.
© ISO/IEC 2009 – All rights reserved 7

a) Choose an arbitrary bit string X of bit length L.
b) Compute h = H (X).
c) Let W be the bit string obtained by taking the w rightmost bits of h.
d) Convert the length-L bit string X to an integer z using BS2IP.
e) For i from 1 to s do:
L
⎯ Convert the integer (z + i) mod (2 ) to a length-L bit string X using I2BSP.
i
⎯ Compute W = H (X ).
i i
f) Let W be the bit string obtained by the concatenation of W , W , …, W as follows:
0 1 s
W = W || W || … || W .
0 1 s
g) Convert the length-m bit string W to a field element b using BS2OSP and OS2FEP.
h) If b = 0 , then go to Step a).
F
m
i) Let a be an arbitrary element in F(2 ). (The simplest choice is a = 0 . However, one may want to choose
F
differently for performance reasons.)
m m 2 3 2
j) Compute the order #E(F(2 )) of the elliptic curve E over F(2 ) given by y + xy = x + ax + b.
m
k) Test whether #E(F(2 )) is a nearly prime number using the algorithm specified in 6.1.2. If so, the output of
the algorithm specified in 6.1.2 consists of the integers r, n. If not, then go to Step a).
m
l) Check E(F(2 )) satisfies the MOV-condition specified in B.2.3. If not, then go to Step a).
m) Test whether the prime divisor n satisfies the condition described in B.2.4 for cryptosystems based on
ECDLP, ECDHP, or BDHP with auxiliary inputs as in B.1.5. If not, then go to Step a).
n) Generate a point G on E of order n using the algorithm specified in 6.1.3.
o) Output X, a, b, n, G.
NOTE 2 The necessity of near primality is described in B.2.2.
m
NOTE 3 Methods of computing the order #E(F(2 )) are described in [5], [26] and [29].
6.2.2 Verification of Elliptic Curve Pseudo-Randomness
The following algorithm verifies the validity of a set of elliptic curve parameters. In addition, it determines
m
whether an elliptic curve over F(2 ) was generated using the method of 6.2.1.
The quantities L , L, s, and w, and the hash function H, are as in 6.2.1.
Hash
m
Input: a bit string X of length L, EC parameters q = 2 , a, b, n, and G = (x , y ), and a positive integer n .
G G min
Output: “True” or “False”.
a) Compute h = H (X).
b) Let W be the bit string obtained by taking the w rightmost bits of h.
c) Convert the bit string X to an integer z via BS2IP.
8 © ISO/IEC 2009 – All rights reserved

d) For i from 1 to s do:
L
1) Convert the integer (z + i) mod (2 ) to a length-L bit string X via I2BSP.
i
2) Compute W = H (X ).
i i
e) Let W be the bit string obtained by the concatenation of W , W , …, W as follows:
0 1 s
W = W || W || … || W
0 1 s
f) Convert the length-m bit string W to the field element b′ via BS2OSP and OS2FEP.
g) Verify the following conditions.
⎯ n ≥ n
min
⎯ n is a prime.
⎯ b ≠ 0
F
⎯ b = b′
⎯ G ≠ O
E
2 3 2
⎯ y + x y = x + ax + b
G G G G G
⎯ nG = O
E
h) If all the conditions in Step g) hold, then output “True”; otherwise output “False”.
7 Constructing Elliptic Curves by Complex Multiplication
7.1 General Construction (prime case)
The following algorithm produces an elliptic curve E over F(p) with the given number of rational points N.
NOTE 1 The algorithm is based on [11], which is applied to primality proving [4].
Input: The definition field F(p) and the number of points N = rn, where n is the largest prime divisor of N and r
is a cofactor.
Output: curve parameters of elliptic curve E with #E(F(p)) = N and base point G
a) Test whether the prime divisor n satisfies the condition described in B.2.4 for cryptosystems based on
ECDLP, ECDHP, or BDHP with auxiliary inputs as in B.1.5. If not, then execute a new input.
b) Set t = p + 1 - N.
2 2
c) Choose a pair of integers (D,V) such that 4p - t = DV .
d) Construct the Hilbert class polynomial P (X).
D
e) Find a solution j in F(p) of P (X) = 0 modulo p.
0 D
f) Choose c ∈ F(p)* and construct an elliptic curve over F(p) with the j-invariant j .
2 3 2 3
⎯ E , , : y = x + (3c j / (1728 - j ))x + 2c j / (1728 - j ) (if j ≠ 0 , 1728).
D j0 c 0 0 0 0 0 F
© ISO/IEC 2009 – All rights reserved 9

2 3
⎯ E , , : y = x + c (if j = 0 ).
D j0 c 0 F
2 3
⎯ E , , : y = x + cx (if j = 1728).
D j0 c 0
g) Construct a random point G on E , , (F(p)) such that G ≠ O and r⋅G ≠ O .
D j0 c E E
h) Set G = r⋅G.
i) If n⋅G = O , output curve parameters of E , , and the base point G. If n⋅G ≠ O , go to Step f) to choose
E D j0 c E
another c.
2 2
NOTE 2 Any pair of integers (D,V) such that 4p - t = DV can be used in Step c).
NOTE 3 The definition of the Diophantine equation used in Step c) is given in A.5.
NOTE 4 The definition of the Hilbert class polynomial P (X) is given in A.2.
D
7.2 MNT curve (Miyaji-Nakabayashi-Takano curve)
The following algorithm produces an elliptic curve E over F(p) with the embedding degree B = 6, which is
useful for cryptosystems based on a bilinear pairing. The pairing and the embedding degree are described
in A.3 and B.2.2, respectively.
NOTE 1 Detailed information is given in [20].
Input: lower and upper bound (odd integer) p and p for the definition field (in bits) and upper bound D
min max max
for size of D.
Output: prime p, curve parameters of elliptic curve E/F(p), the order n = #E(F(p)), and basepoint G.
a) Choose a small positive integer D < D such that D ≡ 3 (mod 8) and go to Step c).
max
b) If such D does not exist, then stop and output “fail”.
2 2
c) Find a pair of integers (T,U) with the smallest U > 0 that satisfies T - 3DU = ±1 using the continued
fraction algorithm.
2 2
d) Find a pair of integers (x, y) that satisfies x - 3Dy = -8 and
0 ≤ x < 2U√(2D), 2√(2/D) ≤ y < 2T√(2/D),
using the algorithm of Lagrange. If not, go to Step a).
e) i = 0.
f) Find a pair of primes (p,n) as follows:
i
1) Compute integers x and y such that x + y √(3D) = (x + y√(3D)) (T + U√(3D)) .
i i i i
2) If x ≡ 1(mod 6), then s = (x - 1)/6 and p = 4s - 1;
i i
⎯ else if x ≡ -1(mod 6), then s = (x + 1)/6 and p = 4s - 1;
i i
⎯ else, i = i + 1 and go to Step 1).
3) If p < p , then i = i + 1 and go to Step 1).
min
4) If p > p , then go to Step a).
max
10 © ISO/IEC 2009 – All rights reserved

2 2
5) If p is prime, then n = 4s + 2s + 1 and n = 4s - 2s + 1;
1 2
⎯ else, i = i + 1 and go to Step 1).
6) If n or n prime, then n = n or n = n , respectively and go to Step g);
1 2 1 2
⎯ else, i = i + 1 and go to Step 1).
g) Test whether the prime divisor n satisfies the condition described in B.2.4 for cryptosystems based on
ECDLP, ECDHP, or BDHP with auxiliary inputs as in B.1.5. If not, then go to Step a).
h) Construct the Hilbert class polynomial P (X).
D
i) Find a solution j in F(p) of P (X) = 0 modulo p.
0 D
j) Choose c ∈ F(p)* and construct an elliptic curve over F(p) with the j-invariant j .
2 3 2 3
⎯ E , , : y = x + (3c j / (1728 - j ))x + 2c j / (1728 - j ) (if j ≠ 0 , 1728).
D j0 c 0 0 0 0 0 F
2 3
⎯ E , , : y = x + c (if j = 0 ).
D j0 c 0 F
2 3
⎯ E , , : y = x + cx (if j = 1728).
D j0 c 0
k) Construct a random point G on E , , (F(p)), not equal to the point at infinity O .
D j0 c E
l) If n⋅G = O , output p, E, n, and G.
E
m) Else, go to Step h) to choose another c ∈ F(p)*.
NOTE 2 The definition of the Hilbert class polynomial P (X) is given in A.2.
D
NOTE 3 The continued fraction algorithm in Step c) is given in A.3 and [23].
NOTE 4 The algorithm of Lagrange in Step d) is given in A.4, [18] and [21].
NOTE 5 A technique for speeding up a protocol based on a bilinear pairing is described in [6].
7.3 BN curve (Barreto-Naehrig curve)
The following algorithm produces an elliptic curve E over F(p) with the embedding degree B = 12, which is
useful for cryptosystems based on bilinear pairings. The embedding degree is described in B.2.2.
NOTE 1 Detailed information is given in [6].
Input: the approximate desired size m of the curve order (in bits) and upper bound (odd integer) p for the
max
definition field
Output: prime p, curve parameters of elliptic curve E/F(p), the order n = #E(F(p)), and basepoint G.
4 3 2
a) Let P(u) = 36u + 36u + 24u + 6u + 1.
m/4
b) Compute the smallest u ≈ 2 such that ⎡log P(-u)⎤ = m.
c) While p ≤ p
max
1) t = 6u + 1.
2) p = P(-u) and n = p + 1 - t.
© ISO/IEC 2009 – All rights reserved 11

3) If p and n are prime then go to Step e).
4) p = P(u) and n = p + 1 - t.
5) If p and n are prime, then go to Step e).
6) u = u + 1 and go to Step 1).
d) Stop and output “fail”.
e) Test whether the prime divisor n satisfies the condition described in B.2.4 for cryptosystems based on
ECDLP, ECDHP, or BDHP with auxiliary inputs as in B.1.5. If not, then go to Step a).
f) b = 0.
g) If b + 1 is not represented by b + 1 = y modulo p for an integer y , then b = b + 1 and go to Step g).
0 0
2 3
h) Set an elliptic curve E: y = x + b.
i) Compute a square root y = √(b + 1) modulo p.
j) Set the basepoint G = (1, y ) ∈ E.
k) If n⋅G ≠ O , then set b = b + 1 and go to Step g).
E
l) Output p, E, n, and G.
NOTE 2 A technique for speeding up a protocol based on a bilinear pairing is described in [6].
7.4 F curve (Freeman curve)
The following algorithm produces an elliptic curve E over F(p) with embedding degree B = 10, which is useful
for cryptosystems based on a bilinear pairing. The embedding degree is described in B.2.2.
NOTE 1 Detailed information is given in [13].
Input: lower and upper bound p and p for the size of the definition field (in bits) and upper bound D for
min max max
size of D.
Output: prime p, curve parameters of elliptic curve E/F(p), the order n = #E(F(p)), and basepoint G.
a) Choose a small positive integer D < D such that D ≡ 43 or 67 (mod 120) and 15D is square-free and go
max
to Step c).
b) If such D does not exist, then stop and output “fail”.
2 2
c) Find a pair of integers (T,U) with the smallest U > 0 that satisfies T - 15DU = ±1 using the continued
fraction algorithm.
d) Let d = T - U√(15D).
2 2 2
e) Let g = d if T - 15DU = -1, and let g = d otherwise.
2 2
f) Find a pair of integers (x, y) that satisfies x - 15Dy = -20 and 0 ≤ x < 10U√(3D), 2√1/(3D) ≤ y < 2T√1/(3D)
using the algorithm of Lagrange.
g) For the solution (x, y) in Step f).
12 © ISO/IEC 2009 – All rights reserved

1) If x = ±5 (mod 15), then:
⎯ Let s = (-5 ± x)/ 15.
4 3 2
⎯ Let p = 25s + 25s + 25s + 10s + 3.
4 3 2
⎯ Let n = 25s + 25s + 15s + 5s + 1.
2) Else, go to Step f) to the next (x, y).
3) If p > p , go to Step f) to use the next (x, y).
max
4) Else if p < p , then go to Step 6).
min
5) If p and n are primes, go to Step h).
6) Find a pair of integers (x’, y’) such that x’ + y’√15D = (x + y√15D)⋅g.
7) Let x = x’ and y=y’ and return to Step 1).
h) Test whether the prime divisor n satisfies the condition described in B.2.4 for cryptosystems based on
ECDLP, ECDHP, or BDHP with auxiliary inputs as in B.1.5. If not, then go to Step a).
i) Construct the Hilbert class polynomial P (X).
D
j) Find a solution j in F(p) of P (X) = 0 modulo p.
0 D
k) Choose c ∈ F(p)* and construct an elliptic curve E over F(p) with j-invariant j :
2 3 2 3
⎯ E , , : y = x + (3c j / (1728 - j ))x + 2c j / (1728 - j ) (if j ≠ 0 , 1728).
D j0 c 0 0 0 0 0 F
2 3
⎯ E , , : y = x + c (if j = 0 ).
D j0 c 0 F
2 3
⎯ E , , : y = x + cx (if j = 1728).
D j0 c 0
l) Construct a random point G on E , , (F(p)), not equal to the point at infinity O .
D j0 c E
m) If n⋅G = O , output p, E, n, and G.
E
n) Else, go to Step k) to choose another c ∈ F(p)*.
NOTE 2 The definition of the Hilbert class polynomial P (X) in Step i) is given in A.2.
D
NOTE 3 The continued fraction algorithm in Step c) is given in A.3 and [23].
NOTE 4 The algorithm of Lagrange in Step f) is given in A.4, [18] and [21].
NOTE 5 A technique to speed up a protocol based on a bilinear pairing is described in [6].
7.5 CP curve (Cocks-Pinch curve)
The following algorithm produces an elliptic curve E over F(p) with arbitrary embedding degree B, which is
useful for cryptosystems based on a bilinear pairing. The embedding degree is described in B.2.2.
NOTE 1 Detailed information is given in [7].
Input: a positive integer B and a set R of prime numbers n (n-1 is divisible by B).
© ISO/IEC 2009 – All rights reserved 13

Output: prime p, curve parameters of elliptic curve E/F(p), the order n⋅r = #E(F(p)), and basepoint G.
a) Choose a small square-free positive integer D and n in R such that -D is a square modulo n.
1) Find a B-th root of unity z in F(n)\{0, 1}.
2) t' = z + 1
3) y’ = (t'-2)/ √(-D) (mod n)
4) Let t be an integer such that t is equal to t' modulo n, and let y be an integer such that y is equal to y'
modulo n.
NOTE 2 t = t' and y = y’ are permitted.
2 2
5) p = (t + Dy ) / 4
6) If p is not prime, then go to Step a).
b) Test whether the prime divisor n satisfies the condition described in B.2.4 for cryptosystems based on
ECDLP, ECDHP, or BDHP with auxiliary inputs as in B.1.5. If not, then go to Step a).
c) Construct the Hilbert class polynomial P (X).
D
d) Find a solution j in F(p) of P (X) = 0 modulo p.
0 D
e) Choose c ∈ F(p)* and construct an elliptic curve over F(p) with the j-invariant j .
2 3 2 3
⎯ E , , : y = x + (3c j / (1728 - j ))x + 2c j / (1728 - j ) (if j ≠ 0 , 1728).
D j0 c 0 0 0 0 0 F
2 3
⎯ E , , : y = x + c (if j = 0 ).
D j0 c 0 F
2 3
⎯ E , , : y = x + cx (if j = 1728).
D j0 c 0
f) Set a cofactor r = (p + 1 - t) / n.
g) Construct a random point G on E , , (F(p)) such that G ≠ O and r⋅G ≠ O .
D j0 c E E
h) Set G = r⋅G.
i) If n⋅G = O , output n, G, and the elliptic curve E.
E
j) Else, go to Step e) to choose another c ∈ F(p)*.
NOTE 3 The definition of the Hilbert class polynomial P (X) in Step c) is given in A.2.
D
NOTE 4 A technique for speeding up a protocol based on a bilinear pairing is described in [6].
8 Constructing Elliptic Curves by Lifting
m
The following algorithm produces an elliptic curve E over F(p ) by lifting an elliptic curve E over F(p).
NOTE The algorithm is based on [29].
Input: small finite field F(p), elliptic curve E over F(p), lower and upper bound N and N for the order of
min max
elliptic curve (in bits).
14 © ISO/IEC 2009 – All rights reserved

m
Output: extension degree m, order N = #E(F(p )), basepoint G, and order n of G.
m
a) Count the order of N = #E(F(p)), which is easily executed since F(p) is small.
b) Set t = p + 1 - N and compute algebraic integers α and β that satisfy t = α + β and p = α β.
c) Set m = 1.
d) Find a triple of (m, N , n) as follows:
m
m m m m
1) Compute N = p + 1 – (α + β ) and q = p , which is an integer.
m
2) If N < N , then m = m + 1 and go to Step 1).
m min
3) If N > N , then stop and output “fail”.
m max
4) Test whether N is a nearly prime number using the algorithm specified in 6.1.2. If so, the output of
m
6.1.2 consists of the integers r and n. If not, then m = m + 1 and go to Step 1).
5) Check whether E(F(q)) satisfies the MOV-condition specified in B.2.3, that is the smallest integer B
B
such that n divides q – 1 ensures the desirable security level. If not, then m = m + 1 and go to
Step 1).
e) Generate a point G on E(F(q)) of order n using the algorithm specified in 6.1.3.
f) Output an extension degree m, the order N = #E(F(q)), a basepoint G and the order n.
m
© ISO/IEC 2009 – All rights reserved 15

Annex A
(informative)
Background information on elliptic curves
A.1 j-invariant
m
Let F(q) be a finite field with q = p , where prime p > 3. Let E be an elliptic curve over F(q) given by the short
Weierstrass equation,
2 3
Y = X + aX + b with a, b ∈ F(q),
3 2
where the inequality 4a + 27b ≠ 0 holds in F(q). Then the j-invariant is defined as
F
3 3 2
j = 1728⋅(4a )/(4a + 27b ).
m m
Let F(2 ), for some m ≥ 1, be a finite field. Let E be an elliptic curve over F(2 ) given by the equation
2 3 m
Y + XY = X + aX + b with a, b ∈ F(2 )
where b ≠ 0 . Then the j-invariant is defined as
F
j = 1/ b.
m m
Let F(3 ), for some m ≥ 1, be a finite field. Let E be an elliptic curve over F(3 ) given by the equation
2 3 2 m
Y = X + aX + b with a, b ∈ F(3 )
such that a, b ≠ 0 . Then the j-invariant is defined as
F
j = −a /b.
A.2 Hilbert class polynomial
The construction of elliptic curves by complex multiplication uses the theory of imaginary quadratic fields
Q(√−D). In the case of the imaginary quadratic field Q(√−D), the Hilbert class field K is the extension field of
Q(√−D), which is the unramified abelian extension of Q(√−D). The Hilbert class polynomial P (X) is defined by
D
the minimum polynomial of K over Q(√−D). In the construction of elliptic curves by complex multiplication, the
fact that the j-invariants of elliptic curves E/F(p) are given as a solution of a Hilbert class polynomial P (X)
D
modulo p is used.
NOTE 1 These facts are described in [7] and [10].
NOTE 2 Online databases of Hilbert class polynomials are available in [17].
A.3 Cryptographic pairing
A cryptographic pairing e satisfies the conditions of non-degeneracy, bilinearity, and computability. A pairing
n
e is defined over < G > × < G > as follows,
n 1 2
e : < G > × < G > → µ ,
n 1 2 n
16 © ISO/IEC 2009 – All rights reserved

where < G > and < G > are the cyclic groups of order n and µ is the cyclic group of the n-th roots of unity. A
1 2 n
pairing e is realized by restricting the domain of the Weil or Tate pairings.
n
A.4 Pell Equation
The Pell equation is of the form
2 2
T − dU = ±1,
where d is a fixed integer. In the construction of elliptic curves by complex multiplication, the Pell equation with
a positive integer d that is not a perfect square is used. Then all positive integer solutions of (T,U) are given by
using the least positive solution (T ,U ) with the smallest U > 0 as follows:
0 0 0
k
T + U√d = (T + U√d)
0 0
for k = 1, 2, ….
NOTE These facts are described in [24].
2 2
A.5 The Diophantine equation x − dy = n
2 2
In the construction of elliptic curves by complex multiplication, the Diophantine equation x − dy = n is used.
Here n is an integer and d is a positive integer that is not a perfect square. The number of integer solutions of
this equation is zero or infinite. All positive solutions (x, y) are given by using the least positive solution (T ,U )
0 0
2 2
with the smallest U > 0 of the related Pell equation of T − dU = 1.
NOTE Details are described in [24].
© ISO/IEC 2009 – All rights reserved 17

Annex B
(informative)
Background information on elliptic curve cryptosystems
B.1 Definition of cryptographic problems
B.1.1 The elliptic curve discrete logarithm problem (ECDLP)
For an elliptic curve E/F(q), the base point G ∈ E(F(q)) with order n, and a point P∈E(F(q)), the elliptic curve
discrete logarithm problem (with respect to the base point G) is to find the integer x ∈ [0, n-1] such that P = xG
if such an x exists.
The security of elliptic curve cryptosystems is based on the believed hardness of the elliptic curve discrete
logarithm problem.
B.1.2 The computational elliptic curve Diffie-Hellman problem (ECDHP)
For an elliptic curve E/F(q), the base point G ∈ E(F(q)) with order n, and points aG, bG ∈ E(F(q)), the
computational elliptic curve Diffie-Hellman problem is to compute abG.
The security of some elliptic curve cryptosystems is based on the believed hardness of the computational
elliptic curve Diffie-Hellman problem.
B.1.3 The decisional elliptic curve Diffie-Hellman problem (ECDDHP)
For an elliptic curve E/F(q), the base point G ∈ E(F(q)) with order n, and points aG, bG, Y ∈ E(F(q)), the
decisional elliptic curve Diffie-Hellman problem is to decide wh
...