ISO/IEC 15946-5:2017

INTERNATIONAL ISO/IEC
STANDARD 15946-5
Second edition
2017-08
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 2017
© ISO/IEC 2017, Published in Switzerland
All rights reserved. Unless otherwise specified, no part of this publication may be reproduced or utilized otherwise in any form
or by any means, electronic or mechanical, including photocopying, or posting on the internet or an intranet, without prior
written permission. Permission can be requested from either ISO at the address below or ISO’s member body in the country of
the requester.
ISO copyright office
Ch. de Blandonnet 8 • CP 401
CH-1214 Vernier, Geneva, Switzerland
Tel. +41 22 749 01 11
Fax +41 22 749 09 47
copyright@iso.org
www.iso.org
ii © ISO/IEC 2017 – All rights reserved

Contents Page
Foreword .iv
Introduction .v
1 Scope . 1
2 Normative references . 1
3 Terms and definitions . 1
4 Symbols and conversion functions . 2
4.1 Symbols . 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 . 3
6 Verifiably pseudo-random elliptic curve generation . 4
6.1 General . 4
6.2 Constructing verifiably pseudo-random elliptic curves (prime case) . 4
6.2.1 Construction algorithm . 4
6.2.2 Test for near primality . 5
6.2.3 Finding a point of large prime order . 5
6.2.4 Verification of elliptic curve pseudo-randomness . 6
6.3 Constructing verifiably pseudo-random elliptic curves (binary case) . 7
6.3.1 Construction algorithm . 7
6.3.2 Verification of elliptic curve pseudo-randomness . 8
7 Constructing elliptic curves by complex multiplication . 8
7.1 General construction (prime case) . 8
7.2 Miyaji-Nakabayashi-Takano (MNT) curve . 9
7.3 Barreto-Naehrig (BN) curve .10
7.4 Freeman curve (F curve) .11
7.5 Cocks-Pinch (CP) curve . .13
8 Constructing elliptic curves by lifting .13
Annex A (informative) Background information on elliptic curves .15
Annex B (informative) Background information on elliptic curve cryptosystems .17
Annex C (informative) Numerical examples .20
Annex D (informative) Summary of properties of elliptic curves generated by the complex
multiplication method .28
Bibliography .29
© ISO/IEC 2017 – 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.
The procedures used to develop this document and those intended for its further maintenance are
described in the ISO/IEC Directives, Part 1. In particular the different approval criteria needed for
the different types of document should be noted. This document was drafted in accordance with the
editorial rules of the ISO/IEC Directives, Part 2 (see www .iso .org/ directives).
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. Details of any patent rights identified during the development of the document will be in the
Introduction and/or on the ISO list of patent declarations received (see www .iso .org/ patents).
Any trade name used in this document is information given for the convenience of users and does not
constitute an endorsement.
For an explanation on the voluntary nature of standards, the meaning of ISO specific terms and
expressions related to conformity assessment, as well as information about ISO’s adherence to the
World Trade Organization (WTO) principles in the Technical Barriers to Trade (TBT) see the following
URL: w w w . i s o .org/ iso/ foreword .html.
This document was prepared by Technical Committee ISO/IEC JTC 1, Information technology,
Subcommittee SC 27, IT Security techniques.
This second edition cancels and replaces the first edition (ISO/IEC 15946-5:2009), which has been
technically revised.
It also incorporates the Technical Corrigendum ISO/IEC 15946-5:2009/Cor.1:2012.
The main technical changes between the first edition and this second edition are as follows:
— the terms and definitions given in ISO/IEC 15946-1 are used;
— the scope of verifiably pseudo-random elliptic curve generation has been added;
— the numerical examples in C.4.2 and C.4.3 have been modified.
A list of all parts in the ISO/IEC 15946 series can be found on the ISO website.
iv © ISO/IEC 2017 – 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 independently suggested the use of elliptic curves for public-key cryptographic systems
in 1985, 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 document describes elliptic curve generation techniques useful for implementing the elliptic curve
based mechanisms defined in ISO/IEC 29192-4, ISO/IEC 9796-3, ISO/IEC 11770-3, ISO/IEC 14888-3, and
ISO/IEC 18033-2.
It is the purpose of this document 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 2017 – All rights reserved v

INTERNATIONAL STANDARD ISO/IEC 15946-5:2017(E)
Information technology — Security techniques —
Cryptographic techniques based on elliptic curves —
Part 5:
Elliptic curve generation
1 Scope
The ISO/IEC 15946 series specifies public-key cryptographic techniques based on elliptic curves
described in ISO/IEC 15946-1.
This document defines elliptic curve generation techniques useful for implementing the elliptic curve
based mechanisms defined in ISO/IEC 29192-4, ISO/IEC 9796-3, ISO/IEC 11770-3, ISO/IEC 14888-3 and
ISO/IEC 18033-2.
This document is applicable 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). This
document is not applicable to the representation of elements of the underlying finite field (i.e. which
basis is used).
The ISO/IEC 15946 series does not specify the implementation of the techniques it defines.
Interoperability of products complying with the ISO/IEC 15946 series will not be guaranteed.
2 Normative references
The following documents are referred to in the text in such a way that some or all of their content
constitutes requirements 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 terms and definitions given in ISO/IEC 15946-1 and the
following apply.
ISO and IEC maintain terminological databases for use in standardization at the following addresses:
— IEC Electropedia: available at http:// www .electropedia .org/
— ISO Online browsing platform: available at http:// www .iso .org/ obp
3.1
definition field of an elliptic curve
field that includes all the coefficients of the formula describing an elliptic curve
3.2
hash-function
function which maps strings of bits of variable (but usually upper bounded) length 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;
© ISO/IEC 2017 – All rights reserved 1

— for a given input, it is computationally infeasible to find a second input which maps to the same output
Note 1 to entry: Computational feasibility depends on the specific security requirements and environment. Refer
to ISO/IEC 10118-1:2016, Annex C.
[SOURCE: ISO/IEC 10118-1:2016, 3.4]
3.3
nearly prime number
positive integer, n =m⋅r, where m is a large prime number and r is a small smooth integer (3.5)
Note 1 to entry: 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.4
order of an elliptic curve
E(F)
number of points on an elliptic curve, E, defined over a finite field, F
3.5
smooth integer
integer, r, whose prime factors are all small (i.e. less than some defined bound)
4 Symbols and conversion functions
4.1 Symbols
B
Β embedding degree, the smallest B such that number #E[F(q)] | q −1
2 3 m
Ε elliptic curve, given by a formula of the form Y = X + aX + b over the field F(p ) for p > 3, by
2 3 2 m
a formula of the form Y + XY = X + aX + b over the field F(2 ), or by a formula of the form
2 3 2 m
Y = X + aX + b over the field F(3 ), together with an extra point O referred to as the point
E
m m m
at infinity. The elliptic curve is denoted by E/F(p ), E/F(2 ), or 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
m
efficiency point of view. In applications that use a pairing, E/F(p) or E/F(3 ) is preferable
from an efficiency point of view.
NOTE 2  An elliptic curve is not only the set of points on the curve, but also a group under
an operation defined on these points.
N number of points on an elliptic curve E over F(q), #E[F(q)]
n prime divisor of #E[F(q)]
O elliptic curve point at infinity
E
p prime number
m
q prime power, p for some prime p and some integer m ≥ 1
r cofactor, that is #E[F(q)] = rn
#E[F(q)] order (or cardinality) of E[F(q)]
⎾x⏋ smallest integer greater than or equal to the real number x
⎿x⏌ largest integer smaller than or equal to the real number x
2 © ISO/IEC 2017 – All rights reserved

4.2 Conversion functions
BS2IP bit string to integer conversion primitive
BS2OSP bit string to octet string conversion primitive
EC2OSP elliptic curve point to octet string conversion primitive
E
FE2IP finite field element to integer conversion primitive
F
FE2OSP finite field element to octet string conversion primitive
F
I2BSP integer to bit string conversion primitive
I2OSP integer to octet string conversion primitive
I2ECP integer to elliptic curve conversion primitive
OS2BSP octet string to bit string conversion primitive
OS2FEP octet string to finite field element conversion primitive
F
OS2ECP octet string to elliptic curve point conversion primitive
E
OS2IP 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 could be obtained from an impartial trusted source (e.g. an international or national
standard).
— The curve could be generated and/or verified by a trusted third party.
— The curve could be generated and/or verified by the user.
NOTE 1 Refer to Annex A for background information on elliptic curves.
NOTE 2 Refer to Annex B for background information on elliptic curve cryptosystems.
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.
NOTE 1 Refer to Annex A for background information on elliptic curves.
NOTE 2 Refer to Annex B for background information on elliptic curve cryptosystems.
© ISO/IEC 2017 – All rights reserved 3

6 Verifiably pseudo-random elliptic curve generation
6.1 General
The generation of verifiably pseudo-random elliptic curves focuses on curves over prime and binary
fields (and so, for example, does not deal with curves over fields of characteristic 3).
6.2 Constructing verifiably pseudo-random elliptic curves (prime case)
6.2.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 Reference [9].
NOTE 2 Methods of choosing a prime number p (pseudo) randomly are described in Reference [5].
It is assumed that the following quantities have been chosen:
— 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:
— 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) Let Z = BS2IP(X).
e) For i from 1 to s do:
L
1) Let X = I2BSP(Z + i mod 2 ).
i
2) Compute W = H (X ).
i i
f) Let W = W || W || … || W .
0 1 s
g) Let 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 . Choosing a = b = c will
F F
guarantee the conditions hold, and this choice is recommended.
NOTE 3 Choosing a = b = c may not be optimal from a performance perspective.
4 © ISO/IEC 2017 – All rights reserved

NOTE 4 If the default values are chosen as suggested, the randomness of the generated curve is explicitly
guaranteed.
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.2.2. If so, the
output of the algorithm specified in 6.2.2 consists of integers r, n. If not, then go to step a).
NOTE 5 The necessity of near primality is described in B.2.2
l) Check if E[F(p)] satisfies the MOV-condition specified in B.2.3, that is the smallest integer B such
B
that n divides q − 1 ensures the desirable security level. If not, then go to step a).
m) If #E[F(p)] = p, then go to step a).
NOTE 6 This check is performed in order to protect against the attack specified in B.2.2.
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.2.3.
p) Output X, a, b, n, G.
NOTE 7 Methods to compute the order #E[F(p)] are described in References [11], [30] and [31].
6.2.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
min max
near 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
min
is not 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)
i) Set n = n/l and r = rl.
ii) 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 References [5] and [10]
6.2.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.
© ISO/IEC 2017 – All rights reserved 5

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.2.4 Verification of elliptic curve pseudo-randomness
The following algorithm determines whether or not an elliptic curve over F(p) was generated using the
method of 6.2.1. The quantities L , L, v, s, and w, and the hash function H, are as in 6.2.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) Let Z = BS2IP(X).
d) For i from 1 to s do:
L
1) Let X = I2BSP(Z + i mod 2 ).
i
2) Compute W = H (X ).
i i
e) Let W = W || W || … || W .
0 1 s
f) Convert W to a finite field element c = OS2FEP [BS2OSP (W)].
g) Verify the following conditions.
1) n ≥ n .
min
2) n is a prime.
3) c ≠ 0 .
F
4) 4c + 27 ≠ 0 .
F
5) b ≠ 0 .
F
2 3
6) cb − a = 0 .
F
7) G ≠ O .
E
2 3
8) y = x + ax + b.
G G G
9) nG = O .
E
h) If all the conditions in step g) hold, then output “True”; otherwise output “False”.
6 © ISO/IEC 2017 – All rights reserved

6.3 Constructing verifiably pseudo-random elliptic curves (binary case)
6.3.1 Construction algorithm
The following algorithm produces a set of elliptic curve parameters for a pseudo-random curve over
m
a field F(2 ), along with sufficient information for others to verify that the curve was indeed chosen
pseudo-randomly. See Annex C for additional information.
NOTE 1 The algorithm is consistent with Reference [9].
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.
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) Let Z= BS2IP(x).
e) For i from 1 to s, do:
L
1) Let X = I2BSP(Z + i mod 2 ).
i
2) Compute W = H (X ).
i i
f) Let W = W || W || … || W .
0 1 s
g) Let b = OS2FEP [BS2OSP(W)].
h) If b = 0 , then go to step a).
F
m
i) Let a be an arbitrary element in F(2 ). Choosing a = 0 will guarantee the conditions hold, and this
F
choice is recommended.
NOTE 2 The default values may not be chosen because of performance reasons.
NOTE 3 If the default values are chosen as suggested, the randomness is explicitly guaranteed.
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
NOTE 4 Methods of computing the order #E[F(2 )] are described in References [11], [30] and [33].
m
k) Test whether #E[F(2 )] is a nearly prime number using the algorithm specified in 6.2.2. If so, the
output of the algorithm specified in 6.2.2 consists of integers r, n. If not, then go to step a).
m
l) Check that E[F(2 )] satisfies the MOV-condition specified in B.2.3. If not, then go to step a).
© ISO/IEC 2017 – All rights reserved 7

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.2.3.
o) Output X, a, b, n, G.
NOTE 5 The necessity of near primality is described in B.2.2.
6.3.2 Verification of elliptic curve pseudo-randomness
The following algorithm verifies the validity of a set of elliptic curve parameters. In addition, it
m
determines whether an elliptic curve over F(2 ) was generated using the method of 6.3.1.
The quantities L , L, s, and w, and the hash function H, are as in 6.3.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) Let Z = BS2IP(x).
d) For i from 1 to s, do:
L
1) Let X = I2BSP(Z + i mod 2 ).
i
2) Compute W = H (X ).
i i
e) Let W = W || W || … || W
0 1 s.
f) Let b′ = OS2FEP [BS2OSP(W)].
g) Verify the following conditions.
1) n ≥ n
min
2) n is a prime.
3) b ≠ 0
F
4) b = b′
5) G ≠ O
E
2 3 2
6) y + x y = x + ax + b
G G G G G
7) 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.
[10]
NOTE 1 The algorithm is based on Reference [17] which is applied to the primality proving .
8 © ISO/IEC 2017 – All rights reserved

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
1) E : y = x + [3c j / (1 728 − j )]x + 2c j / (1 728 − j ) (if j ≠ 0 , 1 728).
0 0 0 0 0 F
Dj,,c
2 3
2) E : y = x + c (if j = 0 ).
0 F
Dj,,c
2 3
3) E : y = x + cx (if j = 1 728).
Dj,,c
g) Construct a random point G on E [F(p)] such that G ≠ O and r·G ≠ O .
E E
Dj,,c
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
E E
Dj,,c
choose 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 Miyaji-Nakabayashi-Takano (MNT) curve
The following algorithm produces an elliptic curve E over F(p) with 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. Numerical examples and comparisons are given in Annex C and
Annex D, respectively.
NOTE 1 Some information and an algorithm for generating an MNT curve with B = 3 are given in Reference [24].
NOTE 2 MNT curves can be constructed, not only with B = 6, but also with B = 3 and 4.
Input: lower and upper bound (odd integer) p and p for the definition field (in bits) and upper
min max
bound D for size of D.
max
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.
© ISO/IEC 2017 – All rights reserved 9

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
NOTE 3 Not all solutions can be derived in this way.
2) If x ≡ 1(mod 6), then s = (x − 1)/6 and p = 4s + 1;
i i
i) else if x ≡ −1(mod 6), then s = (x + 1)/6 and p = 4s + 1;
i i
ii) 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
2 2
5) If p is prime, then n = 4s + 2s + 1 and n = 4s − 2s + 1;
1 2
i) else, i = i + 1 and go to step 1).
6) If x ≡ 1(mod 6), then n = n ;
i 1
i) else n = n .
7) If n is prime, then go to step g);
i) 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
1) E : y = x + [3c j / (1 728 − j )]x + 2c j / (1 728 − j ) (if j ≠ 0 , 1 728).
0 0 0 0 0 F
Dj,,c
2 3
2) E : y = x + c (if j = 0 ).
0 F
Dj,,c
2 3
3) E : y = x + cx (if j = 1 728).
Dj,,c
k) Construct a random point G on E [F(p)], not equal to the point at infinity O .
E
Dj,,c
l) If n⋅G = O , output p, E, n, and G.
E
m) If n⋅G ≠ O , go to step j) to choose another c ∈ F(p)*.
E
NOTE 4 The definition of the Hilbert class polynomial P (X) is given in A.2.
D
NOTE 5 The continued fraction algorithm in step c) is given in Reference [27].
NOTE 6 The algorithm of Lagrange in step d) is given in References [22] and [25].
NOTE 7 A technique for speeding up a protocol based on a bilinear pairing is described in Reference [12].
7.3 Barreto-Naehrig (BN) curve
The following algorithm produces an elliptic curve E over F(p) with embedding degree B = 12, which
is useful for cryptosystems based on bilinear pairings. The embedding degree is described in B.2.2.
Numerical examples and comparisons are given in Annex C and Annex D, respectively.
NOTE 1 A detailed information is given in Reference [12].
10 © ISO/IEC 2017 – All rights reserved

NOTE 2 This method will always generate at most one curve for a given value of m.
Input: the approximate desired size m of the curve order (in bits) and upper bound (odd integer) p
max
for the 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.
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 3 A technique for speeding up a protocol based on a bilinear pairing is described in Reference [12].
7.4 Freeman curve (F 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.
Numerical examples and comparisons are given in Annex C and Annex D, respectively.
NOTE 1 Detailed information is given in Reference [18].
Input: lower and upper bound p and p for the size of the definition field (in bits) and upper bound
min max
D for size of D.
max
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
max
and go to step c).
b) If such D does not exist, then stop and output “fail”.
© ISO/IEC 2017 – All rights reserved 11

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 g = T − U√ (15D).
2 2
e) 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.
f) For the current solution (x, y).
1) If x = ±5 (mod 15), then:
i) Let s = (−5 ± x)/ 15.
4 3 2
ii) Let p = 25s + 25s + 25s + 10s + 3.
4 3 2
iii) Let n = 25s + 25s + 15s + 5s + 1.
2) Else, go to step 6).
3) If p > p , go to step a) to choose a new D.
max
4) Else if p < p , then go to step 6).
min
5) If p and n are primes, go to step g).
6) Find a pair of integers (x′, y′) such that x′ + y′ √15D = (x + y√15D)⋅g.
NOTE 2 Not all solutions can be derived in this way.
7) Let x = x′ and y=y′ and return 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 E over F(p) with j-invariant j :
2 3 2 3
1) E : y = x + [3c j / (1 728 − j )]x + 2c j / (1 728 − j ) (if j ≠ 0 , 1 728).
0 0 0 0 0 F
Dj,,c
2 3
2) E : y = x + c (if j = 0 ).
0 F
Dj,,c
2 3
3) E : y = x + cx (if j = 1 728).
Dj,,c
k) Construct a random point G on E [F(p)], not equal to the point at infinity O .
E
Dj,,c
l) If n⋅G = O , output p, E, n, and G.
E
m) Else, go to Step j) to choose another c ∈ F(p)*.
NOTE 3 The definition of the Hilbert class polynomial P (X) in step i) is given in A.2.
D
NOTE 4 The continued fraction algorithm in step c) is given in Reference [27].
NOTE 5 The algorithm of Lagrange in step f) is given in References [22] and [25].
NOTE 6 A technique to speed up a protocol based on a bilinear pairing is described in Reference [12].
12 © ISO/IEC 2017 – All rights reserved

7.5 Cocks-Pinch (CP) 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 Reference [13].
Input: a positive integer B and a set R of prime numbers n (n−1 is divisible by B).
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.
b) Find a B-th primitive root of unity z in F(n).
c) t′ = z + 1.
d) y′ = (t′−2)/ √ (−D) (mod n).
e) 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.
2 2
f) p = (t + Dy ) / 4.
NOTE 2 t = t′ and y = y′ can be used.
g) If p is not prime, then go to step a).
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 over F(p) with the j-invariant j .
2 3 2 3
1) E : y = x + [3c j / (1 728 − j )]x + 2c j / (1 728 − j ) (if j ≠ 0 , 1 728).
0 0 0 0 0 F
Dj,,c
2 3
2) E : y = x + c (if j = 0 ).
0 F
Dj,,c
2 3
3) E : y = x + cx (if j = 1 728).
Dj,,c
l) Set a cofactor r = (p + 1 − t) / n.
m) Construct a random point G on E [F(p)] such that G ≠ O and r⋅G ≠ O .
E E
Dj,,c
n) Set G = r⋅G.
o) If n⋅G = O , output n, G, and the elliptic curve E.
E
p) Else, go to step k) 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 Reference [12].
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 Reference [33].
© ISO/IEC 2017 – All rights reserved 13

Input: small finite field F(p), elliptic curve E over F(p), lower and upper bound N and N for the
min max
order of elliptic curve (in bits).
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
1) Compute N = pm + 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.2.2. If so, the
m
output of 6.2.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
B
integer 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.2.3.
f) Output an extension degree m, the order N = #E[F(q)], a basepoint G and the order n.
m
14 © ISO/IEC 2017 – All rights reserved

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 = 1 728·(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 formula:
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 formula:
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 the minimum polynomial of K over Q(√−D). In the construction of elliptic
D
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) modulo p is used.
D
NOTE 1 These facts are described in References [13] and [16].
NOTE 2 Online databases of Hilbert class polynomials are available in Reference [21].
© ISO/IEC 2017 – All rights reserved 15

A.3 Cryptographic pairing
A cryptographic pairing e satisfies the conditions of non-degeneracy, bilinearity, and computability. A
n
pairing e is defined over < G > × < G > as follows,
n 1 2
e : < G > × < G > → μ
n 1 2 n
where < G > and < G > are the cyclic groups of order n and μ is the cyclic group of the n-th roots of
1 2 n
unity. A 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 Reference [28].
2 2
A.5 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 formula is zero or infinite. An infinite number of integer soluti
...