TOC |
|
This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as “work in progress.”
The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html.
This Internet-Draft will expire on January 7, 2010.
Copyright (c) 2009 IETF Trust and the persons identified as the document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents in effect on the date of publication of this document (http://trustee.ietf.org/license-info). Please review these documents carefully, as they describe your rights and restrictions with respect to this document.
This note describes the fundamental algorithms of Elliptic Curve 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 based on fields of character greater than three are in scope.
1.
Introduction
2.
Mathematical Background
2.1.
Modular Arithmetic
2.2.
Group Operations
2.3.
Finite Fields
3.
Elliptic Curve Groups
3.1.
Homogenous Coordinates
3.2.
Group Parameters
3.2.1.
Security
4.
Elliptic Curve Diffie-Hellman (ECDH)
4.1.
Data Types
4.2.
Compact Representation
5.
Elliptic Curve ElGamal Signatures (ECES)
5.1.
Keypair Generation
5.2.
Signature Creation
5.3.
Signature Verification
5.4.
Hash Functions
5.5.
Rationale
6.
Abbreviated ECES Signatures (AECES)
6.1.
Keypair Generation
6.2.
Signature Creation
6.3.
Signature Verification
7.
Interoperability
7.1.
ECDH
7.2.
ECES, AECES, and ECDSA
8.
Intellectual Property
8.1.
Disclaimer
9.
Security Considerations
9.1.
Subgroups
9.2.
Diffie-Hellman
9.3.
Group Representation and Security
9.4.
Signatures
10.
IANA Considerations
11.
Acknowledgements
12.
References
12.1.
Normative References
12.2.
Informative References
Appendix A.
Random Number Generation
Appendix B.
Example Elliptic Curve Group
§
Author's Address
TOC |
ECC is a public-key technology that offers performance advantages at higher security levels. It includes an Elliptic Curve version of Diffie-Hellman key exchange protocol [DH1976] (Diffie, W. and M. Hellman, “New Directions in Cryptography,” 1976.) and an Elliptic Curve version of the ElGamal Signature Algorithm [E1985] (ElGamal, T., “A public key cryptosystem and a signature scheme based on discrete logarithms,” 1985.). The elliptic curve versions of these algorithms are referred to as ECDH and ECES, respectively. 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 fields with characteristic greater than three, based directly on original references. Its intent is to provide the Internet community with a normative specification of the basic algorithms that predate any specialized or optimized algorithms.
The rest of the note is organized as follows. Section 2.1 (Modular Arithmetic), Section 2.2 (Group Operations), and Section 2.3 (Finite Fields) furnish the necessary terminology and notation from modular arithmetic, group theory and the theory of finite fields, respectively. Section 3 (Elliptic Curve Groups) defines the groups based on elliptic curves over finite fields of characteristic greater than three. Section 4 (Elliptic Curve Diffie-Hellman (ECDH)) and Section 5 (Elliptic Curve ElGamal Signatures (ECES)) present the fundamental ECDH and ECES algorithms, respectively. Section 6 (Abbreviated ECES Signatures (AECES)) presents an abbreviated form of ECES. The previous sections 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 Section 7 (Interoperability). Section 8 (Intellectual Property) reviews intellectual property issues. Section 9 (Security Considerations) summarizes security considerations. Appendix A (Random Number Generation) describes random number generation and Appendix B (Example Elliptic Curve Group) provides an example of an Elliptic Curve group.
TOC |
This section reviews mathematical preliminaries and establishes terminology and notation that is used below.
TOC |
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 such that z divides x and z divides y.
The set Zp = { 0, 1, 2, ..., p-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 Zp, a + b mod p is equal to
a + b if a + b < p, and is equal to a + b - p otherwise.For each pair of integers a and b in Zp, a - b mod p is equal to
a - b if a + b > p, and is equal to a + b otherwise.For each pair of integers a and b in Zp, a * b mod p is equal to the remainder of a * b divided by p.
For each integer x in Zp that is coprime with p, the inverse of x modulo p is denoted as 1 / x mod p, and can be computed using the extended euclidean algorithm (see Section 4.5.2 of [K1981v2] (Knuth, D., “The Art of Computer Programming, Vol. 2: Seminumerical Algorithms,” 1981.), for example).
Algorithms for these operations are well known; for instance, see Chapter 4 of [K1981v2] (Knuth, D., “The Art of Computer Programming, Vol. 2: Seminumerical Algorithms,” 1981.).
TOC |
This section establishes some terminology and notation for mathematical groups, which is needed later on. Background references abound; see [D1966] (Deskins, W., “Abstract Algebra,” 1966.), for example.
A group is a set of elements G and an associated 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. Repeated application
of the group operation n 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 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, g^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.
Every group has an special element called the identity element, which we denote as e. For each element a in G, e * a = a * e = a. By convention, a^0 is equal to the identity element for any a in G.
A cyclic group of order R is a group that contains the R elements
g, g^2, g^3, ..., g^R. The element g is
called the generator of the group. The element g^R is equal to the
identity element e. Note that g^X is equal to g^(X modulo R) for any
non-negative integer X.
Given the element a of order N, and an integer i between 1 and N-1, inclusive, the element a^i can be computed by the "square and multiply" method outlined in Section 2.1 of [M1983] (Massey, J., “Logarithms in finite cyclic groups - cryptographic issues,” 1983.) (see also Knuth, Vol. 2, Section 4.6.3.), or other methods.
TOC |
This section establishes terminology and notation for finite fields with prime characteristic.
When p is a prime number, then the set Zp, with the associated addition, subtraction, multiplication and division operations, is a finite field with character p. There is a one-to-one correspondence between the integers between zero and p-1 and the elements of the field. The field is denoted as Fp.
Equations involving field elements do not include 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 Zp and
z = x + y mod p.
TOC |
This note only covers elliptic curves over fields with characteristic greater than three. For other fields, the definition of the elliptic curve group would be different.
An elliptic curve over a field F is defined by the curve equation
y^2 = x^3 + a*x + b,
where x, y, a, and b are elements of the field Fp [M1985] (Miller, V., “Use of elliptic curves in cryptography,” 1985.). A point on an elliptic curve is a pair (x,y) of values in Fp that satisfy the curve equation, such that x and y are both in Fp, or it is a special point (@,@) that represents the identity element (which is called the "point at infinity"). The order of an elliptic curve group is the 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 group operation associated with the elliptic curve group is as follows [BC1989] (Bender, A. and G. Castagnoli, “On the Implementation of Elliptic Curve Cryptosystems,” 1989.). 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, P is equal to (0,0) and P is an element of the group.
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.
In the above equations, a, x1, x2, x3, y1, y2, and y3 are elements of the field Fp; thus, computation of x3 and y3 in practice use a "mod p" operation.
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.
TOC |
An alternative way to implement the group operation is to use homogeneous coordinates [K1987] (Koblitz, N., “Elliptic Curve Cryptosystems,” 1987.) (see also [KMOV1991] (Koyama, K., Menezes, A., Vanstone, S., and T. Okamoto, “New Public-Key Schemes Based on Elliptic Curves over the Ring Zn,” 1991.)). This method is typically more efficient because it does not require a modular inverse operation.
An elliptic curve point (x,y) is equivalent to a point (X,Y,Z) in homogeneous coordinates whenever x=X/Z and y=Y/Z.
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 equal to P2, and P1 is not equal to -P2. Then the product P3=(X3,Y3,Z3) = P1 * P2 is given by
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),
Z3 = 8 * (Y1)^3 * (Z1)^3,
where u = Y2 * Z1 - Y1 * Z2 and v = X2 * Z1 - X1 * Z2.
The product P3=(X3,Y3,Z3) = P1 * P1 is given by
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.
In the above equations, a, u, v, w, X1, X2, X3, Y1, Y2, Y3, Z1, Z2, and Z3 are elements of the field Fp; thus, computation of X3, Y3, and Z3 in practice use a "mod p" operation.
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.
TOC |
An elliptic curve group over a finite field with characteristic greater than three 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 group.
The order n of the group generated by g.
An example of an Elliptic Curve Group is provided in Appendix B (Example Elliptic Curve Group).
Each elliptic curve point is associated with with a particular group, i.e a particular parameter set. Two elliptic curve groups are equal if and only if each of the parameters in the set are equal. The elliptic curve group operation is only defined between two points on the same group. It is an error to apply the group operation to two elements that are from different groups, or to apply the group operation to a pair of coordinates that are not a valid point. See Section 9.3 (Group Representation and Security) for further information.
TOC |
Security is highly dependent on the choice of these parameters. This section gives normative guidance on acceptable choices. See also Section 9 (Security Considerations) for more information.
The order of the group generated by g should be divisible by a large prime, in order to preclude easy solution of the discrete logarithm problem [K1987] (Koblitz, N., “Elliptic Curve Cryptosystems,” 1987.)
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)
[MOV1993] (Menezes, A., Vanstone, S., and T. Okamoto, “Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field,” September, 1993.). These parameter choices are inferior for
cryptographic purposes and should not be used.
TOC |
The Diffie-Hellman (DH) key exchange protocol [DH1976] (Diffie, W. and M. Hellman, “New Directions in Cryptography,” 1976.) 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 [M1983] (Massey, J., “Logarithms in finite cyclic groups - cryptographic issues,” 1983.) observed that it can be easily generalized so that it is defined in terms of an arbitrary mathematical group. Miller [M1985] (Miller, V., “Use of elliptic curves in cryptography,” 1985.) and Koblitz [K1987] (Koblitz, N., “Elliptic Curve Cryptosystems,” 1987.) 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 uniformly at random, computes g^j and sends that element to B. Party B chooses an exponent k between 1 and t-1 uniformly at random, computes g^k and sends that element to A. Each party can compute g^(j*k); party A computes (g^k)^j, and party B computes (g^j)^k.
See Appendix A (Random Number Generation) regarding generation of random numbers.
TOC |
An ECDH private key a is an integer in Zt.
The corresponding ECDH public key Y is group element, where Y = g^a. Each public key is associated with a particular group, i.e. a particular parameter set as per Section 3.2 (Group Parameters).
The shared secret computed by both parties is a group element.
Each run of the ECDH protocol is associated with a particular group, and both of the public keys and the shared secret are elements of that group.
TOC |
As described in the final paragraph of [M1985] (Miller, V., “Use of elliptic curves in cryptography,” 1985.), 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 [M1985] (Miller, V., “Use of elliptic curves in cryptography,” 1985.) 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.
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.
TOC |
The ElGamal signature algorithm was introduced in 1984 [E1984a] (ElGamal, T., “Cryptography and logarithms over finite fields,” 1984.) [E1984b] (ElGamal, T., “Cryptography and logarithms over finite fields,” 1984.) [E1985] (ElGamal, T., “A public key cryptosystem and a signature scheme based on discrete logarithms,” 1985.). It is based on the discrete logarithm problem in the multiplicative group of the integers modulo a large prime number. It is straightforward to extended it to use an elliptic curve group. In this section we recall a well-specified elliptic curve version of the ElGamal Signature Algorithm, as described in [A1992] (Anderson, J., “Response to the proposed DSS,” July 1992.) and [MV1993] (Menezes, A. and S. Vanstone, “Elliptic Curve Cryptosystems and Their Implementation,” 1993.). This signature method is called Elliptic Curve ElGamal Signatures (ECES).
The algorithm uses an elliptic curve group, as described in Section 3.2 (Group Parameters). We denote the generator as alpha, and the order of the generator as n. We follow [MV1993] (Menezes, A. and S. Vanstone, “Elliptic Curve Cryptosystems and Their Implementation,” 1993.) in describing the algorithms in terms of mathematical groups.
ECES uses a collision-resistant hash function, so that it can sign messages of arbitrary length. We denote the hash function as h(). Its input is a bit string of arbitrary length, and its output is an integer between zero and n-1, inclusive.
ECES uses a function g() from the set of group elements to the set of integers Zn. This function returns the x-coordinate of the affine coordinate representation of the elliptic curve point.
TOC |
The private key a is an integer between 0 and n - 1, inclusive,
generated uniformly at random. The public key is the group element
Q = alpha^a.
TOC |
To sign message m, using the private key a:
s = (h(m) + a * g(r)) / k (mod n).
The signature for message m is the ordered pair (r, s). Note that the first component is a group element, and the second is a non-negative integer.
TOC |
To verify the message m and the signature (r,s) using the public key Q:
Compute the group element r^s * Q^(-g(r)).
Compute the group element alpha^h(m).
Verify that the two elements previously computed are the same. If they are identical, then the signature and message pass the verification; otherwise, they fail.
TOC |
Let H() denote a hash function whose output is a fixed-length bit string. To use H in ECES, we define the mapping between that output 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:
TOC |
This subsection is not normative and is provided only as background information.
The signature verification will pass whenever the signature is properly generated, because
r^s * Q^(-g(r)) = alpha^(k*s - a*g(r)) = alpha^h(m).
The reason that the random variable k must be coprime with n is so that 1/k mod n is defined.
A valid signature with s=0 leaks the secret key, since in that case a = h(m) / g(r) mod n. We adopt Rivest's suggestion to avoid this problem [R1992] (Rivest, R., “Response to the proposed DSS,” July 1992.).
As described in the final paragraph of [M1985] (Miller, V., “Use of elliptic curves in cryptography,” 1985.), for it is suitable to use the x-coordinate of a particular elliptic curve point as a representative for that point. This is what the function g() does.
TOC |
The ECES system is secure and efficient, but has signatures that are slightly larger than they need to be. Koyama and Tsuruoka described a signature system based on Elliptic Curve ElGamal, but with shorter signatures [KT1994] (Koyama, K. and Y. Tsuruoka, “Digital signature system based on elliptic curve and signer device and verifier device for said system,” 1994.). 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] (Menezes, A., Qu, M., and S. Vanstone, “Submission to the IEEE P1363 Working Group (Part 6: Elliptic Curve Systems, Draft 2),” October, 1994.).
In this section we describe an Elliptic Curve Signature Scheme that hash a single elliptic curve coordinate in the signature instead of both coordinates. It is based on ECSSA, but with an inversion operation moved from the signature operation to the verification operation, so that the signing operation is more compatible with ECES. (See [AMV1990] (Agnew, G., Mullin, R., and S. Vanstone, “Improved Digital Signature Scheme based on Discrete Exponentiation,” July, 1990.) and [A1992] (Anderson, J., “Response to the proposed DSS,” July 1992.) for a discussion of these alternatives; the security of the methods is equivalent.) We refer to this scheme as Abbreviated ECES, or AECES.
TOC |
Keypairs are the same as for ECES and are as described in Section 5.1 (Keypair Generation).
TOC |
In this section we describe how to compute the signature for a message m using the private key a.
Signature creation is as for ECES, with the following additional step:
The signature is the ordered pair (s1, s). Both signature components are non-negative integers.
TOC |
Given the message m, the public key Q, and the signature (s1,s) verification is as follows:
u = w * h(m) mod q, and
v = w * s1 mod q.
TOC |
The algorithms in this note can be used to interoperate with some other ECC specifications. This section provides details for each algorithm.
TOC |
Section 4 (Elliptic Curve Diffie-Hellman (ECDH)) can be used with the Internet Key Exchange (IKE) versions one [RFC2409] (Harkins, D. and D. Carrel, “The Internet Key Exchange (IKE),” November 1998.) or two [RFC4306] (Kaufman, C., “Internet Key Exchange (IKEv2) Protocol,” December 2005.). These algorithms are compatible with the ECP groups for the defined by [RFC4753] (Fu, D. and J. Solinas, “ECP Groups For IKE and IKEv2,” January 2007.), [RFC2409] (Harkins, D. and D. Carrel, “The Internet Key Exchange (IKE),” November 1998.), and [RFC2412] (Orman, H., “The OAKLEY Key Determination Protocol,” November 1998.). The group definition used in this protocol uses an affine coordinate representation of the public key and uses neither the compact output nor the compact representation of Section 4.2 (Compact Representation). Note that some groups use a negative curve parameter "a" and express this fact in the curve equation rather than in the parameter. The test cases in Section 8 of [RFC4753] (Fu, D. and J. Solinas, “ECP Groups For IKE and IKEv2,” January 2007.) 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^i and g^r, respectively, with 64 bits of encoding data prepended to them.
The algorithms in Section 4 (Elliptic Curve Diffie-Hellman (ECDH)) can be used to interoperate with the IEEE [P1363] (, “Standard Specifications for Public Key Cryptography,” 2000.) and ANSI [X9.62] (, “Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA),” .) standards for ECDH based on fields of characteristic greater than three.
TOC |
The Digital Signature Algorithm (DSA) is based on the discrete logarithm problem over the multiplicative subgroup of the finite field large prime order [DSA1991] (, “DIGITAL SIGNATURE STANDARD,” August 1991.)[FIPS186] (, “DIGITAL SIGNATURE STANDARD,” 1994.). The Elliptic Curve Digital Signature Algorithm (ECDSA) [P1363] (, “Standard Specifications for Public Key Cryptography,” 2000.) [X9.62] (, “Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA),” .) is an elliptic curve version of DSA.
AECES can interoperate with the IEEE [P1363] (, “Standard Specifications for Public Key Cryptography,” 2000.) and ANSI [X9.62] (, “Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA),” .) standards for Elliptic Curve DSA (ECDSA) based on fields of characteristic greater than three.
An ECES signature can be converted into an ECDSA signature by discarding the y-coordinate from the elliptic curve point.
There is a strong correspondence between ECES signatures and ECDSA signatures. In the notation of Section 5 (Elliptic Curve ElGamal Signatures (ECES)), an ECDSA signature consists of the pair of integers (g(r), s), and signature verification passes if and only if
A^(h(m)/s) * Q^(g(r)/s) = r,
where the equality of the elliptic curve elements is checked by checking for the equality of their x-coordinates. For valid signatures, (h(m)+a*r)/s mod q = k, and thus the two sides are equal. An ECDSA signature contains only the x-coordinate g(r), but this is sufficient to allow the signatures to be checked with the above method.
Whenever the ECES signature (r, s) is valid for a particular message m, and public key Q, then there is a valid ECDSA signature (g(r), s) for the same message and public key.
Whenever the ECDSA signature (c, d) is valid for a particular message m, and public key Q, then there is a valid ECES signature for the same message and public key. This signature has the form ((c, f(c)), d), or ((c, q-f(c)), d) where the function f takes as input an integer in Zq and is defined as
f(x) = sqrt(x^3 + a*x + b) (mod q).
It is possible to compute the square root modulo q, for instance, by using Shanks's method [K1987] (Koblitz, N., “Elliptic Curve Cryptosystems,” 1987.). However, it is not as efficient to convert an ECDSA signature (or an AECES signature) to an ECES signature.
TOC |
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 in this note were published during or before October, 1994, and all of the normative text in this note is based solely on those references.
TOC |
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 [RFC3979] (Bradner, S., “Intellectual Property Rights in IETF Technology,” March 2005.) and [RFC4879] (Narten, T., “Clarification of the Third Party Disclosure Procedure in RFC 3979,” April 2007.) and at https://datatracker.ietf.org/ipr/about/.
TOC |
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 Polhig-Hellman method is a divide-and-conquer technique [PH1978] (Polhig, S. and M. Hellman, “An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance,” 1978.). 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 [K1981v3] (Knuth, D., “The Art of Computer Programming, Vol. 3: Sorting and Searching,” 1981.) computes a discrete logarithm in a group of order n using O(sqrt(n)) operations and O(sqrt(n)) storage. The Pollard rho algorithm [P1978] (Pollard, J., “Monte Carlo methods for index computation mod p,” 1978.) 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.
The Pollard lambda algorithm [P1978] (Pollard, J., “Monte Carlo methods for index computation mod p,” 1978.) can solve the discrete logarithm problem using O(sqrt(w)) operations and O(log(w)) storage, when the exponent belongs to a set of w elements.
The algorithms described above work in any group. There are specialized algorithms that specifically target elliptic curve groups. There are no subexponential algorithms against general elliptic curve groups, though there are methods that target certain special elliptic curve groups; see [MOV1993] (Menezes, A., Vanstone, S., and T. Okamoto, “Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field,” September, 1993.) and [FR1994] (Frey, G. and H. Ruck, “A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves.,” 1994.).
TOC |
A group consisting of a 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" [P1363] (, “Standard Specifications for Public Key Cryptography,” 2000.). Each elliptic curve group (e.g. each parameter set as in Section 3.2 (Group Parameters)) is associated with a particular cofactor.
It is possible and desirable to use a cofactor equal to 1.
It is common to use a "safe prime group" in the conventional Diffie-Hellman protocol over the multiplicative group of the prime field Fp (see Appendix E of [RFC2412] (Orman, H., “The OAKLEY Key Determination Protocol,” November 1998.) for example). A safe prime group is the subgroup of prime order q of the multiplicative group of Zp, where p-1 = 2*q. The use of safe prime groups simplifies protocol design, implementation and use, because they minimize the effectiveness of some cryptanalytic attacks. Elliptic curve groups with a cofactor of 1 have similar benefits.
TOC |
Note that the key exchange protocol as defined in Section 4 (Elliptic Curve Diffie-Hellman (ECDH)) 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 which use end-entity authentication to protect against active attacks, such as OAKLEY [RFC2412] (Orman, H., “The OAKLEY Key Determination Protocol,” November 1998.) and the Internet Key Exchange [RFC2409] (Harkins, D. and D. Carrel, “The Internet Key Exchange (IKE),” November 1998.)[RFC4306] (Kaufman, C., “Internet Key Exchange (IKEv2) Protocol,” December 2005.).
When the cofactor of a group is not equal to 1, there are a number of attacks that are possible against ECDH. See [VW1996] (van Oorschot, P. and M. Wiener, “On Diffie-Hellman key agreement with short exponents,” 1996.), [AV1996] (Anderson, R. and S. Vaudenay, “Minding Your P's and Q's,” 1996.), and [LL1997] (Lim, C. and P. Lee, “A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroup,” 1997.).
TOC |
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 [BMM2000] (Biehl, I., Meyer, B., and V. Muller, “Differential fault analysis on elliptic curve cryptosystems,” 2000.). 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, that is, 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.
TOC |
Elliptic curve parameters should only be used if they come from a trusted source; otherwise, some attacks are possible [AV1996] (Anderson, R. and S. Vaudenay, “Minding Your P's and Q's,” 1996.), [V1996] (Vaudenay, S., “Hidden Collisions on DSS,” 1996.).
In principle, any collision-resistant hash function is suitable for use in ECES. To facilitate interoperability, we recognize the following hashes as suitable for use as the function H defined in Section 5.4 (Hash Functions):
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 [FIPS180‑2] (, “SECURE HASH STANDARD,” August 2002.).
The number of bits in the output of the hash used in ECES should be equal or close to the number of bits needed to represent the group order.
TOC |
This note has no actions for IANA. This section should be removed by the RFC editor before publication as an RFC.
TOC |
The author expresses his thanks to the originators of elliptic curve cryptography, whose work made this note possible.
TOC |
TOC |
[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 Signature Scheme based on Discrete Exponentiation,” Electronics Letters Vol. 26, No. 14, July, 1990. |
[BC1989] | Bender, A. and G. Castagnoli, “On the Implementation of Elliptic Curve Cryptosystems,” Advances in Cryptology - CRYPTO '89 Proceedings Spinger Lecture Notes in Computer Science (LNCS) volume 435, 1989. |
[D1966] | Deskins, W., “Abstract Algebra,” MacMillan Company , 1966. |
[DH1976] | Diffie, W. and M. Hellman, “New Directions in Cryptography,” IEEE Transactions in Information 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 and the discrete logarithm in the divisor class group of curves.,” Mathematics of Computation Vol. 62, No. 206, pp. 865-874, 1994. |
[K1981v2] | Knuth, D., “The Art of Computer Programming, Vol. 2: Seminumerical Algorithms,” Addison Wesley , 1981. |
[K1987] | Koblitz, N., “Elliptic Curve Cryptosystems,” Mathematics of Computation Vol. 48, 1987, 203-209, 1987. |
[M1983] | Massey, J., “Logarithms in finite cyclic groups - cryptographic issues,” Processings of the 4th Symposium on Information Theory , 1983. |
[M1985] | Miller, V., “Use of elliptic curves in cryptography,” Advances in Cryptology - CRYPTO '85 Proceedings Springer Lecture Notes in Computer Science (LNCS) volume 218, 1985. |
[MOV1993] | 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. |
[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. |
TOC |
[AV1996] | Anderson, R. and S. Vaudenay, “Minding Your P's and Q's,” Advances in Cryptology - ASIACRYPT '96 Proceedings Spinger Lecture Notes in Computer Science (LNCS) volume 1163, 1996. |
[BMM2000] | Biehl, I., Meyer, B., and V. Muller, “Differential fault analysis on elliptic curve cryptosystems,” Advances in Cryptology - CRYPTO 2000 Proceedings Spinger Lecture Notes in Computer Science (LNCS) volume 1880, 2000. |
[DSA1991] | “DIGITAL SIGNATURE STANDARD,” Federal Register Vol. 56, August 1991. |
[FIPS180-2] | “SECURE HASH STANDARD,” Federal Information Processing Standard (FIPS) 180-2, August 2002. |
[FIPS186] | “DIGITAL SIGNATURE STANDARD,” Federal Information Processing Standard FIPS-186, 1994. |
[K1981v3] | Knuth, D., “The Art of Computer Programming, Vol. 3: Sorting and Searching,” Addison Wesley , 1981. |
[KMOV1991] | Koyama, K., Menezes, A., Vanstone, S., and T. Okamoto, “New Public-Key Schemes Based on Elliptic Curves over the Ring Zn,” Advances in Cryptology - CRYPTO '91 Proceedings Spinger Lecture Notes in Computer Science (LNCS) volume 576, 1991. |
[KT1994] | Koyama, K. and Y. Tsuruoka, “Digital signature system based on elliptic curve and signer device and verifier device for said system,” Japanese Unexamined Patent Application Publication H6-43809, 1994. |
[LL1997] | Lim, C. and P. Lee, “A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroup,” Advances in Cryptology - CRYPTO '97 Proceedings Spinger Lecture Notes in Computer Science (LNCS) volume 1294, 1997. |
[P1363] | “Standard Specifications for Public Key Cryptography,” Institute of Electric and Electronic Engineers (IEEE) P1363, 2000. |
[P1978] | Pollard, J., “Monte Carlo methods for index computation mod p,” Mathematics of Computation Vol. 32, 1978. |
[PH1978] | Polhig, 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. |
[RFC2409] | Harkins, D. and D. Carrel, “The Internet Key Exchange (IKE),” RFC 2409, November 1998 (TXT, HTML, XML). |
[RFC2412] | Orman, H., “The OAKLEY Key Determination Protocol,” RFC 2412, November 1998 (TXT, HTML, XML). |
[RFC3979] | Bradner, S., “Intellectual Property Rights in IETF Technology,” BCP 79, RFC 3979, March 2005 (TXT). |
[RFC4306] | Kaufman, C., “Internet Key Exchange (IKEv2) Protocol,” RFC 4306, December 2005 (TXT). |
[RFC4753] | Fu, D. and J. Solinas, “ECP Groups For IKE and IKEv2,” RFC 4753, January 2007 (TXT). |
[RFC4879] | Narten, T., “Clarification of the Third Party Disclosure Procedure in RFC 3979,” BCP 79, RFC 4879, April 2007 (TXT). |
[V1996] | Vaudenay, S., “Hidden Collisions on DSS,” Advances in Cryptology - CRYPTO '96 Proceedings Spinger Lecture Notes in Computer Science (LNCS) volume 1109, 1996. |
[VW1996] | van Oorschot, P. and M. Wiener, “On Diffie-Hellman key agreement with short exponents,” Advances in Cryptology - EUROCRYPT '96 Proceedings Spinger Lecture Notes in Computer Science (LNCS) volume 1070, 1996. |
[X9.62] | “Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA),” American National Standards Institute (ANSI) X9.62. |
TOC |
It is easy to generate an integer uniformly at random between zero and 2^t, for some positive integer t. Generate a random bit string 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-two expansion of an integer.
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:
For example, to generate a number between 1 and n-1, repeatedly generate integers between zero and 2^t, stopping at the first integer that falls within that interval.
TOC |
For concreteness, we recall an elliptic curve defined by Solinas and Yu in [RFC4753] (Fu, D. and J. Solinas, “ECP Groups For IKE and IKEv2,” January 2007.) and referred to as P-256, which is believed to provide a 128-bit security level. We use the notation of Section 3.2 (Group Parameters), and express the generator in the affine coordinate representation g=(gx,gy), where the values gx and gy are in Zp.
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.
TOC |
David A. McGrew | |
Cisco Systems | |
510 McCarthy Blvd. | |
Milpitas, CA 95035 | |
US | |
Phone: | (408) 525 8651 |
Email: | mcgrew@cisco.com |
URI: | http://www.mindspring.com/~dmcgrew/dam.htm |