ISO/IEC 15946-1:2016
(Main)Information technology — Security techniques — Cryptographic techniques based on elliptic curves — Part 1: General
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
Relations
Buy Standard
Standards Content (Sample)
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 15946-1:2016(E)
©
ISO/IEC 2016
---------------------- Page: 1 ----------------------
ISO/IEC 15946-1:2016(E)
COPYRIGHT PROTECTED DOCUMENT
© 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. +41 22 749 01 11
Fax +41 22 749 09 47
copyright@iso.org
www.iso.org
ii © ISO/IEC 2016 – All rights reserved
---------------------- Page: 2 ----------------------
ISO/IEC 15946-1:2016(E)
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
---------------------- Page: 3 ----------------------
ISO/IEC 15946-1:2016(E)
Foreword
ISO (the International Organization for Standardization) and IEC (the International Electrotechnical
Commission) form the specialized system for worldwide standardization. National bodies that are
members of ISO or IEC participate in the development of International Standards through technical
committees established by the respective organization to deal with particular fields of technical
activity. ISO and IEC technical committees collaborate in fields of mutual interest. Other international
organizations, governmental and non-governmental, in liaison with ISO and IEC, also take part in the
work. In the field of information technology, ISO and IEC have established a joint technical committee,
ISO/IEC JTC 1.
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
---------------------- Page: 4 ----------------------
ISO/IEC 15946-1:2016(E)
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
---------------------- Page: 5 ----------------------
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
---------------------- Page: 6 ----------------------
ISO/IEC 15946-1:2016(E)
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
---------------------- Page: 7 ----------------------
ISO/IEC 15946-1:2016(E)
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
---------------------- Page: 8 ----------------------
ISO/IEC 15946-1:2016(E)
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
---------------------- Page: 9 ----------------------
ISO/IEC 15946-1:2016(E)
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
---------------------- Page: 10 ----------------------
ISO/IEC 15946-1:2016(E)
— 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).
2
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)].
256
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
---------------------- Page: 11 ----------------------
ISO/IEC 15946-1:2016(E)
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
...
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
---------------------- Page: 1 ----------------------
ISO/IEC DIS 15946-1:2015(E)
COPYRIGHT PROTECTED DOCUMENT
© 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 copyright@iso.org
Web www.iso.org
Published in Switzerland
ii © ISO/IEC 2015 – All rights reserved
---------------------- Page: 2 ----------------------
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
---------------------- Page: 3 ----------------------
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
---------------------- Page: 4 ----------------------
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
---------------------- Page: 5 ----------------------
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
---------------------- Page: 6 ----------------------
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
---------------------- Page: 7 ----------------------
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
---------------------- Page: 8 ----------------------
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
---------------------- Page: 9 ----------------------
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
---------------------- Page: 10 ----------------------
ISO/IEC DIS 15946-1
m m m 2 3
E(F(p
...
Questions, Comments and Discussion
Ask us and Technical Secretary will try to provide an answer. You can facilitate discussion about the standard in here.