ISO/IEC 15946-1:2002
(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
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
Standards Content (Sample)
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 15946-1:2002(E)
©
ISO/IEC 2002
---------------------- Page: 1 ----------------------
ISO/IEC 15946-1:2002(E)
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
---------------------- Page: 2 ----------------------
ISO/IEC 15946-1:2002(E)
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
---------------------- Page: 3 ----------------------
ISO/IEC 15946-1:2002(E)
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
---------------------- Page: 4 ----------------------
ISO/IEC 15946-1:2002(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.
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
---------------------- Page: 5 ----------------------
ISO/IEC 15946-1:2002(E)
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
---------------------- Page: 6 ----------------------
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
---------------------- Page: 7 ----------------------
ISO/IEC 15946-1:2002(E)
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
---------------------- Page: 8 ----------------------
ISO/IEC 15946-1:2002(E)
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
---------------------- Page: 9 ----------------------
ISO/IEC 15946-1:2002(E)
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
---------------------- Page: 10 ----------------------
ISO/IEC 15946-1:2002(E)
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
---------------------- Page: 11 ----------------------
ISO/IEC 15946-1:2002(E)
(i) If E is defined over F(p) then π(Q) = x .
Q
m
...
Questions, Comments and Discussion
Ask us and Technical Secretary will try to provide an answer. You can facilitate discussion about the standard in here.