ISO/IEC 15946-1:2008

INTERNATIONAL ISO/IEC
STANDARD 15946-1
Second edition
2008-04-15
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 2008
PDF disclaimer
This PDF file may contain embedded typefaces. In accordance with Adobe's licensing policy, this file may be printed or viewed but
shall not be edited unless the typefaces which are embedded are licensed to and installed on the computer performing the editing. In
downloading this file, parties accept therein the responsibility of not infringing Adobe's licensing policy. The ISO Central Secretariat
accepts no liability in this area.
Adobe is a trademark of Adobe Systems Incorporated.
Details of the software products used to create this PDF file can be found in the General Info relative to the file; the PDF-creation
parameters were optimized for printing. Every care has been taken to ensure that the file is suitable for use by ISO member bodies. In
the unlikely event that a problem relating to it is found, please inform the Central Secretariat at the address given below.

©  ISO/IEC 2008
All rights reserved. Unless otherwise specified, no part of this publication may be reproduced or utilized in any form or by any means,
electronic or mechanical, including photocopying and microfilm, without permission in writing from either ISO at the address below or
ISO's member body in the country of the requester.
ISO copyright office
Case postale 56 • CH-1211 Geneva 20
Tel. + 41 22 749 01 11
Fax + 41 22 749 09 47
E-mail copyright@iso.org
Web www.iso.org
Published in Switzerland
ii © ISO/IEC 2008 – All rights reserved

Contents Page
Foreword. iv
Introduction . v
1 Scope .1
2 Terms and definitions.1
3 Symbols .2
4 Conventions of fields .3
4.1 Finite prime fields F(p).3
m
4.2 Finite fields F(p ).3
5 Conventions of elliptic curves.4
5.1 Definition of elliptic curves.4
5.2 The group law on elliptic curves.5
5.3 Cryptographic bilinear map .5
6 Conversion functions.5
6.1 Octet string / bit string conversion: OS2BSP and BS2OSP.5
6.2 Bit string / integer conversion: BS2IP and I2BSP.5
6.3 Octet string / integer conversion: OS2IP and I2OSP .6
6.4 Finite field element / integer conversion: FE2IP .6
F
6.5 Octet string / finite field element conversion: OS2FEP and FE2OSP .6
F F
6.6 Elliptic curve point / octet string conversion: EC2OSP and OS2ECP .7
E E
6.7 Integer / elliptic curve conversion: I2ECP .8
7 Elliptic curve domain parameters and public key .8
7.1 Elliptic curve domain parameters over F(q) .8
7.2 Elliptic curve key generation .9
Annex A (informative) Background information on finite fields .10
A.1 Bit strings .10
A.2 Octet strings.10
A.3 The finite field F(q).10
Annex B (informative) Background information on elliptic curves.12
B.1 Properties of elliptic curves.12
B.2 The group law for elliptic curves E over F(q) with p > 3.12
m
B.3 The group law for elliptic curves over F(2 ) .16
m
B.4 The group law for elliptic curves over F(3 ) .17
B.5 The existence condition of an elliptic curve E.19
Annex C (informative) Background information on elliptic curve cryptosystems.21
C.1 Definition of cryptographic problems.21
C.2 Algorithms to determine discrete logarithms on elliptic curves.21
C.3 Scalar multiplication algorithms of elliptic curve points.22
C.4 Algorithms to compute pairings.24
C.5 Elliptic curve domain parameters and public key validation (optional).25
Bibliography .30

© ISO/IEC 2008 – 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.
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, IT Security techniques.
This second edition cancels and replaces the first edition (ISO/IEC 15946-1:2002), 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 3: Key establishment
Elliptic curve generation will form the subject of a future Part 5.
iv © ISO/IEC 2008 – All rights reserved

Introduction
One of the most interesting alternatives to the RSA and F(p) based cryptosystems that are currently available
are cryptosystems based on elliptic curves defined over finite fields. 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 any of the mechanisms described in other parts of ISO/IEC 15946 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 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 licences
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:
ISO/IEC JTC 1/SC 27 Standing Document 8 (SD 8) “Patent Information”

SD 8 is publicly available at: http://www.ni.din.de/sc27

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.
© ISO/IEC 2008 – All rights reserved v

INTERNATIONAL STANDARD ISO/IEC 15946-1:2008(E)

Information technology — Security techniques — Cryptographic
techniques based on elliptic curves —
Part 1:
General
1 Scope
ISO/IEC 15946 specifies public-key cryptographic techniques based on elliptic curves. These include the
establishment of keys for secret-key systems, and digital signature mechanisms.
This part of ISO/IEC 15946 describes the mathematical background and general techniques necessary for
implementing any of the mechanisms described in other parts of ISO/IEC 15946 and other ISO/IEC standards.
The scope of this part of ISO/IEC 15946 is restricted to cryptographic techniques based on elliptic curves
defined over finite fields of prime power order (including the special cases of prime order and characteristic
two). The representation of elements of the underlying finite field when the field is not of prime order (i.e. which
basis is used) is outside the scope of this part of ISO/IEC 15946.
ISO/IEC 15946 does not specify the implementation of the techniques it defines. Interoperability of products
complying with this part of ISO/IEC 15946 will not be guaranteed.
2 Terms and definitions
For the purposes of this document, the following terms and definitions apply.
2.1
finite field
any field containing a finite number of elements
m
NOTE For any positive integer m and a prime p, there exists a finite field containing exactly p elements. This field is
m m
unique up to isomorphism and is denoted by F(p ), where p is called the characteristic of F(p ).
2.2
elliptic curve
any cubic curve E without any singular point
NOTE The set of points of E is 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.
2.3
cryptographic bilinear map
cryptographic bilinear map e satisfying the non-degeneracy, bilinearity, and computability
n
© ISO/IEC 2008 – All rights reserved 1

3 Symbols
In this document, the following notation is used to describe public-key systems based on elliptic curve
technology.
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
|F | The bit size of a finite field 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 order n.
The group generated by G with cardinality n.
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-coordinates of Q ≠ O .
Q
E
y
The y-coordinates 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
NOTE Oct(m) and L(m) are defined in Clauses 6.2 and 6.3, respectively.
2 © ISO/IEC 2008 – All rights reserved

4 Conventions of fields
4.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 “+”.
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
4.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 cause
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
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 [7].
© ISO/IEC 2008 – All rights reserved 3

5 Conventions of elliptic curves
5.1 Definition of elliptic curves
m
5.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
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
5.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
5.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
4 © ISO/IEC 2008 – All rights reserved

5.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 on
1 2
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.
5.3 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 Tate
n
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
⎯ Computabilty : 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
6 Conversion functions
6.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 (in the natural way)
and outputs the bit string y.
⎯ 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 strings is {0, 1} .
6.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
© ISO/IEC 2008 – All rights reserved 5

⎯ 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.
6.3 Octet string / integer 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 0e in its hexadecimal format.
NOTE 3 The length in octets of a non-negative integer m is denoted by L(m).
6.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
∑
6.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
6 © ISO/IEC 2008 – All rights reserved

6.6 Elliptic curve point / octet string conversion: EC2OSP and OS2ECP
E E
6.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
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.
6.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 ỹ.
6.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
© ISO/IEC 2008 – All rights reserved 7

⎯ 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.
⎯ 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.
6.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.
7 Elliptic curve domain parameters and public key
7.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 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.
8 © ISO/IEC 2008 – All rights reserved

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 [7].
7.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.
© ISO/IEC 2008 – All rights reserved 9

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 , . . . , x 〉 of bits x , . . . , x . The length of
l−1 0 0 l−1
n
a bit string x is the number l of bits in the string x. Given a non-negative integer n, {0, 1} denotes the set of bit
n
*
strings of length n. {0, 1} = ∪ {0, 1} denotes the set of bit strings, including the null string (whose length
n ≥ 0
is 0).
A.2 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.
A.3 The finite field F(q)
m
It is assumed that the reader is familiar with ordinary field arithmetic. For any prime power, q=p with some
integer m ≥ 1, there exists a finite field consisting of exactly q elements. This field is uniquely determined up to
isomorphism and in this document it is referred to as the finite field F(q). F(q) is endowed with two basic
operations, addition “+” and multiplication “·” such that
⎯ F(q) is an abelian group with respect to addition “+”,

⎯ F(q) \{0 } is an abelian group with respect to multiplication “·”.
F
NOTE 1 If m = 1, then the addition and multiplication coincide with modular addition and multiplication mod p.
The set F(q) \{0 } is denoted by F(q)*. This is a cyclic group of order q-1 under multiplication. Hence, there
F
i
exists at least one element γ in F(q)* such that every element a in F(q)* can be uniquely written as a = γ , for
some i ∈ {0,., q-2}.
Characteristic of a finite field
The characteristic of a field is the smallest positive integer c such that c additions of 1 give the zero element.
F
m
If no such c exist, the characteristic is 0. For any prime p, the characteristic of the field F(p ) is p.
Inverting elements of F(q)*
Let a be an element of F(q)*. Then there exists a unique element b ∈ F(q)* such that a·b = b·a = 1 , and b is
F
-1 i -1 -1 q-1-i
called the multiplicative inverse of a, denoted by a . If a = γ , then a can be computed as a = γ .
-1
NOTE 2 If m = 1, a is given as x in the equation of ax + py = 1, which can be solved using the extended Euclidean
algorithm.
10 © ISO/IEC 2008 – All rights reserved

Squares and non-squares in F(q)
Assume the characteristic of F(q) > 2. An element a ∈ F(q)* is called a square in F(q)* if there exists an
element b ∈ F(q)* such that a = b . Whether a ∈ F(q)* is a square or not can be determined by making use of
the equivalence:
(
q-1)/2
a is a square in F(q)* ⇔ a = 1 .
F
Finding square-roots in F(q)
Assume the characteristic of F(q) > 2. There are various methods for finding square roots in F(q). That is,
given a ∈ F(q)* where a is a square, find b ∈ F(q)* such that a = b .
(q + 1)/4
NOTE 3 If q = 3(mod 4), then the square-root can be computed as b = a . The other cases are described in [7].
© ISO/IEC 2008 – All rights reserved 11

Annex B
(informative)
Background information on elliptic curves
It is the purpose of this annex to present the information on elliptic curves that is necessary for the elliptic
curve based public key schemes.
B.1 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 “+”.
2 1 2
The number of points of E (including O ) is called the order (or cardinality) of E and is denoted by #E(F(q)). The
E
order satisfies the following theorem of Hasse.
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.
Clause B.5 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
m m
over F(q) with #E(F(q)) = p where q=p is called anomalous. Supersingular curves are subject to the Frey-
Rück [10] and Menezes-Okamoto-Vanstone [12] algorithms. Anomalous curves are vulnerable to attacks using
the Araki-Satoh [13], Smart [15] and Semaev [14] algorithms.
B.2 The group law for elliptic curves E over F(q) with p > 3
B.2.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.
B.2.2 The 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). (More precisely, (Aff) is called the affine Weierstrass
F
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
12 © ISO/IEC 2008 – All rights reserved

⎯ Let R = (x , y ) and R = (x , y ) be two distinct points on E such that R ≠ ± R and R , R ≠ O . The sum is
1 1 1 2 2 2 1 2 1 2 E
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.2.3 The group law in projective coordinates
NOTE 1 Using projective coordinates will result in more multiplications during the calculation of the group 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 (X, Y, Z)
proj
∈ F(q) × F(q) × F(q) \ {(0 , 0 , 0 )}, where two triplets (X, Y, Z), (X', Y', Z') ∈ F(q) × F(q) × F(q) \ {(0 , 0 , 0 )} are
F F F F F F
said to be equivalent if there exists λ ∈ F(q)* such that (X', Y', Z') = (λX, λY, λZ). The projective analogue of the
short affine Weierstrass equation (Aff) is defined over Π (F(q)) and given by the homogeneous cubic
proj
equation,
2 3 2 3
(Proj) Y Z = X + aXZ + bZ with a, b ∈ F(q).
NOTE 3 The set of all triplets equivalent to (X, Y, Z) is denoted by (X, Y, Z)/~.
The elliptic curve given in projective coordinates consists of all points R = (X, Y, Z) of F(q) × F(q) × F(q) \ {(0 ,
F
0 , 0 )} such that the triple (X, Y, Z) is a solution of the equation (Proj), where by an abuse of notation we
F F
identify (X, Y, Z) with the equivalence class (X, Y, Z)/~ containing (X, Y, Z). There is a relation between the
points Q of E when the curve is given in affine coordinates and the points R in projective coordinates. Indeed,
the following holds:
⎯ If Q = (X , Y ) is an affine point of E, then R = (X , Y , 1 ) is the corresponding point in projective
Q Q Q Q F
coordinates.
⎯ If R = (X, Y, Z) (with Z ≠ 0 ) is a solution of (Proj) then Q = (X/Z, Y/Z) is the corresponding affine point of E.
F
⎯ There is only one solution of (Proj) with Z = 0, namely the point (0 , 1 , 0 ). This point corresponds to O .
F F F E
In projective coordinates the group law on an elliptic curve given by (Proj) reads as follows:
⎯ The point (0 , 1 , 0 ) is the identity element O with respect to “+”.
F F F E
⎯ Let R = (X, Y, Z) ≠ (0 , 1 , 0 ) be a point on E given in projective coordinates. Then - R = (X, - Y, Z) .
F F F
© ISO/IEC 2008 – All rights reserved 13

⎯ Let R = (X , Y , Z ) and R = (X , Y , Z ) be two distinct points on E such that R ≠ R and R , R ≠ (0 , 1 ,
1 1 1 1 2 2 2 2 1 2 1 2 F F
0 ) and denote the sum by R = (X , Y , Z ). The coordinates X , Y and Z can be computed using the
F 3 3 3 3 3 3 3
following formulae:
X = - su,
2 3
Y = t ( u + s X Z ) - s Y Z ,
3 1 2 1 2
Z = s Z Z ,
3 1 2
2 2
with s = X Z - X Z , t = Y Z - Y Z , and u = s
...