ISO/IEC 15946-1:2002

INTERNATIONAL ISO/IEC
STANDARD 15946-1
First edition
2002-12-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 2002
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 2002
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 2002 – All rights reserved

Contents Page
Foreword . v
Introduction. vi
1 Scope. 1
2 Normative references. 1
3 Symbols (and abbreviated terms) . 2
4 Definition of fields and curves. 2
4.1 Finite fields . 2
4.1.1 Finite prime fields. 2
m
4.1.2 Finite fields of order 2 . 3
m
4.1.3 Finite fields of F(p ) . 4
m m
4.2 Elliptic curves over F(p), F(2 ) and F(p ) . 4
4.2.1 Definition of elliptic curves over F(p). 4
m
4.2.2 Definition of elliptic curves over F(2 ). 4
m
4.2.3 Definition of elliptic curves over F(p ). 5
4.2.4 Definition of the term weak curve. 5
4.2.5 The group law on elliptic curves . 5
m
4.2.6 Negative of a Point over F(p) and F(p ) . 5
m
4.2.7 Negative of a Point on an elliptic curve over F(2 ). 5
4.2.8 Integer multiplication and the Discrete Logarithm Problem on elliptic curves. 5
4.2.9 Elliptic curve point to integer conversion . 5
5 Elliptic Curve Domain Parameters and their Validation. 6
m
5.1 Elliptic Curve Domain Parameters and their Validation Over F(p) and F(p ) . 6
m
5.1.1 Elliptic curve domain parameters over F(p) and F(p ). 6
m
5.2 Elliptic curve domain parameter validation over F(p) and F(p ) (Optional). 7
m
5.3 Elliptic Curve Domain Parameters and their Validation Over F(2 ). 7
m
5.3.1 Elliptic curve domain parameters over F(2 ) . 7
m
5.3.2 Elliptic curve domain parameter validation over F(2 ) (Optional) . 8
6 Elliptic Curve Key Pair Generation and Public Key Validation. 8
6.1 Key Generation I. 8
6.1.1 Key Generation II. 9
7 Public Key Validation (Optional). 9
Annex A (informative) Background Information on Elliptic Curves . 10
A.1 The finite prime field F(p) . 10
A.1.1 Definition of F(p). 10
A.1.2 Elliptic Curves over F(p). 11
A.1.3 The order of an elliptic curve E defined over F(p) . 13
m
A.2 The finite field F(2 ) . 13
m
A.2.1 Definition of F(2 ). 13
m
A.2.2 Elliptic Curves over F(2 ) . 14
m
A.2.3 The order of an elliptic curve E defined over F(2 ) . 16
m
A.3 The finite field F(p ) . 17
m
A.3.1 Definition of F(p ). 17
m
A.3.2 Elliptic Curves over F(p ). 18
m
A.3.3 The order of an elliptic curve E defined over F(p ) . 20
A.4 Integer multiplication on an elliptic curve . 20
A.4.1 Evaluating the integer multiplication . 20
A.5 Methods to determine discrete logarithms on elliptic curves. 21
A.5.1 The MOV Condition. 21
© ISO/IEC 2002 – All rights reserved iii

A.6 Point Compression (Optional) . 22
A.6.1 Point Compression and decompression Techniques for Elliptic Curves over F(p) (Optional). 22
m
A.6.2 Point Compression Technique for Elliptic Curves over F(2 ) (Optional) . 22
m
A.6.3 Point Compression and Decompression Techniques for Elliptic Curves over (p )(Optional) . 23
Annex B (informative) Examples . 24
B.1 Curves over Binary Fields (GF(2^m)). 24
Bibliography. 26

iv © ISO/IEC 2002 – All rights reserved

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 3.
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.
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 2: Digital signatures
 Part 3: Key establishment
 Part 4: Digital signatures giving message recovery
Annexes A and B of this part of ISO/IEC 15946 are for information only.
© ISO/IEC 2002 – All rights reserved v

Introduction
One of the most interesting alternatives to the RSA and GF(p) based systems 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 rather simple:
 Every elliptic curve is endowed with a binary operation "+" under which it forms a finite abelian group.
 The group law on elliptic curves extends in a natural way to a "discrete exponentiation" on the point group of
the elliptic curve.
 Based on the discrete exponentiation on an elliptic curve one can easily derive elliptic curve analogues of the
well known public key schemes of Diffie-Hellman and ElGamal type.
The security of such a public key system depends on the difficulty of determining discrete logarithms in the group of
points of an elliptic curve. This problem is - with current knowledge - much harder than the factorisation of integers
or the computation of discrete logarithms in a finite field. Indeed, since Miller and Koblitz in 1985 independently
suggested the use of elliptic curves for public-key cryptographic systems, no substantial progress in tackling the
elliptic curve discrete logarithm problem has been reported. In general, only algorithms which take exponential time
are known to determine elliptic curve discrete logarithms. 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 avoids the use of extra large integer arithmetic completely.
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.
It is the purpose of this document to meet the increasing interest in elliptic curve based public key technology and
describe the components that are necessary to implement a secure digital signature system based on elliptic
curves. Schemes are described for key-exchange, key-transport and digital signatures that are based on the elliptic
curve discrete logarithm problem.
The International Organization for Standardization (ISO) and International Electrotechnical Commission (IEC) draw
attention to the fact that it is claimed that compliance with this International Standard may involve the use of
patents.
ISO and IEC take no position concerning the evidence, validity and scope of these patent rights.
The holders of these patent rights have assured 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 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.din.de/ni/sc27
Attention is drawn to the possibility that some of the elements of this International Standard 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 2002 – All rights reserved

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

Information technology — Security techniques — Cryptographic
techniques based on elliptic curves —
Part 1:
General
1 Scope
International Standard ISO/IEC 15946 specifies public-key cryptographic techniques based on elliptic curves. They
include the establishment of keys for secret-key systems, and digital signature mechanisms.
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.
The scope of this standard is restricted to cryptographic techniques based on elliptic curves defined over finite
fields of prime power order (including the special cases of prime order and characteristic two). The representation
of elements of the underlying finite field (i.e. which basis is used) is outside the scope of this standard.
International Standard ISO/IEC 15946 does not specify the implementation of the techniques it defines.
Interoperability of products complying to this international standard will not be guaranteed.
2 Normative references
The following normative documents contain provisions which, through reference in this text, constitute provisions of
this part of ISO 15946. For dated references, subsequent amendments to, or revisions of, any of these publications
do not apply. However, parties to agreements based on this part of ISO 15946 are encouraged to investigate the
possibility of applying the most recent editions of the normative documents indicated below. For undated
references, the latest edition of the normative document referred to applies. Members of ISO and IEC maintain
registers of currently valid International Standards.
ISO/IEC 9796 (all parts), Information technology — Security techniques — Digital signature schemes giving
message recovery
ISO/IEC 9797 (all parts), Information technology — Security techniques — Message Authentication Codes (MACs)
ISO/IEC 10118 (all parts), Information technology — Security techniques — Hash-functions
ISO/IEC 11770-3:1999, Information technology — Security techniques — Key management — Part 3: Mechanisms
using asymmetric techniques
ISO/IEC 14888 (all parts), Information technology — Security techniques — Digital signatures with appendix
ISO/IEC 15946-2:2002, Information technology — Security techniques — Cryptographic techniques based on
elliptic curves — Part 2: Digital signatures
ISO/IEC 15946-3:2002, Information technology — Security techniques — Cryptographic techniques based on
elliptic curves — Part 3: Key establishment
ISO/IEC 15946-4, Information technology — Security techniques — Cryptographic techniques based on elliptic
curves — Part 4: Digital signatures giving message recovery (to be published)
© ISO/IEC 2002 – All rights reserved 1

3 Symbols (and abbreviated terms)
In the remainder of this document the following notation will be used to describe public key systems based on
elliptic curve technology:
p A prime number not equal to 3.
NOTE p=3 is not part of this standard for simplicity and not because of security reasons.
F(p) The finite prime field consisting of exactly p elements.

m m
F(2 ) The finite field consisting of exactly 2 elements.
m m
F(p ) The finite field consisting of exactly p elements.
m
2 3
E An elliptic curve, either given by an equation of the form Y = X + aX + b over the field F(p ) for p>3 or by an
m
2 3 2
equation of the form Y + XY = X + aX + b over the field F(2 ), together with an extra point 0 refered to as the
E
point of infinity.
#(E) The order (or cardinality) of E.
m
q A prime power, p for some integer m ≥ 1.
n A prime divisor of #(E).
Q A point on E.
x The x-coordinate of Q.
Q
y The y-coordinate of Q.
Q
Q +Q The elliptic curve sum of two points Q and Q .
1 2
1 2
kQ The k-th multiple of some point Q of E, i.e. Q+Q+ …+Q, k summands, with 0Q = 0 and (–k)Q = k(-Q).
E
G A point on E generating a cyclic group of cardinality n.
A, B Two entities making use of the public key system.
d The private key of entity A. (In all schemes d is a random integer in the set {1,…,n-1}.)
A A
P The public key of entity A. (In all schemes P is an elliptic curve point.)
A A
π(Q) The integer obtained from the point Q by the conversion π.
0 The point at infinity.
E
4 Definition of fields and curves
4.1 Finite fields
4.1.1 Finite prime fields
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).
2 © ISO/IEC 2002 – All rights reserved

The elements of a finite prime field F(p) may be identified with the set {0, 1, 2, ., 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:
(i) F(p) is an abelian group with respect to the addition operation “+”.
(ii) F(p)\{0} denoted as F(p)* is an abelian group with respect to the multiplication operation “⋅”.
The two group operations involved are introduced as follows:
Addition “⊕”: 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.
Multiplication “⊗”: 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.
If there is no confusion to be expected with the ordinary addition and multiplication the symbols “+” and “⋅” are used
instead of “⊕” and “⊗”.
See A.1.1. for additional information.
m
4.1.2 Finite fields of order 2
m
For any integer m ≥ 1 there exists a finite field of exactly 2 elements. This field is unique up to isomorphism and in
m
this document it is referred to as the finite field F(2 ).
m
The elements of a finite field F(2 ) may be identified with the set of bit strings of length m in the following way.
m m m
Every finite field F(2 ) contains at least one basis {β ,β ,., β } over F(2 ) such that every element α ∈ F(2 )
1 2 m
has a unique representation of the form α = b β + b β +" + b β , with b ∈ {0,1} for i = 1,2,.,m . The
1 1 2 2 m m i
element α can then be identified with the bit string (b b "b ). The choice of basis is beyond the scope of this
1 2 m
m
document. Detailed information can be found in [1] and [3]. F(2 ) is endowed with two operations called addition
and multiplication such that the following conditions hold:
m
(i) F(2 ) is an abelian group with respect to the addition operation “⊕”.
m m
(ii) F(2 )\{0} denoted as F(2 )* is an abelian group with respect to the multiplication operation “⊗”.
The two group operations involved are introduced as follows:
m m
Addition “⊕”: For a, b ∈ F(2 ) the sum a ⊕ b is given as a ⊕ b := r, where r ∈ F(2 ) is the bit string obtained
by XORing the bit strings a and b.
m
Multiplication “⊗”: For a, b ∈ F(2 ) the product a ⊗ b will be a bit string of length m. For each 1,≤ i, j ≤ m β β is
i j
m m m m
an element of the field. Thus, if a = a β and b = b β then a ⊗ b = a b β β by
∑ i i ∑ j j ∑∑ i j i j
i =1 j =1 i==11j
using β β in their base representation.
i j
Again, if there is no confusion to be expected with the ordinary addition and multiplication the symbols “+” and “⋅”
are used instead of “⊕” and “⊗”.
NOTE The finite fields used in this paragraph are considered as an ordered set of elements. Otherwise no conversion of
curve-points would be possible in a consistent manner.
© ISO/IEC 2002 – All rights reserved 3

m
4.1.3 Finite fields of F(p )
m
For any positive integer m and a prime p, there exists a finite field of exactly p elements. This field is unique up to
m
isomorphism and in this document it is referred to as the finite field F(p ).
m m
NOTE F(p ) is the more general definition including F(p)for m = 1 and F(2 ) for p = 2.
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 field
m m m
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
(i) F (p ) is an abelian group with respect to the addition operation “⊕”.
m m *
(ii) F (p )\{0}, denoted by F (p ) , is an abelian group with respect to the multiplication operation “⊗”.
The two group operations involved are introduced as follows:
m m
Addition "⊕": For a, b ∈ F (p ) the sum a ⊕ b is given as a ⊕ b := r , where r ∈ F (p ) is a p-ary string. If a
m m m
= a β , b = b β , then a ⊕ b =()a + b mod p β .
∑ i i ∑ i i ∑ i i i
i =1 i =1 i =1
m
Multiplication "⊗": For a, b ∈ F(p ) the product a ⊗ b will be a p-ary string of length m. For each 1≤i, j≤m, β β is an
i j
m m m m
element of the field. Thus, if a = a β , b = b β , then a ⊗ b = a b β β , by using
∑ i i ∑ i i ∑∑ i j i j
i =1 i =1 i==11j
β β in their basis representation.
i j
Again, if there is no confusion to be expected with the ordinary addition and multiplication the symbols “+” and “⋅”
are used instead of “⊕” and “⊗”.
NOTE The finite fields used in this paragraph are considered as an ordered set of elements. Otherwise no conversion of
curve-points would be possible in a consistent manner.
m m
4.2 Elliptic curves over F(p), F(2 ) and F(p )
4.2.1 Definition of elliptic curves over F(p)
Let F(p) be a finite prime field with p > 3. An elliptic curve E over F(p) is a curve given by a non-singular cubic

equation over F(p) . In this document it is assumed that E is described by a “short Weierstrass equation”, that is an
equation of type
2 3
(1) Y = X + aX + b with a, b ∈ F(p)
3 2
such that the inequality (4a + 27b ) ≠ 0 holds in F(p).
An elliptic curve E over F(p) given by an equation of type (1) consists of the set of points Q = (x ,y ) ∈ F(p) × F(p)
Q Q
2 3
such that the equation y = x + ax + b holds, together with an extra point 0 referred to as the point at infinity of
Q Q Q E
E. 0 is not contained in F(p) × F(p) and does not solve the defining equation of (1).
E
m
4.2.2 Definition of elliptic curves over F(2 )
m m
Let F(2 ), for some m ≥ 1, be a finite field. An ordinary elliptic curve E over F(2 ) is a curve given by an equation of
type
4 © ISO/IEC 2002 – All rights reserved

m
2 3 2
(2) Y + XY = X + aX + b with a, b ∈ F(2 ).
m
such that b ≠ 0 holds in F(2 ).
NOTE For cryptographic use, m should be a prime to prevent certain kinds of attacks on the cryptosystem.
m m
An elliptic curve E over F(2 ) given by an equation of type (2) consists of the set of points Q = (x ,y ) ∈ F(2 ) ×
Q Q
m
2 3 2
F(2 ) such that the equation y + x y = x + ax + b holds, together with an extra point 0 , the point at infinity
Q Q Q Q Q E
m m
of E. 0 is not contained in F(2 ) × F(2 ) and does not solve the defining equation of (2).
E
m
4.2.3 Definition of elliptic curves over F(p )
m m
Let F(p ) be a finite field with a prime p > 3 and a positive integer m. An elliptic curve over F(p ) is a curve given by
m
a non-singular cubic equation over F(p ). In this document it is assumed that E is described by a “short Weierstrass
equation”, that is an equation of type
m
2 3
(3) Y = X + aX + b with a, b ∈ F(p ).
3 2 m
such that (4a + 27b ) ≠ 0 holds in F(p ).
m m
An elliptic curve E over F(p ) given by an equation of type (3) consists of the set of points Q = (x ,y ) ∈ F(p ) ×
Q Q
m 2 3
F(p ) such that the equation y = x + ax + b holds, together with an extra point 0 referred to as the point at
Q Q Q E
m m
infinity of E. 0 is not contained in F(p ) × F(p ) and does not solve the defining equation of (3).
E
m m
F(p ) is the more general definition including F(p), i.e. F(p ) for m = 1.
4.2.4 Definition of the term weak curve
A curve is considered weak if, due to its inherent structure and characteristics, it can be attacked with a much
smaller complexity than one would expect from the size of its parameters. Supersingular and anomalous curves fall
into this category (see A.1.3).
4.2.5 The group law on elliptic curves
Elliptic curves are endowed with a binary operation +: E × E → E, defining for each pair (Q , Q ) of points on E a
1 2
third point Q + Q . With respect to this operation E is an abelian group with identity element 0 . Formulae to
1 2 E
compute the sum Q + Q are given in Annex A.1.2, A.2.2 and A.3.2.
1 2
m
4.2.6 Negative of a Point over F(p) and F(p )
The negative of a point P=(x,y) is defined as –P=-(x,y)=(x,-y) defined over F(p), p>3.
m
4.2.7 Negative of a Point on an elliptic curve over F(2 )
m
The negative of a Point P=(x,y) is –P=(x,x+y) defined over F(2 ).
4.2.8 Integer multiplication and the Discrete Logarithm Problem on elliptic curves
Let G be a point on an elliptic curve E generating a cyclic group of finite cardinality n with respect to the group
operation “+”. Therefore each element of is some multiple kG of G, where kG is an abbreviation for
(G + G + . + G), k summands, with 0G = 0 (the point at infinity) and (–k)G = k(-G).
E
4.2.9 Elliptic curve point to integer conversion
Let Q = (x , y ) be a point on an elliptic curve E. The following conversion π(Q) converts the point Q to an integer.
Q Q
© ISO/IEC 2002 – All rights reserved 5

(i) If E is defined over F(p) then π(Q) = x .
Q
m
(ii) If E is defined over F(2 ) then x is a bit string of length m. Let s s …s be the bit string x . Then:
Q m-1 m-2 0 Q
m−1
i
π(Q) = 2 s
i
∑
i =0
m
(iii) If E is defined over F(p ) then x is a p-ary string of length m. Let x = (s s ⋅⋅⋅ s s ) be the p-ary string of
Q Q m-1 m-2 1 0
length m defined over F(p). Then:
m−1
i
π(Q) = p s
i
∑
i =0
NOTE This conversion does not define a 1-1 mapping. For example, this conversion will associate the elliptic curve points
Q and –Q with the same integer.
5 Elliptic Curve Domain Parameters and their Validation
This section describes the elliptic curve domain parameters and how they may be validated. A specific set of
domain parameters may be agreed upon by the parties involved to be used only for one purpose (e.g. ECDSA) or
for multiple purposes (eg. ECDSA as defined in Part 2 of the Standard and ECMQV as defined in Part 3 of the
Standard).
If a candidate set of domain parameters are invalid, then all assumptions about security should be assumed to be
void, including the intended security of any cryptographic operations and the privacy of the private key. Therefore
before using a candidate set of domain parameters, a user should have assurance that they are valid. This
assurance might be achieved because:
A. The domain parameters were generated by the user or for the user by a Trusted Third Party.
B. The domain parameters were explicitly validated by the user or a Trusted Third Party.
m
5.1 Elliptic Curve Domain Parameters and their Validation Over F(p) and F(p )
m
5.1.1 Elliptic curve domain parameters over F(p) and F(p )
m
Elliptic curve parameters over F(p ) (including the special case F(p) where m=1) shall consist of the following
parameters:
NOTE There must be an agreement on the choice of the basis between the communicating parties!
m m
1. A field size p which defines the underlying finite field F(p ), where p > 3 shall be a prime number and
an indication of the basis used to represent the elements of the field in case m>1.
2. (Optional) A bit string SEED if the elliptic curve was randomly generated. See [1] for an example of
how to generate an elliptic curve verifiably at random using an initial seed.
m 2 3
3. Two field elements a and b in F(p ) which define the equation of the elliptic curve E: y = x + ax+ b.
m
4. Two field elements x and y in F(p ) which define a point G = (x , y ) of prime order on E.
G G G G
m
5. The order n of the point G with n > 4 p .
m
6. The cofactor h = #E(F(p ))/n (when required by the underlying scheme)
6 © ISO/IEC 2002 – All rights reserved

7. The curve must not be member of the exclude list.
m
5.2 Elliptic curve domain parameter validation over F(p) and F(p ) (Optional)
The following conditions may be verified by a user of the elliptic curve parameters.
m
1. Verify that p is an odd prime power.
2. Verify that a, b, x and y are elements of the underlying field.
G G
3. If the elliptic curve was randomly generated, verify that a and b were suitably derived from SEED.
3 2
m
4. Verify that (4a + 27b ) is not equal 0 in F(p ).
m
2 3
5. Verify that y = x + ax + b in F(p ).
G G G
m
6. Verify that n is prime and that n > 4 ⋅ p
NOTE n is the primary security parameter. Specific bounds are given at the descriptions of the algorithms.
7. Verify that nG = 0 .
E
m 2
 
8. Compute h' = ( p + 1) / n and verify that h = h'
 
 
9. Check the list to exclude known weak curves
• Verify that the MOV condition holds, see Annex A.5.1 which excludes supersingular curves.
m
• Verify that the curve is not anomalous, that is, that #E≠p .
If any of the above verifications fail then the domain parameters should be considered invalid.
NOTE The class number is an important security parameter and should be chosen to be large enough. This does not apply
for randomly generated curves since the class number of this curves is always large.
m
5.3 Elliptic Curve Domain Parameters and their Validation Over F(2 )
m
5.3.1 Elliptic curve domain parameters over F(2 )
m
Elliptic curve parameters over F(2 ) shall consist of the following parameters:
m m
1. A field size q = 2 which defines the underlying finite field F(2 ) and an indication of the basis used
to represent the elements of the field.
2. (Optional) A bit string SEED if the elliptic curve was randomly generated.
m 2 3
3. Two field elements a and b in F(2 ) which define the equation of the elliptic curve E: y + xy = x +
ax + b.
m
4. Two field elements x and y in F(2 ) which define a point G = (x ,y ) of prime order on E.
G G G G
m
5. The order n of the point G with n > 4 2
m
6. Optionally, the cofactor h = #E(F(2 ))/n (When required by the underlying scheme).
© ISO/IEC 2002 – All rights reserved 7

m
5.3.2 Elliptic curve domain parameter validation over F(2 ) (Optional)
The following conditions may be verified by a user of the elliptic curve parameters.
m
1. Verify that q = 2 for some m.
2. Verify that a, b, x and y are bit strings of length m bits.
G G
3. If the elliptic curve was randomly generated, verify that a and b were suitably derived from SEED.
4. Verify that b ≠ 0.
m
2 3 2
5. Verify that y + x y = x + ax + b in F(2 ).
G G G G G
m
6. Verify that n is prime, and n > 4 2 .
NOTE n is the primary security parameter. Specific bounds are given at the descriptions of the algorithms.
7. Verify that nG = 0 .
E
m 2
 
8. Compute h' = ( 2 + 1) / n and verify that h = h'.
 
 
9. Check list to exclude known weak curves
• Verify that the MOV condition holds, see Annex A.5.1 which excludes supersingular curves.
m
• Verify that the curve is not anomalous, that is, that #E≠2 .
If any of the above verifications fails then the domain parameters should be considered invalid.
NOTE The class number is an important security parameter and should be chosen large enough. This does not apply for
randomly generated curves since the class number of this curves is always large.
6 Elliptic Curve Key Pair Generation and Public Key Validation
In this section a description of two methods to generate a private key, public key pair and validate a public key for a
valid set of elliptic curve domain parameters is given. Other, equivalent methods are also allowed by this standard.
6.1 Key Generation I
Given a valid set of elliptic curve domain parameters a private key and corresponding public key may be generated
as follows.
1. Select a random or pseudorandom integer d in the set [1, n-1]. The integer d must be protected from
unauthorised disclosure and be unpredictable.
NOTE It is allowed to exclude a few values, such as 1 or n-1.
2. Compute the point Q = (x , y ) = dG.
Q Q
3. The key pair is (Q, d ), where Q will be used as public key, and d is the private key.
8 © ISO/IEC 2002 – All rights reserved

6.1.1 Key Generation II
Given a valid set of elliptic curve domain parameters a private key and corresponding public key may be generated
as follows.
1. Select a random or pseudorandom integer e in the set [1, n-1] and compute an integer d in the interval
[1, n-1] with the property de≡1 mod n. The integers d and e must be protected from unauthorised
disclosure and be unpredictable.
NOTE It is allowed to exclude a few values, such as 1 or n-1.
2. Compute the point Q = (x , y ) = eG.
Q Q
3. The key pair is (Q, d), where Q will be used as public key, and d is the private key.
7 Public Key Validation (Optional)
Given a valid set of elliptic curve parameters and an associated claimed public key Q which has a value, a certain
range and a certain order, the public key may be validated as follows:
1. Verify that Q is not the point at infinity 0 .
E
2. Verify that x and y are elements in the field F(q), where x and y are the x and y coordinates of Q,
Q Q Q Q
respectively.
m m m
2 3
3. If q = p is an odd prime power, verify that y = x + ax + b in F(p ). If q = 2 , verify that
Q Q Q
m
2 3 2
y + x y = x + ax + b in F(2 ).
Q Q Q Q Q
4. Verify that nQ = 0 .
E
If any of the above verifications fail then the public key should be considered invalid.
If a candidate public key is invalid, then all assumptions about security should be assumed to be void, including the
intended security of any cryptographic operation and the privacy of the associated private key. In addition, use of
an invalid public key in a cryptographic operation, for example in key establishment, with your private key may leak
information about your private key. Therefore, before using a candidate public key, a user should have assurance
that it is valid. This might be addressed because:
A. The public key was explicitly validated by the user.
B. The public key was explicitly validated by a TTP for the user.
C. The user accepts the risk of using an unvalidated public key. This should include an analysis that indicates the
potential of security is limited in the particular application. Such acceptance of risk may be more appropriate for
an ephemeral public key than a long term public key. Note that performing EC public key validation is a safe
default, since there are no potential negative security consequences of doing it.
Further a non verified public key can be used under the conditions that the key was generated or explicitly
validated by an entity trusted by the user for the lifetime of the key.
NOTE Public Key Validation does not provide assurance that the claimed owner of a private key is the genuine owner of
the key.
© ISO/IEC 2002 – All rights reserved 9

Annex A
(informative)
Background Information on Elliptic Curves
It is the purpose of this annex to present the mathematical ingredients that are necessary to implement the elliptic
curve based public key schemes mentioned in this standard.
A.1 The finite prime field F(p)
A.1.1 Definition of F(p)
It is assumed that the reader is familiar with ordinary modular arithmetic. As mentioned in clause 4, 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 objects of F(p) are identified with the set {0, 1, 2,
..., p - 1} of all non-negative integers less than p. F(p) is endowed with two basic operations, modular addition “+”
and modular multiplication “⋅” such that:
(i) F(p) is an abelian group with respect to modular addition “+”.

(ii) F(p) \{0} is an abelian group with respect to modular multiplication “⋅”.
As usual, the set F(p) \{0} is denoted by F(p)*. This is a cyclic group of order p-1. Hence, there exists at least one
j
element γ in F(p)* such that every element a in F(p)* can be uniquely written as a = γ , for some j ∈ {0,., p-2}.
Inverting elements of F(p)*
j
Let a = γ be an element of F(p)*. Then there exists the unique b ∈ F(p)* such that a⋅b = b⋅a = 1, and b is called
-1 -1 p-1-j
the multiplicative inverse of a, denoted by a , which can be computed by a = γ .
Characteristic of a finite field
If c additions of the unit element are required to reach the zero element, than c is called the characteristic of a field.
If the zero element cannot be reached through addition of unit elements, c is not infinite but zero.
Division in F(p)
-1
The value b/a in F(p) exists if the denominator a is non-zero. In this case, the quotient is b/a = b⋅(a ).

Squares and non-squares in F(p)
Assume p > 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 .
Whether a ∈ F(p)* is a square or not can be determined by making use of the equivalence:
(p-1)/2
a is a square in F(p)* ⇔ a = 1.
Finding square-roots in F(p)
There are various methods for finding square roots in F(p). That is, given a ∈ F(p)* where a is a square finding b ∈
F(p)* such that a = b . An example of such methods can be found in [1] and [3].
10 © ISO/IEC 2002 – All rights reserved

A.1.2 Elliptic Curves over F(p)
In this clause, two different but equivalent descriptions of elliptic curves defined over finite prime fields are given.
A.1.2.1 Affine Description
Let F(p) be a finite prime field with p > 3. An elliptic curve E over F(p) is given by a non-singular cubic equation over
F(p) In this document it is assumed that E is described by a “short Weierstrass equation”, that is an equation of
.
type
2 3
(Aff)   Y = X + aX+ b   with a, b ∈ F(p)
.
3 2
such that the inequality (4a + 27b ) ≠ 0 holds in F(p). (More exactly, (Aff) is called an affine Weierstrass equation.)
An elliptic curve E over F(p) given by an equation of type (Aff) consists of the set of points Q = (x ,y )∈ F(p) × F(p)
Q Q
2 3
such that the equation y = x + a x + b holds, together with an extra point 0 referred to as the point at infinity
Q Q Q E
of E.
0 is not contained in F(p) × F(p) and does not solve the defining equation (Aff). The set of points on E of type (x ,
E Q
y ) ∈ F(p) × F(p) is called the affine part of E.
Q
A.1.2.1.1 The group law in affine description
An elliptic curve E over F(p) is endowed with a binary operation “+” : E × E → E assigning to any two points Q , Q
1 2
on E a third point Q + Q on E. The elliptic curve E is an abelian group with respect to “+” possessing the following
1 2
properties:
1) The point at infinity 0 is the identity element for the group operation on E:
E
0 + Q = Q + 0 = Q, for all points Q on E.
E E
2) If Q = (x,y) is an affine point of E then the inverse point −Q has the co-ordinates (x, −y) and Q + (−Q) = 0 .
E
If Q = (x , y ) and Q = (x , y ) are affine points of E, where Q ≠ −Q , then the co-ordinates x and y of the “sum”
1 2 1 2
1 1 2 2 3 3
Q = Q + Q are given by the following formulae:
3 1 2
x = r − x −x
3 1 2
.
y = r (x −x ) −y
3 1 3
where either r = (y − y )/(x − x ), if Q ≠ Q
2 1 2 1 1 2
or r = (3x + a)/(2y ),  if Q = Q
1 1 1 2
Note the difference in the formulae for doubling a point and for adding two distinct points.
It is evident that in the affine description of the elliptic curve group law given above, the point at infinity - introduced
only as a formal symbol - plays a rather obscure role that is not easily understood. The major drawback of the
affine description is that it makes heavy use of divisions in F(p). In most implementations of finite prime field
arithmetic the 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 the projective description of the elliptic curve group
law. Both descriptions of elliptic curves are
...