< draft-mcgrew-fundamental-ecc-00.txt   draft-mcgrew-fundamental-ecc-01.txt >
Network Working Group D. McGrew Network Working Group D. McGrew
Internet-Draft Cisco Systems Internet-Draft Cisco Systems
Intended status: Informational July 6, 2009 Intended status: Informational October 26, 2009
Expires: January 7, 2010 Expires: April 29, 2010
Fundamental Elliptic Curve Cryptography Algorithms Fundamental Elliptic Curve Cryptography Algorithms
draft-mcgrew-fundamental-ecc-00.txt draft-mcgrew-fundamental-ecc-01.txt
Status of this Memo Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet- other groups may also distribute working documents as Internet-
Drafts. Drafts.
skipping to change at page 1, line 32 skipping to change at page 1, line 32
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
This Internet-Draft will expire on January 7, 2010. This Internet-Draft will expire on April 29, 2010.
Copyright Notice Copyright Notice
Copyright (c) 2009 IETF Trust and the persons identified as the Copyright (c) 2009 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents in effect on the date of Provisions Relating to IETF Documents in effect on the date of
publication of this document (http://trustee.ietf.org/license-info). publication of this document (http://trustee.ietf.org/license-info).
Please review these documents carefully, as they describe your rights Please review these documents carefully, as they describe your rights
and restrictions with respect to this document. and restrictions with respect to this document.
Abstract Abstract
This note describes the fundamental algorithms of Elliptic Curve This note describes the fundamental algorithms of Elliptic Curve
Cryptography (ECC) as they are defined in some early references. Cryptography (ECC) as they are defined in some early references.
These descriptions may be useful to those who want to implement the These descriptions may be useful to those who want to implement the
fundamental algorithms without using any of the specialized methods fundamental algorithms without using any of the specialized methods
that were developed in following years. Only elliptic curves based that were developed in following years. Only elliptic curves defined
on fields of character greater than three are in scope. over fields of characteristic greater than three are in scope; these
curves are those used in Suite B.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. Conventions Used In This Document . . . . . . . . . . . . 4
2. Mathematical Background . . . . . . . . . . . . . . . . . . . 5 2. Mathematical Background . . . . . . . . . . . . . . . . . . . 5
2.1. Modular Arithmetic . . . . . . . . . . . . . . . . . . . . 5 2.1. Modular Arithmetic . . . . . . . . . . . . . . . . . . . . 5
2.2. Group Operations . . . . . . . . . . . . . . . . . . . . . 5 2.2. Group Operations . . . . . . . . . . . . . . . . . . . . . 5
2.3. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 6 2.3. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 6
3. Elliptic Curve Groups . . . . . . . . . . . . . . . . . . . . 7 3. Elliptic Curve Groups . . . . . . . . . . . . . . . . . . . . 8
3.1. Homogenous Coordinates . . . . . . . . . . . . . . . . . . 8 3.1. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 9
3.2. Group Parameters . . . . . . . . . . . . . . . . . . . . . 8 3.2. Group Parameters . . . . . . . . . . . . . . . . . . . . . 10
3.2.1. Security . . . . . . . . . . . . . . . . . . . . . . . 9 3.2.1. Security . . . . . . . . . . . . . . . . . . . . . . . 10
4. Elliptic Curve Diffie-Hellman (ECDH) . . . . . . . . . . . . . 10 4. Elliptic Curve Diffie-Hellman (ECDH) . . . . . . . . . . . . . 11
4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 10 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2. Compact Representation . . . . . . . . . . . . . . . . . . 10 4.2. Compact Representation . . . . . . . . . . . . . . . . . . 11
5. Elliptic Curve ElGamal Signatures (ECES) . . . . . . . . . . . 12 5. Elliptic Curve ElGamal Signatures (ECES) . . . . . . . . . . . 13
5.1. Keypair Generation . . . . . . . . . . . . . . . . . . . . 12 5.1. Keypair Generation . . . . . . . . . . . . . . . . . . . . 13
5.2. Signature Creation . . . . . . . . . . . . . . . . . . . . 12 5.2. Signature Creation . . . . . . . . . . . . . . . . . . . . 13
5.3. Signature Verification . . . . . . . . . . . . . . . . . . 13 5.3. Signature Verification . . . . . . . . . . . . . . . . . . 14
5.4. Hash Functions . . . . . . . . . . . . . . . . . . . . . . 13 5.4. Hash Functions . . . . . . . . . . . . . . . . . . . . . . 14
5.5. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 13 5.5. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 14
6. Abbreviated ECES Signatures (AECES) . . . . . . . . . . . . . 15 6. Abbreviated ECES Signatures (AECES) . . . . . . . . . . . . . 16
6.1. Keypair Generation . . . . . . . . . . . . . . . . . . . . 15 6.1. Keypair Generation . . . . . . . . . . . . . . . . . . . . 16
6.2. Signature Creation . . . . . . . . . . . . . . . . . . . . 15 6.2. Signature Creation . . . . . . . . . . . . . . . . . . . . 16
6.3. Signature Verification . . . . . . . . . . . . . . . . . . 15 6.3. Signature Verification . . . . . . . . . . . . . . . . . . 16
7. Interoperability . . . . . . . . . . . . . . . . . . . . . . . 17 7. Interoperability . . . . . . . . . . . . . . . . . . . . . . . 18
7.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 7.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
7.2. ECES, AECES, and ECDSA . . . . . . . . . . . . . . . . . . 17 7.2. ECES, AECES, and ECDSA . . . . . . . . . . . . . . . . . . 18
8. Intellectual Property . . . . . . . . . . . . . . . . . . . . 19 8. Intellectual Property . . . . . . . . . . . . . . . . . . . . 20
8.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . 19 8.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . 20
9. Security Considerations . . . . . . . . . . . . . . . . . . . 20 9. Security Considerations . . . . . . . . . . . . . . . . . . . 21
9.1. Subgroups . . . . . . . . . . . . . . . . . . . . . . . . 20 9.1. Subgroups . . . . . . . . . . . . . . . . . . . . . . . . 21
9.2. Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . 21 9.2. Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . 22
9.3. Group Representation and Security . . . . . . . . . . . . 21 9.3. Group Representation and Security . . . . . . . . . . . . 22
9.4. Signatures . . . . . . . . . . . . . . . . . . . . . . . . 22 9.4. Signatures . . . . . . . . . . . . . . . . . . . . . . . . 22
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24
11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 24 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 25
12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 25 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 26
12.1. Normative References . . . . . . . . . . . . . . . . . . . 25 12.1. Normative References . . . . . . . . . . . . . . . . . . . 26
12.2. Informative References . . . . . . . . . . . . . . . . . . 26 12.2. Informative References . . . . . . . . . . . . . . . . . . 27
Appendix A. Random Number Generation . . . . . . . . . . . . . . 29 Appendix A. Key Words . . . . . . . . . . . . . . . . . . . . . . 30
Appendix B. Example Elliptic Curve Group . . . . . . . . . . . . 30 Appendix B. Random Number Generation . . . . . . . . . . . . . . 31
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 31 Appendix C. Example Elliptic Curve Group . . . . . . . . . . . . 32
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 33
1. Introduction 1. Introduction
ECC is a public-key technology that offers performance advantages at ECC is a public-key technology that offers performance advantages at
higher security levels. It includes an Elliptic Curve version of higher security levels. It includes an Elliptic Curve version of
Diffie-Hellman key exchange protocol [DH1976] and an Elliptic Curve Diffie-Hellman key exchange protocol [DH1976] and an Elliptic Curve
version of the ElGamal Signature Algorithm [E1985]. The elliptic version of the ElGamal Signature Algorithm [E1985]. The elliptic
curve versions of these algorithms are referred to as ECDH and ECES, curve versions of these algorithms are referred to as ECDH and ECES,
respectively. The adoption of ECC has been slower than had been respectively. The adoption of ECC has been slower than had been
anticipated, perhaps due to the lack of freely available normative anticipated, perhaps due to the lack of freely available normative
skipping to change at page 4, line 34 skipping to change at page 4, line 34
notation from modular arithmetic, group theory and the theory of notation from modular arithmetic, group theory and the theory of
finite fields, respectively. Section 3 defines the groups based on finite fields, respectively. Section 3 defines the groups based on
elliptic curves over finite fields of characteristic greater than elliptic curves over finite fields of characteristic greater than
three. Section 4 and Section 5 present the fundamental ECDH and ECES three. Section 4 and Section 5 present the fundamental ECDH and ECES
algorithms, respectively. Section 6 presents an abbreviated form of algorithms, respectively. Section 6 presents an abbreviated form of
ECES. The previous sections contain all of the normative text (the ECES. The previous sections contain all of the normative text (the
text that defines the norm for implementations conforming to this text that defines the norm for implementations conforming to this
specification), and all of the following sections are purely specification), and all of the following sections are purely
informative. Interoperability is discussed in Section 7. Section 8 informative. Interoperability is discussed in Section 7. Section 8
reviews intellectual property issues. Section 9 summarizes security reviews intellectual property issues. Section 9 summarizes security
considerations. Appendix A describes random number generation and considerations. Appendix B describes random number generation and
Appendix B provides an example of an Elliptic Curve group. Appendix C provides an example of an Elliptic Curve group.
1.1. Conventions Used In This Document
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in Appendix A.
2. Mathematical Background 2. Mathematical Background
This section reviews mathematical preliminaries and establishes This section reviews mathematical preliminaries and establishes
terminology and notation that is used below. terminology and notation that is used below.
2.1. Modular Arithmetic 2.1. Modular Arithmetic
This section reviews modular arithmetic. Two integers x and y are This section reviews modular arithmetic. Two integers x and y are
said to be congruent modulo n if x - y is an integer multiple of n. said to be congruent modulo n if x - y is an integer multiple of n.
Two integers x and y are coprime when their greatest common divisor Two integers x and y are coprime when their greatest common divisor
is 1; in this case, there is no third number z such that z divides x is 1; in this case, there is no third number z > 1 such that z
and z divides y. divides x and z divides y.
The set Zp = { 0, 1, 2, ..., p-1 } is closed under the operations of The set Zq = { 0, 1, 2, ..., q-1 } is closed under the operations of
modular addition, modular subtraction, modular multiplication, and modular addition, modular subtraction, modular multiplication, and
modular inverse. These operations are as follows. modular inverse. These operations are as follows.
For each pair of integers a and b in Zp, a + b mod p is equal to For each pair of integers a and b in Zq, a + b mod q is equal to
a + b if a + b < p, and is equal to a + b - p otherwise. a + b if a + b < q, and is equal to a + b - q otherwise.
For each pair of integers a and b in Zp, a - b mod p is equal to For each pair of integers a and b in Zq, a - b mod q is equal to
a - b if a + b > p, and is equal to a + b otherwise. a - b if a - b >= 0, and is equal to a - b + q otherwise.
For each pair of integers a and b in Zp, a * b mod p is equal to For each pair of integers a and b in Zq, a * b mod q is equal to
the remainder of a * b divided by p. the remainder of a * b divided by q.
For each integer x in Zp that is coprime with p, the inverse of x For each integer x in Zq that is coprime with q, the inverse of x
modulo p is denoted as 1 / x mod p, and can be computed using the modulo q is denoted as 1 / x mod q, and can be computed using the
extended euclidean algorithm (see Section 4.5.2 of [K1981v2], for extended euclidean algorithm (see Section 4.5.2 of [K1981v2], for
example). example).
Algorithms for these operations are well known; for instance, see Algorithms for these operations are well known; for instance, see
Chapter 4 of [K1981v2]. Chapter 4 of [K1981v2].
2.2. Group Operations 2.2. Group Operations
This section establishes some terminology and notation for This section establishes some terminology and notation for
mathematical groups, which is needed later on. Background references mathematical groups, which is needed later on. Background references
abound; see [D1966], for example. abound; see [D1966], for example.
A group is a set of elements G and an associated operation that A group is a set of elements G together with an operation that
combines any two elements in G and returns a third element in G. The combines any two elements in G and returns a third element in G. The
operation is denoted as * and its application is denoted as a * b, operation is denoted as * and its application is denoted as a * b,
for any two elements a and b in G. Repeated application of the group for any two elements a and b in G. The operation is associative, that
operation n times to the element a is denoted as a^N, for any element is, for all a, b and c in G, a * (b * c) is identical to (a * b) * c.
a in G and any positive integer N. That is, a^2, = a * a, Repeated application of the group operation N times to the element a
a^3 = a * a * a, and so on. is denoted as a^N, for any element a in G and any positive integer N.
That is, a^2, = a * a, a^3 = a * a * a, and so on. The associativity
of the group operation ensures that the computation of a^n is
unambiguous; any grouping of the terms gives the same result.
The above definition of a group operation uses multiplicative The above definition of a group operation uses multiplicative
notation. Sometimes an alternative called additive notation is used, notation. Sometimes an alternative called additive notation is used,
in which a * b is denoted as a + b, and a^N is denoted as N * a. In in which a * b is denoted as a + b, and a^N is denoted as N * a. In
multiplicative notation, g^N is called exponentiation, while the multiplicative notation, g^N is called exponentiation, while the
equivalent operation in additive notation is called scalar equivalent operation in additive notation is called scalar
multiplication. In this document, multiplicative notation is used multiplication. In this document, multiplicative notation is used
throughout for consistency. throughout for consistency.
Every group has an special element called the identity element, which Every group has an special element called the identity element, which
we denote as e. For each element a in G, e * a = a * e = a. By we denote as e. For each element a in G, e * a = a * e = a. By
convention, a^0 is equal to the identity element for any a in G. convention, a^0 is equal to the identity element for any a in G.
Every group element a has a unique inverse element b such that a * b
= b * a = e. The inverse of a is denoted as a^-1 in multiplicative
notation. (In additive notation, the inverse of a is denoted as -a.)
A cyclic group of order R is a group that contains the R elements A cyclic group of order R is a group that contains the R elements
g, g^2, g^3, ..., g^R. The element g is called the generator of the g, g^2, g^3, ..., g^R. The element g is called the generator of the
group. The element g^R is equal to the identity element e. Note group. The element g^R is equal to the identity element e. Note
that g^X is equal to g^(X modulo R) for any non-negative integer X. that g^X is equal to g^(X modulo R) for any non-negative integer X.
Given the element a of order N, and an integer i between 1 and N-1, Given the element a of order N, and an integer i between 1 and N-1,
inclusive, the element a^i can be computed by the "square and inclusive, the element a^i can be computed by the "square and
multiply" method outlined in Section 2.1 of [M1983] (see also Knuth, multiply" method outlined in Section 2.1 of [M1983] (see also Knuth,
Vol. 2, Section 4.6.3.), or other methods. Vol. 2, Section 4.6.3.), or other methods.
2.3. Finite Fields 2.3. Finite Fields
This section establishes terminology and notation for finite fields This section establishes terminology and notation for finite fields
with prime characteristic. with prime characteristic.
When p is a prime number, then the set Zp, with the associated When p is a prime number, then the set Zp, with the addition,
addition, subtraction, multiplication and division operations, is a subtraction, multiplication and division operations, is a finite
finite field with character p. There is a one-to-one correspondence field with characteristic p. Each nonzero element x in Zp has an
between the integers between zero and p-1 and the elements of the inverse 1/x. There is a one-to-one correspondence between the
integers between zero and p-1, inclusive, and the elements of the
field. The field is denoted as Fp. field. The field is denoted as Fp.
Equations involving field elements do not include the "mod p" Equations involving field elements do not explicitly denote the "mod
operation, but it is understood to be implicit. For example, the p" operation, but it is understood to be implicit. For example, the
statement that x, y, and z are in Fp and statement that x, y, and z are in Fp and
z = x + y z = x + y
is equivalent to the statement that x, y, and z are in Zp and is equivalent to the statement that x, y, and z are in the set { 0,
1, ..., p-1 } and
z = x + y mod p. z = x + y mod p.
3. Elliptic Curve Groups 3. Elliptic Curve Groups
This note only covers elliptic curves over fields with characteristic This note only covers elliptic curves over fields with characteristic
greater than three. For other fields, the definition of the elliptic greater than three; these are the curves used in Suite B [SuiteB].
curve group would be different. For other fields, the definition of the elliptic curve group would be
different.
An elliptic curve over a field F is defined by the curve equation An elliptic curve over a field F is defined by the curve equation
y^2 = x^3 + a*x + b, y^2 = x^3 + a*x + b,
where x, y, a, and b are elements of the field Fp [M1985]. A point where x, y, a, and b are elements of the field Fp, and the
on an elliptic curve is a pair (x,y) of values in Fp that satisfy the discriminant 16*(4*a^3 - 27*b^2) is nonzero [M1985]. A point on an
curve equation, such that x and y are both in Fp, or it is a special elliptic curve is a pair (x,y) of values in Fp that satisfy the curve
point (@,@) that represents the identity element (which is called the equation, such that x and y are both in Fp, or it is a special point
(@,@) that represents the identity element (which is called the
"point at infinity"). The order of an elliptic curve group is the "point at infinity"). The order of an elliptic curve group is the
number of distinct points. number of distinct points.
Two elliptic curve points (x1,y1) and (x2,y2) are equal whenever Two elliptic curve points (x1,y1) and (x2,y2) are equal whenever
x1=x2 and y1=y2, or when both points are the point at infinity. x1=x2 and y1=y2, or when both points are the point at infinity. The
inverse of the point (x1,y1) is the point (x1,-y1).
The group operation associated with the elliptic curve group is as The group operation associated with the elliptic curve group is as
follows [BC1989]. To an arbitrary pair of points P and Q specified follows [BC1989]. To an arbitrary pair of points P and Q specified
by their coordinates (x1,y1) and (x2,y2) respectively, the group by their coordinates (x1,y1) and (x2,y2) respectively, the group
operation assigns a third point P*Q with the coordinates (x3,y3). operation assigns a third point P*Q with the coordinates (x3,y3).
These coordinates are computed as follows These coordinates are computed as follows
(x3,y3) = (@,@) when P is not equal to Q and x1 is equal to x2. (x3,y3) = (@,@) when P is not equal to Q and x1 is equal to x2.
x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 and x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 and
y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 when P is not equal to Q and y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 when P is not equal to Q and
x1 is not equal to x2. x1 is not equal to x2.
(x3,y3) = (@,@) when P is equal to Q, P is equal to (0,0) and P is (x3,y3) = (@,@) when P is equal to Q and y1 is equal to 0,
an element of the group.
x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 and x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 and
y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y1 if P is equal to Q. y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y1 if P is equal to Q and y1 is
not equal to 0.
In the above equations, a, x1, x2, x3, y1, y2, and y3 are elements of In the above equations, a, x1, x2, x3, y1, y2, and y3 are elements of
the field Fp; thus, computation of x3 and y3 in practice use a "mod the field Fp; thus, computation of x3 and y3 in practice must reduce
p" operation. the right-hand-side modulo p.
The representation of elliptic curve points as a pair of integers in The representation of elliptic curve points as a pair of integers in
Zp is known as the affine coordinate representation. This Zp is known as the affine coordinate representation. This
representation is suitable as an external data representation for representation is suitable as an external data representation for
communicating or storing group elements, though the point at infinity communicating or storing group elements, though the point at infinity
must be treated as a special case. must be treated as a special case.
Some pairs of integers are not valid elliptic curve points. A valid Some pairs of integers are not valid elliptic curve points. A valid
pair will satisfy the curve equation, while an invalid pair will not. pair will satisfy the curve equation, while an invalid pair will not.
3.1. Homogenous Coordinates 3.1. Homogeneous Coordinates
An alternative way to implement the group operation is to use An alternative way to implement the group operation is to use
homogeneous coordinates [K1987] (see also [KMOV1991]). This method homogeneous coordinates [K1987] (see also [KMOV1991]). This method
is typically more efficient because it does not require a modular is typically more efficient because it does not require a modular
inverse operation. inversion operation.
An elliptic curve point (x,y) is equivalent to a point (X,Y,Z) in An elliptic curve point (x,y) (other than the point at infinity
homogeneous coordinates whenever x=X/Z and y=Y/Z. (@,@)) is equivalent to a point (X,Y,Z) in homogeneous coordinates
whenever x=X/Z mod p and y=Y/Z mod p.
Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on an elliptic curve Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on an elliptic curve
and suppose that the points P1, P2 are not equal to (@,@), P1 is not and suppose that the points P1, P2 are not equal to (@,@), P1 is not
equal to P2, and P1 is not equal to -P2. Then the product equal to P2, and P1 is not equal to P2^-1. Then the product
P3=(X3,Y3,Z3) = P1 * P2 is given by P3=(X3,Y3,Z3) = P1 * P2 is given by
X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3), X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3) mod p,
Y3 = z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3), Y3 = z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) mod p,
Z3 = 8 * (Y1)^3 * (Z1)^3, Z3 = 8 * (Y1)^3 * (Z1)^3 mod p,
where u = Y2 * Z1 - Y1 * Z2 and v = X2 * Z1 - X1 * Z2. where u = Y2 * Z1 - Y1 * Z2 mod p and v = X2 * Z1 - X1 * Z2 mod p.
When the points P1 and P2 are equal, then (X1/Z1, Y1/Z1) is equal to
(X2/Z2, Y2/Z2), which is true if and only if u and v are both equal
to zero.
The product P3=(X3,Y3,Z3) = P1 * P1 is given by The product P3=(X3,Y3,Z3) = P1 * P1 is given by
X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1), X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1) mod p,
Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3, Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3 mod p,
Z3 = 8 * (Y1 * Z1)^3. Z3 = 8 * (Y1 * Z1)^3 mod p,
In the above equations, a, u, v, w, X1, X2, X3, Y1, Y2, Y3, Z1, Z2, where w = 3 * X1^2 + a * Z1^2 mod p. In the above equations, a, u,
and Z3 are elements of the field Fp; thus, computation of X3, Y3, and v, w, X1, X2, X3, Y1, Y2, Y3, Z1, Z2, and Z3 are integers in the set
Z3 in practice use a "mod p" operation. Fp.
When converting from affine coordinates to homogeneous coordinates, When converting from affine coordinates to homogeneous coordinates,
it is convenient to set Z to 1. When converting from homogeneous it is convenient to set Z to 1. When converting from homogeneous
coordinates to affine coordinates, it is necessary to perform a coordinates to affine coordinates, it is necessary to perform a
modular inverse to find 1/Z mod p. modular inverse to find 1/Z mod p.
3.2. Group Parameters 3.2. Group Parameters
An elliptic curve group over a finite field with characteristic An elliptic curve group over a finite field with characteristic
greater than three is completely specified by the following greater than three is completely specified by the following
parameters: parameters:
The prime number p that indicates the order of the field Fp. The prime number p that indicates the order of the field Fp.
The value a used in the curve equation. The value a used in the curve equation.
The value b used in the curve equation. The value b used in the curve equation.
The generator g of the group. The generator g of the group.
The order n of the group generated by g. The order n of the group generated by g.
An example of an Elliptic Curve Group is provided in Appendix B. An example of an Elliptic Curve Group is provided in Appendix C.
Each elliptic curve point is associated with with a particular group, Each elliptic curve point is associated with a particular group, i.e
i.e a particular parameter set. Two elliptic curve groups are equal a particular parameter set. Two elliptic curve groups are equal if
if and only if each of the parameters in the set are equal. The and only if each of the parameters in the set are equal. The
elliptic curve group operation is only defined between two points on elliptic curve group operation is only defined between two points on
the same group. It is an error to apply the group operation to two the same group. It is an error to apply the group operation to two
elements that are from different groups, or to apply the group elements that are from different groups, or to apply the group
operation to a pair of coordinates that are not a valid point. See operation to a pair of coordinates that are not a valid point. See
Section 9.3 for further information. Section 9.3 for further information.
3.2.1. Security 3.2.1. Security
Security is highly dependent on the choice of these parameters. This Security is highly dependent on the choice of these parameters. This
section gives normative guidance on acceptable choices. See also section gives normative guidance on acceptable choices. See also
Section 9 for more information. Section 9 for informative guidance.
The order of the group generated by g should be divisible by a large The order of the group generated by g MUST be divisible by a large
prime, in order to preclude easy solution of the discrete logarithm prime, in order to preclude easy solution of the discrete logarithm
problem [K1987] problem [K1987]
With some parameter choices, the discrete log problem is With some parameter choices, the discrete log problem is
significantly easier to solve. This includes parameter sets in which significantly easier to solve. This includes parameter sets in which
b = 0 and p = 3 (mod 4), and parameter sets in which a = 0 and b = 0 and p = 3 (mod 4), and parameter sets in which a = 0 and
p = 2 (mod 3) [MOV1993]. These parameter choices are inferior for p = 2 (mod 3) [MOV1993]. These parameter choices are inferior for
cryptographic purposes and should not be used. cryptographic purposes and SHOULD NOT be used.
4. Elliptic Curve Diffie-Hellman (ECDH) 4. Elliptic Curve Diffie-Hellman (ECDH)
The Diffie-Hellman (DH) key exchange protocol [DH1976] allows two The Diffie-Hellman (DH) key exchange protocol [DH1976] allows two
parties communicating over an insecure channel to agree on a secret parties communicating over an insecure channel to agree on a secret
key. It was originally defined in terms of operations in the key. It was originally defined in terms of operations in the
multiplicative group of a field with a large prime characteristic. multiplicative group of a field with a large prime characteristic.
Massey [M1983] observed that it can be easily generalized so that it Massey [M1983] observed that it can be easily generalized so that it
is defined in terms of an arbitrary mathematical group. Miller is defined in terms of an arbitrary mathematical group. Miller
[M1985] and Koblitz [K1987] analyzed the DH protocol over an elliptic [M1985] and Koblitz [K1987] analyzed the DH protocol over an elliptic
curve group. We describe DH following the former reference. curve group. We describe DH following the former reference.
Let G be a group, and g be a generator for that group, and let t Let G be a group, and g be a generator for that group, and let t
denote the order of G. The DH protocol runs as follows. Party A denote the order of G. The DH protocol runs as follows. Party A
chooses an exponent j between 1 and t-1 uniformly at random, computes chooses an exponent j between 1 and t-1 uniformly at random, computes
g^j and sends that element to B. Party B chooses an exponent k g^j and sends that element to B. Party B chooses an exponent k
between 1 and t-1 uniformly at random, computes g^k and sends that between 1 and t-1 uniformly at random, computes g^k and sends that
element to A. Each party can compute g^(j*k); party A computes element to A. Each party can compute g^(j*k); party A computes
(g^k)^j, and party B computes (g^j)^k. (g^k)^j, and party B computes (g^j)^k.
See Appendix A regarding generation of random numbers. See Appendix B regarding generation of random numbers.
4.1. Data Types 4.1. Data Types
An ECDH private key a is an integer in Zt. An ECDH private key z is an integer in Zt.
The corresponding ECDH public key Y is group element, where Y = g^a. The corresponding ECDH public key Y is the group element, where Y =
Each public key is associated with a particular group, i.e. a g^z. Each public key is associated with a particular group, i.e. a
particular parameter set as per Section 3.2. particular parameter set as per Section 3.2.
The shared secret computed by both parties is a group element. The shared secret computed by both parties is a group element.
Each run of the ECDH protocol is associated with a particular group, Each run of the ECDH protocol is associated with a particular group,
and both of the public keys and the shared secret are elements of and both of the public keys and the shared secret are elements of
that group. that group.
4.2. Compact Representation 4.2. Compact Representation
skipping to change at page 11, line 6 skipping to change at page 12, line 6
In the ECDH key exchange protocol, after the element g^(j*k) has been In the ECDH key exchange protocol, after the element g^(j*k) has been
computed, the x-coordinate of that value can be used as the shared computed, the x-coordinate of that value can be used as the shared
secret. We call this compact output. secret. We call this compact output.
Following [M1985] again, when compact output is used in ECDH, only Following [M1985] again, when compact output is used in ECDH, only
the x-coordinate of an elliptic curve point needs to be transmitted, the x-coordinate of an elliptic curve point needs to be transmitted,
instead of both coordinates as in the typical affine coordinate instead of both coordinates as in the typical affine coordinate
representation. We call this the compact representation. representation. We call this the compact representation.
ECDH can be used with or without compact output. Both parties in a ECDH can be used with or without compact output. Both parties in a
particular run of the ECDH protocol must use the same method. ECDH particular run of the ECDH protocol MUST use the same method. ECDH
can be used with or without compact representation. If compact can be used with or without compact representation. If compact
representation is used in a particular run of the ECDH protocol, then representation is used in a particular run of the ECDH protocol, then
compact output must be used as well. compact output MUST be used as well.
5. Elliptic Curve ElGamal Signatures (ECES) 5. Elliptic Curve ElGamal Signatures (ECES)
The ElGamal signature algorithm was introduced in 1984 [E1984a] The ElGamal signature algorithm was introduced in 1984 [E1984a]
[E1984b] [E1985]. It is based on the discrete logarithm problem in [E1984b] [E1985]. It is based on the discrete logarithm problem in
the multiplicative group of the integers modulo a large prime number. the multiplicative group of the integers modulo a large prime number.
It is straightforward to extended it to use an elliptic curve group. It is straightforward to extend it to use an elliptic curve group.
In this section we recall a well-specified elliptic curve version of In this section we recall a well-specified elliptic curve version of
the ElGamal Signature Algorithm, as described in [A1992] and the ElGamal Signature Algorithm, as described in [A1992] and
[MV1993]. This signature method is called Elliptic Curve ElGamal [MV1993]. This signature method is called Elliptic Curve ElGamal
Signatures (ECES). Signatures (ECES).
The algorithm uses an elliptic curve group, as described in The algorithm uses an elliptic curve group, as described in
Section 3.2. We denote the generator as alpha, and the order of the Section 3.2, with prime field order p, curve equation parameters a
generator as n. We follow [MV1993] in describing the algorithms in and b. We follow [MV1993] in describing the algorithms in terms of
terms of mathematical groups. mathematical groups, and denoting the generator as alpha, and its
order as n.
ECES uses a collision-resistant hash function, so that it can sign ECES uses a collision-resistant hash function, so that it can sign
messages of arbitrary length. We denote the hash function as h(). messages of arbitrary length. We denote the hash function as h().
Its input is a bit string of arbitrary length, and its output is an Its input is a bit string of arbitrary length, and its output is an
integer between zero and n-1, inclusive. integer between zero and n-1, inclusive.
ECES uses a function g() from the set of group elements to the set of ECES uses a function g() from the set of group elements to the set of
integers Zn. This function returns the x-coordinate of the affine integers Zn. This function returns the x-coordinate of the affine
coordinate representation of the elliptic curve point. coordinate representation of the elliptic curve point.
5.1. Keypair Generation 5.1. Keypair Generation
The private key a is an integer between 0 and n - 1, inclusive, The private key z is an integer between 0 and n - 1, inclusive,
generated uniformly at random. The public key is the group element generated uniformly at random. The public key is the group element
Q = alpha^a. Q = alpha^z.
5.2. Signature Creation 5.2. Signature Creation
To sign message m, using the private key a: To sign message m, using the private key z:
1. First, choose an integer k uniformly at random from the set of 1. First, choose an integer k uniformly at random from the set of
all integers k in Zn that are coprime to n. (If n is a prime, all integers k in Zn that are coprime to n. (If n is a prime,
then choose an integer uniformly at random between 1 and n-1.) then choose an integer uniformly at random between 1 and n-1.)
(See Appendix A regarding random integers.) (See Appendix B regarding random integers.)
2. Next, compute the group element r = alpha^k. 2. Next, compute the group element r = alpha^k.
3. Finally, compute the integer s as 3. Finally, compute the integer s as
s = (h(m) + a * g(r)) / k (mod n). s = (h(m) + z * g(r)) / k (mod n).
4. If s is equal to zero, then the signature creation must be 4. If s is equal to zero, then the signature creation MUST be
repeated, starting at Step 1 and using a newly chosen k value. repeated, starting at Step 1 and using a newly chosen k value.
The signature for message m is the ordered pair (r, s). Note that The signature for message m is the ordered pair (r, s). Note that
the first component is a group element, and the second is a non- the first component is a group element, and the second is a non-
negative integer. negative integer.
5.3. Signature Verification 5.3. Signature Verification
To verify the message m and the signature (r,s) using the public key To verify the message m and the signature (r,s) using the public key
Q: Q:
skipping to change at page 13, line 50 skipping to change at page 14, line 50
3. After conversion, reduce i modulo n, where n is the group order. 3. After conversion, reduce i modulo n, where n is the group order.
5.5. Rationale 5.5. Rationale
This subsection is not normative and is provided only as background This subsection is not normative and is provided only as background
information. information.
The signature verification will pass whenever the signature is The signature verification will pass whenever the signature is
properly generated, because properly generated, because
r^s * Q^(-g(r)) = alpha^(k*s - a*g(r)) = alpha^h(m). r^s * Q^(-g(r)) = alpha^(k*s - z*g(r)) = alpha^h(m).
The reason that the random variable k must be coprime with n is so The reason that the random variable k must be coprime with n is so
that 1/k mod n is defined. that 1/k mod n is defined.
A valid signature with s=0 leaks the secret key, since in that case a A valid signature with s=0 leaks the secret key, since in that case a
= h(m) / g(r) mod n. We adopt Rivest's suggestion to avoid this = h(m) / g(r) mod n. We adopt Rivest's suggestion to avoid this
problem [R1992]. problem [R1992].
As described in the final paragraph of [M1985], for it is suitable to As described in the final paragraph of [M1985], it is suitable to use
use the x-coordinate of a particular elliptic curve point as a the x-coordinate of a particular elliptic curve point as a
representative for that point. This is what the function g() does. representative for that point. This is what the function g() does.
6. Abbreviated ECES Signatures (AECES) 6. Abbreviated ECES Signatures (AECES)
The ECES system is secure and efficient, but has signatures that are The ECES system is secure and efficient, but has signatures that are
slightly larger than they need to be. Koyama and Tsuruoka described slightly larger than they need to be. Koyama and Tsuruoka described
a signature system based on Elliptic Curve ElGamal, but with shorter a signature system based on Elliptic Curve ElGamal, but with shorter
signatures [KT1994]. Their idea is to include only the x-coordinate signatures [KT1994]. Their idea is to include only the x-coordinate
of the EC point in the signature, instead of both coordinates. of the EC point in the signature, instead of both coordinates.
Menezes, Qu, and Vanstone independently developed the same idea, Menezes, Qu, and Vanstone independently developed the same idea,
which was the basis for the "Elliptic Curve Signature Scheme with which was the basis for the "Elliptic Curve Signature Scheme with
Appendix (ECSSA)" submission to the IEEE 1363 working group Appendix (ECSSA)" submission to the IEEE 1363 working group
[MQV1994]. [MQV1994].
In this section we describe an Elliptic Curve Signature Scheme that In this section we describe an Elliptic Curve Signature Scheme that
hash a single elliptic curve coordinate in the signature instead of uses a single elliptic curve coordinate in the signature instead of
both coordinates. It is based on ECSSA, but with an inversion both coordinates. It is based on [KT1994] and [MQV1994], but with
operation moved from the signature operation to the verification the finite field inversion operation moved from the signature
operation, so that the signing operation is more compatible with operation to the verification operation, so that the signing
ECES. (See [AMV1990] and [A1992] for a discussion of these operation is more compatible with ECES. (See [AMV1990] and [A1992]
alternatives; the security of the methods is equivalent.) We refer for a discussion of these alternatives; the security of the methods
to this scheme as Abbreviated ECES, or AECES. is equivalent.) We refer to this scheme as Abbreviated ECES, or
AECES.
6.1. Keypair Generation 6.1. Keypair Generation
Keypairs are the same as for ECES and are as described in Keypairs are the same as for ECES and are as described in
Section 5.1. Section 5.1.
6.2. Signature Creation 6.2. Signature Creation
In this section we describe how to compute the signature for a In this section we describe how to compute the signature for a
message m using the private key a. message m using the private key z.
Signature creation is as for ECES, with the following additional Signature creation is as for ECES, with the following additional
step: step:
1. Let the integer s1 be equal to the x-coordinate of r. 1. Let the integer s1 be equal to the x-coordinate of r.
The signature is the ordered pair (s1, s). Both signature components The signature is the ordered pair (s1, s). Both signature components
are non-negative integers. are non-negative integers.
6.3. Signature Verification 6.3. Signature Verification
Given the message m, the public key Q, and the signature (s1,s) Given the message m, the public key Q, and the signature (s1, s)
verification is as follows: verification is as follows:
1. Compute the inverse of s modulo q. We denote this value as w. 1. Compute the inverse of s modulo n. We denote this value as w.
2. Compute the non-negative integers u and v, where 2. Compute the non-negative integers u and v, where
u = w * h(m) mod q, and
v = w * s1 mod q. u = w * h(m) mod n, and
v = w * s1 mod n.
3. Compute the elliptic curve point R' = alpha^u * Q^v 3. Compute the elliptic curve point R' = alpha^u * Q^v
4. If the x-coordinate of R' is equal to s1, then the signature and 4. If the x-coordinate of R' is equal to s1, then the signature and
message pass the verification; otherwise, they fail. message pass the verification; otherwise, they fail.
7. Interoperability 7. Interoperability
The algorithms in this note can be used to interoperate with some The algorithms in this note can be used to interoperate with some
other ECC specifications. This section provides details for each other ECC specifications. This section provides details for each
skipping to change at page 17, line 28 skipping to change at page 18, line 28
compact output nor the compact representation of Section 4.2. Note compact output nor the compact representation of Section 4.2. Note
that some groups use a negative curve parameter "a" and express this that some groups use a negative curve parameter "a" and express this
fact in the curve equation rather than in the parameter. The test fact in the curve equation rather than in the parameter. The test
cases in Section 8 of [RFC4753] can be used to test an cases in Section 8 of [RFC4753] can be used to test an
implementation; these cases use the multiplicative notation, as does implementation; these cases use the multiplicative notation, as does
this note. The KEi and KEr payloads are equal to g^i and g^r, this note. The KEi and KEr payloads are equal to g^i and g^r,
respectively, with 64 bits of encoding data prepended to them. respectively, with 64 bits of encoding data prepended to them.
The algorithms in Section 4 can be used to interoperate with the IEEE The algorithms in Section 4 can be used to interoperate with the IEEE
[P1363] and ANSI [X9.62] standards for ECDH based on fields of [P1363] and ANSI [X9.62] standards for ECDH based on fields of
characteristic greater than three. characteristic greater than three. To use IEEE P1363 ECDH in a
manner that will interoperate with this specification, the following
options and parameter choices should be used: prime curves with a
cofactor of 1, the ECSVDP-DH primitive, and the Key Derivation
Function must be the "identity" function (equivalently, omit the KDF
step and output the shared secret value directly).
7.2. ECES, AECES, and ECDSA 7.2. ECES, AECES, and ECDSA
The Digital Signature Algorithm (DSA) is based on the discrete The Digital Signature Algorithm (DSA) is based on the discrete
logarithm problem over the multiplicative subgroup of the finite logarithm problem over the multiplicative subgroup of the finite
field large prime order [DSA1991][FIPS186]. The Elliptic Curve field large prime order [DSA1991][FIPS186]. The Elliptic Curve
Digital Signature Algorithm (ECDSA) [P1363] [X9.62] is an elliptic Digital Signature Algorithm (ECDSA) [P1363] [X9.62] is an elliptic
curve version of DSA. curve version of DSA.
AECES can interoperate with the IEEE [P1363] and ANSI [X9.62] AECES can interoperate with the IEEE [P1363] and ANSI [X9.62]
standards for Elliptic Curve DSA (ECDSA) based on fields of standards for Elliptic Curve DSA (ECDSA) based on fields of
characteristic greater than three. characteristic greater than three.
An ECES signature can be converted into an ECDSA signature by An ECES signature can be converted into an ECDSA or AECES signature
discarding the y-coordinate from the elliptic curve point. by discarding the y-coordinate from the elliptic curve point.
There is a strong correspondence between ECES signatures and ECDSA There is a strong correspondence between ECES signatures and ECDSA or
signatures. In the notation of Section 5, an ECDSA signature AECES signatures. In the notation of Section 5, an ECDSA (or AECES)
consists of the pair of integers (g(r), s), and signature signature consists of the pair of integers (g(r), s), and signature
verification passes if and only if verification passes if and only if
A^(h(m)/s) * Q^(g(r)/s) = r, A^(h(m)/s) * Q^(g(r)/s) = r,
where the equality of the elliptic curve elements is checked by where the equality of the elliptic curve elements is checked by
checking for the equality of their x-coordinates. For valid checking for the equality of their x-coordinates. For valid
signatures, (h(m)+a*r)/s mod q = k, and thus the two sides are equal. signatures, (h(m)+a*r)/s mod q = k, and thus the two sides are equal.
An ECDSA signature contains only the x-coordinate g(r), but this is An ECDSA (or AECES) signature contains only the x-coordinate g(r),
sufficient to allow the signatures to be checked with the above but this is sufficient to allow the signatures to be checked with the
method. above method.
Whenever the ECES signature (r, s) is valid for a particular message Whenever the ECES signature (r, s) is valid for a particular message
m, and public key Q, then there is a valid ECDSA signature (g(r), s) m, and public key Q, then there is a valid AECES or ECDSA signature
for the same message and public key. (g(r), s) for the same message and public key.
Whenever the ECDSA signature (c, d) is valid for a particular message Whenever an AECES or ECDSA signature (c, d) is valid for a particular
m, and public key Q, then there is a valid ECES signature for the message m, and public key Q, then there is a valid ECES signature for
same message and public key. This signature has the form ((c, f(c)), the same message and public key. This signature has the form ((c,
d), or ((c, q-f(c)), d) where the function f takes as input an f(c)), d), or ((c, q-f(c)), d) where the function f takes as input an
integer in Zq and is defined as integer in Zq and is defined as
f(x) = sqrt(x^3 + a*x + b) (mod q). f(x) = sqrt(x^3 + a*x + b) (mod q).
It is possible to compute the square root modulo q, for instance, by It is possible to compute the square root modulo q, for instance, by
using Shanks's method [K1987]. However, it is not as efficient to using Shanks's method [K1987]. However, it is not as efficient to
convert an ECDSA signature (or an AECES signature) to an ECES convert an ECDSA signature (or an AECES signature) to an ECES
signature. signature.
8. Intellectual Property 8. Intellectual Property
Concerns about intellectual property have slowed the adoption of ECC, Concerns about intellectual property have slowed the adoption of ECC,
because a number of optimizations and specialized algorithms have because a number of optimizations and specialized algorithms have
been patented in recent years. been patented in recent years.
All of the normative references in this note were published during or All of the normative references for ECDH (as defined in Section 4)
before October, 1994, and all of the normative text in this note is were published during or before 1989, those for ECES were published
based solely on those references. during or before 1993, and those for AECES were published during or
before October, 1994. All of the normative text for these algorithms
is based solely on their respective references.
8.1. Disclaimer 8.1. Disclaimer
This document is not intended as legal advice. Readers are advised This document is not intended as legal advice. Readers are advised
to consult their own legal advisers if they would like a legal to consult their own legal advisers if they would like a legal
interpretation of their rights. interpretation of their rights.
The IETF policies and processes regarding intellectual property and The IETF policies and processes regarding intellectual property and
patents are outlined in [RFC3979] and [RFC4879] and at patents are outlined in [RFC3979] and [RFC4879] and at
https://datatracker.ietf.org/ipr/about/. https://datatracker.ietf.org/ipr/about/.
9. Security Considerations 9. Security Considerations
The security level of an elliptic curve cryptosystem is determined by The security level of an elliptic curve cryptosystem is determined by
the cryptanalytic algorithm that is the least expensive for an the cryptanalytic algorithm that is the least expensive for an
attacker to implement. There are several algorithms to consider. attacker to implement. There are several algorithms to consider.
The Polhig-Hellman method is a divide-and-conquer technique [PH1978]. The Pohlig-Hellman method is a divide-and-conquer technique [PH1978].
If the group order n can be factored as If the group order n can be factored as
n = q1 * q2 * ... * qz, n = q1 * q2 * ... * qz,
then the discrete log problem over the group can be solved by then the discrete log problem over the group can be solved by
independently solving a discrete log problem in groups of order q1, independently solving a discrete log problem in groups of order q1,
q2, ..., qz, then combining the results using the Chinese remainder q2, ..., qz, then combining the results using the Chinese remainder
theorem. The overall computational cost is dominated by that of the theorem. The overall computational cost is dominated by that of the
discrete log problem in the subgroup with the largest order. discrete log problem in the subgroup with the largest order.
Shanks algorithm [K1981v3] computes a discrete logarithm in a group Shanks algorithm [K1981v3] computes a discrete logarithm in a group
of order n using O(sqrt(n)) operations and O(sqrt(n)) storage. The of order n using O(sqrt(n)) operations and O(sqrt(n)) storage. The
Pollard rho algorithm [P1978] computes a discrete logarithm in a Pollard rho algorithm [P1978] computes a discrete logarithm in a
group of order n using O(sqrt(n)) operations, with a negligible group of order n using O(sqrt(n)) operations, with a negligible
amount of storage, and can be efficiently parallelized. amount of storage, and can be efficiently parallelized [VW1994].
The Pollard lambda algorithm [P1978] can solve the discrete logarithm The Pollard lambda algorithm [P1978] can solve the discrete logarithm
problem using O(sqrt(w)) operations and O(log(w)) storage, when the problem using O(sqrt(w)) operations and O(log(w)) storage, when the
exponent belongs to a set of w elements. exponent belongs to a set of w elements.
The algorithms described above work in any group. There are The algorithms described above work in any group. There are
specialized algorithms that specifically target elliptic curve specialized algorithms that specifically target elliptic curve
groups. There are no subexponential algorithms against general groups. There are no subexponential algorithms against general
elliptic curve groups, though there are methods that target certain elliptic curve groups, though there are methods that target certain
special elliptic curve groups; see [MOV1993] and [FR1994]. special elliptic curve groups; see [MOV1993] and [FR1994].
9.1. Subgroups 9.1. Subgroups
A group consisting of a set of elements S with associated group A group consisting of a nonempty set of elements S with associated
operation * is a subgroup of the group with the set of elements G, if group operation * is a subgroup of the group with the set of elements
the latter group uses the same group operation and S is a subset of G, if the latter group uses the same group operation and S is a
G. For each elliptic curve equation, there is an elliptic curve group subset of G. For each elliptic curve equation, there is an elliptic
whose group order is equal to the order of the elliptic curve; that curve group whose group order is equal to the order of the elliptic
is, there is a group that contains every point on the curve. curve; that is, there is a group that contains every point on the
curve.
The order m of the elliptic curve is divisible by the order n of the The order m of the elliptic curve is divisible by the order n of the
group associated with the generator; that is, for each elliptic curve group associated with the generator; that is, for each elliptic curve
group, m = n * c for some number c. The number c is called the group, m = n * c for some number c. The number c is called the
"cofactor" [P1363]. Each elliptic curve group (e.g. each parameter "cofactor" [P1363]. Each elliptic curve group (e.g. each parameter
set as in Section 3.2) is associated with a particular cofactor. set as in Section 3.2) is associated with a particular cofactor.
It is possible and desirable to use a cofactor equal to 1. It is possible and desirable to use a cofactor equal to 1.
It is common to use a "safe prime group" in the conventional Diffie-
Hellman protocol over the multiplicative group of the prime field Fp
(see Appendix E of [RFC2412] for example). A safe prime group is the
subgroup of prime order q of the multiplicative group of Zp, where
p-1 = 2*q. The use of safe prime groups simplifies protocol design,
implementation and use, because they minimize the effectiveness of
some cryptanalytic attacks. Elliptic curve groups with a cofactor of
1 have similar benefits.
9.2. Diffie-Hellman 9.2. Diffie-Hellman
Note that the key exchange protocol as defined in Section 4 does not Note that the key exchange protocol as defined in Section 4 does not
protect against active attacks; Party A must use some method to protect against active attacks; Party A must use some method to
ensure that (g^k) originated with the intended communicant B, rather ensure that (g^k) originated with the intended communicant B, rather
than an attacker, and Party B must do the same with (g^j). than an attacker, and Party B must do the same with (g^j).
It is not sufficient to authenticate the shared secret g^(j*k), since It is not sufficient to authenticate the shared secret g^(j*k), since
this leaves the protocol open to attacks that manipulate the public this leaves the protocol open to attacks that manipulate the public
keys. Instead, the values of the public keys g^x and g^y that are keys. Instead, the values of the public keys g^x and g^y that are
skipping to change at page 22, line 16 skipping to change at page 23, line 6
assume that each pair of coordinates in Zp is actually a point on the assume that each pair of coordinates in Zp is actually a point on the
appropriate elliptic curve. appropriate elliptic curve.
9.4. Signatures 9.4. Signatures
Elliptic curve parameters should only be used if they come from a Elliptic curve parameters should only be used if they come from a
trusted source; otherwise, some attacks are possible [AV1996], trusted source; otherwise, some attacks are possible [AV1996],
[V1996]. [V1996].
In principle, any collision-resistant hash function is suitable for In principle, any collision-resistant hash function is suitable for
use in ECES. To facilitate interoperability, we recognize the use in ECES or AECES. To facilitate interoperability, we recognize
following hashes as suitable for use as the function H defined in the following hashes as suitable for use as the function H defined in
Section 5.4: Section 5.4:
SHA-256, which has a 256-bit output. SHA-256, which has a 256-bit output.
SHA-384, which has a 384-bit output. SHA-384, which has a 384-bit output.
SHA-512, which has a 512-bit output. SHA-512, which has a 512-bit output.
All of these hash functions are defined in [FIPS180-2]. All of these hash functions are defined in [FIPS180-2].
The number of bits in the output of the hash used in ECES should be The number of bits in the output of the hash used in ECES or AECES
equal or close to the number of bits needed to represent the group should be equal or close to the number of bits needed to represent
order. the group order.
10. IANA Considerations 10. IANA Considerations
This note has no actions for IANA. This section should be removed by This note has no actions for IANA. This section should be removed by
the RFC editor before publication as an RFC. the RFC editor before publication as an RFC.
11. Acknowledgements 11. Acknowledgements
The author expresses his thanks to the originators of elliptic curve The author expresses his thanks to the originators of elliptic curve
cryptography, whose work made this note possible. cryptography, whose work made this note possible, and all of the
reviewers, who provided valuable constructive feedback.
12. References 12. References
12.1. Normative References 12.1. Normative References
[A1992] Anderson, J., "Response to the proposed DSS", [A1992] Anderson, J., "Response to the proposed DSS",
Communications of the ACM v.35 n.7 p.50-52, July 1992. Communications of the ACM v.35 n.7 p.50-52, July 1992.
[AMV1990] Agnew, G., Mullin, R., and S. Vanstone, "Improved Digital [AMV1990] Agnew, G., Mullin, R., and S. Vanstone, "Improved Digital
Signature Scheme based on Discrete Exponentiation", Signature Scheme based on Discrete Exponentiation",
skipping to change at page 25, line 51 skipping to change at page 26, line 51
and the discrete logarithm in the divisor class group of and the discrete logarithm in the divisor class group of
curves.", Mathematics of Computation Vol. 62, No. 206, pp. curves.", Mathematics of Computation Vol. 62, No. 206, pp.
865-874, 1994. 865-874, 1994.
[K1981v2] Knuth, D., "The Art of Computer Programming, Vol. 2: [K1981v2] Knuth, D., "The Art of Computer Programming, Vol. 2:
Seminumerical Algorithms", Addison Wesley , 1981. Seminumerical Algorithms", Addison Wesley , 1981.
[K1987] Koblitz, N., "Elliptic Curve Cryptosystems", Mathematics [K1987] Koblitz, N., "Elliptic Curve Cryptosystems", Mathematics
of Computation Vol. 48, 1987, 203-209, 1987. of Computation Vol. 48, 1987, 203-209, 1987.
[KT1994] Koyama, K. and Y. Tsuruoka, "Digital signature system
based on elliptic curve and signer device and verifier
device for said system", Japanese Unexamined Patent
Application Publication H6-43809, February 18, 1994.
[M1983] Massey, J., "Logarithms in finite cyclic groups - [M1983] Massey, J., "Logarithms in finite cyclic groups -
cryptographic issues", Processings of the 4th Symposium on cryptographic issues", Proceedings of the 4th Symposium on
Information Theory , 1983. Information Theory , 1983.
[M1985] Miller, V., "Use of elliptic curves in cryptography", [M1985] Miller, V., "Use of elliptic curves in cryptography",
Advances in Cryptology - CRYPTO '85 Proceedings Springer Advances in Cryptology - CRYPTO '85 Proceedings Springer
Lecture Notes in Computer Science (LNCS) volume 218, 1985. Lecture Notes in Computer Science (LNCS) volume 218, 1985.
[MOV1993] Menezes, A., Vanstone, S., and T. Okamoto, "Reducing [MOV1993] Menezes, A., Vanstone, S., and T. Okamoto, "Reducing
Elliptic Curve Logarithms to Logarithms in a Finite Elliptic Curve Logarithms to Logarithms in a Finite
Field", IEEE Transactions on Information Theory Vol 39, Field", IEEE Transactions on Information Theory Vol 39,
No. 5, pp. 1639-1646, September, 1993. No. 5, pp. 1639-1646, September, 1993.
skipping to change at page 27, line 10 skipping to change at page 28, line 15
[K1981v3] Knuth, D., "The Art of Computer Programming, Vol. 3: [K1981v3] Knuth, D., "The Art of Computer Programming, Vol. 3:
Sorting and Searching", Addison Wesley , 1981. Sorting and Searching", Addison Wesley , 1981.
[KMOV1991] [KMOV1991]
Koyama, K., Menezes, A., Vanstone, S., and T. Okamoto, Koyama, K., Menezes, A., Vanstone, S., and T. Okamoto,
"New Public-Key Schemes Based on Elliptic Curves over the "New Public-Key Schemes Based on Elliptic Curves over the
Ring Zn", Advances in Cryptology - CRYPTO '91 Ring Zn", Advances in Cryptology - CRYPTO '91
Proceedings Spinger Lecture Notes in Computer Science Proceedings Spinger Lecture Notes in Computer Science
(LNCS) volume 576, 1991. (LNCS) volume 576, 1991.
[KT1994] Koyama, K. and Y. Tsuruoka, "Digital signature system
based on elliptic curve and signer device and verifier
device for said system", Japanese Unexamined Patent
Application Publication H6-43809, 1994.
[LL1997] Lim, C. and P. Lee, "A Key Recovery Attack on Discrete [LL1997] Lim, C. and P. Lee, "A Key Recovery Attack on Discrete
Log-based Schemes Using a Prime Order Subgroup", Advances Log-based Schemes Using a Prime Order Subgroup", Advances
in Cryptology - CRYPTO '97 Proceedings Spinger Lecture in Cryptology - CRYPTO '97 Proceedings Spinger Lecture
Notes in Computer Science (LNCS) volume 1294, 1997. Notes in Computer Science (LNCS) volume 1294, 1997.
[P1363] "Standard Specifications for Public Key Cryptography", [P1363] "Standard Specifications for Public Key Cryptography",
Institute of Electric and Electronic Engineers Institute of Electric and Electronic Engineers
(IEEE) P1363, 2000. (IEEE) P1363, 2000.
[P1978] Pollard, J., "Monte Carlo methods for index computation [P1978] Pollard, J., "Monte Carlo methods for index computation
mod p", Mathematics of Computation Vol. 32, 1978. mod p", Mathematics of Computation Vol. 32, 1978.
[PH1978] Polhig, S. and M. Hellman, "An Improved Algorithm for [PH1978] Pohlig, S. and M. Hellman, "An Improved Algorithm for
Computing Logarithms over GF(p) and its Cryptographic Computing Logarithms over GF(p) and its Cryptographic
Significance", IEEE Transactions on Information Theory Vol Significance", IEEE Transactions on Information Theory Vol
24, pp. 106-110, 1978. 24, pp. 106-110, 1978.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC2409] Harkins, D. and D. Carrel, "The Internet Key Exchange [RFC2409] Harkins, D. and D. Carrel, "The Internet Key Exchange
(IKE)", RFC 2409, November 1998. (IKE)", RFC 2409, November 1998.
[RFC2412] Orman, H., "The OAKLEY Key Determination Protocol", [RFC2412] Orman, H., "The OAKLEY Key Determination Protocol",
RFC 2412, November 1998. RFC 2412, November 1998.
[RFC3979] Bradner, S., "Intellectual Property Rights in IETF [RFC3979] Bradner, S., "Intellectual Property Rights in IETF
Technology", BCP 79, RFC 3979, March 2005. Technology", BCP 79, RFC 3979, March 2005.
[RFC4306] Kaufman, C., "Internet Key Exchange (IKEv2) Protocol", [RFC4306] Kaufman, C., "Internet Key Exchange (IKEv2) Protocol",
RFC 4306, December 2005. RFC 4306, December 2005.
[RFC4753] Fu, D. and J. Solinas, "ECP Groups For IKE and IKEv2", [RFC4753] Fu, D. and J. Solinas, "ECP Groups For IKE and IKEv2",
RFC 4753, January 2007. RFC 4753, January 2007.
[RFC4879] Narten, T., "Clarification of the Third Party Disclosure [RFC4879] Narten, T., "Clarification of the Third Party Disclosure
Procedure in RFC 3979", BCP 79, RFC 4879, April 2007. Procedure in RFC 3979", BCP 79, RFC 4879, April 2007.
[SuiteB] "NSA Suite B Cryptography", Web Page http://www.nsa.gov/
ia/programs/suiteb_cryptography/index.shtml.
[V1996] Vaudenay, S., "Hidden Collisions on DSS", Advances in [V1996] Vaudenay, S., "Hidden Collisions on DSS", Advances in
Cryptology - CRYPTO '96 Proceedings Spinger Lecture Notes Cryptology - CRYPTO '96 Proceedings Spinger Lecture Notes
in Computer Science (LNCS) volume 1109, 1996. in Computer Science (LNCS) volume 1109, 1996.
[VW1994] van Oorschot, P. and M. Wiener, "Parallel Collision Search
with Application to Hash Functions and Discrete
Logarithms", Proceedings of the 2nd ACM Conference on
Computer and communications security pp. 210-218, 1994.
[VW1996] van Oorschot, P. and M. Wiener, "On Diffie-Hellman key [VW1996] van Oorschot, P. and M. Wiener, "On Diffie-Hellman key
agreement with short exponents", Advances in Cryptology - agreement with short exponents", Advances in Cryptology -
EUROCRYPT '96 Proceedings Spinger Lecture Notes in EUROCRYPT '96 Proceedings Spinger Lecture Notes in
Computer Science (LNCS) volume 1070, 1996. Computer Science (LNCS) volume 1070, 1996.
[X9.62] "Public Key Cryptography for the Financial Services [X9.62] "Public Key Cryptography for the Financial Services
Industry: The Elliptic Curve Digital Signature Algorithm Industry: The Elliptic Curve Digital Signature Algorithm
(ECDSA)", American National Standards Institute (ANSI) (ECDSA)", American National Standards Institute (ANSI)
X9.62. X9.62.
Appendix A. Random Number Generation Appendix A. Key Words
The definitions of these key words are quoted from [RFC2119] and are
commonly used in Internet standards. They are reproduced in this
note in order to avoid a normative reference from after 1994.
1. MUST - This word, or the terms "REQUIRED" or "SHALL", mean that
the definition is an absolute requirement of the specification.
2. MUST NOT - This phrase, or the phrase "SHALL NOT", mean that the
definition is an absolute prohibition of the specification.
3. SHOULD - This word, or the adjective "RECOMMENDED", mean that
there may exist valid reasons in particular circumstances to
ignore a particular item, but the full implications must be
understood and carefully weighed before choosing a different
course.
4. SHOULD NOT - This phrase, or the phrase "NOT RECOMMENDED" mean
that there may exist valid reasons in particular circumstances
when the particular behavior is acceptable or even useful, but
the full implications should be understood and the case carefully
weighed before implementing any behavior described with this
label.
5. MAY - This word, or the adjective "OPTIONAL", mean that an item
is truly optional. One vendor may choose to include the item
because a particular marketplace requires it or because the
vendor feels that it enhances the product while another vendor
may omit the same item. An implementation which does not include
a particular option MUST be prepared to interoperate with another
implementation which does include the option, though perhaps with
reduced functionality. In the same vein an implementation which
does include a particular option MUST be prepared to interoperate
with another implementation which does not include the option
(except, of course, for the feature the option provides.)
Appendix B. Random Number Generation
It is easy to generate an integer uniformly at random between zero It is easy to generate an integer uniformly at random between zero
and 2^t, for some positive integer t. Generate a random bit string and 2^t -1, inclusive, for some positive integer t. Generate a
that contains exactly t bits, and then convert the bit string to a random bit string that contains exactly t bits, and then convert the
non-negative integer by treating the bits as the coefficients in a bit string to a non-negative integer by treating the bits as the
base-two expansion of an integer. coefficients in a base-two expansion of an integer.
It is sometimes necessary to generate an integer r uniformly at It is sometimes necessary to generate an integer r uniformly at
random so that r satisfies a certain property P, for example, lying random so that r satisfies a certain property P, for example, lying
within a certain interval. A simple way to do this is with the within a certain interval. A simple way to do this is with the
rejection method: rejection method:
1. Generate a candidate number c uniformly at random from a set that 1. Generate a candidate number c uniformly at random from a set that
includes many numbers that satisfy property P. includes all numbers that satisfy property P (plus some other
numbers, preferably not too many)
2. If c satisfies property P, then return c. Otherwise, return to 2. If c satisfies property P, then return c. Otherwise, return to
Step 1. Step 1.
For example, to generate a number between 1 and n-1, repeatedly For example, to generate a number between 1 and n-1, inclusive,
generate integers between zero and 2^t, stopping at the first integer repeatedly generate integers between zero and 2^t - 1, inclusive,
that falls within that interval. stopping at the first integer that falls within that interval.
Appendix B. Example Elliptic Curve Group Appendix C. Example Elliptic Curve Group
For concreteness, we recall an elliptic curve defined by Solinas and For concreteness, we recall an elliptic curve defined by Solinas and
Yu in [RFC4753] and referred to as P-256, which is believed to Yu in [RFC4753] and referred to as P-256, which is believed to
provide a 128-bit security level. We use the notation of provide a 128-bit security level. We use the notation of
Section 3.2, and express the generator in the affine coordinate Section 3.2, and express the generator in the affine coordinate
representation g=(gx,gy), where the values gx and gy are in Zp. representation g=(gx,gy), where the values gx and gy are in Fp.
p: FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF p: FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
a: - 3 a: - 3
b: 5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B b: 5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
n: FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551 n: FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551
gx: 6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296 gx: 6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
 End of changes. 92 change blocks. 
190 lines changed or deleted 269 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/