< draft-mcgrew-fundamental-ecc-01.txt   draft-mcgrew-fundamental-ecc-02.txt >
Network Working Group D. McGrew Network Working Group D. McGrew
Internet-Draft Cisco Systems Internet-Draft Cisco Systems
Intended status: Informational October 26, 2009 Intended status: Informational K. Igoe
Expires: April 29, 2010 Expires: August 23, 2010 National Security Agency
February 19, 2010
Fundamental Elliptic Curve Cryptography Algorithms Fundamental Elliptic Curve Cryptography Algorithms
draft-mcgrew-fundamental-ecc-01.txt draft-mcgrew-fundamental-ecc-02.txt
Abstract
This note describes the fundamental algorithms of Elliptic Curve
Cryptography (ECC) as they are defined in some early references.
These descriptions may be useful for implementing the fundamental
algorithms without using any of the specialized methods that were
developed in following years. Only elliptic curves defined over
fields of characteristic greater than three are in scope; these
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 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 43
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 April 29, 2010. This Internet-Draft will expire on August 23, 2010.
Copyright Notice Copyright Notice
Copyright (c) 2009 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 in effect on the date of Provisions Relating to IETF Documents
publication of this document (http://trustee.ietf.org/license-info). (http://trustee.ietf.org/license-info) in effect on the date of
Please review these documents carefully, as they describe your rights publication of this document. Please review these documents
and restrictions with respect to this document. carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
Abstract include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
This note describes the fundamental algorithms of Elliptic Curve described in the BSD License.
Cryptography (ECC) as they are defined in some early references.
These descriptions may be useful to those who want to implement the
fundamental algorithms without using any of the specialized methods
that were developed in following years. Only elliptic curves defined
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 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 . . . . . . . . . . . . . . . . . . . . . . 7
3. Elliptic Curve Groups . . . . . . . . . . . . . . . . . . . . 8 3. Elliptic Curve Groups . . . . . . . . . . . . . . . . . . . . 7
3.1. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 9 3.1. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 8
3.2. Group Parameters . . . . . . . . . . . . . . . . . . . . . 10 3.2. Other Coordinates . . . . . . . . . . . . . . . . . . . . 9
3.2.1. Security . . . . . . . . . . . . . . . . . . . . . . . 10 3.3. ECC Parameters . . . . . . . . . . . . . . . . . . . . . . 9
4. Elliptic Curve Diffie-Hellman (ECDH) . . . . . . . . . . . . . 11 3.3.1. Security . . . . . . . . . . . . . . . . . . . . . . . 10
4. Elliptic Curve Diffie-Hellman (ECDH) . . . . . . . . . . . . . 10
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 (ECES) . . . . . . . . . . . 13 5. Elliptic Curve ElGamal Signatures . . . . . . . . . . . . . . 12
5.1. Keypair Generation . . . . . . . . . . . . . . . . . . . . 13 5.1. Background . . . . . . . . . . . . . . . . . . . . . . . . 12
5.2. Signature Creation . . . . . . . . . . . . . . . . . . . . 13 5.2. Hash Functions . . . . . . . . . . . . . . . . . . . . . . 12
5.3. Signature Verification . . . . . . . . . . . . . . . . . . 14 5.3. KT-IV Signatures . . . . . . . . . . . . . . . . . . . . . 13
5.4. Hash Functions . . . . . . . . . . . . . . . . . . . . . . 14 5.3.1. Keypair Generation . . . . . . . . . . . . . . . . . . 13
5.5. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 14 5.3.2. Signature Creation . . . . . . . . . . . . . . . . . . 13
6. Abbreviated ECES Signatures (AECES) . . . . . . . . . . . . . 16 5.3.3. Signature Verification . . . . . . . . . . . . . . . . 13
6.1. Keypair Generation . . . . . . . . . . . . . . . . . . . . 16 5.4. KT-I Signatures . . . . . . . . . . . . . . . . . . . . . 14
6.2. Signature Creation . . . . . . . . . . . . . . . . . . . . 16 5.4.1. Keypair Generation . . . . . . . . . . . . . . . . . . 14
6.3. Signature Verification . . . . . . . . . . . . . . . . . . 16 5.4.2. Signature Creation . . . . . . . . . . . . . . . . . . 14
7. Interoperability . . . . . . . . . . . . . . . . . . . . . . . 18 5.4.3. Signature Verification . . . . . . . . . . . . . . . . 15
5.5. Converting KT-IV signatures to KT-I signatures . . . . . . 15
5.6. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 15
6. Interoperability . . . . . . . . . . . . . . . . . . . . . . . 17
6.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6.2. KT-I and ECDSA . . . . . . . . . . . . . . . . . . . . . . 17
7. Validating an Implementation . . . . . . . . . . . . . . . . . 18
7.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 7.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
7.2. ECES, AECES, and ECDSA . . . . . . . . . . . . . . . . . . 18 7.2. KT-I . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
8. Intellectual Property . . . . . . . . . . . . . . . . . . . . 20 8. Intellectual Property . . . . . . . . . . . . . . . . . . . . 19
8.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . 20 8.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . 19
9. Security Considerations . . . . . . . . . . . . . . . . . . . 21
9.1. Subgroups . . . . . . . . . . . . . . . . . . . . . . . . 21 9. Security Considerations . . . . . . . . . . . . . . . . . . . 20
9.2. Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . 22 9.1. Subgroups . . . . . . . . . . . . . . . . . . . . . . . . 20
9.3. Group Representation and Security . . . . . . . . . . . . 22 9.2. Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . 21
9.3. Group Representation and Security . . . . . . . . . . . . 21
9.4. Signatures . . . . . . . . . . . . . . . . . . . . . . . . 22 9.4. Signatures . . . . . . . . . . . . . . . . . . . . . . . . 22
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22
11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 25 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 22
12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 26 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 23
12.1. Normative References . . . . . . . . . . . . . . . . . . . 26 12.1. Normative References . . . . . . . . . . . . . . . . . . . 23
12.2. Informative References . . . . . . . . . . . . . . . . . . 27 12.2. Informative References . . . . . . . . . . . . . . . . . . 24
Appendix A. Key Words . . . . . . . . . . . . . . . . . . . . . . 30 Appendix A. Key Words . . . . . . . . . . . . . . . . . . . . . . 27
Appendix B. Random Number Generation . . . . . . . . . . . . . . 31 Appendix B. Random Integer Generation . . . . . . . . . . . . . . 27
Appendix C. Example Elliptic Curve Group . . . . . . . . . . . . 32 Appendix C. Why Compact Representation Works . . . . . . . . . . 28
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 33 Appendix D. Example ECC Parameter Set . . . . . . . . . . . . . . 29
Appendix E. Additive and multiplicative notation . . . . . . . . 29
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 30
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 Elliptic Curve
version of the ElGamal Signature Algorithm [E1985]. The elliptic versions of the ElGamal Signature Algorithm [E1985]. The adoption of
curve versions of these algorithms are referred to as ECDH and ECES, ECC has been slower than had been anticipated, perhaps due to the
respectively. The adoption of ECC has been slower than had been lack of freely available normative documents and uncertainty over
anticipated, perhaps due to the lack of freely available normative intellectual property rights.
documents and uncertainty over 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 normative specification of the basic algorithms that predate with a summary of the basic algorithms that predate any specialized
any specialized or optimized algorithms. or optimized algorithms, which can be used as a normative
specification. The original descriptions and notations were followed
as closely as possible.
There are several standards that specify or incorporate ECC
algorithms, including the Internet Key Exchange (IKE), ANSI X9.62,
and IEEE P1363. The algorithms in this note can interoperate with
some of the algorithms in these standards, with a suitable choice of
parameters and options. The specifics are itemized in Section 6.
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 and Section 5 present the fundamental ECDH and ECES three. Section 4 presents the fundamental ECDH algorithm. Section 5
algorithms, respectively. Section 6 presents an abbreviated form of presents elliptic curve versions of the ElGamal signature method.
ECES. The previous sections contain all of the normative text (the Sections 2 through 5, inclusive, contain all of the normative text
text that defines the norm for implementations conforming to this (the text that defines the norm for implementations conforming to
specification), and all of the following sections are purely this specification), and all of the following sections are purely
informative. Interoperability is discussed in Section 7. Section 8 informative. Interoperability is discussed in Section 6. Validation
reviews intellectual property issues. Section 9 summarizes security testing is described in Section 7. Section 8 reviews intellectual
considerations. Appendix B describes random number generation and property issues. Section 9 summarizes security considerations.
Appendix C provides an example of an Elliptic Curve group. 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 5, line 51 skipping to change at page 5, line 51
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 together with an 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. The operation is associative, that for any two elements a and b in G. The operation is associative, that
is, for all a, b and c in G, a * (b * c) is identical to (a * b) * c. is, for all a, b and c in G, a * (b * c) is identical to (a * b) * c.
Repeated application of the group operation N times to the element a Repeated application of the group operation N-1 times to the element
is denoted as a^N, for any element a in G and any positive integer N. a 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
That is, a^2, = a * a, a^3 = a * a * a, and so on. The associativity associativity of the group operation ensures that the computation of
of the group operation ensures that the computation of a^n is a^n is unambiguous; any grouping of the terms gives the same result.
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. Appendix E elucidates the correspondence
between the two notations.
Every group has an special element called the identity element, which Every group has a 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 Every group element a has a unique inverse element b such that
= b * a = e. The inverse of a is denoted as a^-1 in multiplicative a * b = b * a = e. The inverse of a is denoted as a^-1 in
notation. (In additive notation, the inverse of a is denoted as -a.) 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 For any positive integer X, a^(-X) is defined to be (a^-1)^(X).
g, g^2, g^3, ..., g^R. The element g is called the generator of the Using this convention, exponentiation behaves as one would expect,
group. The element g^R is equal to the identity element e. Note namely for any integers X and Y:
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, a^(X+Y) = (a^X)*(a^Y)
(a^X)^Y = a^(XY) = (a^Y)^X.
A group element a is said to have finite order if a^X = e for some
positive integer X, and the order of a is the smallest such X. If no
such X exists, a is said to have infinite order. In cryptographic
applications one typically deals with finite groups (groups with a
finite number of elements), and all elements of finite groups have
finite 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^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,
called the cyclic subgroup generated by a, and a is said to be a
generator of H.
Typically there are several group elements that generate H. Any group
element of the form a^M, with M relatively prime to R, also generates
H. Note that a^M is equal to g^(M modulo R) for any non-negative
integer M.
Given the element a of order R, and an integer i between 1 and R-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 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 is denoted as Fp. field. The field Zp is sometimes denoted as Fp.
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 { 0, is equivalent to the statement that x, y, and z are in the set
1, ..., p-1 } and { 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; 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 F 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, and the where x, y, a, and b are elements of the field Fp [M1985]. A point
discriminant 16*(4*a^3 - 27*b^2) is nonzero [M1985]. A point on an on an elliptic curve is a pair (x,y) of values in Fp that satisfy the
elliptic curve is a pair (x,y) of values in Fp that satisfy the curve curve equation, such that x and y are both in Fp, or it is a special
equation, such that x and y are both in Fp, or it is a special point point (@,@) that represents the identity element (which is called the
(@,@) 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. 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). inverse of the point (x1,y1) is the point (x1,-y1). The point at
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
skipping to change at page 9, line 26 skipping to change at page 9, line 10
An elliptic curve point (x,y) (other than the point at infinity An elliptic curve point (x,y) (other than the point at infinity
(@,@)) is equivalent to a point (X,Y,Z) in homogeneous coordinates (@,@)) is equivalent to a point (X,Y,Z) in homogeneous coordinates
whenever x=X/Z mod p and y=Y/Z mod p. 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^-1. 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) mod p, 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) mod p, Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3 mod p
Z3 = 8 * (Y1)^3 * (Z1)^3 mod p, Z3 = v^3 * Z1 * Z2 mod p
where u = Y2 * Z1 - Y1 * Z2 mod p and v = X2 * Z1 - X1 * Z2 mod p. 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 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 (X2/Z2, Y2/Z2), which is true if and only if u and v are both equal
to zero. 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) 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.
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. Other Coordinates
An elliptic curve group over a finite field with characteristic Some other coordinate systems have been described; several are
greater than three is completely specified by the following documented in [CC1986], including Jacobi coordinates.
parameters:
3.3. ECC Parameters
In cryptographic contexts, an elliptic curve parameter set consists
of a cyclic subgroup of an elliptic curve together with a preferred
generator of that subgroup. When working over a prime order finite
field with characteristic greater than three, an elliptic curve group
is completely specified by the following 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 subgroup.
The order n of the group generated by g. The order n of the subgroup generated by g.
An example of an Elliptic Curve Group is provided in Appendix C. An example of an ECC parameter set is provided in Appendix D.
Each elliptic curve point is associated with a particular group, i.e Each elliptic curve point is associated with a particular parameter
a particular parameter set. Two elliptic curve groups are equal if set. The elliptic curve group operation is only defined between two
and only if each of the parameters in the set are equal. The points in the same group. It is an error to apply the group
elliptic curve group operation is only defined between two points on operation to two elements that are from different groups, or to apply
the same group. It is an error to apply the group operation to two the group operation to a pair of coordinates that is not a valid
elements that are from different groups, or to apply the group point. (A pair (x,y) of coordinates in Fp is a valid point only when
operation to a pair of coordinates that are not a valid point. See they satisfy the curve equation.) See Section 9.3 for further
Section 9.3 for further information. information.
3.2.1. Security For each elliptic curve group, the discriminant - 16*(4*a^3 + 27*b^2)
must be nonzero modulo p.
Parameter generation is out of scope for this note.
3.3.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 informative guidance. Section 9 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 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
skipping to change at page 11, line 18 skipping to change at page 11, line 12
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, inclusive, uniformly at
g^j and sends that element to B. Party B chooses an exponent k random, computes g^j and sends that element to B. Party B chooses an
between 1 and t-1 uniformly at random, computes g^k and sends that exponent k between 1 and t-1, inclusive, uniformly at random,
element to A. Each party can compute g^(j*k); party A computes computes g^k and sends that element to A. Each party can compute
(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 numbers. 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. An ECDH private key z is an integer in Zt.
The corresponding ECDH public key Y is the group element, where Y = The corresponding ECDH public key Y is the group element, where Y =
g^z. Each public key is associated with a particular group, i.e. a g^z. Each public key is associated with a particular particular
particular parameter set as per Section 3.2. parameter set as per Section 3.3.
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
and both of the public keys and the shared secret are elements of parameter set, and both of the public keys and the shared secret are
that group. elements of that group.
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.
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. Its
mathematical background is explained in Appendix C.
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
5.1. Background
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, and
the multiplicative group of the integers modulo a large prime number. was originally defined for the multiplicative group of the integers
It is straightforward to extend it to use an elliptic curve group. modulo a large prime number. It is straightforward to extend it to
In this section we recall a well-specified elliptic curve version of use other finite groups, such as the multiplicative group of the
the ElGamal Signature Algorithm, as described in [A1992] and field GF(2^w) [AMV1990] or an elliptic curve group [A1992].
[MV1993]. This signature method is called Elliptic Curve ElGamal
Signatures (ECES).
The algorithm uses an elliptic curve group, as described in An ElGamal signature consists of a pair of components. There are
Section 3.2, with prime field order p, curve equation parameters a many possible generalizations of ElGamal signature methods that have
and b. We follow [MV1993] in describing the algorithms in terms of been obtained by different rearrangements of the equation for the
mathematical groups, and denoting the generator as alpha, and its second component; see [HMP1994], [HP1994], [NR1994], [A1992], and
order as n. [AMV1990]. These generalizations are independent of the mathematical
group used, and have been described for the multiplicative group
modulo a prime number, the multiplicative group of GF(2^w), and
elliptic curve groups [HMP1994][NR1994] [AMV1990][A1992].
ECES uses a collision-resistant hash function, so that it can sign The Digital Signature Algorithm (DSA) [FIPS186] is an important
messages of arbitrary length. We denote the hash function as h(). ElGamal signature variant.
Its input is a bit string of arbitrary length, and its output is an
integer between zero and n-1, inclusive.
ECES uses a function g() from the set of group elements to the set of 5.2. Hash Functions
integers Zn. This function returns the x-coordinate of the affine
coordinate representation of the elliptic curve point.
5.1. Keypair Generation ElGamal signatures must use a collision-resistant hash function, so
that it can sign messages of arbitrary length and can avoid
existential forgery attacks; see Section 9.4. (This is true for all
ElGamal variants [HMP1994].) We denote the hash function as h().
Its input is a bit string of arbitrary length, and its output is a
non-negative integer.
The private key z is an integer between 0 and n - 1, inclusive, Let H() denote a hash function whose output is a fixed-length bit
generated uniformly at random. The public key is the group element string. To use H in an ElGamal signature method, we define the
Q = alpha^z. mapping between that output and the non-negative integers; this
realizes the function h() described above. Given a bit string m, the
function h(m) is computed as follows:
5.2. Signature Creation 1. H(m) is evaluated; the result is a fixed-length bit string.
To sign message m, using the private key z: 2. Convert the resulting bit string to an integer i by treating its
leftmost (initial) bit as the most significant bit of i, and
treating its rightmost (final) bit as the least significant bit
of i.
1. First, choose an integer k uniformly at random from the set of 5.3. KT-IV Signatures
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.)
(See Appendix B regarding random integers.)
2. Next, compute the group element r = alpha^k. Koyama and Tsuruoka described a signature method based on Elliptic
Curve ElGamal, in which the first signature component is the
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.
3. Finally, compute the integer s as The algorithm uses an elliptic curve group, as described in
Section 3.3, with prime field order p, and curve equation parameters
a and b. We denote the generator as alpha, and the order of the
generator as q. We follow [FIPS186] in checking for exceptional
cases.
s = (h(m) + z * g(r)) / k (mod n). 5.3.1. Keypair Generation
4. If s is equal to zero, then the signature creation MUST be The private key z is an integer between 1 and q - 1, inclusive,
repeated, starting at Step 1 and using a newly chosen k value. generated uniformly at random. (See Appendix B regarding random
integers.) The public key is the group element
Y = alpha^z. Each public key is associated with a particular
particular parameter set as per Section 3.3.
The signature for message m is the ordered pair (r, s). Note that 5.3.2. Signature Creation
the first component is a group element, and the second is a non-
negative integer.
5.3. Signature Verification To compute a KT-IV signature for a message m using the private key z:
To verify the message m and the signature (r,s) using the public key 1. Choose an integer k uniformly at random from the set of all
Q: integers between 1 and q-1, inclusive. (See Appendix B regarding
random integers.)
Compute the group element r^s * Q^(-g(r)). 2. Calculate R = (r_x, r_y) = alpha^k.
Compute the group element alpha^h(m). 3. Calculate s1 = r_x mod q.
Verify that the two elements previously computed are the same. If 4. Calculate s2 = k / (h(m) + z * s1) mod q.
they are identical, then the signature and message pass the
verification; otherwise, they fail.
5.4. Hash Functions 5. As an option, one MAY check if s1 = 0 or s2 = 0. If either
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.)
Let H() denote a hash function whose output is a fixed-length bit The signature is the ordered pair (s1, s2). Both signature
string. To use H in ECES, we define the mapping between that output components are non-negative integers.
and the integers between zero and n-1; this realizes the function h()
described above. Given a bit string m, the function h(m) is computed
as follows:
1. H(m) is evaluated; the result is a fixed-length bit string. 5.3.3. Signature Verification
2. Convert the resulting bit string to an integer i by treating its Given the message m, the public key Y, and the signature (s1, s2)
leftmost (initial) bit as the most significant bit of i, and verification is as follows:
treating its rightmost (final) bit as the least significant bit
of i.
3. After conversion, reduce i modulo n, where n is the group order. 1. Check to see that 0 < s1 < q and 0 < s2 < q; if either condition
is violated, the signature SHALL be rejected.
5.5. Rationale 2. Compute the non-negative integers u1 and u2, where
This subsection is not normative and is provided only as background u1 = h(m) * s2 mod q, and
information.
The signature verification will pass whenever the signature is u2 = s1 * s2 mod q.
properly generated, because
r^s * Q^(-g(r)) = alpha^(k*s - z*g(r)) = alpha^h(m). 3. Compute the elliptic curve point R' = alpha^u1 * Y^u2.
The reason that the random variable k must be coprime with n is so 4. If the x-coordinate of R' mod q is equal to s1, then the
that 1/k mod n is defined. signature and message pass the verification; otherwise, they
fail.
A valid signature with s=0 leaks the secret key, since in that case a 5.4. KT-I Signatures
= h(m) / g(r) mod n. We adopt Rivest's suggestion to avoid this
problem [R1992].
As described in the final paragraph of [M1985], it is suitable to use Horster, Michels, and Petersen categorized many different ElGamal
the x-coordinate of a particular elliptic curve point as a signature methods, demonstrated their equivalence, and showed how to
representative for that point. This is what the function g() does. convert signatures of one type to another type [HMP1994]. In their
terminology, the signature method of Section 5.3 and [KT1994] is a
Type IV method, which is why it is denoted as KT-IV.
6. Abbreviated ECES Signatures (AECES) A Type I KT signature method has a second component that is computed
in the same manner as that of the Digital Signature Algorithm. In
this section, we describe this method, which we refer to as KT-I.
The ECES system is secure and efficient, but has signatures that are 5.4.1. Keypair Generation
slightly larger than they need to be. Koyama and Tsuruoka described
a signature system based on Elliptic Curve ElGamal, but with shorter
signatures [KT1994]. Their idea is to include only the x-coordinate
of the EC point in the signature, instead of both coordinates.
Menezes, Qu, and Vanstone independently developed the same idea,
which was the basis for the "Elliptic Curve Signature Scheme with
Appendix (ECSSA)" submission to the IEEE 1363 working group
[MQV1994].
In this section we describe an Elliptic Curve Signature Scheme that Keypairs and keypair generation are exactly as in Section 5.3.1.
uses a single elliptic curve coordinate in the signature instead of
both coordinates. It is based on [KT1994] and [MQV1994], but with
the finite field inversion operation moved from the signature
operation to the verification operation, so that the signing
operation is more compatible with ECES. (See [AMV1990] and [A1992]
for a discussion of these alternatives; the security of the methods
is equivalent.) We refer to this scheme as Abbreviated ECES, or
AECES.
6.1. Keypair Generation 5.4.2. Signature Creation
Keypairs are the same as for ECES and are as described in To compute a KT-I signature for a message m using the private key z:
Section 5.1.
6.2. Signature Creation 1. Choose an integer k uniformly at random from the set of all
integers between 1 and q-1, inclusive. (See Appendix B regarding
random integers.)
In this section we describe how to compute the signature for a 2. Calculate R = (r_x, r_y) = alpha^k.
message m using the private key z.
Signature creation is as for ECES, with the following additional 3. Calculate s1 = r_x mod q.
step:
1. Let the integer s1 be equal to the x-coordinate of r. 4. Calculate s2 = (h(m) + z * s1) / k mod q.
The signature is the ordered pair (s1, s). Both signature components 5. As an option, one MAY check if s1 = 0 or s2 = 0. If either
are non-negative integers. 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.)
6.3. Signature Verification The signature is the ordered pair (s1, s2). Both signature
components are non-negative integers.
Given the message m, the public key Q, and the signature (s1, s) 5.4.3. Signature Verification
Given the message m, the public key Y, and the signature (s1, s2)
verification is as follows: verification is as follows:
1. Compute the inverse of s modulo n. We denote this value as w. 1. Check to see that 0 < s1 < q and 0 < s2 < q; if either condition
is violated the signature SHALL be rejected.
2. Compute the non-negative integers u and v, where 2. Compute s2_inv = 1 / s2 mod q.
u = w * h(m) mod n, and 3. Compute the non-negative integers u1 and u2, where
v = w * s1 mod n. u1 = h(m) * s2_inv mod q, and
3. Compute the elliptic curve point R' = alpha^u * Q^v u2 = s1 * s2_inv mod q.
4. If the x-coordinate of R' is equal to s1, then the signature and 4. Compute the elliptic curve point R' = alpha^u1 * Y^u2.
message pass the verification; otherwise, they fail.
7. Interoperability 5. If the x-coordinate of R' mod q is equal to s1, then the
signature and message pass the verification; otherwise, they
fail.
5.5. Converting KT-IV signatures to KT-I signatures
A KT-IV signature for a message m and a public key Y can easily be
converted into a KT-I signature for the same message and public key.
If (s1, s2) is a KT-IV signature for a message m, then
(s1, 1/s2 mod q) is a KT-I signature for the same message [HMP1994].
The conversion operation uses only public information, and it can be
performed by the creator of the pre-conversion KT-IV signature, the
verifier of the post-conversion KT-I signature, or by any other
entity.
An implementation MAY use this method to compute KT-I signatures.
5.6. Rationale
This subsection is not normative for this specification and is
provided only as background information.
[HMP1994] presents many generalizations of ElGamal signatures.
Equation (5) of that reference shows the general signature equation
A = x_A * B + k * C (mod q)
where x_A is the private key, k is the secret value, and A, B, and C
are determined by the Type of the equation, as shown in Table 1 of
[HMP1994]. DSA [FIPS186] is an EG-I.1 signature method (as is KT-I),
with A = m, B = -r, and C = s. (Here we use the notation of
[HMP1994] in which the first signature component is r and the second
signature component is s; in KT-I and KT-IV these components are
denoted as s1 and s2 respectively. The private key x_A corresponds
to the private key z.) Its signature equation is
m = - r * z + s * k (mod q).
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
is
m * s = - r * s * z + k (mod q)
The functions f and g mentioned in Table 1 are merely multiplication,
as described under the heading "Fifth generalization".
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
to signing in order to prevent existential forgery attacks.
Nyberg and Rueppel [NR1994] studied many different ElGamal signature
methods, and defined "strong equivalence" as follows:
Two signature methods are called strongly equivalent if the
signature of the first scheme can be transformed efficiently into
signatures of the second scheme and vice versa, without knowledge
of the private key.
KT-I and KT-IV signatures are obviously strongly equivalent.
A valid signature with s2=0 leaks the secret key, since in that case
z = - h(m) / s1 mod q. We follow [FIPS186] in checking for this
exceptional case and the case that s1=0. The s2=0 check was
suggested by Rivest [R1992] and is discussed in [BS1992].
[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
elliptic curve point R = (r_x, r_y). The value q' is also used
during signature validation when comparing the x-coordinate of a
computed elliptic curve point to the value to s1. In this note, we
use the simplifying convention that q' = q.
6. 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.
7.1. ECDH 6.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 for the defined by [RFC4753], [RFC2409], and the ECP groups defined by [RFC4753], [RFC2409], and [RFC2412]. The
[RFC2412]. The group definition used in this protocol uses an affine group definition used in this protocol uses an affine coordinate
coordinate representation of the public key and uses neither the representation of the public key and uses neither the compact output
compact output nor the compact representation of Section 4.2. Note nor the compact representation of Section 4.2. Note that some groups
that some groups use a negative curve parameter "a" and express this use a negative curve parameter "a" and express this fact in the curve
fact in the curve equation rather than in the parameter. The test equation rather than in the parameter. The test cases in Section 8
cases in Section 8 of [RFC4753] can be used to test an of [RFC4753] can be used to test an implementation; these cases use
implementation; these cases use the multiplicative notation, as does the multiplicative notation, as does this note. The KEi and KEr
this note. The KEi and KEr payloads are equal to g^i and g^r, payloads are equal to g^j and g^k, respectively, with 64 bits of
respectively, with 64 bits of encoding data prepended to them. 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. To use IEEE P1363 ECDH in a characteristic greater than three. IEEE P1363 ECDH can be used in a
manner that will interoperate with this specification, the following manner that will interoperate with this note, with the following
options and parameter choices should be used: prime curves with a options and parameter choices from that specification:
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 prime curves with a cofactor of 1,
the ECSVDP-DH primitive, and
the Key Derivation Function must be the "identity" function
(equivalently, the KDF step should be omitted and the shared
secret value should be output directly).
6.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 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.
AECES can interoperate with the IEEE [P1363] and ANSI [X9.62] KT-I is mathematically and functionally equivalent to ECDSA, and can
standards for Elliptic Curve DSA (ECDSA) based on fields of interoperate with the IEEE [P1363] and ANSI [X9.62] standards for
characteristic greater than three. Elliptic Curve DSA (ECDSA) based on fields of characteristic greater
than three. KT-I signatures can be verified using the ECDSA
verification algorithm, and ECDSA signatures can be verified using
the KT-I verification algorithm.
An ECES signature can be converted into an ECDSA or AECES signature 7. Validating an Implementation
by discarding the y-coordinate from the elliptic curve point.
There is a strong correspondence between ECES signatures and ECDSA or It is essential to validate the implementation of a cryptographic
AECES signatures. In the notation of Section 5, an ECDSA (or AECES) algorithm. This section outlines tests that should be performed on
signature consists of the pair of integers (g(r), s), and signature the algorithms defined in this note.
verification passes if and only if
A^(h(m)/s) * Q^(g(r)/s) = r, 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
output, which is also a fixed value. KATs for ECDH and KT-I are set
out in the following subsections.
where the equality of the elliptic curve elements is checked by A consistency test generates inputs for one algorithm being tested
checking for the equality of their x-coordinates. For valid using a second algorithm that is also being tested, then checks the
signatures, (h(m)+a*r)/s mod q = k, and thus the two sides are equal. output of the first algorithm. A signature creation algorithm can be
An ECDSA (or AECES) signature contains only the x-coordinate g(r), tested for consistency against a signature verification algorithm.
but this is sufficient to allow the signatures to be checked with the Implementations of KT-I should be tested in this way. Their
above method. signature generation processes are non-deterministic, and thus cannot
be tested using a KAT. Signature verification algorithms, on the
other hand, are deterministic and should be tested via a KAT. This
combination of tests provides coverage for all of the operations,
including keypair generation. Consistency testing should also be
applied to ECDH.
Whenever the ECES signature (r, s) is valid for a particular message 7.1. ECDH
m, and public key Q, then there is a valid AECES or ECDSA signature
(g(r), s) for the same message and public key.
Whenever an AECES or ECDSA signature (c, d) is valid for a particular An ECDH implementation can be validated using the known answer test
message m, and public key Q, then there is a valid ECES signature for cases from [RFC4753]. The correspondence between the notation in
the same message and public key. This signature has the form ((c, that RFC and the notation in this note are summarized in the
f(c)), d), or ((c, q-f(c)), d) where the function f takes as input an following table. (Refer to Section 3.3 and Section 4), and express
integer in Zq and is defined as the generator g in the affine coordinate representation as (gx, gy).
f(x) = sqrt(x^3 + a*x + b) (mod q). +----------------------+---------------------------------------+
| ECDH | RFC 4753 |
+----------------------+---------------------------------------+
| order p of field Fp | p |
| curve coefficient a | -3 |
| curve coefficient b | b |
| generator g | g=(gx, gy) |
| private keys j and k | i and r |
| public keys g^j, g^k | g^i = (gix, giy) and g^r = (grx, gry) |
+----------------------+---------------------------------------+
It is possible to compute the square root modulo q, for instance, by 7.2. KT-I
using Shanks's method [K1987]. However, it is not as efficient to
convert an ECDSA signature (or an AECES signature) to an ECES A KT-I implementation can be validated using the known answer test
signature. cases from [RFC4754]. The correspondence between the notation in
that RFC and the notation in this note are summarized in the
following table.
+---------------------+------------------+
| KT-I | RFC 4754 |
+---------------------+------------------+
| order p of field Fp | p |
| curve coefficient a | -3 |
| curve coefficient b | b |
| generator alpha | g |
| group order q | q |
| private key z | w |
| public key Y | g^w = (gwx,gwy) |
| random k | ephem priv k |
| s1 | r |
| s2 | s |
| s2_inv | sinv |
| u1 | u = h*sinv mod q |
| u2 | v = r*sinv mod q |
+---------------------+------------------+
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 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, those for ECES were published were published during or before 1989, and those for KT-I were
during or before 1993, and those for AECES were published during or published during or before May, 1994. All of the normative text for
before October, 1994. All of the normative text for these algorithms these algorithms is based solely on their respective references.
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/.
skipping to change at page 21, line 30 skipping to change at page 20, line 30
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 belongs to a set of w elements. 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 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 9.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 elliptic curve group (e.g. each parameter "cofactor" [P1363]. Each ECC parameter set as in Section 3.3 is
set as in Section 3.2) 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 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).
skipping to change at page 22, line 48 skipping to change at page 21, line 48
This attack can gain useful information about an ECDH private key This attack can gain useful information about an ECDH private key
that is associated with a static public key, that is, a public key that is associated with a static public key, that is, a public key
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
representation (see Appendix C).
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].
If no hash function is used in an ElGamal signature system, then the
system is vulnerable to existential forgeries, in which an attacker
who does not know a private key can generate valid signatures for the
associated public key, but cannot generate a signature for a message
of its own choosing. (See [E1985] for instance.) The use of a
collision-resistant hash function eliminates this vulnerability.
In principle, any collision-resistant hash function is suitable for In principle, any collision-resistant hash function is suitable for
use in ECES or AECES. To facilitate interoperability, we recognize use in KT signatures. To facilitate interoperability, we recognize
the 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.2:
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 or AECES 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 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, and all of the cryptography, whose work made this note possible, and all of the
reviewers, who provided valuable constructive feedback. reviewers, who provided valuable constructive feedback. Thanks are
especially due to Howard Pinder and Andrey Jivsov.
12. References 12. References
12.1. Normative References 12.1. Normative References
[A1992] Anderson, J., "Response to the proposed DSS",
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",
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.
[D1966] Deskins, W., "Abstract Algebra", MacMillan Company , 1966. [CC1986] Chudnovsky, D. and G. Chudnovsky, "Sequences of numbers
generated by addition in formal groups and new primality
and factorization tests", Advances in Applied
Mathematics Volume 7, Issue 4, December 1986.
[D1966] Deskins, W., "Abstract Algebra", MacMillan Company New
York, 1966.
[DH1976] Diffie, W. and M. Hellman, "New Directions in [DH1976] Diffie, W. and M. Hellman, "New Directions in
Cryptography", IEEE Transactions in Information Cryptography", IEEE Transactions in Information
Theory IT-22, pp 644-654, 1976. Theory IT-22, pp 644-654, 1976.
[E1984a] ElGamal, T., "Cryptography and logarithms over finite
fields", Stanford University UMI Order No. DA 8420519,
1984.
[E1984b] ElGamal, T., "Cryptography and logarithms over finite
fields", Advances in Cryptology - CRYPTO '84
Proceedings Springer Lecture Notes in Computer Science
(LNCS) volume 196, 1984.
[E1985] ElGamal, T., "A public key cryptosystem and a signature
scheme based on discrete logarithms", IEEE Transactions on
Information Theory Vol 30, No. 4, pp. 469-472, 1985.
[FR1994] Frey, G. and H. Ruck, "A remark concerning m-divisibility [FR1994] Frey, G. and H. Ruck, "A remark concerning m-divisibility
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.
[HMP1994] Horster, P., Michels, M., and H. Petersen, "Meta-ElGamal
signature schemes", University of Technology Chemnitz-
Zwickau Department of Computer Science Technical
Report TR-94-5, May 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 [KT1994] Koyama, K. and Y. Tsuruoka, "Digital signature system
based on elliptic curve and signer device and verifier based on elliptic curve and signer device and verifier
device for said system", Japanese Unexamined Patent device for said system", Japanese Unexamined Patent
Application Publication H6-43809, February 18, 1994. Application Publication H6-43809, February 18, 1994.
skipping to change at page 27, line 20 skipping to change at page 24, line 14
[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.
[MQV1994] Menezes, A., Qu, M., and S. Vanstone, "Submission to the
IEEE P1363 Working Group (Part 6: Elliptic Curve Systems,
Draft 2)", Working Document , October, 1994.
[MV1993] Menezes, A. and S. Vanstone, "Elliptic Curve Cryptosystems
and Their Implementation", Journal of Cryptology Volume 6,
No. 4, pp209-224, 1993.
[R1992] Rivest, R., "Response to the proposed DSS", Communications
of the ACM v.35 n.7 p.41-47., July 1992.
12.2. Informative References 12.2. Informative References
[A1992] Anderson, J., "Response to the proposed DSS",
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
NIST Proposed Digital Signature Standard", Advances in
Cryptology - CRYPTO '92 Proceedings Springer Lecture Notes
in Computer Science (LNCS) volume 740, August 1992.
[DSA1991] "DIGITAL SIGNATURE STANDARD", Federal Register Vol. 56, [DSA1991] "DIGITAL SIGNATURE STANDARD", Federal Register Vol. 56,
August 1991. August 1991.
[E1984a] ElGamal, T., "Cryptography and logarithms over finite
fields", Stanford University UMI Order No. DA 8420519,
1984.
[E1984b] ElGamal, T., "Cryptography and logarithms over finite
fields", Advances in Cryptology - CRYPTO '84
Proceedings Springer Lecture Notes in Computer Science
(LNCS) volume 196, 1984.
[E1985] ElGamal, T., "A public key cryptosystem and a signature
scheme based on discrete logarithms", IEEE Transactions on
Information Theory Vol 30, No. 4, pp. 469-472, 1985.
[FIPS180-2] [FIPS180-2]
"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] "DIGITAL SIGNATURE STANDARD", Federal Information
Processing Standard FIPS-186, 1994. Processing Standard FIPS-186, May 1994.
[HP1994] Horster, P. and H. Petersen, "Verallgemeinerte ElGamal-
Signaturen", Proceedings der Fachtagung SIS '94, Verlag
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., Menezes, A., Vanstone, S., and T. Okamoto, Koyama, K., Maurer, U., Vanstone, S., and T. Okamoto, "New
"New Public-Key Schemes Based on Elliptic Curves over the Public-Key Schemes Based on Elliptic Curves over the Ring
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",
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
Schemes Based on the Discrete Logarithm Problem", Advances
in Cryptology - EUROCRYPT '94 Proceedings Springer Lecture
Notes in Computer Science (LNCS) volume 950, May 1994.
[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] Pohlig, 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.
[R1988] Rose, H., "A Course in Number Theory", Oxford University
Press , 1988.
[R1992] Rivest, R., "Response to the proposed DSS", Communications
of the ACM v.35 n.7 p.41-47., July 1992.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. 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.
[RFC4086] Eastlake, D., Schiller, J., and S. Crocker, "Randomness
Requirements for Security", BCP 106, RFC 4086, June 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.
[RFC4754] Fu, D. and J. Solinas, "IKE and IKEv2 Authentication Using
the Elliptic Curve Digital Signature Algorithm (ECDSA)",
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/ [SuiteB] "NSA Suite B Cryptography", Web Page http://www.nsa.gov/
ia/programs/suiteb_cryptography/index.shtml. 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.
skipping to change at page 31, line 5 skipping to change at page 27, line 43
because a particular marketplace requires it or because the because a particular marketplace requires it or because the
vendor feels that it enhances the product while another vendor vendor feels that it enhances the product while another vendor
may omit the same item. An implementation which does not include may omit the same item. An implementation which does not include
a particular option MUST be prepared to interoperate with another a particular option MUST be prepared to interoperate with another
implementation which does include the option, though perhaps with implementation which does include the option, though perhaps with
reduced functionality. In the same vein an implementation which reduced functionality. In the same vein an implementation which
does include a particular option MUST be prepared to interoperate does include a particular option MUST be prepared to interoperate
with another implementation which does not include the option with another implementation which does not include the option
(except, of course, for the feature the option provides.) (except, of course, for the feature the option provides.)
Appendix B. Random Number Generation Appendix B. Random Integer 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 -1, inclusive, for some positive integer t. Generate a and 2^t -1, inclusive, for some positive integer t. Generate a
random bit string that contains exactly t bits, and then convert the random bit string that contains exactly t bits, and then convert the
bit string to a non-negative integer by treating the bits as the bit string to a non-negative integer by treating the bits as the
coefficients in a 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
skipping to change at page 32, line 5 skipping to change at page 28, line 21
includes all numbers that satisfy property P (plus some other includes all numbers that satisfy property P (plus some other
numbers, preferably not too many) 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, inclusive, For example, to generate a number between 1 and n-1, inclusive,
repeatedly generate integers between zero and 2^t - 1, inclusive, repeatedly generate integers between zero and 2^t - 1, inclusive,
stopping at the first integer that falls within that interval. stopping at the first integer that falls within that interval.
Appendix C. Example Elliptic Curve Group Recommendations on how to generate random bit strings are provided in
[RFC4086].
Appendix C. Why Compact Representation Works
In the affine representation, the x-coordinate of the point P^i does
not depend on the y-coordinate of the point P, for any non-negative
exponent i and any point P. This fact can be seen as follows. When
given only the x-coordinate of a point P, it is not possible to
determine exactly what the y-coordinate is, but the y value will be a
solution to the curve equation
y^2 = x^3 + a*x + b (mod p).
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
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
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,
and then ignoring the y-coordinate of that result.
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.
When p = 3 (mod 4), the square roots of z mod p are w and -w mod p,
where
w = z ^ ((p+1)/4) (mod p);
this observation is due to Lehmer [L1969]. When p satisfies this
property, y can be computed from the curve equation, and either y = w
or y = -w mod p, where
w = (x^3 + a*x + b)^((p+1)/4) (mod 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
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
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
elliptic curve point. This is an important consideration when ECDH
is used with compact output; see Section 9.3.
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).
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
Yu 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.2, and express the generator in the affine coordinate Section 3.3, and express the generator in the affine coordinate
representation g=(gx,gy), where the values gx and gy are in Fp. 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
gy: 4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5 gy: 4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
Note that p can also be expressed as Note that p can also be expressed as
p = 2^(256)-2^(224)+2^(192)+2^(96)-1. p = 2^(256)-2^(224)+2^(192)+2^(96)-1.
Author's Address Appendix E. Additive and multiplicative notation
The early publications on elliptic curve cryptography used
multiplicative notation, but most modern publications use additive
notation. This section includes a table mapping between those two
conventions. In this section, a and b are elements of an elliptic
curve group, and N is an integer.
+-------------------------+-----------------------+
| Multiplicative Notation | Additive Notation |
+-------------------------+-----------------------+
| multiplication | addition |
| a * b | a + b |
| squaring | doubling |
| a * a = a^2 | a + a = 2a |
| exponentiation | scalar multiplication |
| a^N = a * a * ... * a | Na = a + a + ... + a |
| inverse | inverse |
| a^-1 | -a |
+-------------------------+-----------------------+
Authors' Addresses
David A. McGrew David A. McGrew
Cisco Systems Cisco Systems
510 McCarthy Blvd. 510 McCarthy Blvd.
Milpitas, CA 95035 Milpitas, CA 95035
US 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
National Security Agency
Commercial Solutions Center
United States of America
Email: kmigoe@nsa.gov
 End of changes. 139 change blocks. 
340 lines changed or deleted 623 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/