Information security — Cryptographic techniques based on elliptic curves — Part 5: Elliptic curve generation

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, ISO/IEC 18033‑2 and ISO/IEC 18033‑5. 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).

Sécurité de l'information — Techniques cryptographiques fondées sur les courbes elliptiques — Partie 5: Génération de courbes elliptiques

General Information

Status
Published
Publication Date
27-Feb-2022
Current Stage
5060 - Close of voting Proof returned by Secretariat
Completion Date
27-Oct-2021
Ref Project

RELATIONS

Buy Standard

Standard
ISO/IEC 15946-5:2022 - Information security — Cryptographic techniques based on elliptic curves — Part 5: Elliptic curve generation Released:2/28/2022
English language
35 pages
sale 15% off
Preview
sale 15% off
Preview
Draft
ISO/IEC FDIS 15946-5 - Information security -- Cryptographic techniques based on elliptic curves
English language
34 pages
sale 15% off
Preview
sale 15% off
Preview

Standards Content (sample)

INTERNATIONAL ISO/IEC
STANDARD 15946-5
Third edition
2022-02
Information security — Cryptographic
techniques based on elliptic curves —
Part 5:
Elliptic curve generation
Sécurité de l'information — Techniques cryptographiques fondées sur
les courbes elliptiques —
Partie 5: Génération de courbes elliptiques
Reference number
ISO/IEC 15946-5:2022(E)
© ISO/IEC 2022
---------------------- Page: 1 ----------------------
ISO/IEC 15946-5:2022(E)
COPYRIGHT PROTECTED DOCUMENT
© ISO/IEC 2022

All rights reserved. Unless otherwise specified, or required in the context of its implementation, 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
CP 401 • Ch. de Blandonnet 8
CH-1214 Vernier, Geneva
Phone: +41 22 749 01 11
Email: copyright@iso.org
Website: www.iso.org
Published in Switzerland
© ISO/IEC 2022 – All rights reserved
---------------------- Page: 2 ----------------------
ISO/IEC 15946-5:2022(E)
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 Conventions for elliptic curves ............................................................................................................................................................. 3

5.1 Definitions of elliptic curves ...................................................................................................................................................... 3

5.1.1 Elliptic curves over F(p ) ........................................................................................................................................... 3

5.1.2 Elliptic curves over F(2 ) ........................................................................................................................................... 4

5.1.3 Elliptic curves over F(3 ) ........................................................................................................................................... 4

5.2 Group law on elliptic curves ....................................................................................................................................................... 4

6 Framework for elliptic curve generation .................................................................................................................................. 5

6.1 Trust in elliptic curve ....................................................................................................................................................................... 5

6.2 Overview of elliptic curve generation................................................................................................................................ 5

7 Verifiably pseudo-random elliptic curve generation .................................................................................................... 5

7.1 General ........................................................................................................................................................................................................... 5

7.2 Constructing verifiably pseudo-random elliptic curves (prime case) .................................................. 5

7.2.1 Construction algorithm ................................................................................................................................................ 5

7.2.2 Test for near primality .................................................................................................................................................. 7

7.2.3 Finding a point of large prime order ................................................................................................................. 7

7.2.4 Verification of elliptic curve pseudo-randomness ............................................................................... 7

7.3 Constructing verifiably pseudo-random elliptic curves (binary case) ................................................ 8

7.3.1 Construction algorithm ................................................................................................................................................ 8

7.3.2 Verification of elliptic curve pseudo-randomness ............................................................................... 9

8 Constructing elliptic curves by complex multiplication ........................................................................................10

8.1 General ........................................................................................................................................................................................................ 10

8.2 Barreto-Naehrig (BN) curve ................................................................................................................................................... 10

8.3 Barreto-Lynn-Scott (BLS) curve ......... ................................................................................................................................. 11

9 Constructing elliptic curves by lifting .......................................................................................................................................12

Annex A (informative) Background information on elliptic curves ...............................................................................14

Annex B (informative) Background information on elliptic curve cryptosystems ........................................16

Annex C (informative) Background information on constructing elliptic curves by complex

multiplication .......................................................................................................................................................................................................19

Annex D (informative) Numerical examples ............................................................................................................................................24

Annex E (informative) Summary of properties of elliptic curves generated by the complex

multiplication method ................................................................................................................................................................................32

Bibliography .............................................................................................................................................................................................................................33

iii
© ISO/IEC 2022 – All rights reserved
---------------------- Page: 3 ----------------------
ISO/IEC 15946-5:2022(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.

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 or

www.iec.ch/members_experts/refdocs).

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) or the IEC

list of patent declarations received (see patents.iec.ch).

Any trade name used in this document is information given for the convenience of users and does not

constitute an endorsement.

For an explanation of 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

www.iso.org/iso/foreword.html. In the IEC, see www.iec.ch/understanding-standards.

This document was prepared by Joint Technical Committee ISO/IEC JTC 1, Information technology,

Subcommittee ISO/IEC JTC 1/SC 27, Information security, cybersecurity and privacy protection.

This third edition cancels and replaces the second edition (ISO/IEC 15946-5:2017), which has been

technically revised.
The main changes compared to the previous edition are as follows:
— BLS curves have been added to Clause 7;

— security background for pairing-friendly curves has been added to Annex B, including the exTNFS

attack that affects the security of numerical examples of BN curves;
— except for BN curves, all other curves have been moved to Annex C;

— associated numerical examples (Annex D) and properties (Annex E) have been updated.

A list of all parts in the ISO/IEC 15946 series can be found on the ISO website.

Any feedback or questions on this document should be directed to the user’s national standards

body. A complete listing of these bodies can be found at www.iso.org/members.html and

www.iec.ch/national-committees.
© ISO/IEC 2022 – All rights reserved
---------------------- Page: 4 ----------------------
ISO/IEC 15946-5:2022(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. With current knowledge, this problem is 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.

The purpose of this document is to meet the increasing interest in elliptic curve based public-key

technology by describing elliptic curve generation methods to support key management, encryption

and digital signatures based on an elliptic curve.
© ISO/IEC 2022 – All rights reserved
---------------------- Page: 5 ----------------------
INTERNATIONAL STANDARD ISO/IEC 15946-5:2022(E)
Information security — 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,

ISO/IEC 18033-2 and ISO/IEC 18033-5.

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).
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 terminology databases for use in standardization at the following addresses:

— ISO Online browsing platform: available at https:// www. iso. org/o bp;
— IEC Electropedia: available at https:// www.e lectropedia. org/.
3.1
cryptographic hash function

function that maps octet strings of any length to octet strings of fixed length, such that it is

computationally infeasible to find correlations between inputs and outputs, and such that given one

part of the output, but not the input, it is computationally infeasible to predict any bit of the remaining

output

[SOURCE: ISO/IEC 18033-2:2006, 3.11, modified — Deleted the last phrase, "The precise security

requirements depend on the application.]
3.2
definition field of an elliptic curve

field that includes all the coefficients of the formula describing an elliptic curve

© ISO/IEC 2022 – All rights reserved
---------------------- Page: 6 ----------------------
ISO/IEC 15946-5:2022(E)
3.3
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;

— 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.4
nearly prime number

positive integer, n =m⋅r, where m is a large prime number and r is a small smooth integer (3.6)

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.5
order of an elliptic curve E(F)
number of points on an elliptic curve, E, defined over a finite field, F
3.6
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
0 zero element in a field F
a, b elliptic curve parameters

Β embedding degree, the smallest B such that number #E(F(q)) is a divisor of q -1

2 3 m

Ε elliptic curve, given by an equation of the form Y = X + aX + b over the field F(p ) for p > 3,

2 3 2 m

by an equation of the form Y + XY = X + aX + b over the field F(2 ), or by an equation of the

2 3 2 m

form Y = X + aX + b over the field F(3 ), together with an extra point O referred to as the

m m m

point at infinity; the curve is denoted by E/F(p ), E/F(2 ), or E/F(3 ), respectively

F finite field
F(p)* multiplicative group of F(p)
L, m positive integers

mod modulo, a mod b means a residue of a modulo b for integers a and b (b is positive)

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
p prime number
© ISO/IEC 2022 – All rights reserved
---------------------- Page: 7 ----------------------
ISO/IEC 15946-5:2022(E)
q prime power, p for some prime p and some integer m ≥ 1
r cofactor, that is #E(F(q)) = rn
u positive integer
v positive integer
λ positive integer
v(i) polynomial of i
#E(F(q)) order of an elliptic curve 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
∪ or
‖ concatenation
∈ element is included in a set
4.2 Conversion functions
BS2IP bit string to integer conversion primitive
BS2OSP bit string to octet string conversion primitive
I2BSP integer to bit string conversion primitive
OS2FEP octet string to finite field element conversion primitive
NOTE Refer to ISO/IEC 15946-1:2016, Clause 7 for detailed conversion functions.
5 Conventions for elliptic curves
5.1 Definitions of elliptic curves
5.1.1 Elliptic curves over F(p )
m m

Let F(p ) be a definition field of an elliptic curve, where F(p ) is a finite field with a prime p > 3 and a

positive integer m. In this document, it is assumed that E is described by a “short (affine) Weierstrass

equation”, that is an equation of type
2 3 m
Y = X + aX + b with a, b ∈ F(p )
3 2 m
such that 4a + 27b ≠ 0 holds in F(p ).
3 2

NOTE 1 The above curve with 4a + 27b = 0 is called a singular curve, which is not an elliptic curve.

© ISO/IEC 2022 – All rights reserved
---------------------- Page: 8 ----------------------
ISO/IEC 15946-5:2022(E)
The set of F(p )-valued points of E is given by Formula (1):
m m m 2 3
E(F(p )) = {Q = (x , y ) ∈ F(p ) × F(p )|y = x + ax + b} ∪ {O} (1)
Q Q Q Q Q E
where O is an extra point referred to as the point at infinity of E.

NOTE 2 In applications not based on a pairing, E/F(p) or E/F(2 ) is preferable from an efficiency point of view.

In applications that use a pairing, E/F(p) is preferable from an efficiency point of view.

5.1.2 Elliptic curves over F(2 )

Let F(2 ) for m ≥ 1 be a definition field of an elliptic curve. In this document, it is assumed that E is

described by an equation of the type
2 3 2 m
Y + XY = X + aX + b with a, b ∈ F(2 )
such that b ≠ 0 holds in F(2 ).

For cryptographic use, m shall be a prime to prevent certain kinds of attacks on the cryptosystem.

NOTE The above curve with b = 0 is called a singular curve, which is not an elliptic curve.

The set of F(2 )-valued points of E is given by Formula (2):
m m m 2 3 2
E(F(2 )) = {Q = (x , y ) ∈ F(2 ) × F(2 )|y + x y = x + ax + b} ∪ {O} (2)
Q Q Q Q Q Q Q E
where O is an extra point referred to as the point at infinity of E.
5.1.3 Elliptic curves over F(3 )
m m

Let F(3 ) be a definition field of an elliptic curve, where F(3 ) is a finite field with a positive integer m.

In this document, it is assumed that E is described by an equation of the type
2 3 2 m
Y = X + aX + b with a, b ∈ F(3 )
such that a, b ≠ 0 holds in F(3 ).

NOTE The above curve with a or b = 0 is called a singular curve, which is not an elliptic curve.

The set of F(3 )-valued points of E is given by Formula (3):
m m m 2 3 2
E(F(3 )) = {Q = (x , y ) ∈ F(3 ) × F(3 )|y = x + ax + b} ∪ {O} (3)
Q Q Q Q Q E
where O is an extra point referred to as the point at infinity of E.
5.2 Group law on elliptic curves

Elliptic curves are endowed with the addition operation +: E × E → E, defining for each pair (Q , Q )

1 2

of points on E a third point Q + Q . With respect to this addition, E is an abelian group with identity

1 2

element O . The kth multiple of Q is given as kQ, where kQ = Q + …+ Q (k summands) if k > 0, kQ = (−k)

(−Q) if k < 0, and kQ = O if k = 0. The smallest positive k with kQ = O is called the order of Q.

E E

In order to use an elliptic curve for a cryptosystem, it is necessary to compute group law on an elliptic

curve. ISO/IEC 15946-1 shall be referred to for methods of group law on elliptic curves.

© ISO/IEC 2022 – All rights reserved
---------------------- Page: 9 ----------------------
ISO/IEC 15946-5:2022(E)
6 Framework for elliptic curve generation
6.1 Trust in elliptic curve

If an elliptic curve is poorly or maliciously generated, this can enable an adversary to break a

cryptosystem that uses it. 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 can be obtained from an impartial trusted source (e.g. an international or national

standard).
— The curve can be generated and/or verified by a trusted third party.
— The curve can 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 cryptography.

6.2 Overview of elliptic curve generation
There are three main ways to generate elliptic curves:

— by applying the order of counting algorithms to a (pseudo-)randomly chosen elliptic curve as

specified in Clause 7;
— by applying a complex multiplication method as specified in Clause 8;

— by lifting an elliptic curve over a small finite field over a reasonably large field as specified in

Clause 9.
NOTE 1 Refer to Annex A for background information on elliptic curves.

NOTE 2 Refer to Annex B for background information on elliptic curve cryptography.

7 Verifiably pseudo-random elliptic curve generation
7.1 General

The generation of verifiably pseudo-random elliptic curves focuses on curves over prime and binary

fields.
7.2 Constructing verifiably pseudo-random elliptic curves (prime case)
7.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 IEEE P1363-2000.

NOTE 2 Methods of choosing a prime number p (pseudo) randomly are described in ISO/IEC 18032.

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
© ISO/IEC 2022 – All rights reserved
---------------------- Page: 10 ----------------------
ISO/IEC 15946-5:2022(E)
— 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 the following:
1) Let X = I2BSP(Z + i mod 2 ).
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

F F
guarantees the conditions hold, and this choice is recommended.

NOTE 3 It is possible that choosing a = b = c is not optimal from a performance perspective.

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 7.2.2. If so, the

output of the algorithm specified in 7.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

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 7.2.3.
p) Output X, a, b, n, G.

NOTE 7 Methods to compute the order #E(F(p)) are described in References [12], [31] and [32].

© ISO/IEC 2022 – All rights reserved
---------------------- Page: 11 ----------------------
ISO/IEC 15946-5:2022(E)
7.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 the following:
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 ISO/IEC 18032 and Reference [11].

7.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.

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.
b) Set G = rP.
c) If G = O , then go to step a).
d) Set Q = nG.
e) If Q ≠ O , then output “wrong order” and stop.
f) Output G.
7.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 7.2.1. The quantities L , L, v, s, and w, and the hash-function H, are as in 7.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).
© ISO/IEC 2022 – All rights reserved
---------------------- Page: 12 ----------------------
ISO/IEC 15946-5:2022(E)
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 the following:
1) Let X = I2BSP(Z + i mod 2 ).
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 .
4) 4c + 27 ≠ 0 .
5) b ≠ 0 .
2 3
6) cb − a = 0 .
7) G ≠ O .
2 3
8) y = x + ax + b.
G G G
9) nG = O .

h) If all the conditions in step g) hold, then output “True”; otherwise output “False”.

7.3 Constructing verifiably pseudo-random elliptic curves (binary case)
7.3.1 Construction algorithm

The following algorithm produces a set of elliptic curve parameters for a pseudo-random curve over

a field F(2 ), along with sufficient information for others to verify that the curve was indeed chosen

pseudo-randomly. See Annex D for additional information.
NOTE 1 The algorithm is consistent with IEEE P1363-2000.
It is assumed that the following quantities have been chosen:
— 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
...

FINAL
INTERNATIONAL ISO/IEC
DRAFT
STANDARD FDIS
15946-5
ISO/IEC JTC 1/SC 27
Information security — Cryptographic
Secretariat: DIN
techniques based on elliptic curves —
Voting begins on:
2021-08-31
Part 5:
Voting terminates on:
Elliptic curve generation
2021-10-26
Sécurité de l'information — Techniques cryptographiques fondées sur
les courbes elliptiques —
Partie 5: Génération de courbes elliptiques
RECIPIENTS OF THIS DRAFT ARE INVITED TO
SUBMIT, WITH THEIR COMMENTS, NOTIFICATION
OF ANY RELEVANT PATENT RIGHTS OF WHICH
THEY ARE AWARE AND TO PROVIDE SUPPOR TING
DOCUMENTATION.
IN ADDITION TO THEIR EVALUATION AS
Reference number
BEING ACCEPTABLE FOR INDUSTRIAL, TECHNO-
ISO/IEC FDIS 15946-5:2021(E)
LOGICAL, COMMERCIAL AND USER PURPOSES,
DRAFT INTERNATIONAL STANDARDS MAY ON
OCCASION HAVE TO BE CONSIDERED IN THE
LIGHT OF THEIR POTENTIAL TO BECOME STAN-
DARDS TO WHICH REFERENCE MAY BE MADE IN
NATIONAL REGULATIONS. ISO/IEC 2021
---------------------- Page: 1 ----------------------
ISO/IEC FDIS 15946-5:2021(E)
COPYRIGHT PROTECTED DOCUMENT
© ISO/IEC 2021

All rights reserved. Unless otherwise specified, or required in the context of its implementation, 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
CP 401 • Ch. de Blandonnet 8
CH-1214 Vernier, Geneva
Phone: +41 22 749 01 11
Email: copyright@iso.org
Website: www.iso.org
Published in Switzerland
ii © ISO/IEC 2021 – All rights reserved
---------------------- Page: 2 ----------------------
ISO/IEC FDIS 15946-5:2021(E)
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 Conventions for elliptic curves .............................................................................................................................................................. 3

5.1 Definitions of elliptic curves ........................................................................................................................................................ 3

5.1.1 Elliptic curves over F(p ) ......................................................................................................................................... 3

5.1.2 Elliptic curves over F(2 ) ........................................................................................................................................ 4

5.1.3 Elliptic curves over F(3 ) ......................................................................................................................................... 4

5.2 Group law on elliptic curves ........................................................................................................................................................ 4

6 Framework for elliptic curve generation .................................................................................................................................... 4

6.1 Trust in elliptic curve......................................................................................................................................................................... 4

6.2 Overview of elliptic curve generation ................................................................................................................................. 5

7 Verifiably pseudo-random elliptic curve generation ..................................................................................................... 5

7.1 General ........................................................................................................................................................................................................... 5

7.2 Constructing verifiably pseudo-random elliptic curves (prime case) .................................................... 5

7.2.1 Construction algorithm .............................................................................................................................................. 5

7.2.2 Test for near primality ................................................................................................................................................ 6

7.2.3 Finding a point of large prime order .............................................................................................................. 7

7.2.4 Verification of elliptic curve pseudo-randomness .............................................................................. 7

7.3 Constructing verifiably pseudo-random elliptic curves (binary case) ................................................... 8

7.3.1 Construction algorithm .............................................................................................................................................. 8

7.3.2 Verification of elliptic curve pseudo-randomness .............................................................................. 9

8 Constructing elliptic curves by complex multiplication ...........................................................................................10

8.1 General ........................................................................................................................................................................................................10

8.2 Barreto-Naehrig (BN) curve .....................................................................................................................................................10

8.3 Barreto-Lynn-Scott (BLS) curve ............................................................................................................................................11

9 Constructing elliptic curves by lifting ..........................................................................................................................................12

Annex A (informative) Background information on elliptic curves ..................................................................................13

Annex B (informative) Background information on elliptic curve cryptosystems ............................................15

Annex C (informative) Background information on constructing elliptic curves by complex

multiplication .......................................................................................................................................................................................................18

Annex D (informative) Numerical examples .............................................................................................................................................23

Annex E (informative) Summary of properties of elliptic curves generated by the complex

multiplication method .................................................................................................................................................................................31

Bibliography .............................................................................................................................................................................................................................32

© ISO/IEC 2021 – All rights reserved iii
---------------------- Page: 3 ----------------------
ISO/IEC FDIS 15946-5:2021(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.

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 or www .iec .ch/ members

_experts/ refdocs).

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) or the IEC

list of patent declarations received (see patents.iec.ch).

Any trade name used in this document is information given for the convenience of users and does not

constitute an endorsement.

For an explanation of 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 www .iso .org/

iso/ foreword .html. In the IEC, see www .iec .ch/ understanding -standards.

This document was prepared by Joint Technical Committee ISO/IEC JTC 1, Information technology,

Subcommittee ISO/IEC JTC 1/SC 27, Information security, cybersecurity and privacy protection.

This third edition cancels and replaces the second edition (ISO/IEC 15946-5:2017), which has been

technically revised.
The main changes compared to the previous edition are as follows:
— BLS curves have been added to Clause 7;

— security background for pairing-friendly curves has been added to Annex B, including the exTNFS

attack that affects the security of numerical examples of BN curves;
— except for BN curves, all other curves have been moved to Annex C;

— associated numerical examples (Annex D) and properties (Annex E) have been updated.

A list of all parts in the ISO/IEC 15946 series can be found on the ISO website.

Any feedback or questions on this document should be directed to the user’s national standards body. A

complete listing of these bodies can be found at www .iso .org/ members .html and www .iec .ch/ national

-committees.
iv © ISO/IEC 2021 – All rights reserved
---------------------- Page: 4 ----------------------
ISO/IEC FDIS 15946-5:2021(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. With current knowledge, this problem is 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.

The purpose of this document is to meet the increasing interest in elliptic curve based public-key

technology by describing elliptic curve generation methods to support key management, encryption

and digital signatures based on an elliptic curve.
© ISO/IEC 2021 – All rights reserved v
---------------------- Page: 5 ----------------------
FINAL DRAFT INTERNATIONAL STANDARD ISO/IEC FDIS 15946-5:2021(E)
Information security — 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,

ISO/IEC 18033-2 and ISO/IEC 18033-5.

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).
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:

— ISO Online browsing platform: available at https:// www .iso .org/ obp;
— IEC Electropedia: available at https:// www .electropedia .org/ .
3.1
cryptographic hash function

function that maps octet strings of any length to octet strings of fixed length, such that it is

computationally infeasible to find correlations between inputs and outputs, and such that given one

part of the output, but not the input, it is computationally infeasible to predict any bit of the remaining

output

[SOURCE: ISO/IEC 18033-2:2006, 3.11, modified — Deleted the last phrase, "The precise security

requirements depend on the application.]
3.2
definition field of an elliptic curve

field that includes all the coefficients of the formula describing an elliptic curve

© ISO/IEC 2021 – All rights reserved 1
---------------------- Page: 6 ----------------------
ISO/IEC FDIS 15946-5:2021(E)
3.3
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;

— 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.4
nearly prime number

positive integer, n =m⋅r, where m is a large prime number and r is a small smooth integer (3.6)

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.5
order of an elliptic curve E(F)
number of points on an elliptic curve, E, defined over a finite field, F
3.6
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
0 zero element in a field F
a, b elliptic curve parameters
Β embedding degree, the smallest B such that number #E[F(q)] | q −1
2 3 m

Ε elliptic curve, given by an equation of the form Y = X + aX + b over the field F(p ) for p > 3,

2 3 2 m

by an equation of the form Y + XY = X + aX + b over the field F(2 ), or by an equation of the

2 3 2 m

form Y = X + aX + b over the field F(3 ), together with an extra point O referred to as the

m m m

point at infinity; the curve is denoted by E/F(p ), E/F(2 ), or E/F(3 ), respectively

F finite field
L, m positive integers

mod modulo, a mod b means a residue of a modulo b for integers a and b (b is positive)

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
p prime number
q prime power, p for some prime p and some integer m ≥ 1
2 © ISO/IEC 2021 – All rights reserved
---------------------- Page: 7 ----------------------
ISO/IEC FDIS 15946-5:2021(E)
r cofactor, that is #E[F(q)] = rn
v positive integer
λ positive integer
v(i) polynomial of i
#E(F(q) ) order of an elliptic curve 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
4.2 Conversion functions
BS2IP bit string to integer conversion primitive
BS2OSP bit string to octet string conversion primitive
I2BSP integer to bit string conversion primitive
OS2FEP octet string to finite field element conversion primitive
NOTE Refer to ISO/IEC 15946-1:2016, Clause 7 for detailed conversion functions.
5 Conventions for elliptic curves
5.1 Definitions of elliptic curves
5.1.1 Elliptic curves over F(p )
m m

Let F(p ) be a definition field of an elliptic curve, where F(p ) is a finite field with a prime p > 3 and a

positive integer m. In this document, it is assumed that E is described by a “short (affine) Weierstrass

equation”, that is an equation of type
2 3 m
Y = X + aX + b with a, b ∈ F(p )
3 2 m
such that 4a + 27b ≠ 0 holds in F(p ).
3 2

NOTE 1 The above curve with 4a + 27b = 0 is called a singular curve, which is not an elliptic curve.

The set of F(p )-valued points of E is given by Formula (1):
m m m 2 3
E(F(p )) = {Q = (x , y ) ∈ F(p ) × F(p )|y = x + ax + b} ∪ {O} (1)
Q Q Q Q Q E
where O is an extra point referred to as the point at infinity of E.

NOTE 2 In applications not based on a pairing, E/F(p) or E/F(2 ) is preferable from an efficiency point of view.

In applications that use a pairing, E/F(p) is preferable from an efficiency point of view.

© ISO/IEC 2021 – All rights reserved 3
---------------------- Page: 8 ----------------------
ISO/IEC FDIS 15946-5:2021(E)
5.1.2 Elliptic curves over F(2 )

Let F(2 ) for m ≥ 1 be a definition field of an elliptic curve. In this document, it is assumed that E is

described by an equation of the type
2 3 2 m
Y + XY = X + aX + b with a, b ∈ F(2 )
such that b ≠ 0 holds in F(2 ).

For cryptographic use, m shall be a prime to prevent certain kinds of attacks on the cryptosystem.

NOTE The above curve with b = 0 is called a singular curve, which is not an elliptic curve.

The set of F(2 )-valued points of E is given by Formula (2):
m m m 2 3 2
E(F(2 )) = {Q = (x , y ) ∈ F(2 ) × F(2 )|y + x y = x + ax + b} ∪ {O} (2)
Q Q Q Q Q Q Q E
where O is an extra point referred to as the point at infinity of E.
5.1.3 Elliptic curves over F(3 )
m m

Let F(3 ) be a definition field of an elliptic curve, where F(3 ) is a finite field with a positive integer m.

In this document, it is assumed that E is described by an equation of the type
2 3 2 m
Y = X + aX + b with a, b ∈ F(3 )
such that a, b ≠ 0 holds in F(3 ).

NOTE The above curve with a or b = 0 is called a singular curve, which is not an elliptic curve.

The set of F(3 )-valued points of E is given by Formula (3):
m m m 2 3 2
E(F(3 )) = {Q = (x , y ) ∈ F(3 ) × F(3 )|y = x + ax + b} ∪ {O} (3)
Q Q Q Q Q E
where O is an extra point referred to as the point at infinity of E.
5.2 Group law on elliptic curves

Elliptic curves are endowed with the addition operation +: E × E → E, defining for each pair (Q , Q )

1 2

of points on E a third point Q + Q . With respect to this addition, E is an abelian group with identity

1 2

element O . The kth multiple of Q is given as kQ, where kQ = Q + …+ Q (k summands) if k > 0, kQ = (−k)

(−Q) if k < 0, and kQ = O if k = 0. The smallest positive k with kQ = O is called the order of Q.

E E

In order to use an elliptic curve for a cryptosystem, it is necessary to compute group law on an elliptic

curve. ISO/IEC 15946-1 shall be referred to for methods of group law on elliptic curves.

6 Framework for elliptic curve generation
6.1 Trust in elliptic curve

If an elliptic curve is poorly or maliciously generated, this can enable an adversary to break a

cryptosystem that uses it. 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 can be obtained from an impartial trusted source (e.g. an international or national

standard).
— The curve can be generated and/or verified by a trusted third party.
4 © ISO/IEC 2021 – All rights reserved
---------------------- Page: 9 ----------------------
ISO/IEC FDIS 15946-5:2021(E)
— The curve can 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 cryptography.

6.2 Overview of elliptic curve generation
There are three main ways to generate elliptic curves:

— by applying the order of counting algorithms to a (pseudo-)randomly chosen elliptic curve as

specified in Clause 7;
— by applying a complex multiplication method as specified in Clause 8;

— by lifting an elliptic curve over a small finite field over a reasonably large field as specified in

Clause 9.
NOTE 1 Refer to Annex A for background information on elliptic curves.

NOTE 2 Refer to Annex B for background information on elliptic curve cryptography.

7 Verifiably pseudo-random elliptic curve generation
7.1 General

The generation of verifiably pseudo-random elliptic curves focuses on curves over prime and binary

fields.
7.2 Constructing verifiably pseudo-random elliptic curves (prime case)
7.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 IEEE P1363-2000.

NOTE 2 Methods of choosing a prime number p (pseudo) randomly are described in ISO/IEC 18032.

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
© ISO/IEC 2021 – All rights reserved 5
---------------------- Page: 10 ----------------------
ISO/IEC FDIS 15946-5:2021(E)
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 the following:
1) Let X = I2BSP(Z + i mod 2 ).
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

F F
guarantees the conditions hold, and this choice is recommended.

NOTE 3 It is possible that choosing a = b = c is not optimal from a performance perspective.

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 7.2.2. If so, the

output of the algorithm specified in 7.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

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 7.2.3.
p) Output X, a, b, n, G.

NOTE 7 Methods to compute the order #E[F(p)] are described in References [12], [31] and [32].

7.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.
6 © ISO/IEC 2021 – All rights reserved
---------------------- Page: 11 ----------------------
ISO/IEC FDIS 15946-5:2021(E)
b) For l from 2 to l , do the following:
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 ISO/IEC 18032 and Reference [11].

7.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.

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.
b) Set G = rP.
c) If G = O , then go to step a).
d) Set Q = nG.
e) If Q ≠ O , then output “wrong order” and stop.
f) Output G.
7.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 7.2.1. The quantities L , L, v, s, and w, and the hash-function H, are as in 7.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 the following:
1) Let X = I2BSP(Z + i mod 2 ).
2) Compute W = H (X ).
i i
e) Let W = W || W || … || W .
0 1 s
© ISO/IEC 2021 – All rights reserved 7
---------------------- Page: 12 ----------------------
ISO/IEC FDIS 15946-5:2021(E)
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 .
4) 4c + 27 ≠ 0 .
5) b ≠ 0 .
2 3
6) cb − a = 0 .
7) G ≠ O .
2 3
8) y = x + ax + b.
G G G
9) nG = O .

h) If all the conditions in step g) hold, then output “True”; otherwise output “False”.

7.3 Constructing verifiably pseudo-random elliptic curves (binary case)
7.3.1 Construction algorithm
The following algorithm produces a set of elliptic curve parameters
...

Questions, Comments and Discussion

Ask us and Technical Secretary will try to provide an answer. You can facilitate discussion about the standard in here.