ISO/IEC 15946-5:2009
(Main)Information technology — Security techniques — Cryptographic techniques based on elliptic curves — Part 5: Elliptic curve generation
Information technology — Security techniques — Cryptographic techniques based on elliptic curves — Part 5: Elliptic curve generation
ISO/IEC 15946 specifies public-key cryptographic techniques based on elliptic curves. They include the establishment of keys for secret-key systems and digital signature mechanisms. ISO/IEC 15946-5:2009 defines the elliptic curve generation techniques useful for implementing the mechanisms defined in ISO/IEC 9796-3, ISO/IEC 11770-3, ISO/IEC 14888-3, and ISO/IEC 18033-2. The scope of ISO/IEC 15946-5:2009 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 ISO/IEC 15946-5:2009. 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.
Technologies de l'information — Techniques de sécurité — Techniques cryptographiques fondées sur les courbes elliptiques — Partie 5: Génération de courbes elliptiques
General Information
Relations
Standards Content (Sample)
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 15946-5:2009(E)
©
ISO/IEC 2009
---------------------- Page: 1 ----------------------
ISO/IEC 15946-5:2009(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.
COPYRIGHT PROTECTED DOCUMENT
© 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
---------------------- Page: 2 ----------------------
ISO/IEC 15946-5:2009(E)
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
---------------------- Page: 3 ----------------------
ISO/IEC 15946-5:2009(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 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
---------------------- Page: 4 ----------------------
ISO/IEC 15946-5:2009(E)
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
---------------------- Page: 5 ----------------------
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
---------------------- Page: 6 ----------------------
ISO/IEC 15946-5:2009(E)
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
---------------------- Page: 7 ----------------------
ISO/IEC 15946-5:2009(E)
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
---------------------- Page: 8 ----------------------
ISO/IEC 15946-5:2009(E)
⎯ 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⎤,
2
⎯ 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.
0
d) Convert X to an integer Z = BS2IP(X).
4 © ISO/IEC 2009 – All rights reserved
---------------------- Page: 9 ----------------------
ISO/IEC 15946-5:2009(E)
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
---------------------- Page: 10 ----------------------
ISO/IEC 15946-5:2009(E)
⎯ 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.
0
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
---------------------- Page: 11 ----------------------
ISO/IEC 15946-5:2009(E)
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
---------------------- Page: 12 ----------------------
ISO/IEC 15946-5:2009(E)
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.
0
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.
0
c) Convert the bit string X to an integer z via BS2IP.
8 © ISO/IEC 2009 – All rights reserved
---------------------- Page: 13 ----------------------
ISO/IEC 15946-5:2009(E)
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 .
0
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
---------------------- Page: 14 ----------------------
ISO/IEC 15946-5:2009(E)
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
...
Questions, Comments and Discussion
Ask us and Technical Secretary will try to provide an answer. You can facilitate discussion about the standard in here.