ISO/IEC 15946-1:2016

Information technology - Security techniques - Cryptographic techniques based on elliptic curves - Part 1: General

ISO/IEC 15946-1:2016 describes the mathematical background and general techniques necessary for implementing the elliptic curve cryptography mechanisms defined in ISO/IEC 15946‑5, ISO/IEC 9796‑3, ISO/IEC 11770‑3, ISO/IEC 14888‑3, ISO/IEC 18033‑2 and other ISO/IEC standards. ISO/IEC 15946-1:2016 does not specify the implementation of the techniques it defines. For example, it does not specify the basis representation to be used when the elliptic curve is defined over a finite field of characteristic two. Thus, interoperability of products complying with ISO/IEC 15946-1:2016 will not be guaranteed.

Technologies de l'information — Techniques de sécurité — Techniques cryptographiques basées sur les courbes elliptiques — Partie 1: Généralités

General Information

• Status: Published
• Publication Date: 03-Jul-2016
• ICS: 35.030 - IT Security
• ICS: 35.040 - Information coding
• Technical Committee: ISO/IEC JTC 1/SC 27 - Information security, cybersecurity and privacy protection
• Drafting Committee: ISO/IEC JTC 1/SC 27/WG 2 - Cryptography and security mechanisms
• Current Stage: 9093 - International Standard confirmed
• Start Date: 19-May-2022
• Completion Date: 30-Oct-2025

Relations

• Consolidated By: ISO 22442-1:2020 - Medical devices utilizing animal tissues and their derivatives - Part 1: Application of risk management
• Effective Date: 06-Jun-2022
• Revises: ISO/IEC 15946-1:2008 - Information technology - Security techniques - Cryptographic techniques based on elliptic curves - Part 1: General
• Effective Date: 07-Dec-2013

Overview

ISO/IEC 15946-1:2016 - “Information technology - Security techniques - Cryptographic techniques based on elliptic curves - Part 1: General” - provides the mathematical foundation and general techniques for implementing elliptic curve cryptography (ECC). It documents the conventions, symbols and background needed to support ECC mechanisms (for example, key-exchange, key‑transport and digital signatures) referenced by other ISO/IEC standards. The standard describes finite-field and elliptic-curve conventions, conversion functions, domain-parameter concepts and key-generation guidance, but it intentionally does not prescribe low-level implementation details (e.g., basis representations), so it does not by itself guarantee interoperability.

Key topics and technical requirements

• Mathematical background
  • Finite fields (prime fields F(p) and extension fields F(pm)), algebraic definitions and conventions.
  • Formal definition of elliptic curves over finite fields and the group law used for ECC.
• Symbols and terminology
  • Standardized notation for points, group order, base point G, cofactor h, torsion groups, etc.
• Conversion functions
  • Definitions and usage of common conversion primitives such as OS2IP / I2OSP, OS2FEP / FE2OSP, EC2OSP / OS2ECP and related point compression/decompression rules.
• Elliptic-curve domain parameters and key generation
  • Structure and required elements of ECC domain parameters (curve coefficients, field, base point, order, cofactor) and general key generation procedures.
• Cryptographic bilinear maps
  • Definitions and properties (non-degeneracy, bilinearity, computability) where relevant to pairing-based constructions.
• Informative annexes
  • Background material on finite fields, elliptic curves, ECC systems and coordinate systems to aid implementers and reviewers.
• Intellectual property notice
  • The document draws attention to potential patent claims and lists known patent holders; users are advised to consult ISO/IEC patent databases.

Practical applications and intended users

ISO/IEC 15946-1 is aimed at professionals who design, implement or evaluate cryptographic systems that use elliptic curves:

• Cryptographers and protocol designers specifying ECC-based key-exchange, signatures or key‑transport schemes.
• Software and hardware implementers (TLS libraries, smart cards, secure elements, IoT device firmware) needing standardized mathematical and conversion conventions.
• Security architects and compliance teams assessing ECC implementations and interoperability vs. other ISO/IEC parts.
• Test labs and certification bodies reviewing ECC conformance and correctness of mathematical operations.

While this part supplies essential definitions and techniques, implementers should pair it with implementation-focused parts (e.g., ISO/IEC 15946-5 for curve generation) and consider interoperability, performance and patent/licensing implications.

Related standards

• ISO/IEC 15946-5 (Elliptic curve generation)
• ISO/IEC 9796-3, 11770-3, 14888-3, 18033-2 (standards that reference ECC mechanisms supported by ISO/IEC 15946-1)

Standards Content (Sample)

DRAFT INTERNATIONAL STANDARD
ISO/IEC DIS 15946-1
ISO/IEC JTC 1/SC 27 Secretariat: DIN
Voting begins on: Voting terminates on:
2015-07-28 2015-10-28
Information technology — Security techniques —
Cryptographic techniques based on elliptic curves —
Part 1:
General
Technologies de l’information — Techniques de sécurité — Techniques cryptographiques basées sur les
courbes elliptiques —
Partie 1: Généralités
ICS: 35.040
THIS DOCUMENT IS A DRAFT CIRCULATED
FOR COMMENT AND APPROVAL. IT IS
THEREFORE SUBJECT TO CHANGE AND MAY
NOT BE REFERRED TO AS AN INTERNATIONAL
STANDARD UNTIL PUBLISHED AS SUCH.
IN ADDITION TO THEIR EVALUATION AS
BEING ACCEPTABLE FOR INDUSTRIAL,
TECHNOLOGICAL, COMMERCIAL AND
USER PURPOSES, DRAFT INTERNATIONAL
STANDARDS MAY ON OCCASION HAVE TO
BE CONSIDERED IN THE LIGHT OF THEIR
POTENTIAL TO BECOME STANDARDS TO
WHICH REFERENCE MAY BE MADE IN
Reference number
NATIONAL REGULATIONS.
ISO/IEC DIS 15946-1:2015(E)
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 SUPPORTING DOCUMENTATION. ISO/IEC 2015

ISO/IEC DIS 15946-1:2015(E)
© ISO/IEC 2015
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
Case postale 56 • CH-1211 Geneva 20
Tel. + 41 22 749 01 11
Fax + 41 22 749 09 47
E-mail [e-mail]
Web www.iso.org
Published in Switzerland
ii © ISO/IEC 2015 – All rights reserved

ISO/IEC DIS 15946-1
Contents Page
Foreword . v
Introduction . vi
1 Scope . 1
2 Normative references . 1
3 Terms and definitions . 1
4 Symbol . 2
5 Conventions of fields . 3
5.1 Finite prime fields F(p) . 3
m
5.2 Finite fields F(p ) . 4
6 Conventions of elliptic curves . 4
6.1 Definition of elliptic curves . 4
m
6.1.1 Elliptic curves over F(p ) . 4
m
6.1.2 Elliptic curves over F(2 ) . 5
m
6.1.3 Elliptic curves over F(3 ) . 5
6.2 The group law on elliptic curves . 5
6.3 Generation of elliptic curves . 5
6.4 Cryptographic bilinear map . 6
7 Conversion functions . 6
7.1 Octet string / bit string conversion: OS2BSP and BS2OSP . 6
7.2 Bit string / integer conversion: BS2IP and I2BSP . 6
7.3 Octet string / bit string conversion: OS2IP and I2OSP . 7
7.4 Finite field element / integer conversion: FE2IP . 7
F
7.5 Octet string / finite field element conversion: OS2FEP and FE2OSP . 7
F F
7.6 Elliptic curve point / octet string conversion: EC2OSP and OS2ECP . 7
E E
7.6.1 Compressed elliptic curve points . 7
7.6.2 Point decompression algorithms . 8
7.6.3 Conversion functions . 8
7.7 Integer / elliptic curve conversion: I2ECP . 9
8 Elliptic curve domain parameters and public key . 9
8.1 Elliptic curve domain parameters over F(q). 9
8.2 Elliptic curve key generation . 10
Annex A (informative) Background information on finite fields . 11
A.1 Bit strings . 11
A.2 Octet strings . 11
m
A.3 Characteristic of a finite field F(p ) . 11
m
A.4 Inverting elements of a finite field F(p ) . 11
m
A.5 Squares and non-squares in a finite field F(p ) . 11
m
A.6 Finding square-roots in F(p ) . 11
Annex B (informative) Background information on elliptic curves . 13
B.1 Properties of elliptic curves . 13
B.2 The group law for elliptic curves E over F(q) with p > 3 . 13
B.2.1 Overview of coordinates . 13
B.2.2 The group law in affine coordinates . 13
B.2.3 The group law in projective coordinates . 14
B.2.4 The group law in Jacobian coordinates . 15
B.2.5 The group law in modified Jacobian coordinates . 16
B.2.6 Mixed coordinates . 17
© ISO/IEC 2015 – All rights reserved iii

ISO/IEC DIS 15946-1
m
B.3 The group law for elliptic curves over F(2 ) .17
B.3.1 The group law in affine coordinates .17
B.3.2 The group law in projective coordinates .17
m
B.4 The group law for elliptic curves over F(3 ) .18
B.4.1 The group law in affine coordinates .18
B.4.2 The group law in projective coordinates .19
B.5 The existence condition of an elliptic curve E .20
B.5.1 The order of an elliptic curve E defined over F(p) .20
m
B.5.2 The order of an elliptic curve E defined over F(2 ) .20
m
B.5.3 The order of an elliptic curve E defined over F(p ) with p ≥ 3 .21
B.6 The pairings .21
B.6.1 An overview of pairings .21
B.6.2 The definitions of Weil and Tate pairings .21
B.6.3 Cryptographic bilinear map .22
Annex C (informative) Background information on elliptic curve cryptosystems .23
C.1 Definition of cryptographic problems.23
C.1.1 The elliptic curve discrete logarithm problem (ECDLP) .23
C.1.2 The elliptic curve computational Diffie Hellman problem (ECDHP) .23
C.1.3 The elliptic curve decisional Diffie Hellman problem (ECDDHP) .23
C.1.4 The bilinear Diffie-Hellman (BDH) problem .23
C.2 Algorithms to determine discrete logarithms on elliptic curves .24
C.2.1 Security of ECDLP .24
C.2.2 Overview of algorithms .24
C.2.3 The MOV condition .24
C.3 Scalar multiplication algorithms of elliptic curve points .25
C.3.1 Basic algorithm .25
C.3.2 Algorithm with pre-computed table .25
C.4 Resistance to side-channel analysis .26
C.4.1 Overview of side-channel analysis .26
C.4.2 Basic algorithm secure against SPA .26
C.4.3 Basic algorithm secure against DPA .27
C.5 Algorithms to compute pairings .27
C.5.1 The auxiliary functions .27
C.5.2 Algorithm to compute the Weil pairing .28
C.5.3 Algorithm to compute the Tate pairing .28
C.6 Elliptic curve domain parameters and public key validation (optional).29
C.6.1 General .29
C.6.2 Elliptic curve domain parameter validation over F(q) .29
C.6.3 Public Key Validation (Optional) .29
Annex D (informative) Summary of coordinates .31
Bibliography .33

iv © ISO/IEC 2015 – All rights reserved

ISO/IEC DIS 15946-1
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.
ISO/IEC 15946-1 was prepared by Joint Technical Committee ISO/IEC JTC 1, Information technology,
Subcommittee SC 27, Security techniques.
This third edition cancels and replaces the second edition (ISO/IEC 15946-1:2008 with
ISO/IEC 15946-1/Cor.2:2014), which has been technically revised.
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

© ISO/IEC 2015 – All rights reserved v

ISO/IEC DIS 15946-1
Introduction
Cryptosystems based on elliptic curves defined over finite fields provide an interesting alternative to the RSA
cryptosystem and to finite field discrete log based cryptosystems. The concept of an elliptic curve based
public-key cryptosystem is quite simple.
 Every elliptic curve over a finite field is endowed with an addition "+" 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 the Diffie–Hellman and ElGamal type.
The security of such a public-key cryptosystem 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
factorisation 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
recognisable, cases. There has been no substantial progress in finding a 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 some finite field. This yields significantly shorter digital
signatures and system parameters and the integers to be handled by a cryptosystem are much smaller.
This part of ISO/IEC 15946 describes the mathematical background and general techniques necessary for
implementing the elliptic curve cryptography mechanisms defined in ISO/IEC 15946-5, ISO/IEC 9796-3,
ISO/IEC 11770-3, ISO/IEC 14888-3, ISO/IEC 18033-2 and other ISO/IEC standards.
It is the purpose of this part of ISO/IEC 15946 to meet the increasing interest in elliptic curve based public-key
technology and to describe the components that are necessary to implement secure elliptic curve
cryptosystems such as key-exchange, key-transport and digital signatures.

The International Organization for Standardization (ISO) and International Electrotechnical Commission (IEC)
draw attention to the fact that it is claimed that compliance with this document may involve the use of patents.
The ISO and IEC take no position concerning the evidence, validity and scope of these patent rights.
The holders of these patent rights have assured the ISO and IEC that they are willing to negotiate licenses
under reasonable and non-discriminatory terms and conditions with applicants throughout the world. In this
respect, the statements of the holders of these patent rights are registered with the ISO and IEC. Information
may be obtained from:
Certicom Corp. Address: 4701 Tahoe Blvd., Building A, Mississauga, ON L4W0B5, Canada

Matsushita Electric Industrial Co., Ltd. Address: 1006, Kadoma, Kadoma City, Osaka, 571-8501, Japan

Attention is drawn to the possibility that some of the elements of this document may be the subject of patent
rights other than those identified above. ISO and IEC shall not be held responsible for identifying any or all
such patent rights.
vi © ISO/IEC 2015 – All rights reserved

DRAFT INTERNATIONAL STANDARD ISO/IEC DIS 15946-1

Information technology — Security techniques —
Cryptographic techniques based on elliptic curves — Part 1:
General
1 Scope
This part of ISO/IEC 15946 describes the mathematical background and general techniques necessary for
implementing the elliptic curve cryptography mechanisms defined in ISO/IEC 15946-5, ISO/IEC 9796-3,
ISO/IEC 11770-3, ISO/IEC 14888-3, ISO/IEC 18033-2 and other ISO/IEC standards.
This part of ISO/IEC 15946 does not specify the implementation of the techniques it defines. For example it
does not specify the basis representation to be used when the elliptic curve is defined over a finite field of
characteristic two. Thus interoperability of products complying with this part of ISO/IEC 15946 will not be
guaranteed.
2 Normative references
The following referenced documents, in whole or in part, are normatively referenced in this document and are
indispensable for its application. 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-5:2009, Information technology — Security techniques — Cryptographic techniques based on
elliptic curves — Part 5: Elliptic curve generation.
3 Terms and definitions
For the purposes of this document, the following terms and definitions apply.
3.1
abelian group
group (G, ) such that a b=b a for every a and b in G
* * *
3.2
cubic curve
set of solutions, made up of pairs of elements of a specified field known as points, to a cubic equation of
special form
3.3
elliptic curve
cubic curve E without a singular point
Note 1 to entry: The set of points E together with an appropriately defined operation (see 6.2) forms an abelian
group. The field that includes all coefficients of the equation describing E is called the definition field of E. In
this part of ISO/IEC 15946, we deal with only finite fields F as the definition field. When we describe the
definition field F of E explicitly, we denote the curve as E/F.
© ISO/IEC 2015 – All rights reserved 1

ISO/IEC DIS 15946-1
Note 2 to entry: The form of a cubic curve equation used to define an elliptic curve varies depending on the
field – the general form of an appropriate cubic equation for all possible finite fields is defined in 6.1.
Note 3 to entry: A definition of a cubic curve is given in bibliography item [15].
3.4
field
set of elements S and a pair of operations (+, ) defined on S such that: (i) a (b+c)=a b+a c for every a, b and c in
* * * *
S, (ii) S together with + forms an abelian group (with identity element 0), and (iii) S excluding 0 together with
*
forms an abelian group
3.5
finite field
field containing a finite number of elements
m
Note 1 to entry: For any positive integer m and a prime p, there exists a finite field containing exactly p
m
elements. This field is unique up to isomorphism and is denoted by F(p ), where p is called the characteristic
m
of F(p ).
3.6
group
set of elements G and an operation defined on the set of elements such that (i) a (b c)=(a b) c for every a, b
* * * * *
and c in G, (ii) there exists an identity element e in G such that a e=e a=a for every a in G, and (iii) for every a in
* *
-1
-1 -1
G there exists an inverse element a in G such that a a = a a=e
* *
3.7
map
map satisfying the non-degeneracy, bilinearity, and computability conditions
Note 1 to entry: Definitions of non-degeneracy, bilinearity and computability are provided in 6.4.
3.8
singular point
point at which a given mathematical object is not defined
4 Symbol
In this document, the following notation is used to describe public-key systems based on elliptic curve
technology.
B
B
The smallest integer such that n divides q -1.
d The private key of a user. (d is a random integer in the set [2, n-2].)
2 3 m
E
An elliptic curve, either 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 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 point
E
m m m
at infinity. The curve is denoted by E/F(p ), E/F(2 ), or E/F(3 ), respectively.
E(F(q)) The set of F(q)-valued points of E and O .
E
#E(F(q)) The order (or cardinality) of E(F(q)).
E[n]
The n-torsion group of E, that is { Q ∈ E | nQ = O }.
E
A cryptographic bilinear map.
e
ｎ
2 © ISO/IEC 2015 – All rights reserved

ISO/IEC DIS 15946-1
|F | The number of elements in F.
m m
F(q) The finite field consisting of exactly q elements. This includes the cases of F(p), F(2 ), and F(p ).
F(q)* F(q)\{0 }
F
G The base point on E with prime order n.
The group generated by G with prime cardinality n.
h The cofactor of E(F(q)).
kQ The k-th multiple of some point Q of E, i.e. kQ = Q+ …+Q (k summands) if k > 0, kQ = (–k)(–Q) if k
< 0, and kQ = O if k = 0.
E
The cyclic group of order n comprised of the n-th roots of unity in the algebraic closure of F(q).
μ
n
n A prime divisor of #E(F(q)).
O The elliptic curve point at infinity.
E
p A prime number.
P The public key of a user. (P is an elliptic curve point in .)
m
q A prime power, p for some prime p and some integer m ≥1.
Q A point on E with coordinates (x , y ).
Q Q
Q +Q The elliptic curve sum of two points Q and Q .
1 2 1 2
x
The x-coordinate of Q ≠ O .
Q
E
y The y-coordinate of Q ≠ O .
Q
E
[0, k] The set of integers from 0 to k inclusive.
0 The identity element of F(q) for addition.
F
1 The identity element of F(q) for multiplication.
F
5 Conventions of fields
5.1 Finite prime fields F(p)
For any prime p there exists a finite field consisting of exactly p elements. This field is uniquely determined up
to isomorphism and in this document it is referred to as the finite prime field F(p).
The elements of a finite prime field F(p) may be identified with the set [0, p - 1] of all non-negative integers less
than p. F(p) is endowed with two operations called addition and multiplication such that the following
conditions hold:
 F(p) is an abelian group with respect to the addition operation “+”.
© ISO/IEC 2015 – All rights reserved 3

ISO/IEC DIS 15946-1
For a, b ∈ F(p) the sum a + b is given as a + b := r, where r ∈ F(p) is the remainder obtained when the
integer sum a + b is divided by p.
 F(p)\{0} denoted as F(p)* is an abelian group with respect to the multiplication operation “×”.
For a, b ∈ F(p) the product a × b is given as a × b := r, where r ∈ F(p) is the remainder obtained when the
integer product a × b is divided by p. When it does not cause confusion, × is omitted and the notation ab is
used or the notation a⋅b is used.
m
5.2 Finite fields F(p )
m
For any positive integer m and prime p, there exists a finite field of exactly p elements. This field is unique up
m
to isomorphism and in this document it is referred to as the finite field F(p ).
m m
NOTE 1 (1) F(p ) is the general definition including F(p) for m = 1 and F(2 ) for p = 2
(2) If p = 2, then field elements may be identified with bit strings of length m and the sum of two field elements is
the bit-wise XOR of the two bit strings.
m
The finite field F(p ) may be identified with the set of p-ary strings of length m in the following way. Every finite
m m
field F(p ) contains at least one basis {ξ , ξ ,∙∙∙, ξ } over F(p) such that every element α ∈ F(p ) has a unique
1 2 m
representation of the form α = a ξ + a ξ + ∙∙∙ + a ξ , with a ∈ F(p) for i = 1, 2,∙∙∙, m. The element α can then be
1 1 2 2 m m i
m
identified with the p-ary string (a , a ,∙∙∙, a ). The choice of basis is beyond the scope of this document. F(p ) is
1 2 m
endowed with two operations called addition and multiplication such that the following conditions hold:
m
 F (p ) is an abelian group with respect to the addition operation “+”.
For α = (a , a ,∙∙∙, a ) and β = (b , b ,∙∙∙, b ) the sum a + β is given by a + β := γ = (c , c ,∙∙∙, c ), where c =
1 2 m 1 2 m 1 2 m i
a + b is the sum in F (p). The identity element for addition is 0 = (0,∙∙∙, 0).
i i F
*
m m
 F(p )\{0}, denoted by F(p ) , is an abelian group with respect to the multiplication operation “×”.
For α = (a , a ,∙∙∙, a ) and β = (b , b ,∙∙∙, b ) the product α × β is given by a p-ary string a × β :=γ = (c , c ,∙∙∙,
1 2 m 1 2 m 1 2
c ), where c =  a b d for ξ ξ = d ξ + d ξ + . + d ξ (1 ≤ j, k ≤ m). When it does not
m i ∑1≤ j,k ≤m j k i,j,k j k  1,j,k 1 2,j,k 2 m,j,k m
cause confusion, × is omitted and the notation ab is used. The basis can be chosen in such a way that
the identity element for multiplication is 1 = (1,0,∙∙∙, 0).
F
NOTE 2 The choice of basis is described in [4].
6 Conventions of elliptic curves
6.1 Definition of elliptic curves
m
6.1.1 Elliptic curves over F(p )
m
Let F(p ) be 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 ).
F
3 2
NOTE The above curve with 4a + 27b = 0 is called a singular curve, which is not an elliptic curve.
F
m
The set of F(p )-valued points of E is given by
4 © ISO/IEC 2015 – All rights reserved

ISO/IEC DIS 15946-1
m m m 2 3
E(F(p )) = {Q = (x , y ) ∈ F(p ) × F(p ) | y = x + ax + b } ∪ { O },
Q Q Q Q Q E
where O is an extra point referred to as the point at infinity of E.
E
m
6.1.2 Elliptic curves over F(2 )
m
Let F(2 ), for some m ≥ 1, be a finite field. 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 )
m
such that b ≠ 0 holds in F(2 ).
F
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.
F
m
The set of F(2 )-valued points of E is given by
m m m 2 3 2
E(F(2 )) = {Q = (x , y ) ∈ F(2 ) × F(2 ) | y + x y = x + ax + b} ∪ { O },
Q Q Q Q Q Q Q E
where O is an extra point referred to as the point at infinity of E.
E
m
6.1.3 Elliptic curves over F(3 )
m
Let F(3 ) be 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 )
m
such that a, b ≠ 0 holds in F(3 ).
F
NOTE The above curve with a or b = 0 is called a singular curve, which is not an elliptic curve.
F
m
The set of F(3 )-valued points of E is given by
m m m 2 3 2
E(F(3 )) = {Q = (x , y ) ∈ F(3 ) × F(3 ) | y = x + ax + b } ∪ { O },
Q Q Q Q Q E
where O is an extra point referred to as the point at infinity of E.
E
6.2 The group law on elliptic curves
Elliptic curves are endowed with the addition operation +: E × E → E, defining for each pair (Q , Q ) of points
1 2
on E a third point Q + Q . With respect to this addition, E is an abelian group with identity element O . The k-th
1 2 E
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
E
k = 0. The smallest positive k with kQ = O is called the order of Q.
E
NOTE Formulae of the group law and Q are given in Clauses B.2, B.3, and B.4.
6.3 Generation of elliptic curves
In order to use elliptic curve for cryptosystem, it is necessary to generate an appropriate elliptic curve.
ISO/IEC 15946-5 shall be referred for various generations of elliptic curves.
© ISO/IEC 2015 – All rights reserved 5

ISO/IEC DIS 15946-1
6.4 Cryptographic bilinear map
A cryptographic bilinear map e is used in some cryptographic applications such as signature schemes or key
n
agreement schemes. The cryptographic bilinear map e is realized by restricting the domain of the Weil or
n
Tate pairings as follows:
e : < G >×< G > → μ
n 1 2 n
The cryptographic bilinear map e satisfies the following properties:
n
ab
 Bilinear : e (aG , bG ) = e(G , G ) (∀a,b ∈ [0, n-1]).
n 1 2 1 2
 Non-degenerate : e (G , G ) ≠ 1.
n 1 2
 Computability : There exists an efficient algorithm to compute e .
n
NOTE 1 The relation between the cryptographic bilinear map and the Weil or Tate pairing is given in Clause B.6.
NOTE 2 Formulae for the Weil and Tate pairings are given in Clause C.4.
NOTE 3 There are two types of pairings:
 the case of G = G ,
1 2
 the case of G ≠ G .
1 2
7 Conversion functions
7.1 Octet string / bit string conversion: OS2BSP and BS2OSP
Primitives OS2BSP and BS2OSP to convert between octet strings and bit strings are defined as follows:
 The function OS2BSP(x) takes as input an octet string x, interprets it as a bit string y and outputs the bit
string y. Set the first bit of the bit string to the most significant (leftmost) bit of the first octet, the second bit
to the next most significant bit of the first octet, continue in the same way, and finally set the last bit to the
least significant (rightmost) bit of the last octet.
 The function BS2OSP(y) takes as input a bit string y, whose length is a multiple of 8, and outputs the
unique octet string x such that y = OS2BSP(x).
* *
NOTE The set of finite bit strings is {0, 1} . The set of finite octet string is {0, 1} .
7.2 Bit string / integer conversion: BS2IP and I2BSP
Primitives BS2IP and I2BSP to convert between bit strings and integers are defined as follows:
 The function BS2IP(x) maps a bit string x to an integer value x′, as follows. If x = 〈x , . . . , x 〉 where
l−1 0
i
x , . . . , x are bits, then the value x′ is defined as x′ = 2 , and
0 l−1 0 ≤ i < l, x = ‘1’
∑
i
 The function I2BSP(m, l ) takes as input two non-negative integers m and l, and outputs the unique bit
string x of length l such that BS2IP(x) = m, if such an x exists. Otherwise, the function outputs an error
message.
The length in bits of a non-negative integer m is the number of bits in its binary representation, i.e. log (m + 1).
As a notational convenience, Oct(m) is defined as Oct(m) = I2BSP(m, 8).
6 © ISO/IEC 2015 – All rights reserved

ISO/IEC DIS 15946-1
NOTE I2BSP(m, l ) fails if and only if the length of m in bits is greater than l.
7.3 Octet string / string conversion: OS2IP and I2OSP
Primitives OS2IP and I2OSP to convert between octet strings and integers are defined as follows:
 The function OS2IP(x) takes as input an octet string x, and outputs the integer BS2IP(OS2BSP(x)).

 The function I2OSP(m, l ) takes as input two non-negative integers m and l, and outputs the unique octet
string x of length l in octets such that OS2IP(x) = m, if such an x exists. Otherwise, the function outputs an
error message.
The length in octets of a non-negative integer m is the number of digits in its representation base 256, i.e.
log (m + 1).
NOTE 1 I2OSP(m, l ) fails if and only if the length of m in octets is greater than l.
NOTE 2 An octet x is often written in its hexadecimal format of length 2; when OS2IP(x) < 16, “0”, representing the bit
string 0000, is prepended. For example, an integer 15 is written as 0f in its hexadecimal format.
NOTE 3 The length in octets of a non-negative integer m is denoted by L(m).
7.4 Finite field element / integer conversion: FE2IP
F
The primitive FE2IP to convert elements of F to integer values is defined as follows:
F
 The function FE2IP maps an element a ∈ F to an integer value a′, as follows. If an element a of F is
F
m
identified with an m-tuple (a , . . . , a ), where the cardinality of F is q = p and a ∈ [0, p-1] for 1 ≤ i ≤ m, then
1 m i
i − 1
the value a′ is defined as a′ = a p .
1 ≤ i ≤ m i
∑
7.5 Octet string / finite field element conversion: OS2FEP and FE2OSP
F F
Primitives OS2FEP and FE2OSP to convert between octet strings and elements of an explicitly given finite
F F
field F are defined as follows:
 The function FE2OSP (a) takes as input an element a of the field F and outputs the octet string
F
I2OSP(a′, l ), where a′ = FE2IP (a) and l = L(|F |−1). Thus, the output of FE2OSP (a) is always an octet
F F
string of length exactly log |F |.
NOTE 1 L(x) represents the length in octets of integer x or octet string x (non-negative integer).
 The function OS2FEP (x) takes as input an octet string x, and outputs the (unique) field element a ∈ F
F
such that FE2OSP (a) = x, if such an a exists, and otherwise fails.
F
NOTE 2 OS2FEP (x) fails if and only if either x does not have length exactly log |F |, or OS2IP(x) ≥ |F |.
F 256
7.6 Elliptic curve point / octet string conversion: EC2OSP and OS2ECP
E E
7.6.1 Compressed elliptic curve points
Let E be an elliptic curve over an explicitly given finite field F, where F has characteristic p. A point P ≠ O can
E
be represented in either compressed, uncompressed, or hybrid form. If P = (x, y), then (x, y) is the
uncompressed form of P. The compressed form of P is the pair (x, ỹ), where ỹ ∈ {0, 1} is determined as
follows:
 If p ≠ 2 and y = 0 , then ỹ = 0.
F
© ISO/IEC 2015 – All rights reserved 7

ISO/IEC DIS 15946-1
f
 If p ≠ 2 and y ≠ 0 , then ỹ = ((y′/p ) mod p) mod 2, where y′ = FE2IP (y), and where f is the largest non-
F F
f
negative integer such that p | y′.
NOTE 1 If p ≠ 2 and y = (y , . . . , y ) ≠ 0 , this is equivalent to letting j be the smallest index with y ≠ 0 and define ỹ = y
1 m F j j
mod 2.
 If p = 2 and x = 0 , then ỹ = 0.
F
f
 If p = 2 and x ≠ 0 , then ỹ = z′/2  mod 2, where z = y/x, where z′ = FE2IP (z), and where f is the largest non-
F F
f
negative integer such that 2 divides FE2IP (1 ).
F F
NOTE 2 If p = 2 and x ≠ 0, this is equivalent to letting y/x = (z , . . . , z ) and define ỹ = z .
1 m 1
The hybrid form of P = (x, y) is the triple (x, ỹ, y), where ỹ is as in the previous paragraph.
7.6.2 Point decompression algorithms
There exist efficient procedures for point decompression, i.e. computing y from (x, ỹ). These are briefly
described here:
 If p ≠ 2, then let (x, ỹ) be the compressed form of (x, y). The point (x, y) satisfies the Weierstrass equation
y = f (x) defined in Clause 5.1.1 or 5.1.3. If f (x) = 0 , then there is only one possible choice for y, namely,
F
y = 0 . Otherwise, if f (x) ≠ 0 , then there are two possible choices of y, which differ only in sign, and the
F F
correct choice is determined by ỹ. There are well-known algorithms for computing square roots in finite
fields, and so the two choices of y are easily computed.
 If p = 2, then let (x, ỹ) be the compressed form of (x, y). The point (x, y) satisfies the equation
2 3 2 2
y + xy = x + ax + b. If x = 0 , then we have y = b, from which y is uniquely determined and easily
F
2 −2
computed. Otherwise, if x ≠ 0 , then setting z = y/x, we have z + z = g(x), where g(x) = x + a + bx . The
F
value of y is uniquely determined by, and easily computed from, the values z and x, and so it suffices to
compute z. To compute z, observe that for a fixed x, if z is one solution to the equation z + z = g(x), then
there is exactly one other solution, namely z + 1 . It is easy to compute these two candidate values of z,
F
and the correct choice of z is easily seen to be determined by ỹ.
7.6.3 Conversion functions
Let E be an elliptic curve over an explicitly given finite field F.
Primitives EC2OSP and OS2ECP for converting between points on an elliptic curve E and octet strings are
E E
defined as follows:
 The function EC2OSP (P, fmt) takes as input a point P on E and a format specifier fmt, which is one of the
E
symbolic values compressed, uncompressed, or hybrid. The output is an octet string EP, computed
as follows:
 If P = O , then EP = Oct(0).
E
 If P = (x, y) ≠ O , with compressed form (x, ỹ), then EP = H || X || Y, where
E
 H is a single octet of the form Oct(4U + C · (2 + ỹ )), where
 U = 1 if fmt is either uncompressed or hybrid, and otherwise, U = 0,
 C = 1 if fmt is either compressed or hybrid, and otherwise, C = 0,
 X is the octet string FE2OSP (x),
F
 Y is the octet string FE2OSP (y) if fmt is either uncompressed or hybrid, and otherwise Y is
F
the null octet string.
8 © ISO/IEC 2015 – All rights reserved

ISO/IEC DIS 15946-1
 The function OS2ECP (EP) takes as input an octet string EP. If there exists a point P on the curve E and a
E
format specifier fmt such that EC2OSP (P, fmt) = EP, then the function outputs P (in uncompressed form),
E
and otherwise, the function fails. Note that the point P, if it exists, is uniquely defined, and so the function
OS2ECP (EP) is well defined.
E
NOTE If the format specifier fmt is uncompressed, then both x and y are used; and the value ỹ need not be
computed.
7.7 Integer / elliptic curve conversion: I2ECP
Let E be an elliptic curve over an explicitly given finite field F. Primitive I2ECP to convert from integers to
elliptic curve points is defined as follows.
a) The function I2ECP(x) takes as input an integer x.
b) Convert the integer x to an octet string X = I2OSP(x, L(|F |−1)).
c) If there exists a point P on the curve E such that EC2OSP (P, compressed) = 03||X, then the function
E
outputs P, and otherwise, the function fails.
NOTE 1 The output of point P, if it exists, is uniquely defined.
NOTE 2 The function I2ECP will fail on input x if there does not exist a point P on the curve E such that EC2OSP (P,
E
compressed) = 03||X.
NOTE 3 The range of the I2ECP is approximately half of E(F). That is, the I2ECP always outputs elliptic curve points P =
(x, y) with compressed form (x, 1). It will not output either the point at infinity or an elliptic curve point P = (x, y) with
compressed form (x, 0).
NOTE 4 Some applications based on elliptic curve may need a function which maps octet strings to elliptic curve points.
The function I2ECP is used as a component together with OS2IP or a hash function.
8 Elliptic curve domain parameters and public key
8.1 Elliptic curve domain parameters over F(q)
m
Elliptic curve parameters over F(q) (including the special cases F(p) and F(2 )) shall consist of the following:
NOTE 1 If m>1, there must be an agreement on the choice of the basis between the communicating parties.
m
 The field size q = p which defines the underlying finite field F(q), where p shall be a prime number, and
an indication of the basis used to represent the elements of the field in case m>1.
m
 If q = p with p > 3, two field elements a and b in F(q) which define the equation of the elliptic curve
2 3
E: y = x + ax+ b.
m m
 If q = 2 , two field elements a and b in F(2 ) which define the equation of the elliptic curve
2 3 2
E: y + xy = x + ax + b.
m m
 If q = 3 , two field elements a and b in F(3 ) which define the equation of the elliptic curve
2 3 2
E: y = x + ax + b.
 Two field elements x and y in F(q) which define a point G = (x , y ) of prime order on E.
G G G G
© ISO/IEC 2015 – All rights reserved 9

ISO/IEC DIS 15946-1
 The order n of the point G.
 The cofactor h = #E(F(q))/n (when required by the underlying scheme).
NOTE 2 The computation of #E(F(q)) is described in [4].
8.2 Elliptic curve key generation
Given a valid set of elliptic curve domain parameters, a private key and corresponding public key may be
generated as follows.
a) Select a random or pseudorandom integer d in the set [2, n-2]. The integer d must be protected from
unauthorised disclosure and be unpredictable.
b) Compute the point P = (x , y ) = dG.
P P
c) The key pair is (P, d), where P will be used as the public key, and d is the private key.
In some applications the public key may be eG, where de = 1 mod n.

10 © ISO/IEC 2015 – All rights reserved

ISO/IEC DIS 15946-1
Annex A
(informative)
Background information on finite fields
It is the purpose of this annex to present the information on finite fields that is necessary for the elliptic curve
based public key schemes.
A.1 Bit strings
A bit is either zero “0” or one “1”. A bit string x is a finite sequence 〈x , . .
...

INTERNATIONAL ISO/IEC
STANDARD 15946-1
Third edition
2016-07-01
Information technology — Security
techniques — Cryptographic
techniques based on elliptic curves —
Part 1:
General
Technologies de l’information — Techniques de sécurité —
Techniques cryptographiques basées sur les courbes elliptiques —
Partie 1: Généralités
Reference number
©
ISO/IEC 2016
© ISO/IEC 2016, 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. [phone]
Fax [phone]
[e-mail]
www.iso.org
ii © ISO/IEC 2016 – All rights reserved

Contents Page
Foreword .iv
Introduction .v
1 Scope . 1
2 Normative references . 1
3 Terms and definitions . 1
4 Symbols . 2
5 Conventions for fields . 3
5.1 Finite prime fields F(p) . 3
m
5.2 Finite fields F(p ) . 3
6 Conventions for elliptic curves . 4
6.1 Definitions of elliptic curves . 4
m
6.1.1 Elliptic curves over F(p ) . 4
m
6.1.2 Elliptic curves over F(2 ) . 4
m
6.1.3 Elliptic curves over F(3 ) . 5
6.2 Group law on elliptic curves . 5
6.3 Generation of elliptic curves . 5
6.4 Cryptographic bilinear map . 5
7 Conversion functions . 6
7.1 Octet string/bit string conversion: OS2BSP and BS2OSP . 6
7.2 Bit string/integer conversion: BS2IP and I2BSP . 6
7.3 Octet string/string conversion: OS2IP and I2OSP . 6
7.4 Finite field element/integer conversion: FE2IP .
F 7
7.5 Octet string/finite field element conversion: OS2FEP and FE2OSP .
F F 7
7.6 Elliptic curve point/octet string conversion: EC2OSP and OS2ECP .
E E 7
7.6.1 Compressed elliptic curve points . 7
7.6.2 Point decompression algorithms . 7
7.6.3 Conversion functions . 8
7.7 Integer/elliptic curve conversion: I2ECP . 8
8 Elliptic curve domain parameters and public key . 9
8.1 Elliptic curve domain parameters over F(q) . 9
8.2 Elliptic curve key generation . 9
Annex A (informative) Background information on finite fields .10
Annex B (informative) Background information on elliptic curves .12
Annex C (informative) Background information on elliptic curve cryptosystems .22
Annex D (informative) Summary of coordinate systems .30
Bibliography .31
© ISO/IEC 2016 – 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 meaning of ISO specific terms and expressions related to conformity
assessment, as well as information about ISO’s adherence to the WTO principles in the Technical
Barriers to Trade (TBT), see the following URL: Foreword — Supplementary information.
The committee responsible for this document is ISO/IEC JTC 1, Information technology, Subcommittee
SC 27, Security techniques.
This third edition cancels and replaces the second edition (ISO/IEC 15946-1:2008 with
ISO/IEC 15946-1/Cor 1:2009), which has been technically revised.
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 2016 – All rights reserved

Introduction
Cryptosystems based on elliptic curves defined over finite fields provide an interesting alternative to
the RSA cryptosystem and to finite field discrete log based cryptosystems. The concept of an elliptic
curve based public-key cryptosystem is 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 the Diffie–Hellman and ElGamal type.
The security of such a public-key cryptosystem 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 for a given parameter size than the factorisation 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 recognisable, cases. There has been no
substantial progress in finding a 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 some finite field. This yields significantly shorter digital signatures
and system parameters and the integers to be handled by a cryptosystem are much smaller.
This part of ISO/IEC 15946 describes the mathematical background and general techniques
necessary for implementing the elliptic curve cryptography mechanisms defined in ISO/IEC 15946-5,
ISO/IEC 9796-3, ISO/IEC 11770-3, ISO/IEC 14888-3, ISO/IEC 18033-2 and other ISO/IEC standards.
It is the purpose of this part of ISO/IEC 15946 to meet the increasing interest in elliptic curve based
public-key technology and to describe the components that are necessary to implement secure elliptic
curve cryptosystems such as key-exchange, key-transport and digital signatures.
The International Organization for Standardization (ISO) and the International Electrotechnical
Commission (IEC) draw attention to the fact that it is claimed that compliance with this part of
ISO/IEC 15946 may involve the use of patents.
The ISO and IEC take no position concerning the evidence, validity and scope of these patent rights.
The holders of these patent rights have assured the ISO and IEC that they are willing to negotiate
licenses under reasonable and non-discriminatory terms and conditions with applicants throughout
the world. In this respect, the statements of the holders of these patent rights are registered with ISO
and IEC. Information may be obtained from:
Certicom Corp. Address: 4701 Tahoe Blvd., Building A, Mississauga, ON L4W0B5, Canada
Matsushita Electric Industrial Co., Ltd. Address: 1006, Kadoma, Kadoma City, Osaka, 571-8501, Japan
Attention is drawn to the possibility that some of the elements of this document may be the subject
of patent rights other than those identified above. ISO and/or IEC shall not be held responsible for
identifying any or all such patent rights.
ISO (www.iso.org/patents) and IEC (http://patents.iec.ch) maintain on-line databases of patents
relevant to their standards. Users are encouraged to consult the databases for the most up to date
information concerning patents.
© ISO/IEC 2016 – All rights reserved v

INTERNATIONAL STANDARD ISO/IEC 15946-1:2016(E)
Information technology — Security techniques —
Cryptographic techniques based on elliptic curves —
Part 1:
General
1 Scope
This part of ISO/IEC 15946 describes the mathematical background and general techniques
necessary for implementing the elliptic curve cryptography mechanisms defined in ISO/IEC 15946-5,
ISO/IEC 9796-3, ISO/IEC 11770-3, ISO/IEC 14888-3, ISO/IEC 18033-2 and other ISO/IEC standards.
This part of ISO/IEC 15946 does not specify the implementation of the techniques it defines. For
example, it does not specify the basis representation to be used when the elliptic curve is defined
over a finite field of characteristic two. Thus, interoperability of products complying with this part of
ISO/IEC 15946 will not be guaranteed.
2 Normative references
The following referenced documents, in whole or in part, are normatively referenced in this document
and are indispensable for its application. 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-5, Information technology — Security techniques — Cryptographic techniques based on
elliptic curves — Part 5: Elliptic curve generation
3 Terms and definitions
For the purposes of this document, the following terms and definitions apply.
3.1
abelian group
group (S, ) such that a b = b a for every a and b in S
* * *
3.2
cubic curve
set of solutions, made up of pairs of elements of a specified field known as points, to a cubic equation of
special form
3.3
elliptic curve
cubic curve E without a singular point
Note 1 to entry: The set of points E together with an appropriately defined operation (see 6.2) forms an abelian
group. The field that includes all coefficients of the equation describing E is called the definition field of E. In this
part of ISO/IEC 15946, only finite fields F are dealt with as the definition field. When it is necessary to describe
the definition field F of E explicitly, the curve is denoted as E/F.
Note 2 to entry: The form of a cubic curve equation used to define an elliptic curve varies depending on the field.
The general form of an appropriate cubic equation for all possible finite fields is defined in 6.1.
Note 3 to entry: A definition of a cubic curve is given in Reference [15].
© ISO/IEC 2016 – All rights reserved 1

3.4
field
set of elements S and a pair of operations (+, ) defined on S such that: (i) a (b + c) = a b + a c for every a,
* * * *
b and c in S, (ii) S together with + forms an abelian group (with identity element 0), and (iii) S excluding
0 together with forms an abelian group
*
3.5
finite field
field containing a finite number of elements
m
Note 1 to entry: For any positive integer m and a prime p, there exists a finite field containing exactly p elements.
m m
This field is unique up to isomorphism and is denoted by F(p ), where p is called the characteristic of F(p ).
3.6
group
set of elements S and an operation defined on the set of elements such that (i) a (b c) = (a b) c for every
* * * * *
a, b and c in S, (ii) there exists an identity element e in S such that a e = e a = a for every a in S, and (iii)
* *
−1 −1 −1
for every a in S there exists an inverse element a in S such that a a = a a = e
* *
3.7
cryptographic bilinear map
map satisfying the non-degeneracy, bilinearity, and computability conditions
Note 1 to entry: Definitions of non-degeneracy, bilinearity and computability are provided in 6.4.
3.8
singular point
point at which a given mathematical object is not defined
4 Symbols
B
B smallest integer such that n divides q -1
d private key of a user (d is a random integer in the set [2, n-2])
2 3 m
E 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
E
m m m
point at infinity; the curve is denoted by E/F(p ), E/F(2 ), or E/F(3 ), respectively
E(F(q)) set of F(q)-valued points of E together with O
E
#E(F(q)) order (or cardinality) of E(F(q))
E[n] n-torsion group of E, that is {Q ∈ E | nQ = O }
E
e cryptographic bilinear map
n
|F | number of elements in F
m m
F(q) finite field consisting of exactly q elements; this includes the cases of F(p), F(2 ), and F(p )
F(q)* F(q)\{0 }
F
G base point on E with prime order n
group generated by G with prime cardinality n
h cofactor of E(F(q))
2 © ISO/IEC 2016 – All rights reserved

kQ kth multiple of some point Q of E, i.e. kQ = Q + …+ Q (k summands) if k > 0, kQ = (–k)(–Q), if
k < 0, and kQ = O if k = 0
E
μ cyclic group of order n comprised of the nth roots of unity in the algebraic closure of F(q)
n
n prime divisor of #E(F(q))
O elliptic curve point at infinity
E
p prime number
P public key of a user (P is an elliptic curve point in )
m
q prime power p for some prime p and some integer m ≥ 1
Q point on E with coordinates (x , y )
Q Q
Q +Q elliptic curve sum of two points Q and Q
1 2 1 2
x x-coordinate of Q ≠ O
Q E
y y-coordinate of Q ≠ O
Q E
[0, k] set of integers from 0 to k inclusive
0 identity element of F(q) for addition
F
1 identity element of F(q) for multiplication
F
5 Conventions for fields
5.1 Finite prime fields F(p)
For any prime p, there exists a finite field consisting of exactly p elements. This field is uniquely
determined up to isomorphism and in this part of ISO/IEC 15946 it is referred to as the finite prime
field F(p).
The elements of a finite prime field F(p) may be identified with the set [0, p − 1] of all non-negative
integers less than p. F(p) is endowed with two operations called addition and multiplication such that
the following conditions hold:
— F(p) is an abelian group with respect to the addition operation “+”.
For a, b ∈ F(p) the sum a + b is given as a + b: = r, where r ∈ F(p) is the remainder obtained when the
integer sum a + b is divided by p.
— F(p)\{0} denoted as F(p)* is an abelian group with respect to the multiplication operation “×”.
For a, b ∈ F(p) the product a × b is given as a × b: = r, where r ∈ F(p) is the remainder obtained when the
integer product a × b is divided by p. When it does not cause confusion, × is omitted and the notation ab
is used or the notation a⋅b is used.
m
5.2 Finite fields F(p )
m
For any positive integer m and prime p, there exists a finite field of exactly p elements. This field is
m
unique up to isomorphism and in this part of ISO/IEC 15946 it is referred to as the finite field F(p ).
m m
NOTE 1 F(p ) is the general definition including F(p) for m = 1 and F(2 ) for p = 2.
© ISO/IEC 2016 – All rights reserved 3

NOTE 2 If p = 2, then field elements may be identified with bit strings of length m and the sum of two field
elements is the bit-wise XOR of the two bit strings.
m
The finite field F(p ) may be identified with the set of p-ary strings of length m in the following way.
m
Every finite field F(p ) contains at least one basis {ξ , ξ , …, ξ } over F(p) such that every element α
1 2 m
m
∈ F(p ) has a unique representation of the form α = aξ + aξ + … + a ξ , with a ∈ F(p) for i = 1,
1 1 2 2 m m i
2,∙∙∙, m. The element α can then be identified with the p-ary string (a , a ,∙∙∙, a ). The choice of basis is
1 2 m
m
beyond the scope of this part of ISO/IEC 15946. F(p ) is endowed with two operations called addition
and multiplication such that the following conditions hold:
m
— F(p ) is an abelian group with respect to the addition operation “+”.
For α = (a , a ,∙∙∙, a ) and β = (b , b ,∙∙∙, b ), the sum a + β is given by a + β: = γ = (c , c ,∙∙∙, c ), where
1 2 m 1 2 m 1 2 m
c = a + b is the sum in F(p). The identity element for addition is 0 = (0, …, 0).
i i i F
m m
— F(p )\{0}, denoted by F(p )*, is an abelian group with respect to the multiplication operation “×”.
For α = (a , a ,∙∙∙, a ) and β = (b , b ,∙∙∙, b ) the product α × β is given by a p-ary string a × β: = γ = (c , c ,∙∙∙, c ),
1 2 m 1 2 m 1 2 m
where c = ∑  a b d for ξξ = d ξ + d  ξ + . + d ξ (1 ≤ j, k ≤ m). When it does not
i 1 ≤ j,k ≤ m j k i,j,k j k 1,j,k 1 2,j,k 2 m,j,k m
cause confusion, × is omitted and the notation ab is used. The basis can be chosen in such a way that the
identity element for multiplication is 1 = (1, 0, …, 0).
F
NOTE 3 The choice of basis is described in Reference [4].
6 Conventions for elliptic curves
6.1 Definitions of elliptic curves
m
6.1.1 Elliptic curves over F(p )
m
Let F(p ) be a finite field with a prime P > 3 and a positive integer m. In this part of ISO/IEC 15946, 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 ).
F
3 2
NOTE The above curve with 4a + 27b = 0 is called a singular curve, which is not an elliptic curve.
F
m
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.
E
m
6.1.2 Elliptic curves over F(2 )
m
Let F(2 ), for some m ≥ 1, be a finite field. In this part of ISO/IEC 15946, 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 )
m
such that b ≠ 0 holds in F(2 ).
F
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.
F
4 © ISO/IEC 2016 – All rights reserved

m
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.
E
m
6.1.3 Elliptic curves over F(3 )
m
Let F(3 ) be a finite field with a positive integer m. In this part of ISO/IEC 15946, 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 )
m
such that a, b ≠ 0 holds in F(3 ).
F
NOTE The above curve with a or b = 0 is called a singular curve, which is not an elliptic curve.
F
m
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.
E
6.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)
E
(−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
NOTE Formulae of the group law and Q are given in B.3, B.4, and B.5.
6.3 Generation of elliptic curves
In order to use an elliptic curve for a cryptosystem, it is necessary to generate an appropriate elliptic
curve. ISO/IEC 15946-5 shall be referred to for methods of generation of elliptic curves.
6.4 Cryptographic bilinear map
A cryptographic bilinear map e is used in some cryptographic applications such as signature schemes
n
or key agreement schemes. A cryptographic bilinear map e is realized by restricting the domain of the
n
Weil or Tate pairings as follows.
e : × → μ
n 1 2 n
where the cryptographic bilinear map e satisfies the following properties:
n
ab
— bilinearity: e (aG , bG ) = e(G , G ) (∀a,b ∈ [0, n-1]);
n 1 2 1 2
— non-degeneracy: e (G , G ) ≠ 1;
n 1 2
— computability: There exists an efficient algorithm to compute e .
n
NOTE 1 The relation between the cryptographic bilinear map and the Weil or Tate pairing is given in B.7.
NOTE 2 Formulae for the Weil and Tate pairings are given in C.6.
NOTE 3 There are two types of pairings:
© ISO/IEC 2016 – All rights reserved 5

— the case G = G ;
1 2
— the case G ≠ G .
1 2
7 Conversion functions
7.1 Octet string/bit string conversion: OS2BSP and BS2OSP
Primitives OS2BSP and BS2OSP to convert between octet strings and bit strings are defined as follows:
— The function OS2BSP(x) takes as input an octet string x, interprets it as a bit string y and outputs the
bit string y. Set the first bit of the bit string to the most significant (leftmost) bit of the first octet, the
second bit to the next most significant bit of the first octet, continue in the same way, and finally set
the last bit to the least significant (rightmost) bit of the last octet.
— The function BS2OSP(y) takes as input a bit string y, whose length is a multiple of 8, and outputs the
unique octet string x such that y = OS2BSP(x).
7.2 Bit string/integer conversion: BS2IP and I2BSP
Primitives BS2IP and I2BSP to convert between bit strings and integers are defined as follows:
— The function BS2IP(x) maps a bit string x to an integer value x′, as follows:
i
If x = 〈x , . . . , x 〉, where x , . . . , x are bits, then the value x′ is defined as x′ = ∑    2 .
l−1 0 0 l−1 0 ≤ i < l, xi = ‘1’
— The function I2BSP(m, l ) takes as input two non-negative integers, m and l, and outputs the unique
bit string x of length l, such that BS2IP(x) = m, if such an x exists. Otherwise, the function outputs an
error message.
The length in bits of a non-negative integer m is the number of bits in its binary representation, i.e.
[log (m + 1)]. As a notational convenience, Oct(m) is defined as Oct(m) = I2BSP(m, 8).
NOTE I2BSP(m, l) fails if, and only if, the length of m in bits is greater than l.
7.3 Octet string/string conversion: OS2IP and I2OSP
Primitives OS2IP and I2OSP to convert between octet strings and integers are defined as follows:
— The function OS2IP(x) takes as input an octet string x, and outputs the integer BS2IP[OS2BSP(x)].
— The function I2OSP(m, l) takes as input two non-negative integers, m and l, and outputs the unique
octet string x of length l in octets, such that OS2IP(x) = m, if such an x exists. Otherwise, the function
outputs an error message.
The length in octets of a non-negative integer m is the number of digits in its representation base 256,
i.e. [log (m + 1)].
NOTE 1 I2OSP(m, l) fails if, and only if, the length of m in octets is greater than l.
NOTE 2 An octet x is often written in its hexadecimal format of length 2; when OS2IP(x) < 16, “0”, representing
the bit string 0000, is prepended. For example, an integer 15 is written as 0f in its hexadecimal format.
NOTE 3 The length in octets of a non-negative integer m is denoted by L(m).
6 © ISO/IEC 2016 – All rights reserved

7.4 Finite field element/integer conversion: FE2IP
F
The primitive FE2IP to convert elements of F to integer values is defined as follows:
F
— The function FE2IP maps an element a ∈ F to an integer value a′, as follows:
F
m
If an element a of F is identified with an m-tuple (a , . . ., a ), where the cardinality of F is q = p and
1 m
i − 1
a ∈ [0, p − 1] for 1 ≤ i ≤ m, then the value a′ is defined as a′ = ∑  a p .
i 1 ≤ i ≤ m i
7.5 Octet string/finite field element conversion: OS2FEP and FE2OSP
F F
Primitives OS2FEP and FE2OSP to convert between octet strings and elements of an explicitly given
F F
finite field F are defined as follows:
— The function FE2OSP (a) takes as input an element a of the field F and outputs the octet string
F
I2OSP(a′, l), where a′ = FE2IP (a) and l = L(|F|−1). Thus, the output of FE2OSP (a) is always an octet
F F
string of length exactly [log |F|].
NOTE 1 L(x) represents the length in octets of integer x or octet string x (non-negative integer).
— The function OS2FEP (x) takes as input an octet string x, and outputs the (unique) field element
F
a ∈ F, such that FE2OSP (a) = x, if such an a exists, and otherwise fails.
F
NOTE 2 OS2FEP (x) fails if and only if either x does not have length exactly [log |F|], or OS2IP(x) ≥ |F|.
F 256
7.6 Elliptic curve point/octet string conversion: EC2OSP and OS2ECP
E E
7.6.1 Compressed elliptic curve points
Let E be an elliptic curve over an explicitly given finite field F, where F has characteristic p. A point
P ≠ O can be represented in either compressed, uncompressed, or hybrid form. If P = (x, y), then
E
(x, y) is the uncompressed form of P. The compressed form of P is the pair (x, ỹ), where ỹ ∈ {0, 1} and is
determined as follows:
— if p ≠ 2 and y = 0 , then ỹ = 0;
F
f
— if p ≠ 2 and y ≠ 0 , then ỹ = [(y′/p ) mod p] mod 2, where y′ = FE2IP (y), and where f is the largest
F F
f
non-negative integer, such that p |y′;
NOTE 1 If p ≠ 2 and y = ( y , . . ., y ) ≠ 0 , this is equivalent to letting j be the smallest index with y ≠ 0 and
1 m F j
defining ỹ = y mod 2.
j
— if p = 2 and x = 0 , then ỹ = 0;
F
f
— if p = 2 and x ≠ 0 , then ỹ = [z′/2 ] mod 2, where z = y/x, where z′ = FE2IP (z), and where f is the largest
F F
f
non-negative integer such that 2 divides FE2IP (1 ).
F F
NOTE 2 If p = 2 and x ≠ 0, this is equivalent to letting y/x = (z , . . ., z ) and defining ỹ = z .
1 m 1
The hybrid form of P = (x, y) is the triple (x, ỹ, y), where ỹ is as in the previous paragraph.
7.6.2 Point decompression algorithms
There exist efficient procedures for point decompression, i.e. computing y from (x, ỹ). These are briefly
described here.
— If p ≠ 2, then let (x, ỹ) be the compressed form of (x, y) where the point (x, y) satisfies the Weierstrass
equation y = f (x) defined in 6.1.1 or 6.1.3. If f (x) = 0 , then there is only one possible choice for y,
F
namely, y = 0 . Otherwise, if f (x) ≠ 0 , then there are two possible choices of y, which differ only in
F F
sign, and the correct choice is determined by ỹ. There are well-known algorithms for computing
square roots in finite fields, and so the two choices of y are easily computed.
© ISO/IEC 2016 – All rights reserved 7

— If p = 2, then let (x, ỹ) be the compressed form of (x, y) where the point (x, y) satisfies the equation
2 3 2 2
y + xy = x + ax + b. If x = 0 , then the equation is y = b, from which y is uniquely determined
F
and easily computed. Otherwise, if x ≠ 0 , then setting z = y/x, the equation is z + z = g(x), where
F
−2
g(x) = x + a + bx . The value of y is uniquely determined by, and easily computed from, the values z
and x, and so it suffices to compute z. To compute z, observe that for a fixed x, if z is one solution to
the equation z + z = g(x), then there is exactly one other solution, namely z + 1 . It is easy to compute
F
these two candidate values of z, and the correct choice of z is easily seen to be determined by ỹ.
7.6.3 Conversion functions
Let E be an elliptic curve over an explicitly given finite field F.
Primitives EC2OSP and OS2ECP for converting between points on an elliptic curve E and octet strings
E E
are defined as follows:
— The function EC2OSP (P, fmt) takes as input a point P on E and a format specifier fmt, which is one
E
of the symbolic values compressed, uncompressed, or hybrid. The output is an octet string, EP,
computed as follows:
— if P = O , then EP = Oct(0);
E
— if P = (x, y) ≠ O , with compressed form (x, ỹ), then EP = H||X||Y, where
E
— H is a single octet of the form Oct[4U + C(2 + ỹ)], where
— U = 1 if fmt is either uncompressed or hybrid, and otherwise, U = 0,
— C = 1 if fmt is either compressed or hybrid, and otherwise, C = 0;
— X is the octet string FE2OSP (x);
F
— Y is the octet string FE2OSP (y) if fmt is either uncompressed or hybrid, and otherwise
F
Y is the null octet string.
— The function OS2ECP (EP) takes as input an octet string EP. If there exists a point P on the curve
E
E and a format specifier fmt, such that EC2OSP (P, fmt) = EP, then the function outputs P (in
E
uncompressed form), and otherwise, the function fails. Note that the point P, if it exists, is uniquely
defined, and so the function OS2ECP (EP) is well defined.
E
NOTE If the format specifier fmt is uncompressed, then both x and y are used; and the value ỹ need not be
computed.
7.7 Integer/elliptic curve conversion: I2ECP
Let E be an elliptic curve over an explicitly given finite field F. Primitive I2ECP to convert from integers
to elliptic curve points is defined as follows:
a) The function I2ECP(x) takes as input an integer x.
b) Convert the integer x to an octet string X = I2OSP[x, L(|F|−1)].
c) If there exists a point P on the curve E such that EC2OSP (P, compressed) = 03||X, then the
E
function outputs P, and otherwise, the function fails.
NOTE 1 The output of point P, if it exists, is uniquely defined.
NOTE 2 The function I2ECP will fail on input x if there does not exist a point P on the curve E such that EC2OSP
E
(P, compressed) = 03||X.
NOTE 3 The range of the I2ECP is approximately half of E(F). That is, the I2ECP always outputs elliptic curve
points P = (x, y) with compressed form (x, 1). It will not output either the point at infinity or an elliptic curve point
P = (x, y) with compressed form (x, 0).
8 © ISO/IEC 2016 – All rights reserved

NOTE 4 Some applications based on elliptic curves may need a function which maps octet strings to elliptic
curve points. The function I2ECP is used as a component together with OS2IP or a hash function.
8 Elliptic curve domain parameters and public key
8.1 Elliptic curve domain parameters over F(q)
m
Elliptic curve parameters over F(q) [including the special cases F(p) and F(2 )] shall consist of the
following:
If m > 1, there should be an agreement on the choice of the basis between the communicating parties.
m
— the field size q = p which defines the underlying finite field F(q), where p shall be a prime number,
and an indication of the basis used to represent the elements of the field in case m > 1;
m
— if q = p with P > 3, two field elements a and b in F(q) which define the equation of the elliptic curve
2 3
E: y = x + ax + b;
m m
— if q = 2 , two field elements a and b in F(2 ) which define the equation of the elliptic curve
2 3 2
E: y + xy = x + ax + b;
m m
— if q = 3 , two field elements a and b in F(3 ) which define the equation of the elliptic curve
2 3 2
E: y = x + ax + b;
— two field elements x and y in F(q) which define a point G = (x , y ) of prime order on E;
G G G G
— the order n of the point G;
— the cofactor h = #E(F(q))/n (when required by the underlying scheme).
NOTE The computation of #E(F(q)) is described in Reference [4].
8.2 Elliptic curve key generation
Given a valid set of elliptic curve domain parameters, a private key and corresponding public key may
be generated as follows:
a) Select a random or pseudorandom integer d in the set [2, n-2]. The integer d shall be protected from
unauthorised disclosure and be unpredictable.
b) Compute the point P = (x , y ) = dG.
P P
c) The key pair is (P, d), where P will be used as the public key and d is the private key.
In some applications, the public key may be eG, where de = 1 mod n.
© ISO/IEC 2016 – All rights reserved 9

Annex A
(informative)
Background information on finite fields
A.1 General
Annex A presents the information on finite fields that is necessary for the elliptic curve based public
key schemes.
A.2 Bit strings
A bit is either zero “0” or one “1”. A bit string x is a finite sequence 〈x , . . . , x 〉 of bits x , . . . , x . The
l−1 0 0 l−1
n
length of a bit string x is the number l of bits in the string x. Given a non-negative integer n, {0, 1}
n
denotes the set of bit strings of length n. {0, 1}* = ∪  {0, 1} denotes the set of bit strings, including
n ≥ 0
the null string (whose length is 0).
A.3 Octet strings
An octet is a bit string of length 8. An octet string is a finite sequence of octets. The length of an octet
string is the number of octets in the string. {0, 1} * denotes the set of octet strings, including the null
string (whose length is 0). An octet is often written in its hexadecimal format, using the range between
00 and FF.
m
A.4 Characteristic of a finite field F(p )
The characteristic of a field is the smallest positive integer c such that c additions of 1 give the zero
F
element. If no such c exists, the characteristic is 0. For any prime p, the characteristic of the field
m
F(p ) is p.
m
A.5 Inverting elements of a finite field F(p )
m m
Let a be an element of F(p ). Then there exists a unique element b ∈ F(p ) such that a∙b = b∙a = 1 , and b
F
−1 i −1 −1 q-1-i
is called the multiplicative inverse of a, denoted by a . If a = γ  , then a can be computed as a = γ  .
-1
NOTE If m = 1, a is given as x in the equation ax + py = 1, which can be solved using the extended Euclidean
algorithm.
m
A.6 Squares and non-squares in a finite field F(p )
m m m 2
An element a ∈ F(p ) is called a square in F(p ), if there exists an element b ∈ F(p ), such that a = b .
m
Whether or not a ∈ F(p ) is a square can be determined by making use of Formula (A.1):
m (q-1)/2
a is a square in F(p ) ⇔ a = 1 (A.1)
F
10 © ISO/IEC 2016 – All rights reserved

m
A.7 Finding square-roots in F(p )
m m
There are various methods for finding square roots in F(p ). That is, given a ∈ F(p ), where a is a
m 2
square, find b ∈ F(p ), such that a = b .
(q 1)/4
NOTE If q = 3 (mod 4), then the square-root can be computed as b = a + . The other cases are described
in References [4] and [5].
© ISO/IEC 2016 – All rights reserved 11

Annex B
(informative)
Background information on elliptic curves
B.1 General
Annex B presents the information on elliptic curves that is necessary for the elliptic curve based public
key schemes.
B.2 Properties of elliptic curves
An elliptic curve E over F(q) is endowed with a binary operation “+”: E × E → E assigning to any two
points Q , Q on E a third point Q + Q on E. The elliptic curve E is an abelian group with respect to “+”.
1 2 1 2
The number of points of E (including O ) is called the order (or cardinality) of E and is denoted by
E
#E(F(q)). The order satisfies the following theorem of Hasse:
q + 1 − 2√q ≤ #E(F(q)) ≤ q + 1 + 2√q
The integer t defined by t = q +1 − #E(F(q)) is called the trace. Hasse’s theorem gives a bound on the
trace. B.6 gives sufficient conditions that for a given t in [−2√q, 2√q], there is an elliptic curve E over F(q)
with trace t.
Anomalous and supersingular curves
An elliptic curve E defined over F(q) with trace t divisible by p is called supersingular. An elliptic curve
E defined over F(q) with #E(F(q)) = q is called anomalous. Supersingular curves are subject to the Frey-
[7] [10]
Rück and Menezes-Okamoto-Vanstone algorithms. Cryptsystems using anomalous curves are
[12] [13] [14]
vulnerable to attacks using the Araki-Satoh , Semaev and Smart algorithms.
B.3 Group law for elliptic curves E over F(q) with P > 3
B.3.1 Overview of coordinates
An elliptic curve is generally defined in terms of affine coordinates. Therefore, the base point or a user
public key is given in affine coordinates. The major drawback of affine coordinates is that they make
heavy use of divisions in F(q) for both addition and doubling. In most implementations of finite field
arithmetic, field division is a very “expensive” operation and in such situations it can be prudent to
avoid divisions as much as possible. This can be achieved by using other coordinates for the elliptic
curve points such as projective, Jacobian, and modified Jacobian coordinates. All of the coordinate
systems given for an elliptic curve are compatible.
12 © ISO/IEC 2016 – All rights reserved

B.3.2 Group law in affine coordinates
Let F(q) be a finite field with P > 3. Let E be an elliptic curve over F(q) given by the “short Weierstrass
equation”:
2 3
(Aff)  y = x + ax + b     with a, b ∈ F(q)
3 2
where the inequality 4a + 27b ≠ 0 holds in F(q).
F
NOTE More precisely, (Aff) is called the affine Weierstrass equation.
In affine coordinates, the group law on an elliptic curve given by (Aff) reads as follows:
— the point at infinity is the identity element O with respect to “+”;
E
— let R = (x, y) be a point on E, such that R ≠ O , then −R = (x, −y);
E
— let R = (x , y ) and R = (x , y ) be two distinct points on E, such that R ≠ ± R and R , R ≠ O ; the
1 1 1 2 2 2 1 2 1 2 E
sum is the point R = (x , y ) where:
3 3 3
x = r − x − x ;
3 1 2
y = r (x − x ) − y ;
3 1 3 1
with r = (y − y ) / (x − x );
2 1 2 1
— let R = (x, y) be a point on E, such that R ≠ O and y ≠ 0 ; its doubling is the point 2R = (x , y ), where:
E F 3 3
x = r − 2x;
y = r (x − x ) − y;
3 3
with r = (3x + a) / (2y).
In the case of R = (x, 0 ), its doubling is 2R = O .
F E
B.3.3 Group law in projective coordinates
NOTE 1 Using projective coordinates will result in more multiplications during the calculation of the group
[6]
laws but no inversions have to be computed.
NOTE 2 When using elliptic curves for cryptosystems, usually a transformation into affine coordinates has to
be done at the end of the scalar multiplication. When converting projective into affine coordinates, 1 division is
necessary.
The two-dimensional projective space over F(q), Π (F(q)), is given by equivalence classes of triplets
proj
(X, Y, Z) ∈ F(q) × F(q) × F(q) \ {(0 , 0 , 0 )}, where two triplets (X, Y, Z), (X’, Y’, Z’) ∈ F(q) × F(q) × F(q) \
F F F
{(0 , 0 , 0 )} are said to be equivalent, if there exists λ ∈ F(q)*, such that (X’, Y’, Z’) = (λX, λY, λZ). The
F F F
projective analogue of the short affine Weierstrass equation (Aff) is defined over Π (F(q)) and given
proj
by the homogeneous cubic formula
2 3 2 3
(Proj)   Y Z = X + aXZ + bZ     with a, b ∈ F(q).
NOTE 3 The set of all triplets equiva
...