6090
INFORMATIONAL
Fundamental Elliptic Curve Cryptography Algorithms
Authors: D. McGrew, K. Igoe, M. Salter
Date: February 2011
Working Group: NON WORKING GROUP
Stream: IETF
Abstract
This note describes the fundamental algorithms of Elliptic Curve Cryptography (ECC) as they were defined in some seminal references from 1994 and earlier. 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. This document is not an Internet Standards Track specification; it is published for informational purposes.
RFC 6090
INFORMATIONAL
Errata Exist
Internet Engineering Task Force (IETF) D. McGrew
Request for Comments: 6090 Cisco Systems
Category: Informational K. Igoe
ISSN: 2070-1721 M. Salter
National Security Agency
February 2011
<span class="h1">Fundamental Elliptic Curve Cryptography Algorithms</span>
Abstract
This note describes the fundamental algorithms of Elliptic Curve
Cryptography (ECC) as they were defined in some seminal references
from 1994 and earlier. 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
This document is not an Internet Standards Track specification; it is
published for informational purposes.
This document is a product of the Internet Engineering Task Force
(IETF). It represents the consensus of the IETF community. It has
received public review and has been approved for publication by the
Internet Engineering Steering Group (IESG). Not all documents
approved by the IESG are a candidate for any level of Internet
Standard; see <a href="./rfc5741#section-2">Section 2 of RFC 5741</a>.
Information about the current status of this document, any errata,
and how to provide feedback on it may be obtained at
<a href="https://www.rfc-editor.org/info/rfc6090">http://www.rfc-editor.org/info/rfc6090</a>.
<span class="grey">McGrew, et al. Informational [Page 1]</span><span id="page-2" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
Copyright Notice
Copyright (c) 2011 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to <a href="https://www.rfc-editor.org/bcp/bcp78">BCP 78</a> and the IETF Trust's Legal
Provisions Relating to IETF Documents
(<a href="http://trustee.ietf.org/license-info">http://trustee.ietf.org/license-info</a>) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
<a href="#section-1">1</a>. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-3">3</a>
<a href="#section-1.1">1.1</a>. Conventions Used in This Document . . . . . . . . . . . . <a href="#page-4">4</a>
<a href="#section-2">2</a>. Mathematical Background . . . . . . . . . . . . . . . . . . . <a href="#page-4">4</a>
<a href="#section-2.1">2.1</a>. Modular Arithmetic . . . . . . . . . . . . . . . . . . . . <a href="#page-4">4</a>
<a href="#section-2.2">2.2</a>. Group Operations . . . . . . . . . . . . . . . . . . . . . <a href="#page-5">5</a>
<a href="#section-2.3">2.3</a>. The Finite Field Fp . . . . . . . . . . . . . . . . . . . <a href="#page-6">6</a>
<a href="#section-3">3</a>. Elliptic Curve Groups . . . . . . . . . . . . . . . . . . . . <a href="#page-7">7</a>
<a href="#section-3.1">3.1</a>. Homogeneous Coordinates . . . . . . . . . . . . . . . . . <a href="#page-8">8</a>
<a href="#section-3.2">3.2</a>. Other Coordinates . . . . . . . . . . . . . . . . . . . . <a href="#page-9">9</a>
<a href="#section-3.3">3.3</a>. ECC Parameters . . . . . . . . . . . . . . . . . . . . . . <a href="#page-9">9</a>
<a href="#section-3.3.1">3.3.1</a>. Discriminant . . . . . . . . . . . . . . . . . . . . . <a href="#page-10">10</a>
<a href="#section-3.3.2">3.3.2</a>. Security . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-10">10</a>
<a href="#section-4">4</a>. Elliptic Curve Diffie-Hellman (ECDH) . . . . . . . . . . . . . <a href="#page-10">10</a>
<a href="#section-4.1">4.1</a>. Data Types . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-11">11</a>
<a href="#section-4.2">4.2</a>. Compact Representation . . . . . . . . . . . . . . . . . . <a href="#page-11">11</a>
<a href="#section-5">5</a>. Elliptic Curve ElGamal Signatures . . . . . . . . . . . . . . <a href="#page-11">11</a>
<a href="#section-5.1">5.1</a>. Background . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-11">11</a>
<a href="#section-5.2">5.2</a>. Hash Functions . . . . . . . . . . . . . . . . . . . . . . <a href="#page-12">12</a>
<a href="#section-5.3">5.3</a>. KT-IV Signatures . . . . . . . . . . . . . . . . . . . . . <a href="#page-12">12</a>
<a href="#section-5.3.1">5.3.1</a>. Keypair Generation . . . . . . . . . . . . . . . . . . <a href="#page-12">12</a>
<a href="#section-5.3.2">5.3.2</a>. Signature Creation . . . . . . . . . . . . . . . . . . <a href="#page-13">13</a>
<a href="#section-5.3.3">5.3.3</a>. Signature Verification . . . . . . . . . . . . . . . . <a href="#page-13">13</a>
<a href="#section-5.4">5.4</a>. KT-I Signatures . . . . . . . . . . . . . . . . . . . . . <a href="#page-14">14</a>
<a href="#section-5.4.1">5.4.1</a>. Keypair Generation . . . . . . . . . . . . . . . . . . <a href="#page-14">14</a>
<a href="#section-5.4.2">5.4.2</a>. Signature Creation . . . . . . . . . . . . . . . . . . <a href="#page-14">14</a>
<a href="#section-5.4.3">5.4.3</a>. Signature Verification . . . . . . . . . . . . . . . . <a href="#page-14">14</a>
<a href="#section-5.5">5.5</a>. Converting KT-IV Signatures to KT-I Signatures . . . . . . <a href="#page-15">15</a>
<a href="#section-5.6">5.6</a>. Rationale . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-15">15</a>
<a href="#section-6">6</a>. Converting between Integers and Octet Strings . . . . . . . . <a href="#page-16">16</a>
<a href="#section-6.1">6.1</a>. Octet-String-to-Integer Conversion . . . . . . . . . . . . <a href="#page-17">17</a>
<a href="#section-6.2">6.2</a>. Integer-to-Octet-String Conversion . . . . . . . . . . . . <a href="#page-17">17</a>
<span class="grey">McGrew, et al. Informational [Page 2]</span><span id="page-3" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
<a href="#section-7">7</a>. Interoperability . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-17">17</a>
<a href="#section-7.1">7.1</a>. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-17">17</a>
<a href="#section-7.2">7.2</a>. KT-I and ECDSA . . . . . . . . . . . . . . . . . . . . . . <a href="#page-18">18</a>
<a href="#section-8">8</a>. Validating an Implementation . . . . . . . . . . . . . . . . . <a href="#page-18">18</a>
<a href="#section-8.1">8.1</a>. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-19">19</a>
<a href="#section-8.2">8.2</a>. KT-I . . . . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-20">20</a>
<a href="#section-9">9</a>. Intellectual Property . . . . . . . . . . . . . . . . . . . . <a href="#page-20">20</a>
<a href="#section-9.1">9.1</a>. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-20">20</a>
<a href="#section-10">10</a>. Security Considerations . . . . . . . . . . . . . . . . . . . <a href="#page-21">21</a>
<a href="#section-10.1">10.1</a>. Subgroups . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-21">21</a>
<a href="#section-10.2">10.2</a>. Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . <a href="#page-22">22</a>
<a href="#section-10.3">10.3</a>. Group Representation and Security . . . . . . . . . . . . <a href="#page-22">22</a>
<a href="#section-10.4">10.4</a>. Signatures . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-23">23</a>
<a href="#section-11">11</a>. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-23">23</a>
<a href="#section-12">12</a>. References . . . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-23">23</a>
<a href="#section-12.1">12.1</a>. Normative References . . . . . . . . . . . . . . . . . . . <a href="#page-23">23</a>
<a href="#section-12.2">12.2</a>. Informative References . . . . . . . . . . . . . . . . . . <a href="#page-25">25</a>
<a href="#appendix-A">Appendix A</a>. Key Words . . . . . . . . . . . . . . . . . . . . . . <a href="#page-29">29</a>
<a href="#appendix-B">Appendix B</a>. Random Integer Generation . . . . . . . . . . . . . . <a href="#page-29">29</a>
<a href="#appendix-C">Appendix C</a>. Why Compact Representation Works . . . . . . . . . . <a href="#page-30">30</a>
<a href="#appendix-D">Appendix D</a>. Example ECC Parameter Set . . . . . . . . . . . . . . <a href="#page-31">31</a>
<a href="#appendix-E">Appendix E</a>. Additive and Multiplicative Notation . . . . . . . . <a href="#page-32">32</a>
<a href="#appendix-F">Appendix F</a>. Algorithms . . . . . . . . . . . . . . . . . . . . . <a href="#page-32">32</a>
<a href="#appendix-F.1">F.1</a>. Affine Coordinates . . . . . . . . . . . . . . . . . . . . <a href="#page-32">32</a>
<a href="#appendix-F.2">F.2</a>. Homogeneous Coordinates . . . . . . . . . . . . . . . . . <a href="#page-33">33</a>
<span class="h2"><a class="selflink" id="section-1" href="#section-1">1</a>. Introduction</span>
ECC is a public-key technology that offers performance advantages at
higher security levels. It includes an elliptic curve version of the
Diffie-Hellman key exchange protocol [<a href="#ref-DH1976" title=""New Directions in Cryptography"">DH1976</a>] and elliptic curve
versions of the ElGamal Signature Algorithm [<a href="#ref-E1985" title=""A public key cryptosystem and a signature scheme based on discrete logarithms"">E1985</a>]. The adoption of
ECC has been slower than had been anticipated, perhaps due to the
lack of freely available normative documents and uncertainty over
intellectual property rights.
This note contains a description of the fundamental algorithms of ECC
over finite fields with characteristic greater than three, based
directly on original references. Its intent is to provide the
Internet community with a summary of the basic algorithms that
predate any specialized or optimized algorithms. The summary is
detailed enough for use as a normative reference. 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
<span class="grey">McGrew, et al. Informational [Page 3]</span><span id="page-4" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
some of the algorithms in these standards, with a suitable choice of
parameters and options. The specifics are itemized in <a href="#section-7">Section 7</a>.
The rest of the note is organized as follows. Sections <a href="#section-2.1">2.1</a>, <a href="#section-2.2">2.2</a>, and
2.3 furnish the necessary terminology and notation from modular
arithmetic, group theory, and the theory of finite fields,
respectively. <a href="#section-3">Section 3</a> defines the groups based on elliptic curves
over finite fields of characteristic greater than three. <a href="#section-4">Section 4</a>
presents the fundamental Elliptic Curve Diffie-Hellman (ECDH)
algorithm. <a href="#section-5">Section 5</a> presents elliptic curve versions of the ElGamal
signature method. The representation of integers as octet strings is
specified in <a href="#section-6">Section 6</a>. Sections <a href="#section-2">2</a> through <a href="#section-6">6</a>, inclusive, contain all
of the normative text (the text that defines the norm for
implementations conforming to this specification), and all of the
following sections are purely informative. Interoperability is
discussed in <a href="#section-7">Section 7</a>. Validation testing is described in
<a href="#section-8">Section 8</a>. <a href="#section-9">Section 9</a> reviews intellectual property issues.
<a href="#section-10">Section 10</a> summarizes security considerations. <a href="#appendix-B">Appendix B</a> describes
random number generation, and other appendices provide clarifying
details.
<span class="h3"><a class="selflink" id="section-1.1" href="#section-1.1">1.1</a>. Conventions Used in This Document</span>
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in <a href="#appendix-A">Appendix A</a>.
<span class="h2"><a class="selflink" id="section-2" href="#section-2">2</a>. Mathematical Background</span>
This section reviews mathematical preliminaries and establishes
terminology and notation that are used below.
<span class="h3"><a class="selflink" id="section-2.1" href="#section-2.1">2.1</a>. Modular Arithmetic</span>
This section reviews modular arithmetic. Two integers x and y are
said to be congruent modulo n if x - y is an integer multiple of n.
Two integers x and y are coprime when their greatest common divisor
is 1; in this case, there is no third number z > 1 such that z
divides x and z divides y.
The set Zq = { 0, 1, 2, ..., q-1 } is closed under the operations of
modular addition, modular subtraction, modular multiplication, and
modular inverse. These operations are as follows.
For each pair of integers a and b in Zq, a + b mod q is equal to
a + b if a + b < q, and is equal to a + b - q otherwise.
<span class="grey">McGrew, et al. Informational [Page 4]</span><span id="page-5" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
For each pair of integers a and b in Zq, a - b mod q is equal to
a - b if a - b >= 0, and is equal to a - b + q otherwise.
For each pair of integers a and b in Zq, a * b mod q is equal to
the remainder of a * b divided by q.
For each integer x in Zq that is coprime with q, the inverse of x
modulo q is denoted as 1/x mod q, and can be computed using the
extended Euclidean algorithm (see Section 4.5.2 of [<a href="#ref-K1981v2" title=""The Art of Computer Programming, Vol. 2: Seminumerical Algorithms"">K1981v2</a>], for
example).
Algorithms for these operations are well known; for instance, see
Chapter 4 of [<a href="#ref-K1981v2" title=""The Art of Computer Programming, Vol. 2: Seminumerical Algorithms"">K1981v2</a>].
<span class="h3"><a class="selflink" id="section-2.2" href="#section-2.2">2.2</a>. Group Operations</span>
This section establishes some terminology and notation for
mathematical groups, which are needed later on. Background
references abound; see [<a href="#ref-D1966" title=""Abstract Algebra"">D1966</a>], for example.
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
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 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-1 times to the
element 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
associativity of the group operation ensures that the computation of
a^n is unambiguous; any grouping of the terms gives the same result.
The above definition of a group operation uses multiplicative
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
multiplicative notation, a^N is called exponentiation, while the
equivalent operation in additive notation is called scalar
multiplication. In this document, multiplicative notation is used
throughout for consistency. <a href="#appendix-E">Appendix E</a> elucidates the correspondence
between the two notations.
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
convention, a^0 is equal to the identity element for any a in G.
Every group element a has a unique inverse element b such that
a * b = b * a = e. The inverse of a is denoted as a^-1 in
multiplicative notation. (In additive notation, the inverse of a is
denoted as -a.)
<span class="grey">McGrew, et al. Informational [Page 5]</span><span id="page-6" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
For any positive integer X, a^(-X) is defined to be (a^-1)^(X).
Using this convention, exponentiation behaves as one would expect,
namely for any integers X and Y:
a^(X+Y) = (a^X)*(a^Y)
(a^X)^Y = a^(XY) = (a^Y)^X.
In cryptographic applications, one typically deals with finite groups
(groups with a finite number of elements), and for such groups, the
number of elements of the group is also called the order of the
group. 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. All elements
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^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
multiply" method outlined in Section 2.1 of [<a href="#ref-M1983" title=""Logarithms in finite cyclic groups - cryptographic issues"">M1983</a>] (see also Knuth,
Vol. 2, <a href="#section-4.6.3">Section 4.6.3</a>), or other methods.
<span class="h3"><a class="selflink" id="section-2.3" href="#section-2.3">2.3</a>. The Finite Field Fp</span>
This section establishes terminology and notation for finite fields
with prime characteristic.
When p is a prime number, then the set Zp, with the addition,
subtraction, multiplication, and division operations, is a finite
field with characteristic p. Each nonzero element x in Zp has an
inverse 1/x. There is a one-to-one correspondence between the
integers between zero and p-1, inclusive, and the elements of the
field. The field Zp is sometimes denoted as Fp or GF(p).
<span class="grey">McGrew, et al. Informational [Page 6]</span><span id="page-7" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
Equations involving field elements do not explicitly denote the "mod
p" operation, but it is understood to be implicit. For example, the
statement that x, y, and z are in Fp and
z = x + y
is equivalent to the statement that x, y, and z are in the set
{ 0, 1, ..., p-1 } and
z = x + y mod p.
<span class="h2"><a class="selflink" id="section-3" href="#section-3">3</a>. Elliptic Curve Groups</span>
This note only covers elliptic curves over fields with characteristic
greater than three; these are the curves used in Suite B [<a href="#ref-SuiteB" title=""NSA Suite B Cryptography"">SuiteB</a>].
For other fields, the definition of the elliptic curve group would be
different.
An elliptic curve over a field Fp is defined by the curve equation
y^2 = x^3 + a*x + b,
where x, y, a, and b are elements of the field Fp [<a href="#ref-M1985" title=""Use of elliptic curves in cryptography"">M1985</a>], and the
discriminant is nonzero (as described in <a href="#section-3.3.1">Section 3.3.1</a>). A point on
an elliptic curve is a pair (x,y) of values in Fp that satisfies the
curve equation, or it is a special point (@,@) that represents the
identity element (which is called the "point at infinity"). The
order of an elliptic curve group is the number of distinct points.
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
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
follows [<a href="#ref-BC1989" title=""On the Implementation of Elliptic Curve Cryptosystems"">BC1989</a>]. To an arbitrary pair of points P and Q specified
by their coordinates (x1,y1) and (x2,y2), respectively, the group
operation assigns a third point P*Q with the coordinates (x3,y3).
These coordinates are computed as follows:
(x3,y3) = (@,@) when P is not equal to Q and x1 is equal to x2.
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
x1 is not equal to x2.
(x3,y3) = (@,@) when P is equal to Q and y1 is equal to 0.
<span class="grey">McGrew, et al. Informational [Page 7]</span><span id="page-8" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
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
not equal to 0.
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 right-hand-side modulo p. Pseudocode for the group operation is
provided in <a href="#appendix-F.1">Appendix F.1</a>.
The representation of elliptic curve points as a pair of integers in
Zp is known as the affine coordinate representation. This
representation is suitable as an external data representation for
communicating or storing group elements, though the point at infinity
must be treated as a special case.
Some pairs of integers are not valid elliptic curve points. A valid
pair will satisfy the curve equation, while an invalid pair will not.
<span class="h3"><a class="selflink" id="section-3.1" href="#section-3.1">3.1</a>. Homogeneous Coordinates</span>
An alternative way to implement the group operation is to use
homogeneous coordinates [<a href="#ref-K1987" title=""Elliptic Curve Cryptosystems"">K1987</a>] (see also [<a href="#ref-KMOV1991" title=""New Public-Key Schemes Based on Elliptic Curves over the Ring Zn"">KMOV1991</a>]). This method
is typically more efficient because it does not require a modular
inversion operation.
An elliptic curve point (x,y) (other than the point at infinity
(@,@)) is equivalent to a point (X,Y,Z) in homogeneous coordinates
whenever x=X/Z mod p and y=Y/Z mod p.
Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on an elliptic curve,
and suppose that the points P1 and P2 are not equal to (@,@), P1 is
not equal to P2, and P1 is not equal to P2^-1. Then the product
P3=(X3,Y3,Z3) = P1 * P2 is given by
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) + u * v^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.
When the points P1 and P2 are equal, then (X1/Z1, Y1/Z1) is equal to
(X2/Z2, Y2/Z2), which is true if and only if u and v are both equal
to zero.
<span class="grey">McGrew, et al. Informational [Page 8]</span><span id="page-9" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
The product P3=(X3,Y3,Z3) = P1 * P1 is given by
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
Z3 = 8 * (Y1 * Z1)^3 mod p
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
Fp. Pseudocode for the group operation in homogeneous coordinates is
provided in <a href="#appendix-F.2">Appendix F.2</a>.
When converting from affine coordinates to homogeneous coordinates,
it is convenient to set Z to 1. When converting from homogeneous
coordinates to affine coordinates, it is necessary to perform a
modular inverse to find 1/Z mod p.
<span class="h3"><a class="selflink" id="section-3.2" href="#section-3.2">3.2</a>. Other Coordinates</span>
Some other coordinate systems have been described; several are
documented in [<a href="#ref-CC1986" title=""Sequences of numbers generated by addition in formal groups and new primality and factorization tests"">CC1986</a>], including Jacobi coordinates.
<span class="h3"><a class="selflink" id="section-3.3" href="#section-3.3">3.3</a>. ECC Parameters</span>
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 value a used in the curve equation.
The value b used in the curve equation.
The generator g of the subgroup.
The order n of the subgroup generated by g.
An example of an ECC parameter set is provided in <a href="#appendix-D">Appendix D</a>.
Parameter generation is out of scope for this note.
Each elliptic curve point is associated with a particular parameter
set. The elliptic curve group operation is only defined between two
points in the same group. It is an error to apply the group
<span class="grey">McGrew, et al. Informational [Page 9]</span><span id="page-10" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
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
point. (A pair (x,y) of coordinates in Fp is a valid point only when
it satisfies the curve equation.) See <a href="#section-10.3">Section 10.3</a> for further
information.
<span class="h4"><a class="selflink" id="section-3.3.1" href="#section-3.3.1">3.3.1</a>. Discriminant</span>
For each elliptic curve group, the discriminant -16*(4*a^3 + 27*b^2)
must be nonzero modulo p [<a href="#ref-S1986" title=""The Arithmetic of Elliptic Curves"">S1986</a>]; this requires that
4*a^3 + 27*b^2 != 0 mod p.
<span class="h4"><a class="selflink" id="section-3.3.2" href="#section-3.3.2">3.3.2</a>. Security</span>
Security is highly dependent on the choice of these parameters. This
section gives normative guidance on acceptable choices. See also
<a href="#section-10">Section 10</a> for informative guidance.
The order of the group generated by g MUST be divisible by a large
prime, in order to preclude easy solutions of the discrete logarithm
problem [<a href="#ref-K1987" title=""Elliptic Curve Cryptosystems"">K1987</a>].
With some parameter choices, the discrete log problem is
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
p = 2 (mod 3) [<a href="#ref-MOV1993" title=""Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field"">MOV1993</a>]. These parameter choices are inferior for
cryptographic purposes and SHOULD NOT be used.
<span class="h2"><a class="selflink" id="section-4" href="#section-4">4</a>. Elliptic Curve Diffie-Hellman (ECDH)</span>
The Diffie-Hellman (DH) key exchange protocol [<a href="#ref-DH1976" title=""New Directions in Cryptography"">DH1976</a>] allows two
parties communicating over an insecure channel to agree on a secret
key. It was originally defined in terms of operations in the
multiplicative group of a field with a large prime characteristic.
Massey [<a href="#ref-M1983" title=""Logarithms in finite cyclic groups - cryptographic issues"">M1983</a>] observed that it can be easily generalized so that it
is defined in terms of an arbitrary cyclic group. Miller [<a href="#ref-M1985" title=""Use of elliptic curves in cryptography"">M1985</a>] and
Koblitz [<a href="#ref-K1987" title=""Elliptic Curve Cryptosystems"">K1987</a>] analyzed the DH protocol over an elliptic 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
denote the order of G. The DH protocol runs as follows. Party A
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 exponent k between 1 and t-1, inclusive, uniformly at random,
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.
<span class="grey">McGrew, et al. Informational [Page 10]</span><span id="page-11" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
See <a href="#appendix-B">Appendix B</a> regarding generation of random integers.
<span class="h3"><a class="selflink" id="section-4.1" href="#section-4.1">4.1</a>. Data Types</span>
Each run of the ECDH protocol is associated with a particular
parameter set (as defined in <a href="#section-3.3">Section 3.3</a>), and the public keys g^j
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.
<span class="h3"><a class="selflink" id="section-4.2" href="#section-4.2">4.2</a>. Compact Representation</span>
As described in the final paragraph of [<a href="#ref-M1985" title=""Use of elliptic curves in cryptography"">M1985</a>], the x-coordinate of
the shared secret value g^(j*k) is a suitable representative for the
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
computed, the x-coordinate of that value can be used as the shared
secret. We call this compact output.
Following [<a href="#ref-M1985" title=""Use of elliptic curves in cryptography"">M1985</a>] again, when compact output is used in ECDH, only
the x-coordinate of an elliptic curve point needs to be transmitted,
instead of both coordinates as in the typical affine coordinate
representation. We call this the compact representation. Its
mathematical background is explained in <a href="#appendix-C">Appendix C</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
can be used with or without compact representation. If compact
representation is used in a particular run of the ECDH protocol, then
compact output MUST be used as well.
<span class="h2"><a class="selflink" id="section-5" href="#section-5">5</a>. Elliptic Curve ElGamal Signatures</span>
<span class="h3"><a class="selflink" id="section-5.1" href="#section-5.1">5.1</a>. Background</span>
The ElGamal signature algorithm was introduced in 1984 [<a href="#ref-E1984a" title=""Cryptography and logarithms over finite fields"">E1984a</a>]
[<a href="#ref-E1984b" title=""Cryptography and logarithms over finite fields"">E1984b</a>] [<a href="#ref-E1985" title=""A public key cryptosystem and a signature scheme based on discrete logarithms"">E1985</a>]. It is based on the discrete logarithm problem, and
was originally defined for the multiplicative group of the integers
modulo a large prime number. It is straightforward to extend it to
use other finite groups, such as the multiplicative group of the
finite field GF(2^w) [<a href="#ref-AMV1990" title=""Improved Digital Signature Scheme based on Discrete Exponentiation"">AMV1990</a>] or an elliptic curve group [<a href="#ref-A1992" title=""Response to the proposed DSS"">A1992</a>].
An ElGamal signature consists of a pair of components. There are
many possible generalizations of ElGamal signature methods that have
been obtained by different rearrangements of the equation for the
second component; see [<a href="#ref-HMP1994" title=""Meta-ElGamal signature schemes"">HMP1994</a>], [<a href="#ref-HP1994" title=""Verallgemeinerte ElGamal- Signaturen"">HP1994</a>], [<a href="#ref-NR1994" title=""Message Recovery for Signature Schemes Based on the Discrete Logarithm Problem"">NR1994</a>], [<a href="#ref-A1992" title=""Response to the proposed DSS"">A1992</a>], and
<span class="grey">McGrew, et al. Informational [Page 11]</span><span id="page-12" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
[<a href="#ref-AMV1990" title=""Improved Digital Signature Scheme based on Discrete Exponentiation"">AMV1990</a>]. 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 [<a href="#ref-HMP1994" title=""Meta-ElGamal signature schemes"">HMP1994</a>] [<a href="#ref-NR1994" title=""Message Recovery for Signature Schemes Based on the Discrete Logarithm Problem"">NR1994</a>] [<a href="#ref-AMV1990" title=""Improved Digital Signature Scheme based on Discrete Exponentiation"">AMV1990</a>] [<a href="#ref-A1992" title=""Response to the proposed DSS"">A1992</a>].
The Digital Signature Algorithm (DSA) [<a href="#ref-FIPS186" title=""DIGITAL SIGNATURE STANDARD"">FIPS186</a>] is an important
ElGamal signature variant.
<span class="h3"><a class="selflink" id="section-5.2" href="#section-5.2">5.2</a>. Hash Functions</span>
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 <a href="#section-10.4">Section 10.4</a>. (This is true for all
ElGamal variants [<a href="#ref-HMP1994" title=""Meta-ElGamal signature schemes"">HMP1994</a>].) We denote the hash function as h().
Its input is a bit string of arbitrary length, and its output is a
non-negative integer.
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
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:
1. H(m) is evaluated; the result is a fixed-length bit string.
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.
<span class="h3"><a class="selflink" id="section-5.3" href="#section-5.3">5.3</a>. KT-IV Signatures</span>
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 [<a href="#ref-KT1994" title=""Digital signature system based on elliptic curve and signer device and verifier device for said system"">KT1994</a>].
In this section, we recall that method, which we refer to as KT-IV.
The algorithm uses an elliptic curve group, as described in
<a href="#section-3.3">Section 3.3</a>, 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 [<a href="#ref-FIPS186" title=""DIGITAL SIGNATURE STANDARD"">FIPS186</a>] in checking for exceptional
cases.
<span class="h4"><a class="selflink" id="section-5.3.1" href="#section-5.3.1">5.3.1</a>. Keypair Generation</span>
The private key z is an integer between 1 and q-1, inclusive,
generated uniformly at random. (See <a href="#appendix-B">Appendix B</a> regarding random
integers.) The public key is the group element Y = alpha^z. Each
<span class="grey">McGrew, et al. Informational [Page 12]</span><span id="page-13" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
public key is associated with a particular parameter set as per
<a href="#section-3.3">Section 3.3</a>.
<span class="h4"><a class="selflink" id="section-5.3.2" href="#section-5.3.2">5.3.2</a>. Signature Creation</span>
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
integers between 1 and q-1, inclusive. (See <a href="#appendix-B">Appendix B</a> regarding
random integers.)
2. Calculate R = (r_x, r_y) = alpha^k.
3. Calculate s1 = r_x 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. Calculate s2 = k/(h(m) + z*s1) mod q.
The signature is the ordered pair (s1, s2). Both signature
components are non-negative integers.
<span class="h4"><a class="selflink" id="section-5.3.3" href="#section-5.3.3">5.3.3</a>. Signature Verification</span>
Given the message m, the generator g, the group order q, the public
key Y, and the signature (s1, s2), verification is as follows:
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 u1 and u2, where
u1 = h(m) * s2 mod q, and
u2 = s1 * s2 mod q.
3. Compute the elliptic curve point R' = alpha^u1 * Y^u2.
4. If the x-coordinate of R' mod q is equal to s1, then the
signature and message pass the verification; otherwise, they
fail.
<span class="grey">McGrew, et al. Informational [Page 13]</span><span id="page-14" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
<span class="h3"><a class="selflink" id="section-5.4" href="#section-5.4">5.4</a>. KT-I Signatures</span>
Horster, Michels, and Petersen categorized many different ElGamal
signature methods, demonstrated their equivalence, and showed how to
convert signatures of one type to another type [<a href="#ref-HMP1994" title=""Meta-ElGamal signature schemes"">HMP1994</a>]. In their
terminology, the signature method of <a href="#section-5.3">Section 5.3</a> and [<a href="#ref-KT1994" title=""Digital signature system based on elliptic curve and signer device and verifier device for said system"">KT1994</a>] is a
Type IV method, which is why it is denoted as KT-IV.
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.
<span class="h4"><a class="selflink" id="section-5.4.1" href="#section-5.4.1">5.4.1</a>. Keypair Generation</span>
Keypairs and keypair generation are exactly as in <a href="#section-5.3.1">Section 5.3.1</a>.
<span class="h4"><a class="selflink" id="section-5.4.2" href="#section-5.4.2">5.4.2</a>. Signature Creation</span>
To compute a KT-I signature for a message m using the private key z:
1. Choose an integer k uniformly at random from the set of all
integers between 1 and q-1, inclusive. (See <a href="#appendix-B">Appendix B</a> regarding
random integers.)
2. Calculate R = (r_x, r_y) = alpha^k.
3. Calculate s1 = r_x mod q.
4. Calculate s2 = (h(m) + z*s1)/k mod q.
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.)
The signature is the ordered pair (s1, s2). Both signature
components are non-negative integers.
<span class="h4"><a class="selflink" id="section-5.4.3" href="#section-5.4.3">5.4.3</a>. Signature Verification</span>
Given the message m, the public key Y, and the signature (s1, s2),
verification is as follows:
1. Check to see that 0 < s1 < q and 0 < s2 < q; if either condition
is violated, the signature SHALL be rejected.
2. Compute s2_inv = 1/s2 mod q.
<span class="grey">McGrew, et al. Informational [Page 14]</span><span id="page-15" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
3. Compute the non-negative integers u1 and u2, where
u1 = h(m) * s2_inv mod q, and
u2 = s1 * s2_inv mod q.
4. Compute the elliptic curve point R' = alpha^u1 * Y^u2.
5. If the x-coordinate of R' mod q is equal to s1, then the
signature and message pass the verification; otherwise, they
fail.
<span class="h3"><a class="selflink" id="section-5.5" href="#section-5.5">5.5</a>. Converting KT-IV Signatures to KT-I Signatures</span>
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 [<a href="#ref-HMP1994" title=""Meta-ElGamal signature schemes"">HMP1994</a>].
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.
<span class="h3"><a class="selflink" id="section-5.6" href="#section-5.6">5.6</a>. Rationale</span>
This subsection is not normative for this specification and is
provided only as background information.
[<a id="ref-HMP1994">HMP1994</a>] 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
[<a href="#ref-HMP1994" title=""Meta-ElGamal signature schemes"">HMP1994</a>]. DSA [<a href="#ref-FIPS186" title=""DIGITAL SIGNATURE STANDARD"">FIPS186</a>] 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
[<a href="#ref-HMP1994" title=""Meta-ElGamal signature schemes"">HMP1994</a>] 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).
<span class="grey">McGrew, et al. Informational [Page 15]</span><span id="page-16" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
The signature method of [<a href="#ref-KT1994" title=""Digital signature system based on elliptic curve and signer device and verifier device for said system"">KT1994</a>] and <a href="#section-5.3">Section 5.3</a> 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 of [<a href="#ref-HMP1994" title=""Meta-ElGamal signature schemes"">HMP1994</a>] are merely
multiplication, as described under the heading "Fifth
generalization".
In the above equations, we rely on the implicit conversion of the
message m from a bit string to an integer. No hash function is shown
in these equations, but, as described in <a href="#section-10.4">Section 10.4</a>, a hash
function should be applied to the message prior to signing in order
to prevent existential forgery attacks.
Nyberg and Rueppel [<a href="#ref-NR1994" title=""Message Recovery for Signature Schemes Based on the Discrete Logarithm Problem"">NR1994</a>] 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 [<a href="#ref-FIPS186" title=""DIGITAL SIGNATURE STANDARD"">FIPS186</a>] in checking for this
exceptional case and the case that s1=0. The s2=0 check was
suggested by Rivest [<a href="#ref-R1992" title=""Response to the proposed DSS"">R1992</a>] and is discussed in [<a href="#ref-BS1992" title=""Response to Comments on the NIST Proposed Digital Signature Standard"">BS1992</a>].
[<a id="ref-KT1994">KT1994</a>] 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.
<span class="h2"><a class="selflink" id="section-6" href="#section-6">6</a>. Converting between Integers and Octet Strings</span>
A method for the conversion between integers and octet strings is
specified in this section, following the established conventions of
public key cryptography [<a href="#ref-R1993" title=""PKCS#1: RSA Encryption Standard"">R1993</a>]. 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.
<span class="grey">McGrew, et al. Informational [Page 16]</span><span id="page-17" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
<span class="h3"><a class="selflink" id="section-6.1" href="#section-6.1">6.1</a>. Octet-String-to-Integer Conversion</span>
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).
<span class="h3"><a class="selflink" id="section-6.2" href="#section-6.2">6.2</a>. Integer-to-Octet-String Conversion</span>
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.
<span class="h2"><a class="selflink" id="section-7" href="#section-7">7</a>. Interoperability</span>
The algorithms in this note can be used to interoperate with some
other ECC specifications. This section provides details for each
algorithm.
<span class="h3"><a class="selflink" id="section-7.1" href="#section-7.1">7.1</a>. ECDH</span>
<a href="#section-4">Section 4</a> can be used with the Internet Key Exchange (IKE) versions
one [<a href="./rfc2409" title=""The Internet Key Exchange (IKE)"">RFC2409</a>] or two [<a href="./rfc5996" title=""Internet Key Exchange Protocol Version 2 (IKEv2)"">RFC5996</a>]. These algorithms are compatible with
the ECP groups defined by [<a href="./rfc5903" title=""Elliptic Curve Groups modulo a Prime (ECP Groups) for IKE and IKEv2"">RFC5903</a>], [<a href="./rfc5114" title=""Additional Diffie-Hellman Groups for Use with IETF Standards"">RFC5114</a>], [<a href="./rfc2409" title=""The Internet Key Exchange (IKE)"">RFC2409</a>], and
[<a href="./rfc2412" title=""The OAKLEY Key Determination Protocol"">RFC2412</a>]. The group definition in this protocol uses an affine
coordinate representation of the public key. [<a href="./rfc5903" title=""Elliptic Curve Groups modulo a Prime (ECP Groups) for IKE and IKEv2"">RFC5903</a>] uses the
compact output of <a href="#section-4.2">Section 4.2</a>, while [<a href="./rfc4753" title=""ECP Groups For IKE and IKEv2"">RFC4753</a>] (which was obsoleted
by <a href="./rfc5903">RFC 5903</a>) does not. Neither of those RFCs use compact
representation. Note that some groups indicate that the curve
parameter "a" is negative; these values are to be interpreted modulo
the order of the field. For example, a parameter of a = -3 is equal
to p - 3, where p is the order of the field. The test cases in
<span class="grey">McGrew, et al. Informational [Page 17]</span><span id="page-18" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
<a href="./rfc5903#section-8">Section 8 of [RFC5903]</a> 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 <a href="#section-4">Section 4</a> can be used to interoperate with the IEEE
[<a href="#ref-P1363" title=""Standard Specifications for Public Key Cryptography"">P1363</a>] and ANSI [<a href="#ref-X9.62" title=""Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)"">X9.62</a>] standards for ECDH based on fields of
characteristic greater than three. IEEE P1363 ECDH can be used in a
manner that will interoperate with this note, with the following
options and parameter choices from that specification:
prime curves with a cofactor of 1,
the ECSVDP-DH (Elliptic Curve Secret Value Derivation Primitive,
Diffie-Hellman version),
the Key Derivation Function (KDF) must be the "identity" function
(equivalently, the KDF step should be omitted and the shared
secret value should be output directly).
<span class="h3"><a class="selflink" id="section-7.2" href="#section-7.2">7.2</a>. KT-I and ECDSA</span>
The Digital Signature Algorithm (DSA) is based on the discrete
logarithm problem over the multiplicative subgroup of the finite
field with large prime order [<a href="#ref-DSA1991" title=""DIGITAL SIGNATURE STANDARD"">DSA1991</a>] [<a href="#ref-FIPS186" title=""DIGITAL SIGNATURE STANDARD"">FIPS186</a>]. The Elliptic Curve
Digital Signature Algorithm (ECDSA) [<a href="#ref-P1363" title=""Standard Specifications for Public Key Cryptography"">P1363</a>] [<a href="#ref-X9.62" title=""Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)"">X9.62</a>] is an elliptic
curve version of DSA.
KT-I is mathematically and functionally equivalent to ECDSA, and can
interoperate with the IEEE [<a href="#ref-P1363" title=""Standard Specifications for Public Key Cryptography"">P1363</a>] and ANSI [<a href="#ref-X9.62" title=""Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)"">X9.62</a>] standards for
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.
<span class="h2"><a class="selflink" id="section-8" href="#section-8">8</a>. Validating an Implementation</span>
It is essential to validate the implementation of a cryptographic
algorithm. This section outlines tests that should be performed on
the algorithms defined in this note.
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.
<span class="grey">McGrew, et al. Informational [Page 18]</span><span id="page-19" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
A consistency test generates inputs for one algorithm being tested
using a second algorithm that is also being tested, then checks the
output of the first algorithm. A signature creation algorithm can be
tested for consistency against a signature verification algorithm.
Implementations of KT-I should be tested in this way. Their
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.
<span class="h3"><a class="selflink" id="section-8.1" href="#section-8.1">8.1</a>. ECDH</span>
An ECDH implementation can be validated using the known answer test
cases from [<a href="./rfc5903" title=""Elliptic Curve Groups modulo a Prime (ECP Groups) for IKE and IKEv2"">RFC5903</a>] or [<a href="./rfc5114" title=""Additional Diffie-Hellman Groups for Use with IETF Standards"">RFC5114</a>]. The correspondence between the
notation in <a href="./rfc5903">RFC 5903</a> and the notation in this note is summarized in
the following table. (Refer to Sections <a href="#section-3.3">3.3</a> and <a href="#section-4">4</a>; the generator g
is expressed in affine coordinate representation as (gx, gy)).
+----------------------+---------------------------------------+
| ECDH | <a href="./rfc5903">RFC 5903</a> |
+----------------------+---------------------------------------+
| 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) |
+----------------------+---------------------------------------+
The correspondence between the notation in <a href="./rfc5114">RFC 5114</a> and the notation
in this note is summarized in the following table.
+-----------------------+---------------------------+
| ECDH | <a href="./rfc5114">RFC 5114</a> |
+-----------------------+---------------------------+
| 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) |
+-----------------------+---------------------------+
<span class="grey">McGrew, et al. Informational [Page 19]</span><span id="page-20" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
<span class="h3"><a class="selflink" id="section-8.2" href="#section-8.2">8.2</a>. KT-I</span>
A KT-I implementation can be validated using the known answer test
cases from [<a href="./rfc4754" title=""IKE and IKEv2 Authentication Using the Elliptic Curve Digital Signature Algorithm (ECDSA)"">RFC4754</a>]. The correspondence between the notation in
that RFC and the notation in this note is summarized in the following
table.
+---------------------+------------------+
| KT-I | <a href="./rfc4754">RFC 4754</a> |
+---------------------+------------------+
| 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 |
+---------------------+------------------+
<span class="h2"><a class="selflink" id="section-9" href="#section-9">9</a>. Intellectual Property</span>
Concerns about intellectual property have slowed the adoption of ECC
because a number of optimizations and specialized algorithms have
been patented in recent years.
All of the normative references for ECDH (as defined in <a href="#section-4">Section 4</a>)
were published during or before 1989, and those for KT-I were
published during or before May 1994. All of the normative text for
these algorithms is based solely on their respective references.
<span class="h3"><a class="selflink" id="section-9.1" href="#section-9.1">9.1</a>. Disclaimer</span>
This document is not intended as legal advice. Readers are advised
to consult their own legal advisers if they would like a legal
interpretation of their rights.
The IETF policies and processes regarding intellectual property and
patents are outlined in [<a href="./rfc3979" title=""Intellectual Property Rights in IETF Technology"">RFC3979</a>] and [<a href="./rfc4879" title=""Clarification of the Third Party Disclosure Procedure in RFC 3979"">RFC4879</a>] and at
<a href="https://datatracker.ietf.org/ipr/about/">https://datatracker.ietf.org/ipr/about/</a>.
<span class="grey">McGrew, et al. Informational [Page 20]</span><span id="page-21" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
<span class="h2"><a class="selflink" id="section-10" href="#section-10">10</a>. Security Considerations</span>
The security level of an elliptic curve cryptosystem is determined by
the cryptanalytic algorithm that is the least expensive for an
attacker to implement. There are several algorithms to consider.
The Pohlig-Hellman method is a divide-and-conquer technique [<a href="#ref-PH1978" title=""An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance"">PH1978</a>].
If the group order n can be factored as
n = q1 * q2 * ... * qz,
then the discrete log problem over the group can be solved by
independently solving a discrete log problem in groups of order q1,
q2, ..., qz, then combining the results using the Chinese remainder
theorem. The overall computational cost is dominated by that of the
discrete log problem in the subgroup with the largest order.
Shanks' algorithm [<a href="#ref-K1981v3" title=""The Art of Computer Programming, Vol. 3: Sorting and Searching"">K1981v3</a>] computes a discrete logarithm in a group
of order n using O(sqrt(n)) operations and O(sqrt(n)) storage. The
Pollard rho algorithm [<a href="#ref-P1978" title=""Monte Carlo methods for index computation mod p"">P1978</a>] computes a discrete logarithm in a
group of order n using O(sqrt(n)) operations, with a negligible
amount of storage, and can be efficiently parallelized [<a href="#ref-VW1994" title=""Parallel Collision Search with Application to Hash Functions and Discrete Logarithms"">VW1994</a>].
The Pollard lambda algorithm [<a href="#ref-P1978" title=""Monte Carlo methods for index computation mod p"">P1978</a>] can solve the discrete logarithm
problem using O(sqrt(w)) operations and O(log(w)) storage, when the
exponent is known to lie in an interval of width w.
The algorithms described above work in any group. There are
specialized algorithms that specifically target elliptic curve
groups. There are no known subexponential algorithms against general
elliptic curve groups, though there are methods that target certain
special elliptic curve groups; see [<a href="#ref-MOV1993" title=""Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field"">MOV1993</a>] and [<a href="#ref-FR1994" title=""A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves."">FR1994</a>].
<span class="h3"><a class="selflink" id="section-10.1" href="#section-10.1">10.1</a>. Subgroups</span>
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
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
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.
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, m = n * c for some number c. The number c is called the
"cofactor" [<a href="#ref-P1363" title=""Standard Specifications for Public Key Cryptography"">P1363</a>]. Each ECC parameter set as in <a href="#section-3.3">Section 3.3</a> is
associated with a particular cofactor.
<span class="grey">McGrew, et al. Informational [Page 21]</span><span id="page-22" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
It is possible and desirable to use a cofactor equal to 1.
<span class="h3"><a class="selflink" id="section-10.2" href="#section-10.2">10.2</a>. Diffie-Hellman</span>
Note that the key exchange protocol as defined in <a href="#section-4">Section 4</a> does not
protect against active attacks; Party A must use some method to
ensure that (g^k) originated with the intended communicant B, rather
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
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
exchanged should be directly authenticated. This is the strategy
used by protocols that build on Diffie-Hellman and that use end-
entity authentication to protect against active attacks, such as
OAKLEY [<a href="./rfc2412" title=""The OAKLEY Key Determination Protocol"">RFC2412</a>] and the Internet Key Exchange [<a href="./rfc2409" title=""The Internet Key Exchange (IKE)"">RFC2409</a>] [<a href="./rfc4306" title=""Internet Key Exchange (IKEv2) Protocol"">RFC4306</a>]
[<a href="./rfc5996" title=""Internet Key Exchange Protocol Version 2 (IKEv2)"">RFC5996</a>].
When the cofactor of a group is not equal to 1, there are a number of
attacks that are possible against ECDH. See [<a href="#ref-VW1996" title=""On Diffie-Hellman key agreement with short exponents"">VW1996</a>], [<a href="#ref-AV1996" title=""Minding Your P's and Q's"">AV1996</a>], and
[<a href="#ref-LL1997" title=""A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroup"">LL1997</a>].
<span class="h3"><a class="selflink" id="section-10.3" href="#section-10.3">10.3</a>. Group Representation and Security</span>
The elliptic curve group operation does not explicitly incorporate
the parameter b from the curve equation. This opens the possibility
that a malicious attacker could learn information about an ECDH
private key by submitting a bogus public key [<a href="#ref-BMM2000" title=""Differential fault analysis on elliptic curve cryptosystems"">BMM2000</a>]. An attacker
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
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
fact that the group operations using the private key of the device
under attack are effectively taking place in G' instead of G.
This attack can gain useful information about an ECDH private key
that is associated with a static public key, i.e., a public key that
is used in more than one run of the protocol. However, it does not
gain any useful information against ephemeral keys.
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
appropriate elliptic curve.
These considerations also apply when ECDH is used with compact
representation (see <a href="#appendix-C">Appendix C</a>).
<span class="grey">McGrew, et al. Informational [Page 22]</span><span id="page-23" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
<span class="h3"><a class="selflink" id="section-10.4" href="#section-10.4">10.4</a>. Signatures</span>
Elliptic curve parameters should only be used if they come from a
trusted source; otherwise, some attacks are possible [<a href="#ref-AV1996" title=""Minding Your P's and Q's"">AV1996</a>]
[<a href="#ref-V1996" title=""Hidden Collisions on DSS"">V1996</a>].
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 [<a href="#ref-E1985" title=""A public key cryptosystem and a signature scheme based on discrete logarithms"">E1985</a>] for instance.) The use of a
collision-resistant hash function eliminates this vulnerability.
In principle, any collision-resistant hash function is suitable for
use in KT signatures. To facilitate interoperability, we recognize
the following hashes as suitable for use as the function H defined in
<a href="#section-5.2">Section 5.2</a>:
SHA-256, which has a 256-bit output.
SHA-384, which has a 384-bit output.
SHA-512, which has a 512-bit output.
All of these hash functions are defined in [<a href="#ref-FIPS180-2" title=""SECURE HASH STANDARD"">FIPS180-2</a>].
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
the group order.
<span class="h2"><a class="selflink" id="section-11" href="#section-11">11</a>. Acknowledgements</span>
The author expresses his thanks to the originators of elliptic curve
cryptography, whose work made this note possible, and all of the
reviewers, who provided valuable constructive feedback. Thanks are
especially due to Howard Pinder, Andrey Jivsov, Alfred Hoenes (who
contributed the algorithms in <a href="#appendix-F">Appendix F</a>), Dan Harkins, and Tina
Tsou.
<span class="h2"><a class="selflink" id="section-12" href="#section-12">12</a>. References</span>
<span class="h3"><a class="selflink" id="section-12.1" href="#section-12.1">12.1</a>. Normative References</span>
[<a id="ref-AMV1990">AMV1990</a>] Agnew, G., Mullin, R., and S. Vanstone, "Improved
Digital Signature Scheme based on Discrete
Exponentiation", Electronics Letters Vol. 26, No. 14,
July, 1990.
<span class="grey">McGrew, et al. Informational [Page 23]</span><span id="page-24" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
[<a id="ref-BC1989">BC1989</a>] Bender, A. and G. Castagnoli, "On the Implementation of
Elliptic Curve Cryptosystems", Advances in Cryptology -
CRYPTO '89 Proceedings, Springer Lecture Notes in
Computer Science (LNCS), volume 435, 1989.
[<a id="ref-CC1986">CC1986</a>] 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.
[<a id="ref-D1966">D1966</a>] Deskins, W., "Abstract Algebra", MacMillan Company New
York, 1966.
[<a id="ref-DH1976">DH1976</a>] Diffie, W. and M. Hellman, "New Directions in
Cryptography", IEEE Transactions in Information
Theory IT-22, pp. 644-654, 1976.
[<a id="ref-FR1994">FR1994</a>] Frey, G. and H. Ruck, "A remark concerning
m-divisibility and the discrete logarithm in the divisor
class group of curves.", Mathematics of Computation Vol.
62, No. 206, pp. 865-874, 1994.
[<a id="ref-HMP1994">HMP1994</a>] 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.
[<a id="ref-K1981v2">K1981v2</a>] Knuth, D., "The Art of Computer Programming, Vol. 2:
Seminumerical Algorithms", Addison Wesley , 1981.
[<a id="ref-K1987">K1987</a>] Koblitz, N., "Elliptic Curve Cryptosystems", Mathematics
of Computation, Vol. 48, 1987, pp. 203-209, 1987.
[<a id="ref-KT1994">KT1994</a>] Koyama, K. and Y. Tsuruoka, "Digital signature system
based on elliptic curve and signer device and verifier
device for said system", Japanese Unexamined Patent
Application Publication H6-43809, February 18, 1994.
[<a id="ref-M1983">M1983</a>] Massey, J., "Logarithms in finite cyclic groups -
cryptographic issues", Proceedings of the 4th Symposium
on Information Theory, 1983.
[<a id="ref-M1985">M1985</a>] Miller, V., "Use of elliptic curves in cryptography",
Advances in Cryptology - CRYPTO '85
Proceedings, Springer Lecture Notes in Computer Science
(LNCS), volume 218, 1985.
<span class="grey">McGrew, et al. Informational [Page 24]</span><span id="page-25" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
[<a id="ref-MOV1993">MOV1993</a>] Menezes, A., Vanstone, S., and T. Okamoto, "Reducing
Elliptic Curve Logarithms to Logarithms in a Finite
Field", IEEE Transactions on Information Theory Vol. 39,
No. 5, pp. 1639-1646, September, 1993.
[<a id="ref-R1993">R1993</a>] RSA Laboratories, "PKCS#1: RSA Encryption Standard",
Technical Note version 1.5, 1993.
[<a id="ref-S1986">S1986</a>] Silverman, J., "The Arithmetic of Elliptic Curves",
Springer-Verlag, New York, 1986.
<span class="h3"><a class="selflink" id="section-12.2" href="#section-12.2">12.2</a>. Informative References</span>
[<a id="ref-A1992">A1992</a>] Anderson, J., "Response to the proposed DSS",
Communications of the ACM, v. 35, n. 7, p. 50-52,
July 1992.
[<a id="ref-AV1996">AV1996</a>] Anderson, R. and S. Vaudenay, "Minding Your P's and
Q's", Advances in Cryptology - ASIACRYPT '96
Proceedings, Springer Lecture Notes in Computer Science
(LNCS), volume 1163, 1996.
[<a id="ref-BMM2000">BMM2000</a>] Biehl, I., Meyer, B., and V. Muller, "Differential fault
analysis on elliptic curve cryptosystems", Advances in
Cryptology - CRYPTO 2000 Proceedings, Springer Lecture
Notes in Computer Science (LNCS), volume 1880, 2000.
[<a id="ref-BS1992">BS1992</a>] 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.
[<a id="ref-DSA1991">DSA1991</a>] U.S. National Institute of Standards and Technology,
"DIGITAL SIGNATURE STANDARD", Federal Register, Vol. 56,
August 1991.
[<a id="ref-E1984a">E1984a</a>] ElGamal, T., "Cryptography and logarithms over finite
fields", Stanford University, UMI Order No. DA 8420519,
1984.
[<a id="ref-E1984b">E1984b</a>] ElGamal, T., "Cryptography and logarithms over finite
fields", Advances in Cryptology - CRYPTO '84
Proceedings, Springer Lecture Notes in Computer Science
(LNCS), volume 196, 1984.
<span class="grey">McGrew, et al. Informational [Page 25]</span><span id="page-26" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
[<a id="ref-E1985">E1985</a>] 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.
[<a id="ref-FIPS180-2">FIPS180-2</a>] U.S. National Institute of Standards and Technology,
"SECURE HASH STANDARD", Federal Information Processing
Standard (FIPS) 180-2, August 2002.
[<a id="ref-FIPS186">FIPS186</a>] U.S. National Institute of Standards and Technology,
"DIGITAL SIGNATURE STANDARD", Federal Information
Processing Standard FIPS-186, May 1994.
[<a id="ref-HP1994">HP1994</a>] Horster, P. and H. Petersen, "Verallgemeinerte ElGamal-
Signaturen", Proceedings der Fachtagung SIS '94, Verlag
der Fachvereine, Zurich, 1994.
[<a id="ref-K1981v3">K1981v3</a>] Knuth, D., "The Art of Computer Programming, Vol. 3:
Sorting and Searching", Addison Wesley, 1981.
[<a id="ref-KMOV1991">KMOV1991</a>] Koyama, K., Maurer, U., Vanstone, S., and T. Okamoto,
"New Public-Key Schemes Based on Elliptic Curves over
the Ring Zn", Advances in Cryptology - CRYPTO '91
Proceedings, Springer Lecture Notes in Computer Science
(LNCS), volume 576, 1991.
[<a id="ref-L1969">L1969</a>] Lehmer, D., "Computer technology applied to the theory
of numbers", M.A.A. Studies in Mathematics, 180-2, 1969.
[<a id="ref-LL1997">LL1997</a>] Lim, C. and P. Lee, "A Key Recovery Attack on Discrete
Log-based Schemes Using a Prime Order Subgroup",
Advances in Cryptology - CRYPTO '97
Proceedings, Springer Lecture Notes in Computer Science
(LNCS), volume 1294, 1997.
[<a id="ref-NR1994">NR1994</a>] 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.
[<a id="ref-P1363">P1363</a>] "Standard Specifications for Public Key Cryptography",
Institute of Electric and Electronic Engineers
(IEEE), P1363, 2000.
[<a id="ref-P1978">P1978</a>] Pollard, J., "Monte Carlo methods for index computation
mod p", Mathematics of Computation, Vol. 32, 1978.
<span class="grey">McGrew, et al. Informational [Page 26]</span><span id="page-27" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
[<a id="ref-PH1978">PH1978</a>] Pohlig, S. and M. Hellman, "An Improved Algorithm for
Computing Logarithms over GF(p) and its Cryptographic
Significance", IEEE Transactions on Information
Theory, Vol. 24, pp. 106-110, 1978.
[<a id="ref-R1988">R1988</a>] Rose, H., "A Course in Number Theory", Oxford
University Press, 1988.
[<a id="ref-R1992">R1992</a>] Rivest, R., "Response to the proposed DSS",
Communications of the ACM, v. 35, n. 7, p. 41-47,
July 1992.
[<a id="ref-RFC2119">RFC2119</a>] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", <a href="https://www.rfc-editor.org/bcp/bcp14">BCP 14</a>, <a href="./rfc2119">RFC 2119</a>, March 1997.
[<a id="ref-RFC2409">RFC2409</a>] Harkins, D. and D. Carrel, "The Internet Key Exchange
(IKE)", <a href="./rfc2409">RFC 2409</a>, November 1998.
[<a id="ref-RFC2412">RFC2412</a>] Orman, H., "The OAKLEY Key Determination Protocol",
<a href="./rfc2412">RFC 2412</a>, November 1998.
[<a id="ref-RFC3979">RFC3979</a>] Bradner, S., "Intellectual Property Rights in IETF
Technology", <a href="https://www.rfc-editor.org/bcp/bcp79">BCP 79</a>, <a href="./rfc3979">RFC 3979</a>, March 2005.
[<a id="ref-RFC4086">RFC4086</a>] Eastlake, D., Schiller, J., and S. Crocker, "Randomness
Requirements for Security", <a href="https://www.rfc-editor.org/bcp/bcp106">BCP 106</a>, <a href="./rfc4086">RFC 4086</a>,
June 2005.
[<a id="ref-RFC4306">RFC4306</a>] Kaufman, C., "Internet Key Exchange (IKEv2) Protocol",
<a href="./rfc4306">RFC 4306</a>, December 2005.
[<a id="ref-RFC4753">RFC4753</a>] Fu, D. and J. Solinas, "ECP Groups For IKE and IKEv2",
<a href="./rfc4753">RFC 4753</a>, January 2007.
[<a id="ref-RFC4754">RFC4754</a>] Fu, D. and J. Solinas, "IKE and IKEv2 Authentication
Using the Elliptic Curve Digital Signature Algorithm
(ECDSA)", <a href="./rfc4754">RFC 4754</a>, January 2007.
[<a id="ref-RFC4879">RFC4879</a>] Narten, T., "Clarification of the Third Party Disclosure
Procedure in <a href="./rfc3979">RFC 3979</a>", <a href="https://www.rfc-editor.org/bcp/bcp79">BCP 79</a>, <a href="./rfc4879">RFC 4879</a>, April 2007.
[<a id="ref-RFC5114">RFC5114</a>] Lepinski, M. and S. Kent, "Additional Diffie-Hellman
Groups for Use with IETF Standards", <a href="./rfc5114">RFC 5114</a>,
January 2008.
[<a id="ref-RFC5903">RFC5903</a>] Fu, D. and J. Solinas, "Elliptic Curve Groups modulo a
Prime (ECP Groups) for IKE and IKEv2", <a href="./rfc5903">RFC 5903</a>,
June 2010.
<span class="grey">McGrew, et al. Informational [Page 27]</span><span id="page-28" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
[<a id="ref-RFC5996">RFC5996</a>] Kaufman, C., Hoffman, P., Nir, Y., and P. Eronen,
"Internet Key Exchange Protocol Version 2 (IKEv2)",
<a href="./rfc5996">RFC 5996</a>, September 2010.
[<a id="ref-SuiteB">SuiteB</a>] U. S. National Security Agency (NSA), "NSA Suite B
Cryptography", <<a href="http://www.nsa.gov/ia/programs/suiteb_cryptography/index.shtml">http://www.nsa.gov/ia/programs/</a>
<a href="http://www.nsa.gov/ia/programs/suiteb_cryptography/index.shtml">suiteb_cryptography/index.shtml</a>>.
[<a id="ref-V1996">V1996</a>] Vaudenay, S., "Hidden Collisions on DSS", Advances in
Cryptology - CRYPTO '96 Proceedings, Springer Lecture
Notes in Computer Science (LNCS), volume 1109, 1996.
[<a id="ref-VW1994">VW1994</a>] van Oorschot, P. and M. Wiener, "Parallel Collision
Search with Application to Hash Functions and Discrete
Logarithms", Proceedings of the 2nd ACM Conference on
Computer and communications security, pp. 210-218, 1994.
[<a id="ref-VW1996">VW1996</a>] van Oorschot, P. and M. Wiener, "On Diffie-Hellman key
agreement with short exponents", Advances in Cryptology
- EUROCRYPT '96 Proceedings, Springer Lecture Notes in
Computer Science (LNCS), volume 1070, 1996.
[<a id="ref-X9.62">X9.62</a>] "Public Key Cryptography for the Financial Services
Industry: The Elliptic Curve Digital Signature Algorithm
(ECDSA)", American National Standards Institute (ANSI)
X9.62.
<span class="grey">McGrew, et al. Informational [Page 28]</span><span id="page-29" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
<span class="h2"><a class="selflink" id="appendix-A" href="#appendix-A">Appendix A</a>. Key Words</span>
The definitions of these key words are quoted from [<a href="./rfc2119" title=""Key words for use in RFCs to Indicate Requirement Levels"">RFC2119</a>] and are
commonly used in Internet standards. They are reproduced in this
note in order to avoid a normative reference from after 1994.
1. MUST - This word, or the terms "REQUIRED" or "SHALL", means that
the definition is an absolute requirement of the specification.
2. MUST NOT - This phrase, or the phrase "SHALL NOT", means that the
definition is an absolute prohibition of the specification.
3. SHOULD - This word, or the adjective "RECOMMENDED", means that
there may exist valid reasons in particular circumstances to
ignore a particular item, but the full implications must be
understood and carefully weighed before choosing a different
course.
4. SHOULD NOT - This phrase, or the phrase "NOT RECOMMENDED", means
that there may exist valid reasons in particular circumstances
when the particular behavior is acceptable or even useful, but
the full implications should be understood and the case carefully
weighed before implementing any behavior described with this
label.
5. MAY - This word, or the adjective "OPTIONAL", means that an item
is truly optional. One vendor may choose to include the item
because a particular marketplace requires it or because the
vendor feels that it enhances the product while another vendor
may omit the same item. An implementation which does not include
a particular option MUST be prepared to interoperate with another
implementation which does include the option, though perhaps with
reduced functionality. In the same vein an implementation which
does include a particular option MUST be prepared to interoperate
with another implementation which does not include the option
(except, of course, for the feature the option provides.)
<span class="h2"><a class="selflink" id="appendix-B" href="#appendix-B">Appendix B</a>. Random Integer Generation</span>
It is easy to generate an integer uniformly at random between zero
and (2^t)-1, inclusive, for some positive integer t. Generate a
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
coefficients in a base-2 expansion of an integer.
<span class="grey">McGrew, et al. Informational [Page 29]</span><span id="page-30" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
It is sometimes necessary to generate an integer r uniformly at
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
rejection method:
1. Generate a candidate number c uniformly at random from a set that
includes all numbers that satisfy property P (plus some other
numbers, preferably not too many)
2. If c satisfies property P, then return c. Otherwise, return to
Step 1.
For example, to generate a number between 1 and n-1, inclusive,
repeatedly generate integers between zero and (2^t)-1, inclusive,
stopping at the first integer that falls within that interval.
Recommendations on how to generate random bit strings are provided in
[<a href="./rfc4086" title=""Randomness Requirements for Security"">RFC4086</a>].
<span class="h2"><a class="selflink" id="appendix-C" href="#appendix-C">Appendix C</a>. Why Compact Representation Works</span>
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' method [<a href="#ref-K1981v2" title=""The Art of Computer Programming, Vol. 2: Seminumerical Algorithms"">K1981v2</a>]; 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);
<span class="grey">McGrew, et al. Informational [Page 30]</span><span id="page-31" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
this observation is due to Lehmer [<a href="#ref-L1969" title=""Computer technology applied to the theory of numbers"">L1969</a>]. 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,
[<a href="#ref-R1988" title=""A Course in Number Theory"">R1988</a>]; 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 <a href="#section-10.3">Section 10.3</a>.
The primes used in the P-256, P-384, and P-521 curves described in
[<a href="./rfc5903" title=""Elliptic Curve Groups modulo a Prime (ECP Groups) for IKE and IKEv2"">RFC5903</a>] all have the property that p = 3 (mod 4).
<span class="h2"><a class="selflink" id="appendix-D" href="#appendix-D">Appendix D</a>. Example ECC Parameter Set</span>
For concreteness, we recall an elliptic curve defined by Solinas and
Fu in [<a href="./rfc5903" title=""Elliptic Curve Groups modulo a Prime (ECP Groups) for IKE and IKEv2"">RFC5903</a>] and referred to as P-256, which is believed to
provide a 128-bit security level. We use the notation of
<a href="#section-3.3">Section 3.3</a>, and express the generator in the affine coordinate
representation g=(gx,gy), where the values gx and gy are in Fp.
p: FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
a: - 3
b: 5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
n: FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551
gx: 6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
gy: 4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
Note that p can also be expressed as
p = 2^(256)-2^(224)+2^(192)+2^(96)-1.
<span class="grey">McGrew, et al. Informational [Page 31]</span><span id="page-32" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
<span class="h2"><a class="selflink" id="appendix-E" href="#appendix-E">Appendix E</a>. Additive and Multiplicative Notation</span>
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 |
+-------------------------+-----------------------+
<span class="h2"><a class="selflink" id="appendix-F" href="#appendix-F">Appendix F</a>. Algorithms</span>
This section contains a pseudocode description of the elliptic curve
group operation. Text that follows the symbol "//" is to be
interpreted as comments rather than instructions.
<span class="h3"><a class="selflink" id="appendix-F.1" href="#appendix-F.1">F.1</a>. Affine Coordinates</span>
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.
<span class="grey">McGrew, et al. Informational [Page 32]</span><span id="page-33" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
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".
<span class="h3"><a class="selflink" id="appendix-F.2" href="#appendix-F.2">F.2</a>. Homogeneous Coordinates</span>
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 nonzero 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 nonzero 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 nonzero (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
<span class="grey">McGrew, et al. Informational [Page 33]</span><span id="page-34" ></span>
<span class="grey"><a href="./rfc6090">RFC 6090</a> Fundamental ECC February 2011</span>
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
David A. McGrew
Cisco Systems
510 McCarthy Blvd.
Milpitas, CA 95035
USA
Phone: (408) 525 8651
EMail: [email protected]
URI: <a href="http://www.mindspring.com/~dmcgrew/dam.htm">http://www.mindspring.com/~dmcgrew/dam.htm</a>
Kevin M. Igoe
National Security Agency
Commercial Solutions Center
United States of America
EMail: [email protected]
Margaret Salter
National Security Agency
9800 Savage Rd.
Fort Meade, MD 20755-6709
USA
EMail: [email protected]
McGrew, et al. Informational [Page 34]
Annotations
Select text to annotate