< draft-mcgrew-fundamental-ecc-02.txt   draft-mcgrew-fundamental-ecc-03.txt >
Network Working Group D. McGrew Network Working Group D. McGrew
Internet-Draft Cisco Systems Internet-Draft Cisco Systems
Intended status: Informational K. Igoe Intended status: Informational K. Igoe
Expires: August 23, 2010 National Security Agency Expires: November 22, 2010 M. Salter
February 19, 2010 National Security Agency
May 21, 2010
Fundamental Elliptic Curve Cryptography Algorithms Fundamental Elliptic Curve Cryptography Algorithms
draft-mcgrew-fundamental-ecc-02.txt draft-mcgrew-fundamental-ecc-03.txt
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 for implementing the fundamental These descriptions may be useful for implementing the fundamental
algorithms without using any of the specialized methods that were algorithms without using any of the specialized methods that were
developed in following years. Only elliptic curves defined over developed in following years. Only elliptic curves defined over
fields of characteristic greater than three are in scope; these fields of characteristic greater than three are in scope; these
curves are those used in Suite B. curves are those used in Suite B.
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 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). Note that other groups may also distribute
other groups may also distribute working documents as Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
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 This Internet-Draft will expire on November 22, 2010.
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on August 23, 2010.
Copyright Notice Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the Copyright (c) 2010 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 Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. Conventions Used In This Document . . . . . . . . . . . . 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 . . . . . . . . . . . . . . . . . . . . . . 7 2.3. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 7
3. Elliptic Curve Groups . . . . . . . . . . . . . . . . . . . . 7 3. Elliptic Curve Groups . . . . . . . . . . . . . . . . . . . . 7
3.1. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 8 3.1. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 8
3.2. Other Coordinates . . . . . . . . . . . . . . . . . . . . 9 3.2. Other Coordinates . . . . . . . . . . . . . . . . . . . . 9
3.3. ECC Parameters . . . . . . . . . . . . . . . . . . . . . . 9 3.3. ECC Parameters . . . . . . . . . . . . . . . . . . . . . . 9
3.3.1. Security . . . . . . . . . . . . . . . . . . . . . . . 10 3.3.1. Discriminant . . . . . . . . . . . . . . . . . . . . . 10
4. Elliptic Curve Diffie-Hellman (ECDH) . . . . . . . . . . . . . 10 3.3.2. Security . . . . . . . . . . . . . . . . . . . . . . . 10
4. Elliptic Curve Diffie-Hellman (ECDH) . . . . . . . . . . . . . 11
4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 11 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2. Compact Representation . . . . . . . . . . . . . . . . . . 11 4.2. Compact Representation . . . . . . . . . . . . . . . . . . 11
5. Elliptic Curve ElGamal Signatures . . . . . . . . . . . . . . 12 5. Elliptic Curve ElGamal Signatures . . . . . . . . . . . . . . 12
5.1. Background . . . . . . . . . . . . . . . . . . . . . . . . 12 5.1. Background . . . . . . . . . . . . . . . . . . . . . . . . 12
5.2. Hash Functions . . . . . . . . . . . . . . . . . . . . . . 12 5.2. Hash Functions . . . . . . . . . . . . . . . . . . . . . . 12
5.3. KT-IV Signatures . . . . . . . . . . . . . . . . . . . . . 13 5.3. KT-IV Signatures . . . . . . . . . . . . . . . . . . . . . 13
5.3.1. Keypair Generation . . . . . . . . . . . . . . . . . . 13 5.3.1. Keypair Generation . . . . . . . . . . . . . . . . . . 13
5.3.2. Signature Creation . . . . . . . . . . . . . . . . . . 13 5.3.2. Signature Creation . . . . . . . . . . . . . . . . . . 13
5.3.3. Signature Verification . . . . . . . . . . . . . . . . 13 5.3.3. Signature Verification . . . . . . . . . . . . . . . . 14
5.4. KT-I Signatures . . . . . . . . . . . . . . . . . . . . . 14 5.4. KT-I Signatures . . . . . . . . . . . . . . . . . . . . . 14
5.4.1. Keypair Generation . . . . . . . . . . . . . . . . . . 14 5.4.1. Keypair Generation . . . . . . . . . . . . . . . . . . 14
5.4.2. Signature Creation . . . . . . . . . . . . . . . . . . 14 5.4.2. Signature Creation . . . . . . . . . . . . . . . . . . 14
5.4.3. Signature Verification . . . . . . . . . . . . . . . . 15 5.4.3. Signature Verification . . . . . . . . . . . . . . . . 15
5.5. Converting KT-IV signatures to KT-I signatures . . . . . . 15 5.5. Converting KT-IV signatures to KT-I signatures . . . . . . 15
5.6. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 15 5.6. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 16
6. Interoperability . . . . . . . . . . . . . . . . . . . . . . . 17 6. Converting between integers and octet strings . . . . . . . . 17
6.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 6.1. Octet-string-to-integer conversion . . . . . . . . . . . . 17
6.2. KT-I and ECDSA . . . . . . . . . . . . . . . . . . . . . . 17 6.2. Integer-to-octet-string conversion . . . . . . . . . . . . 17
7. Validating an Implementation . . . . . . . . . . . . . . . . . 18 7. Interoperability . . . . . . . . . . . . . . . . . . . . . . . 18
7.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 7.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
7.2. KT-I . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 7.2. KT-I and ECDSA . . . . . . . . . . . . . . . . . . . . . . 18
8. Intellectual Property . . . . . . . . . . . . . . . . . . . . 19 8. Validating an Implementation . . . . . . . . . . . . . . . . . 19
8.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . 19 8.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
8.2. KT-I . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
9. Security Considerations . . . . . . . . . . . . . . . . . . . 20 9. Intellectual Property . . . . . . . . . . . . . . . . . . . . 20
9.1. Subgroups . . . . . . . . . . . . . . . . . . . . . . . . 20 9.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . 21
9.2. Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . 21 10. Security Considerations . . . . . . . . . . . . . . . . . . . 21
9.3. Group Representation and Security . . . . . . . . . . . . 21 10.1. Subgroups . . . . . . . . . . . . . . . . . . . . . . . . 22
9.4. Signatures . . . . . . . . . . . . . . . . . . . . . . . . 22 10.2. Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . 22
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22 10.3. Group Representation and Security . . . . . . . . . . . . 22
11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 22 10.4. Signatures . . . . . . . . . . . . . . . . . . . . . . . . 23
12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 23 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23
12.1. Normative References . . . . . . . . . . . . . . . . . . . 23 12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 24
12.2. Informative References . . . . . . . . . . . . . . . . . . 24 13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Appendix A. Key Words . . . . . . . . . . . . . . . . . . . . . . 27 13.1. Normative References . . . . . . . . . . . . . . . . . . . 24
Appendix B. Random Integer Generation . . . . . . . . . . . . . . 27 13.2. Informative References . . . . . . . . . . . . . . . . . . 25
Appendix C. Why Compact Representation Works . . . . . . . . . . 28 Appendix A. Key Words . . . . . . . . . . . . . . . . . . . . . . 28
Appendix D. Example ECC Parameter Set . . . . . . . . . . . . . . 29 Appendix B. Random Integer Generation . . . . . . . . . . . . . . 29
Appendix E. Additive and multiplicative notation . . . . . . . . 29 Appendix C. Why Compact Representation Works . . . . . . . . . . 30
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 30 Appendix D. Example ECC Parameter Set . . . . . . . . . . . . . . 30
Appendix E. Additive and multiplicative notation . . . . . . . . 31
Appendix F. Algorithms . . . . . . . . . . . . . . . . . . . . . 31
F.1. Affine Coordinates . . . . . . . . . . . . . . . . . . . . 32
F.2. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 32
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 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 the
Diffie-Hellman key exchange protocol [DH1976] and Elliptic Curve Diffie-Hellman key exchange protocol [DH1976] and Elliptic Curve
versions of the ElGamal Signature Algorithm [E1985]. The adoption of versions of the ElGamal Signature Algorithm [E1985]. The adoption of
ECC has been slower than had been anticipated, perhaps due to the ECC has been slower than had been anticipated, perhaps due to the
lack of freely available normative documents and uncertainty over lack of freely available normative documents and uncertainty over
intellectual property rights. intellectual property rights.
This note contains a description of the fundamental algorithms of ECC This note contains a description of the fundamental algorithms of ECC
over fields with characteristic greater than three, based directly on over fields with characteristic greater than three, based directly on
original references. Its intent is to provide the Internet community original references. Its intent is to provide the Internet community
with a summary of the basic algorithms that predate any specialized with a summary of the basic algorithms that predate any specialized
or optimized algorithms, which can be used as a normative or optimized algorithms, which can be used as a normative
specification. The original descriptions and notations were followed specification. The original descriptions and notations were followed
as closely as possible. as closely as possible.
There are several standards that specify or incorporate ECC There are several standards that specify or incorporate ECC
algorithms, including the Internet Key Exchange (IKE), ANSI X9.62, algorithms, including the Internet Key Exchange (IKE), ANSI X9.62,
and IEEE P1363. The algorithms in this note can interoperate with and IEEE P1363. The algorithms in this note can interoperate with
some of the algorithms in these standards, with a suitable choice of some of the algorithms in these standards, with a suitable choice of
parameters and options. The specifics are itemized in Section 6. parameters and options. The specifics are itemized in Section 7.
The rest of the note is organized as follows. Section 2.1, The rest of the note is organized as follows. Section 2.1,
Section 2.2, and Section 2.3 furnish the necessary terminology and Section 2.2, and Section 2.3 furnish the necessary terminology and
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 presents the fundamental ECDH algorithm. Section 5 three. Section 4 presents the fundamental ECDH algorithm. Section 5
presents elliptic curve versions of the ElGamal signature method. presents elliptic curve versions of the ElGamal signature method.
Sections 2 through 5, inclusive, contain all of the normative text The representation of integers as octet strings is specified in
(the text that defines the norm for implementations conforming to Section 6. Sections 2 through 6, inclusive, contain all of the
this specification), and all of the following sections are purely normative text (the text that defines the norm for implementations
informative. Interoperability is discussed in Section 6. Validation conforming to this specification), and all of the following sections
testing is described in Section 7. Section 8 reviews intellectual are purely informative. Interoperability is discussed in Section 7.
property issues. Section 9 summarizes security considerations. Validation testing is described in Section 8. Section 9 reviews
Appendix B describes random number generation, and other appendices intellectual property issues. Section 10 summarizes security
provide clarifying details. considerations. Appendix B describes random number generation, and
other appendices provide clarifying details.
1.1. Conventions Used In This Document 1.1. Conventions Used In This Document
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in Appendix A. 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
skipping to change at page 6, line 34 skipping to change at page 6, line 34
denoted as -a.) denoted as -a.)
For any positive integer X, a^(-X) is defined to be (a^-1)^(X). For any positive integer X, a^(-X) is defined to be (a^-1)^(X).
Using this convention, exponentiation behaves as one would expect, Using this convention, exponentiation behaves as one would expect,
namely for any integers X and Y: namely for any integers X and Y:
a^(X+Y) = (a^X)*(a^Y) a^(X+Y) = (a^X)*(a^Y)
(a^X)^Y = a^(XY) = (a^Y)^X. (a^X)^Y = a^(XY) = (a^Y)^X.
A group element a is said to have finite order if a^X = e for some In cryptographic applications one typically deals with finite groups
positive integer X, and the order of a is the smallest such X. If no (groups with a finite number of elements), and for such groups, the
such X exists, a is said to have infinite order. In cryptographic number of elements of the group is also called the order of the
applications one typically deals with finite groups (groups with a group. A group element a is said to have finite order if a^X = e for
finite number of elements), and all elements of finite groups have some positive integer X, and the order of a is the smallest such X.
finite order. If a group element a has order R, then for any If no such X exists, a is said to have infinite order. All elements
integers X and Y, of a finite group have a finite order, and the order of an element is
always a divisor of the group order.
If a group element a has order R, then for any integers X and Y,
a^X = a^(X mod R), a^X = a^(X mod R),
a^X = a^Y if and only if X is congruent to Y mod R, a^X = a^Y if and only if X is congruent to Y mod R,
the set H = { a, a^2, a^3, ... , a^R=e } forms a subgroup of G, the set H = { a, a^2, a^3, ... , a^R=e } forms a subgroup of G,
called the cyclic subgroup generated by a, and a is said to be a called the cyclic subgroup generated by a, and a is said to be a
generator of H. generator of H.
Typically there are several group elements that generate H. Any group Typically there are several group elements that generate H. Any group
skipping to change at page 7, line 22 skipping to change at page 7, line 25
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 addition, When p is a prime number, then the set Zp, with the addition,
subtraction, multiplication and division operations, is a finite subtraction, multiplication and division operations, is a finite
field with characteristic p. Each nonzero element x in Zp has an field with characteristic p. Each nonzero element x in Zp has an
inverse 1/x. There is a one-to-one correspondence between 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 integers between zero and p-1, inclusive, and the elements of the
field. The field Zp is sometimes denoted as Fp. field. The field Zp is sometimes denoted as Fp or GF(p).
Equations involving field elements do not explicitly denote the "mod Equations involving field elements do not explicitly denote the "mod
p" 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 the set is equivalent to the statement that x, y, and z are in the set
{ 0, 1, ..., p-1 } and { 0, 1, ..., p-1 } and
skipping to change at page 7, line 46 skipping to change at page 7, line 49
This note only covers elliptic curves over fields with characteristic This note only covers elliptic curves over fields with characteristic
greater than three; these are the curves used in Suite B [SuiteB]. greater than three; these are the curves used in Suite B [SuiteB].
For other fields, the definition of the elliptic curve group would be For other fields, the definition of the elliptic curve group would be
different. different.
An elliptic curve over a field Fp is defined by the curve equation An elliptic curve over a field Fp 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 [M1985] and the
on an elliptic curve is a pair (x,y) of values in Fp that satisfy the discriminant is nonzero (as described in Section 3.3.1). A point on
curve equation, such that x and y are both in Fp, or it is a special an elliptic curve is a pair (x,y) of values in Fp that satisfies the
point (@,@) that represents the identity element (which is called the curve equation, or it is a special point (@,@) that represents the
"point at infinity"). The order of an elliptic curve group is the identity element (which is called the "point at infinity"). The
number of distinct points. order of an elliptic curve group is the 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. The 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 point at inverse of the point (x1,y1) is the point (x1,-y1). The point at
infinity is its own inverse. infinity is its own inverse.
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 and y1 is equal to 0, (x3,y3) = (@,@) when P is equal to Q and y1 is equal to 0,
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 and y1 is y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y1 if P is equal to Q and y1 is
not equal to 0. 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 must reduce the field Fp; thus, computation of x3 and y3 in practice must reduce
the right-hand-side modulo p. the right-hand-side modulo p. Pseudocode for the group operation is
provided in Appendix F.1.
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.
skipping to change at page 9, line 32 skipping to change at page 9, line 36
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) mod p 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 mod p Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3 mod p
Z3 = 8 * (Y1 * Z1)^3 mod p Z3 = 8 * (Y1 * Z1)^3 mod p
where w = 3 * X1^2 + a * Z1^2 mod p. In the above equations, a, u, where w = 3 * X1^2 + a * Z1^2 mod p. In the above equations, a, u,
v, w, X1, X2, X3, Y1, Y2, Y3, Z1, Z2, and Z3 are integers in the set v, w, X1, X2, X3, Y1, Y2, Y3, Z1, Z2, and Z3 are integers in the set
Fp. Fp. Pseudocode for the group operation in homogeneous coordinates is
provided in Appendix F.2.
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. Other Coordinates 3.2. Other Coordinates
Some other coordinate systems have been described; several are Some other coordinate systems have been described; several are
documented in [CC1986], including Jacobi coordinates. documented in [CC1986], including Jacobi coordinates.
skipping to change at page 10, line 17 skipping to change at page 10, line 20
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 subgroup. The generator g of the subgroup.
The order n of the subgroup generated by g. The order n of the subgroup generated by g.
An example of an ECC parameter set is provided in Appendix D. An example of an ECC parameter set is provided in Appendix D.
Parameter generation is out of scope for this note.
Each elliptic curve point is associated with a particular parameter Each elliptic curve point is associated with a particular parameter
set. The elliptic curve group operation is only defined between two set. The elliptic curve group operation is only defined between two
points in the same group. It is an error to apply the group points in the same group. It is an error to apply the group
operation to two elements that are from different groups, or to apply operation to two elements that are from different groups, or to apply
the group operation to a pair of coordinates that is not a valid the group operation to a pair of coordinates that is not a valid
point. (A pair (x,y) of coordinates in Fp is a valid point only when point. (A pair (x,y) of coordinates in Fp is a valid point only when
they satisfy the curve equation.) See Section 9.3 for further they satisfy the curve equation.) See Section 10.3 for further
information. information.
3.3.1. Discriminant
For each elliptic curve group, the discriminant - 16*(4*a^3 + 27*b^2) For each elliptic curve group, the discriminant - 16*(4*a^3 + 27*b^2)
must be nonzero modulo p. must be nonzero modulo p [S1986]; this requires that
Parameter generation is out of scope for this note. 4*a^3 + 27*b^2 != 0 mod p.
3.3.1. Security 3.3.2. 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 informative guidance. Section 10 for informative guidance.
The order of the group generated by g MUST 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 solutions 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
skipping to change at page 11, line 22 skipping to change at page 11, line 29
chooses an exponent j between 1 and t-1, inclusive, uniformly at chooses an exponent j between 1 and t-1, inclusive, uniformly at
random, computes g^j and sends that element to B. Party B chooses an random, computes g^j and sends that element to B. Party B chooses an
exponent k between 1 and t-1, inclusive, uniformly at random, exponent k between 1 and t-1, inclusive, uniformly at random,
computes g^k and sends that element to A. Each party can compute computes g^k and sends that element to A. Each party can compute
g^(j*k); party A computes (g^k)^j, and party B computes (g^j)^k. g^(j*k); party A computes (g^k)^j, and party B computes (g^j)^k.
See Appendix B regarding generation of random integers. See Appendix B regarding generation of random integers.
4.1. Data Types 4.1. Data Types
An ECDH private key z is an integer in Zt.
The corresponding ECDH public key Y is the group element, where Y =
g^z. Each public key is associated with a particular particular
parameter set as per Section 3.3.
The shared secret computed by both parties is a group element.
Each run of the ECDH protocol is associated with a particular Each run of the ECDH protocol is associated with a particular
parameter set, and both of the public keys and the shared secret are parameter set (as defined in Section 3.3), and the public keys g^j
elements of that group. and g^k and the shared secret g^(j*k) are elements of the cyclic
subgroup associated with the parameter set.
An ECDH private key z is an integer in Zt, where t is the order of
the subgroup.
4.2. Compact Representation 4.2. Compact Representation
As described in the final paragraph of [M1985], the x-coordinate of As described in the final paragraph of [M1985], the x-coordinate of
the shared secret value g^(j*k) is a suitable representative for the the shared secret value g^(j*k) is a suitable representative for the
entire point whenever exponentiation is used as a one-way function. entire point whenever exponentiation is used as a one-way function.
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.
skipping to change at page 12, line 25 skipping to change at page 12, line 29
use other finite groups, such as the multiplicative group of the use other finite groups, such as the multiplicative group of the
field GF(2^w) [AMV1990] or an elliptic curve group [A1992]. field GF(2^w) [AMV1990] or an elliptic curve group [A1992].
An ElGamal signature consists of a pair of components. There are An ElGamal signature consists of a pair of components. There are
many possible generalizations of ElGamal signature methods that have many possible generalizations of ElGamal signature methods that have
been obtained by different rearrangements of the equation for the been obtained by different rearrangements of the equation for the
second component; see [HMP1994], [HP1994], [NR1994], [A1992], and second component; see [HMP1994], [HP1994], [NR1994], [A1992], and
[AMV1990]. These generalizations are independent of the mathematical [AMV1990]. These generalizations are independent of the mathematical
group used, and have been described for the multiplicative group group used, and have been described for the multiplicative group
modulo a prime number, the multiplicative group of GF(2^w), and modulo a prime number, the multiplicative group of GF(2^w), and
elliptic curve groups [HMP1994][NR1994] [AMV1990][A1992]. elliptic curve groups [HMP1994][NR1994][AMV1990][A1992].
The Digital Signature Algorithm (DSA) [FIPS186] is an important The Digital Signature Algorithm (DSA) [FIPS186] is an important
ElGamal signature variant. ElGamal signature variant.
5.2. Hash Functions 5.2. Hash Functions
ElGamal signatures must use a collision-resistant hash function, so ElGamal signatures must use a collision-resistant hash function, so
that it can sign messages of arbitrary length and can avoid that it can sign messages of arbitrary length and can avoid
existential forgery attacks; see Section 9.4. (This is true for all existential forgery attacks; see Section 10.4. (This is true for all
ElGamal variants [HMP1994].) We denote the hash function as h(). ElGamal variants [HMP1994].) We denote the hash function as h().
Its input is a bit string of arbitrary length, and its output is a Its input is a bit string of arbitrary length, and its output is a
non-negative integer. non-negative integer.
Let H() denote a hash function whose output is a fixed-length bit Let H() denote a hash function whose output is a fixed-length bit
string. To use H in an ElGamal signature method, we define the string. To use H in an ElGamal signature method, we define the
mapping between that output and the non-negative integers; this mapping between that output and the non-negative integers; this
realizes the function h() described above. Given a bit string m, the realizes the function h() described above. Given a bit string m, the
function h(m) is computed as follows: function h(m) is computed as follows:
skipping to change at page 13, line 13 skipping to change at page 13, line 18
of i. of i.
5.3. KT-IV Signatures 5.3. KT-IV Signatures
Koyama and Tsuruoka described a signature method based on Elliptic Koyama and Tsuruoka described a signature method based on Elliptic
Curve ElGamal, in which the first signature component is the Curve ElGamal, in which the first signature component is the
x-coordinate of an elliptic curve point reduced modulo q [KT1994]. x-coordinate of an elliptic curve point reduced modulo q [KT1994].
In this section we recall that method, which we refer to as KT-IV. In this section we recall that method, which we refer to as KT-IV.
The algorithm uses an elliptic curve group, as described in The algorithm uses an elliptic curve group, as described in
Section 3.3, with prime field order p, and curve equation parameters Section 3.3, with prime field order p and curve equation parameters a
a and b. We denote the generator as alpha, and the order of the and b. We denote the generator as alpha, and the order of the
generator as q. We follow [FIPS186] in checking for exceptional generator as q. We follow [FIPS186] in checking for exceptional
cases. cases.
5.3.1. Keypair Generation 5.3.1. Keypair Generation
The private key z is an integer between 1 and q - 1, inclusive, The private key z is an integer between 1 and q - 1, inclusive,
generated uniformly at random. (See Appendix B regarding random generated uniformly at random. (See Appendix B regarding random
integers.) The public key is the group element integers.) The public key is the group element
Y = alpha^z. Each public key is associated with a particular Y = alpha^z. Each public key is associated with a particular
particular parameter set as per Section 3.3. particular parameter set as per Section 3.3.
skipping to change at page 13, line 38 skipping to change at page 13, line 43
To compute a KT-IV signature for a message m using the private key z: To compute a KT-IV signature for a message m using the private key z:
1. Choose an integer k uniformly at random from the set of all 1. Choose an integer k uniformly at random from the set of all
integers between 1 and q-1, inclusive. (See Appendix B regarding integers between 1 and q-1, inclusive. (See Appendix B regarding
random integers.) random integers.)
2. Calculate R = (r_x, r_y) = alpha^k. 2. Calculate R = (r_x, r_y) = alpha^k.
3. Calculate s1 = r_x mod q. 3. Calculate s1 = r_x mod q.
4. Calculate s2 = k / (h(m) + z * s1) mod q. 4. Check if h(m) + z * s1 = 0 mod q; if so, a new value of k MUST be
generated and the signature MUST be recalculated. As an option,
one MAY check if s1 = 0; if so, a new value of k SHOULD be
generated and the signature SHOULD be recalculated. (It is
extremely unlikely that s1 = 0 or h(m) + z * s1 = 0 mod q if
signatures are generated properly.)
5. As an option, one MAY check if s1 = 0 or s2 = 0. If either 5. Calculate s2 = k / (h(m) + z * s1) mod q.
s1 = 0 or s2 = 0, a new value of k SHOULD be generated and the
signature SHOULD be recalculated. (It is extremely unlikely that
s1 = 0 or s2 = 0 if signatures are generated properly.)
The signature is the ordered pair (s1, s2). Both signature The signature is the ordered pair (s1, s2). Both signature
components are non-negative integers. components are non-negative integers.
5.3.3. Signature Verification 5.3.3. Signature Verification
Given the message m, the public key Y, and the signature (s1, s2) Given the message m, the public key Y, and the signature (s1, s2)
verification is as follows: verification is as follows:
1. Check to see that 0 < s1 < q and 0 < s2 < q; if either condition 1. Check to see that 0 < s1 < q and 0 < s2 < q; if either condition
skipping to change at page 16, line 27 skipping to change at page 16, line 36
The signature method of [KT1994] and Section 5.3 is an EG-IV.1 The signature method of [KT1994] and Section 5.3 is an EG-IV.1
method, with A = m * s, B = - r * s, C = 1. Its signature equation method, with A = m * s, B = - r * s, C = 1. Its signature equation
is is
m * s = - r * s * z + k (mod q) m * s = - r * s * z + k (mod q)
The functions f and g mentioned in Table 1 are merely multiplication, The functions f and g mentioned in Table 1 are merely multiplication,
as described under the heading "Fifth generalization". as described under the heading "Fifth generalization".
No hash function is shown in the above equations, but as described in No hash function is shown in the above equations, but as described in
Section 9.4, a hash function should be applied to the message prior Section 10.4, a hash function should be applied to the message prior
to signing in order to prevent existential forgery attacks. to signing in order to prevent existential forgery attacks.
Nyberg and Rueppel [NR1994] studied many different ElGamal signature Nyberg and Rueppel [NR1994] studied many different ElGamal signature
methods, and defined "strong equivalence" as follows: methods, and defined "strong equivalence" as follows:
Two signature methods are called strongly equivalent if the Two signature methods are called strongly equivalent if the
signature of the first scheme can be transformed efficiently into signature of the first scheme can be transformed efficiently into
signatures of the second scheme and vice versa, without knowledge signatures of the second scheme and vice versa, without knowledge
of the private key. of the private key.
skipping to change at page 17, line 5 skipping to change at page 17, line 12
exceptional case and the case that s1=0. The s2=0 check was exceptional case and the case that s1=0. The s2=0 check was
suggested by Rivest [R1992] and is discussed in [BS1992]. suggested by Rivest [R1992] and is discussed in [BS1992].
[KT1994] uses "a positive integer q' that does not exceed q" when [KT1994] uses "a positive integer q' that does not exceed q" when
computing the signature component s1 from the x-coordinate r_x of the computing the signature component s1 from the x-coordinate r_x of the
elliptic curve point R = (r_x, r_y). The value q' is also used elliptic curve point R = (r_x, r_y). The value q' is also used
during signature validation when comparing the x-coordinate of a during signature validation when comparing the x-coordinate of a
computed elliptic curve point to the value to s1. In this note, we computed elliptic curve point to the value to s1. In this note, we
use the simplifying convention that q' = q. use the simplifying convention that q' = q.
6. Interoperability 6. Converting between integers and octet strings
A method for the conversion between integers and octet strings is
specified in this section, following the established conventions of
public key cryptography [R1993]. This method allows integers to be
represented as octet strings that are suitable for transmission or
storage. This method SHOULD be used when representing an elliptic
curve point or an elliptic curve coordinate as they are defined in
this note.
6.1. Octet-string-to-integer conversion
The octet string S shall be converted to an integer x as follows.
Let S1, ..., Sk be the octets of S from first to last. Then the
integer x shall satisfy
k
x = SUM 2^(8(k-i)) Si .
i = 1
In other words, the first octet of S has the most significance in the
integer and the last octet of S has the least significance.
Note: the integer x satisfies 0 <= x < 2^(8*k).
6.2. Integer-to-octet-string conversion
The integer x shall be converted to an octet string S of length k as
follows. The string S shall satisfy
k
y = SUM 2^(8(k-i)) Si .
i = 1
where S1, ..., Sk are the octets of S from first to last.
In other words, the first octet of S has the most significance in the
integer and the last octet of S has the least significance.
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
algorithm. algorithm.
6.1. ECDH 7.1. ECDH
Section 4 can be used with the Internet Key Exchange (IKE) versions Section 4 can be used with the Internet Key Exchange (IKE) versions
one [RFC2409] or two [RFC4306]. These algorithms are compatible with one [RFC2409] or two [RFC4306]. These algorithms are compatible with
the ECP groups defined by [RFC4753], [RFC2409], and [RFC2412]. The the ECP groups defined by [RFC4753], [RFC5114], [RFC2409], and
group definition used in this protocol uses an affine coordinate [RFC2412]. The group definition in this protocol uses an affine
representation of the public key and uses neither the compact output coordinate representation of the public key and uses neither the
nor the compact representation of Section 4.2. Note that some groups compact output nor the compact representation of Section 4.2.
use a negative curve parameter "a" and express this fact in the curve [RFC4753] describes data formats that are compatible with those of
equation rather than in the parameter. The test cases in Section 8 Section 6. Note that some groups indicate that the curve parameter
of [RFC4753] can be used to test an implementation; these cases use "a" is negative; these values are to be interpreted modulo the order
the multiplicative notation, as does this note. The KEi and KEr of the field. For example, a parameter of a = -3 is equal to p - 3,
payloads are equal to g^j and g^k, respectively, with 64 bits of where p is the order of the field. The test cases in Section 8 of
encoding data prepended to them. [RFC4753] can be used to test an implementation; these cases use the
multiplicative notation, as does this note. The KEi and KEr payloads
are equal to g^j and g^k, 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. IEEE P1363 ECDH can be used in a characteristic greater than three. IEEE P1363 ECDH can be used in a
manner that will interoperate with this note, with the following manner that will interoperate with this note, with the following
options and parameter choices from that specification: options and parameter choices from that specification:
prime curves with a cofactor of 1, prime curves with a cofactor of 1,
the ECSVDP-DH primitive, and the ECSVDP-DH primitive, and
the Key Derivation Function must be the "identity" function the Key Derivation Function must be the "identity" function
(equivalently, the KDF step should be omitted and the shared (equivalently, the KDF step should be omitted and the shared
secret value should be output directly). secret value should be output directly).
6.2. KT-I and ECDSA 7.2. KT-I 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 with large prime order [DSA1991][FIPS186]. The Elliptic Curve field with 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.
KT-I is mathematically and functionally equivalent to ECDSA, and can KT-I is mathematically and functionally equivalent to ECDSA, and can
interoperate with the IEEE [P1363] and ANSI [X9.62] standards for interoperate with the IEEE [P1363] and ANSI [X9.62] standards for
Elliptic Curve DSA (ECDSA) based on fields of characteristic greater Elliptic Curve DSA (ECDSA) based on fields of characteristic greater
than three. KT-I signatures can be verified using the ECDSA than three. KT-I signatures can be verified using the ECDSA
verification algorithm, and ECDSA signatures can be verified using verification algorithm, and ECDSA signatures can be verified using
the KT-I verification algorithm. the KT-I verification algorithm.
7. Validating an Implementation 8. Validating an Implementation
It is essential to validate the implementation of a cryptographic It is essential to validate the implementation of a cryptographic
algorithm. This section outlines tests that should be performed on algorithm. This section outlines tests that should be performed on
the algorithms defined in this note. the algorithms defined in this note.
A known answer test, or KAT, uses a fixed set of inputs to test an A known answer test, or KAT, uses a fixed set of inputs to test an
algorithm; the output of the algorithm is compared with the expected algorithm; the output of the algorithm is compared with the expected
output, which is also a fixed value. KATs for ECDH and KT-I are set output, which is also a fixed value. KATs for ECDH and KT-I are set
out in the following subsections. out in the following subsections.
skipping to change at page 18, line 29 skipping to change at page 19, line 32
output of the first algorithm. A signature creation algorithm can be output of the first algorithm. A signature creation algorithm can be
tested for consistency against a signature verification algorithm. tested for consistency against a signature verification algorithm.
Implementations of KT-I should be tested in this way. Their Implementations of KT-I should be tested in this way. Their
signature generation processes are non-deterministic, and thus cannot signature generation processes are non-deterministic, and thus cannot
be tested using a KAT. Signature verification algorithms, on the be tested using a KAT. Signature verification algorithms, on the
other hand, are deterministic and should be tested via a KAT. This other hand, are deterministic and should be tested via a KAT. This
combination of tests provides coverage for all of the operations, combination of tests provides coverage for all of the operations,
including keypair generation. Consistency testing should also be including keypair generation. Consistency testing should also be
applied to ECDH. applied to ECDH.
7.1. ECDH 8.1. ECDH
An ECDH implementation can be validated using the known answer test An ECDH implementation can be validated using the known answer test
cases from [RFC4753]. The correspondence between the notation in cases from [RFC4753] or [RFC5114]. The correspondence between the
that RFC and the notation in this note are summarized in the notation in RFC 4753 and the notation in this note are summarized in
following table. (Refer to Section 3.3 and Section 4), and express the following table. (Refer to Section 3.3 and Section 4; the
the generator g in the affine coordinate representation as (gx, gy). generator g is expressed in affine coordinate representation as (gx,
gy)).
+----------------------+---------------------------------------+ +----------------------+---------------------------------------+
| ECDH | RFC 4753 | | ECDH | RFC 4753 |
+----------------------+---------------------------------------+ +----------------------+---------------------------------------+
| order p of field Fp | p | | order p of field Fp | p |
| curve coefficient a | -3 | | curve coefficient a | -3 |
| curve coefficient b | b | | curve coefficient b | b |
| generator g | g=(gx, gy) | | generator g | g=(gx, gy) |
| private keys j and k | i and r | | private keys j and k | i and r |
| public keys g^j, g^k | g^i = (gix, giy) and g^r = (grx, gry) | | public keys g^j, g^k | g^i = (gix, giy) and g^r = (grx, gry) |
+----------------------+---------------------------------------+ +----------------------+---------------------------------------+
7.2. KT-I The correspondence between the notation in RFC 5114 and the notation
in this note are summarized in the following table.
+-----------------------+---------------------------+
| ECDH | RFC 5114 |
+-----------------------+---------------------------+
| order p of field Fp | p |
| curve coefficient a | a |
| curve coefficient b | b |
| generator g | g=(gx, gy) |
| group order n | n |
| private keys j and k | dA and dB |
| public keys g^j, g^k | g^(dA) = (x_qA, y_qA) and |
| | g^(dB) = (x_qB, y_qB) |
| shared secret g^(j*k) | g^(dA*dB) = (x_Z, y_Z) |
+-----------------------+---------------------------+
8.2. KT-I
A KT-I implementation can be validated using the known answer test A KT-I implementation can be validated using the known answer test
cases from [RFC4754]. The correspondence between the notation in cases from [RFC4754]. The correspondence between the notation in
that RFC and the notation in this note are summarized in the that RFC and the notation in this note are summarized in the
following table. following table.
+---------------------+------------------+ +---------------------+------------------+
| KT-I | RFC 4754 | | KT-I | RFC 4754 |
+---------------------+------------------+ +---------------------+------------------+
| order p of field Fp | p | | order p of field Fp | p |
skipping to change at page 19, line 30 skipping to change at page 20, line 47
| private key z | w | | private key z | w |
| public key Y | g^w = (gwx,gwy) | | public key Y | g^w = (gwx,gwy) |
| random k | ephem priv k | | random k | ephem priv k |
| s1 | r | | s1 | r |
| s2 | s | | s2 | s |
| s2_inv | sinv | | s2_inv | sinv |
| u1 | u = h*sinv mod q | | u1 | u = h*sinv mod q |
| u2 | v = r*sinv mod q | | u2 | v = r*sinv mod q |
+---------------------+------------------+ +---------------------+------------------+
8. Intellectual Property 9. 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 for ECDH (as defined in Section 4) All of the normative references for ECDH (as defined in Section 4)
were published during or before 1989, and those for KT-I were were published during or before 1989, and those for KT-I were
published during or before May, 1994. All of the normative text for published during or before May, 1994. All of the normative text for
these algorithms is based solely on their respective references. these algorithms is based solely on their respective references.
8.1. Disclaimer 9.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 10. 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 Pohlig-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 [VW1994]. 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 is known to lie in an interval of width w. exponent is known to lie in an interval of width w.
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 known subexponential algorithms against general groups. There are no known 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 10.1. Subgroups
A group consisting of a nonempty set of elements S with associated A group consisting of a nonempty set of elements S with associated
group operation * is a subgroup of the group with the set of elements group operation * is a subgroup of the group with the set of elements
G, if the latter group uses the same group operation and S is a G, if the latter group uses the same group operation and S is a
subset of G. For each elliptic curve equation, there is an elliptic subset of G. For each elliptic curve equation, there is an elliptic
curve group whose group order is equal to the order of the elliptic curve group whose group order is equal to the order of the elliptic
curve; that is, there is a group that contains every point on the curve; that is, there is a group that contains every point on the
curve. 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 ECC parameter set as in Section 3.3 is "cofactor" [P1363]. Each ECC parameter set as in Section 3.3 is
associated with a particular cofactor. 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.
9.2. Diffie-Hellman 10.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
exchanged should be directly authenticated. This is the strategy exchanged should be directly authenticated. This is the strategy
used by protocols that build on Diffie-Hellman and which use end- used by protocols that build on Diffie-Hellman and which use end-
entity authentication to protect against active attacks, such as entity authentication to protect against active attacks, such as
OAKLEY [RFC2412] and the Internet Key Exchange [RFC2409][RFC4306]. OAKLEY [RFC2412] and the Internet Key Exchange [RFC2409][RFC4306].
When the cofactor of a group is not equal to 1, there are a number of When the cofactor of a group is not equal to 1, there are a number of
attacks that are possible against ECDH. See [VW1996], [AV1996], and attacks that are possible against ECDH. See [VW1996], [AV1996], and
[LL1997]. [LL1997].
9.3. Group Representation and Security 10.3. Group Representation and Security
The elliptic curve group operation does not explicitly incorporate The elliptic curve group operation does not explicitly incorporate
the parameter b from the curve equation. This opens the possibility the parameter b from the curve equation. This opens the possibility
that a malicious attacker could learn information about an ECDH that a malicious attacker could learn information about an ECDH
private key by submitting a bogus public key [BMM2000]. An attacker private key by submitting a bogus public key [BMM2000]. An attacker
can craft an elliptic curve group G' that has identical parameters to can craft an elliptic curve group G' that has identical parameters to
a group G that is being used in an ECDH protocol, except that b is a group G that is being used in an ECDH protocol, except that b is
different. An attacker can submit a point on G' into a run of the different. An attacker can submit a point on G' into a run of the
ECDH protocol that is using group G, and gain information from the ECDH protocol that is using group G, and gain information from the
fact that the group operations using the private key of the device fact that the group operations using the private key of the device
skipping to change at page 22, line 5 skipping to change at page 23, line 18
that is used in more than one run of the protocol. However, it does that is used in more than one run of the protocol. However, it does
not gain any useful information against ephemeral keys. not gain any useful information against ephemeral keys.
This sort of attack is thwarted if an ECDH implementation does not This sort of attack is thwarted if an ECDH implementation does not
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.
These considerations also apply when ECDH is used with compact These considerations also apply when ECDH is used with compact
representation (see Appendix C). representation (see Appendix C).
9.4. Signatures 10.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].
If no hash function is used in an ElGamal signature system, then the If no hash function is used in an ElGamal signature system, then the
system is vulnerable to existential forgeries, in which an attacker system is vulnerable to existential forgeries, in which an attacker
who does not know a private key can generate valid signatures for the who does not know a private key can generate valid signatures for the
associated public key, but cannot generate a signature for a message associated public key, but cannot generate a signature for a message
of its own choosing. (See [E1985] for instance.) The use of a of its own choosing. (See [E1985] for instance.) The use of a
skipping to change at page 22, line 35 skipping to change at page 23, line 48
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 KT signatures The number of bits in the output of the hash used in KT signatures
should be equal or close to the number of bits needed to represent should be equal or close to the number of bits needed to represent
the group order. the group order.
10. IANA Considerations 11. 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 12. 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, and all of the cryptography, whose work made this note possible, and all of the
reviewers, who provided valuable constructive feedback. Thanks are reviewers, who provided valuable constructive feedback. Thanks are
especially due to Howard Pinder and Andrey Jivsov. especially due to Howard Pinder, Andrey Jivsov, Alfred Hoenes (who
contributed the algorithms in Appendix F), and Dan Harkins.
12. References 13. References
12.1. Normative References
13.1. Normative References
[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",
Electronics Letters Vol. 26, No. 14, July, 1990. Electronics Letters Vol. 26, No. 14, July, 1990.
[BC1989] Bender, A. and G. Castagnoli, "On the Implementation of [BC1989] Bender, A. and G. Castagnoli, "On the Implementation of
Elliptic Curve Cryptosystems", Advances in Cryptology - Elliptic Curve Cryptosystems", Advances in Cryptology -
CRYPTO '89 Proceedings Spinger Lecture Notes in Computer CRYPTO '89 Proceedings Spinger Lecture Notes in Computer
Science (LNCS) volume 435, 1989. Science (LNCS) volume 435, 1989.
skipping to change at page 24, line 14 skipping to change at page 25, line 28
[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.
12.2. Informative References [R1993] RSA Laboratories, "PKCS#1: RSA Encryption Standard",
Technical Note version 1.5, 1993.
[S1986] Silverman, J., "The Arithmetic of Elliptic Curves",
Springer-Verlag New York, 1986.
13.2. Informative 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.
[AV1996] Anderson, R. and S. Vaudenay, "Minding Your P's and Q's", [AV1996] Anderson, R. and S. Vaudenay, "Minding Your P's and Q's",
Advances in Cryptology - ASIACRYPT '96 Proceedings Spinger Advances in Cryptology - ASIACRYPT '96 Proceedings Spinger
Lecture Notes in Computer Science (LNCS) volume 1163, Lecture Notes in Computer Science (LNCS) volume 1163,
1996. 1996.
[BMM2000] Biehl, I., Meyer, B., and V. Muller, "Differential fault [BMM2000] Biehl, I., Meyer, B., and V. Muller, "Differential fault
analysis on elliptic curve cryptosystems", Advances in analysis on elliptic curve cryptosystems", Advances in
Cryptology - CRYPTO 2000 Proceedings Spinger Lecture Notes Cryptology - CRYPTO 2000 Proceedings Spinger Lecture Notes
in Computer Science (LNCS) volume 1880, 2000. in Computer Science (LNCS) volume 1880, 2000.
[BS1992] Branstad, D. and M. Smid, "Response to Comments on the [BS1992] Branstad, D. and M. Smid, "Response to Comments on the
NIST Proposed Digital Signature Standard", Advances in NIST Proposed Digital Signature Standard", Advances in
Cryptology - CRYPTO '92 Proceedings Springer Lecture Notes Cryptology - CRYPTO '92 Proceedings Springer Lecture Notes
in Computer Science (LNCS) volume 740, August 1992. in Computer Science (LNCS) volume 740, August 1992.
[DSA1991] "DIGITAL SIGNATURE STANDARD", Federal Register Vol. 56, [DSA1991] U.S. National Institute of Standards and Technology,
"DIGITAL SIGNATURE STANDARD", Federal Register Vol. 56,
August 1991. August 1991.
[E1984a] ElGamal, T., "Cryptography and logarithms over finite [E1984a] ElGamal, T., "Cryptography and logarithms over finite
fields", Stanford University UMI Order No. DA 8420519, fields", Stanford University UMI Order No. DA 8420519,
1984. 1984.
[E1984b] ElGamal, T., "Cryptography and logarithms over finite [E1984b] ElGamal, T., "Cryptography and logarithms over finite
fields", Advances in Cryptology - CRYPTO '84 fields", Advances in Cryptology - CRYPTO '84
Proceedings Springer Lecture Notes in Computer Science Proceedings Springer Lecture Notes in Computer Science
(LNCS) volume 196, 1984. (LNCS) volume 196, 1984.
[E1985] ElGamal, T., "A public key cryptosystem and a signature [E1985] ElGamal, T., "A public key cryptosystem and a signature
scheme based on discrete logarithms", IEEE Transactions on scheme based on discrete logarithms", IEEE Transactions on
Information Theory Vol 30, No. 4, pp. 469-472, 1985. Information Theory Vol 30, No. 4, pp. 469-472, 1985.
[FIPS180-2] [FIPS180-2]
U.S. National Institute of Standards and Technology,
"SECURE HASH STANDARD", Federal Information Processing "SECURE HASH STANDARD", Federal Information Processing
Standard (FIPS) 180-2, August 2002. Standard (FIPS) 180-2, August 2002.
[FIPS186] "DIGITAL SIGNATURE STANDARD", Federal Information [FIPS186] U.S. National Institute of Standards and Technology,
"DIGITAL SIGNATURE STANDARD", Federal Information
Processing Standard FIPS-186, May 1994. Processing Standard FIPS-186, May 1994.
[HP1994] Horster, P. and H. Petersen, "Verallgemeinerte ElGamal- [HP1994] Horster, P. and H. Petersen, "Verallgemeinerte ElGamal-
Signaturen", Proceedings der Fachtagung SIS '94, Verlag Signaturen", Proceedings der Fachtagung SIS '94, Verlag
der Fachvereine Zurich, 1994. der Fachvereine Zurich, 1994.
[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., Maurer, U., Vanstone, S., and T. Okamoto, "New Koyama, K., Maurer, U., Vanstone, S., and T. Okamoto, "New
Public-Key Schemes Based on Elliptic Curves over the Ring Public-Key Schemes Based on Elliptic Curves over the Ring
Zn", Advances in Cryptology - CRYPTO '91 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.
[L1969] "Computer technology applied to the theory of numbers", [L1969] Lehmer, D., "Computer technology applied to the theory of
M.A.A. Studies in Mathematics 180-2, 1969. numbers", M.A.A. Studies in Mathematics 180-2, 1969.
[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.
[NR1994] Nyberg, K. and R. Rueppel, "Message Recovery for Signature [NR1994] Nyberg, K. and R. Rueppel, "Message Recovery for Signature
Schemes Based on the Discrete Logarithm Problem", Advances Schemes Based on the Discrete Logarithm Problem", Advances
in Cryptology - EUROCRYPT '94 Proceedings Springer Lecture in Cryptology - EUROCRYPT '94 Proceedings Springer Lecture
Notes in Computer Science (LNCS) volume 950, May 1994. Notes in Computer Science (LNCS) volume 950, May 1994.
skipping to change at page 26, line 33 skipping to change at page 28, line 8
[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.
[RFC4754] Fu, D. and J. Solinas, "IKE and IKEv2 Authentication Using [RFC4754] Fu, D. and J. Solinas, "IKE and IKEv2 Authentication Using
the Elliptic Curve Digital Signature Algorithm (ECDSA)", the Elliptic Curve Digital Signature Algorithm (ECDSA)",
RFC 4754, January 2007. RFC 4754, 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/ [RFC5114] Lepinski, M. and S. Kent, "Additional Diffie-Hellman
ia/programs/suiteb_cryptography/index.shtml. Groups for Use with IETF Standards", RFC 5114,
January 2008.
[SuiteB] U. S. National Security Agency (NSA), "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 [VW1994] van Oorschot, P. and M. Wiener, "Parallel Collision Search
with Application to Hash Functions and Discrete with Application to Hash Functions and Discrete
Logarithms", Proceedings of the 2nd ACM Conference on Logarithms", Proceedings of the 2nd ACM Conference on
Computer and communications security pp. 210-218, 1994. Computer and communications security pp. 210-218, 1994.
skipping to change at page 28, line 44 skipping to change at page 30, line 25
There are at most two distinct solutions y = w and y = -w mod p, and There are at most two distinct solutions y = w and y = -w mod p, and
the point P must be either Q=(x,w) or Q^-1=(x,-w). Thus P^n is equal the point P must be either Q=(x,w) or Q^-1=(x,-w). Thus P^n is equal
to either Q^n or (Q^-1)^n = (Q^n)^-1. These values have the same to either Q^n or (Q^-1)^n = (Q^n)^-1. These values have the same
x-coordinate. Thus, the x-coordinate of a point P^i can be computed x-coordinate. Thus, the x-coordinate of a point P^i can be computed
from the x-coordinate of a point P by computing one of the possible from the x-coordinate of a point P by computing one of the possible
values of the y coordinate of P, then computing the ith power of P, values of the y coordinate of P, then computing the ith power of P,
and then ignoring the y-coordinate of that result. and then ignoring the y-coordinate of that result.
In general, it is possible to compute a square root modulo p by using In general, it is possible to compute a square root modulo p by using
Shanks's method [K1987]; simple methods exist for some values of p. Shanks' method [K1981v2]; simple methods exist for some values of p.
When p = 3 (mod 4), the square roots of z mod p are w and -w mod p, When p = 3 (mod 4), the square roots of z mod p are w and -w mod p,
where where
w = z ^ ((p+1)/4) (mod p); w = z ^ ((p+1)/4) (mod p);
this observation is due to Lehmer [L1969]. When p satisfies this this observation is due to Lehmer [L1969]. When p satisfies this
property, y can be computed from the curve equation, and either y = w property, y can be computed from the curve equation, and either y = w
or y = -w mod p, where or y = -w mod p, where
w = (x^3 + a*x + b)^((p+1)/4) (mod p). w = (x^3 + a*x + b)^((p+1)/4) (mod p).
Square roots modulo p only exist for a quadratic residue modulo p, Square roots modulo p only exist for a quadratic residue modulo p,
[R1988]; if z is not a quadratic residue, then there is no number w [R1988]; if z is not a quadratic residue, then there is no number w
such that w^2 = z (mod p). A simple way to verify that z is a such that w^2 = z (mod p). A simple way to verify that z is a
quadratic residue after computing w is to verify that quadratic residue after computing w is to verify that
w * w = z (mod p). If this relation does not hold for the above w * w = z (mod p). If this relation does not hold for the above
equation, then the value x is not a valid x-coordinate for a valid equation, then the value x is not a valid x-coordinate for a valid
elliptic curve point. This is an important consideration when ECDH elliptic curve point. This is an important consideration when ECDH
is used with compact output; see Section 9.3. is used with compact output; see Section 10.3.
The primes used in the P-256, P-384, and P-521 curves described in The primes used in the P-256, P-384, and P-521 curves described in
[RFC4753] all have the property that p = 3 (mod 4). [RFC4753] all have the property that p = 3 (mod 4).
Appendix D. Example ECC Parameter Set Appendix D. Example ECC Parameter Set
For concreteness, we recall an elliptic curve defined by Solinas and For concreteness, we recall an elliptic curve defined by Solinas and
Fu in [RFC4753] and referred to as P-256, which is believed to Fu 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.3, and express the generator in the affine coordinate Section 3.3, and express the generator in the affine coordinate
skipping to change at page 30, line 19 skipping to change at page 31, line 46
| multiplication | addition | | multiplication | addition |
| a * b | a + b | | a * b | a + b |
| squaring | doubling | | squaring | doubling |
| a * a = a^2 | a + a = 2a | | a * a = a^2 | a + a = 2a |
| exponentiation | scalar multiplication | | exponentiation | scalar multiplication |
| a^N = a * a * ... * a | Na = a + a + ... + a | | a^N = a * a * ... * a | Na = a + a + ... + a |
| inverse | inverse | | inverse | inverse |
| a^-1 | -a | | a^-1 | -a |
+-------------------------+-----------------------+ +-------------------------+-----------------------+
Appendix F. Algorithms
This section contains a pseudocode description of the elliptic curve
group operation. Text that follows the symbol "//" are to be
interpreted as comments rather than instructions.
F.1. Affine Coordinates
To an arbitrary pair of elliptic curve points P and Q specified by
their affine coordinates P=(x1,y1) and Q=(x2,y2), the group operation
assigns a third point R = P*Q with the coordinates (x3,y3). These
coordinates are computed as follows:
if P is (@,@),
R = Q
else if Q is (@,@),
R = P
else if P is not equal to Q and x1 is equal to x2,
R = (@,@)
else if P is not equal to Q and x1 is not equal to x2,
x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 mod p and
y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 mod p
else if P is equal to Q and y1 is equal to 0,
R = (@,@)
else // P is equal to Q and y1 is not equal to 0
x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 mod p and
y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y mod p.
From the first and second case, it follows that the point at infinity
is the neutral element of this operation, which is its own inverse.
From the curve equation it follows that for a given curve point P =
(x,y) distinct from the point at infinity, (x,-y) also is a curve
point, and from the third and the fifth case it follows that this is
the inverse of P, P^-1.
Note: The fifth and sixth case are known as "point squaring".
F.2. Homogeneous Coordinates
An elliptic curve point (x,y) (other than the point at infinity
(@,@)) is equivalent to a point (X,Y,Z) in homogeneous coordinates
(with X, Y, and Z in Fp and not all three being zero at once)
whenever x=X/Z and y=Y/Z. "Homogenous coordinates" means that two
triples (X,Y,Z) and (X',Y',Z') are regarded as "equal" (i.e.
representing the same point) if there is some non-zero s in Fp such
that X'=s*X, Y'=s*Y, and Z'=s*Z. The point at infinity, (@,@) is
regarded as equivalent to the homogenous coordinates (0,1,0), i.e. it
can be represented by any triple (0,Y,0) with non-zero Y in Fp.
Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on the elliptic curve,
and let u = Y2 * Z1 - Y1 * Z2 and v = X2 * Z1 - X1 * Z2.
We observe that the points P1 and P2 are equal if and only if u and v
are both equal to zero. Otherwise, if either P1 or P2 are equal to
the point at infinity, v is zero and u is non-zero (but the converse
implication does not hold).
Then the product P3=(X3,Y3,Z3) = P1 * P2 is given by:
if P1 is the point at infinity,
P3 = P2
else if P2 is the point at infinity,
P3 = P1
else if u is not equal to 0 but v is equal to 0,
P3 = (0,1,0)
else if both u and v are not equal to 0,
X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3)
Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3
Z3 = v^3 * Z1 * Z2
else // P2 equals P1, P3 = P1 * P1
w = 3 * X1^2 + a * Z1^2
X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1)
Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3
Z3 = 8 * (Y1 * Z1)^3
It thus turns out that the point at infinity is the identity element
and for P1=(X,Y,Z) not equal to this point at infinity, P2=(X,-Y,Z)
represents P1^-1.
Authors' Addresses Authors' Addresses
David A. McGrew David A. McGrew
Cisco Systems Cisco Systems
510 McCarthy Blvd. 510 McCarthy Blvd.
Milpitas, CA 95035 Milpitas, CA 95035
USA USA
Phone: (408) 525 8651 Phone: (408) 525 8651
Email: mcgrew@cisco.com Email: mcgrew@cisco.com
URI: http://www.mindspring.com/~dmcgrew/dam.htm URI: http://www.mindspring.com/~dmcgrew/dam.htm
Kevin M. Igoe Kevin M. Igoe
National Security Agency National Security Agency
Commercial Solutions Center Commercial Solutions Center
United States of America United States of America
Email: kmigoe@nsa.gov Email: kmigoe@nsa.gov
Margaret Salter
National Security Agency
9800 Savage Rd.
Fort Meade, MD 20755-6709
USA
Email: msalter@restarea.ncsc.mil
 End of changes. 65 change blocks. 
139 lines changed or deleted 304 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/