idnits 2.16.02
/tmp/draft-mcgrew-fundamental-ecc-04.txt:
Checking boilerplate required by RFC 5378 and the IETF Trust (see
https://trustee.ietf.org/license-info):
----------------------------------------------------------------------------
No issues found here.
Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt:
----------------------------------------------------------------------------
No issues found here.
Checking nits according to https://www.ietf.org/id-info/checklist :
----------------------------------------------------------------------------
No issues found here.
Miscellaneous warnings:
----------------------------------------------------------------------------
== The copyright year in the IETF Trust and authors Copyright Line does not
match the current year
== Line 1284 has weird spacing: '...ecurity pp. 2...'
== The document seems to lack the recommended RFC 2119 boilerplate, even if
it appears to use RFC 2119 keywords -- however, there's a paragraph with
a matching beginning. Boilerplate error?
(The document does seem to have the reference to RFC 2119 which the
ID-Checklist requires).
-- The document date (December 10, 2010) is 3109 days in the past. Is this
intentional?
Checking references for intended status: Informational
----------------------------------------------------------------------------
-- Obsolete informational reference (is this intentional?): RFC 2409
(Obsoleted by RFC 4306)
-- Obsolete informational reference (is this intentional?): RFC 3979
(Obsoleted by RFC 8179)
-- Obsolete informational reference (is this intentional?): RFC 4306
(Obsoleted by RFC 5996)
-- Obsolete informational reference (is this intentional?): RFC 4753
(Obsoleted by RFC 5903)
-- Obsolete informational reference (is this intentional?): RFC 4879
(Obsoleted by RFC 8179)
Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 6 comments (--).
Run idnits with the --verbose option for more detailed information about
the items above.
--------------------------------------------------------------------------------
2 Network Working Group D. McGrew
3 Internet-Draft Cisco Systems
4 Intended status: Informational K. Igoe
5 Expires: June 13, 2011 M. Salter
6 National Security Agency
7 December 10, 2010
9 Fundamental Elliptic Curve Cryptography Algorithms
10 draft-mcgrew-fundamental-ecc-04.txt
12 Abstract
14 This note describes the fundamental algorithms of Elliptic Curve
15 Cryptography (ECC) as they were defined in some early references.
16 These descriptions may be useful for implementing the fundamental
17 algorithms without using any of the specialized methods that were
18 developed in following years. Only elliptic curves defined over
19 fields of characteristic greater than three are in scope; these
20 curves are those used in Suite B.
22 Status of this Memo
24 This Internet-Draft is submitted in full conformance with the
25 provisions of BCP 78 and BCP 79.
27 Internet-Drafts are working documents of the Internet Engineering
28 Task Force (IETF). Note that other groups may also distribute
29 working documents as Internet-Drafts. The list of current Internet-
30 Drafts is at http://datatracker.ietf.org/drafts/current/.
32 Internet-Drafts are draft documents valid for a maximum of six months
33 and may be updated, replaced, or obsoleted by other documents at any
34 time. It is inappropriate to use Internet-Drafts as reference
35 material or to cite them other than as "work in progress."
37 This Internet-Draft will expire on June 13, 2011.
39 Copyright Notice
41 Copyright (c) 2010 IETF Trust and the persons identified as the
42 document authors. All rights reserved.
44 This document is subject to BCP 78 and the IETF Trust's Legal
45 Provisions Relating to IETF Documents
46 (http://trustee.ietf.org/license-info) in effect on the date of
47 publication of this document. Please review these documents
48 carefully, as they describe your rights and restrictions with respect
49 to this document. Code Components extracted from this document must
50 include Simplified BSD License text as described in Section 4.e of
51 the Trust Legal Provisions and are provided without warranty as
52 described in the Simplified BSD License.
54 Table of Contents
56 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
57 1.1. Conventions Used In This Document . . . . . . . . . . . . 4
58 2. Mathematical Background . . . . . . . . . . . . . . . . . . . 5
59 2.1. Modular Arithmetic . . . . . . . . . . . . . . . . . . . . 5
60 2.2. Group Operations . . . . . . . . . . . . . . . . . . . . . 5
61 2.3. The Finite Field Fp . . . . . . . . . . . . . . . . . . . 7
62 3. Elliptic Curve Groups . . . . . . . . . . . . . . . . . . . . 7
63 3.1. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 8
64 3.2. Other Coordinates . . . . . . . . . . . . . . . . . . . . 9
65 3.3. ECC Parameters . . . . . . . . . . . . . . . . . . . . . . 9
66 3.3.1. Discriminant . . . . . . . . . . . . . . . . . . . . . 10
67 3.3.2. Security . . . . . . . . . . . . . . . . . . . . . . . 10
68 4. Elliptic Curve Diffie-Hellman (ECDH) . . . . . . . . . . . . . 11
69 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 11
70 4.2. Compact Representation . . . . . . . . . . . . . . . . . . 11
71 5. Elliptic Curve ElGamal Signatures . . . . . . . . . . . . . . 12
72 5.1. Background . . . . . . . . . . . . . . . . . . . . . . . . 12
73 5.2. Hash Functions . . . . . . . . . . . . . . . . . . . . . . 12
74 5.3. KT-IV Signatures . . . . . . . . . . . . . . . . . . . . . 13
75 5.3.1. Keypair Generation . . . . . . . . . . . . . . . . . . 13
76 5.3.2. Signature Creation . . . . . . . . . . . . . . . . . . 13
77 5.3.3. Signature Verification . . . . . . . . . . . . . . . . 14
78 5.4. KT-I Signatures . . . . . . . . . . . . . . . . . . . . . 14
79 5.4.1. Keypair Generation . . . . . . . . . . . . . . . . . . 14
80 5.4.2. Signature Creation . . . . . . . . . . . . . . . . . . 14
81 5.4.3. Signature Verification . . . . . . . . . . . . . . . . 15
82 5.5. Converting KT-IV Signatures to KT-I Signatures . . . . . . 15
83 5.6. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 16
84 6. Converting Between Integers and Octet Strings . . . . . . . . 17
85 6.1. Octet-String-to-Integer Conversion . . . . . . . . . . . . 17
86 6.2. Integer-to-Octet-String Conversion . . . . . . . . . . . . 17
87 7. Interoperability . . . . . . . . . . . . . . . . . . . . . . . 18
88 7.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
89 7.2. KT-I and ECDSA . . . . . . . . . . . . . . . . . . . . . . 18
90 8. Validating an Implementation . . . . . . . . . . . . . . . . . 19
91 8.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
92 8.2. KT-I . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
93 9. Intellectual Property . . . . . . . . . . . . . . . . . . . . 21
94 9.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . 21
95 10. Security Considerations . . . . . . . . . . . . . . . . . . . 21
96 10.1. Subgroups . . . . . . . . . . . . . . . . . . . . . . . . 22
97 10.2. Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . 22
98 10.3. Group Representation and Security . . . . . . . . . . . . 23
99 10.4. Signatures . . . . . . . . . . . . . . . . . . . . . . . . 23
100 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24
101 12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 24
102 13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 24
103 13.1. Normative References . . . . . . . . . . . . . . . . . . . 24
104 13.2. Informative References . . . . . . . . . . . . . . . . . . 26
105 Appendix A. Key Words . . . . . . . . . . . . . . . . . . . . . . 29
106 Appendix B. Random Integer Generation . . . . . . . . . . . . . . 30
107 Appendix C. Why Compact Representation Works . . . . . . . . . . 30
108 Appendix D. Example ECC Parameter Set . . . . . . . . . . . . . . 31
109 Appendix E. Additive and multiplicative notation . . . . . . . . 32
110 Appendix F. Algorithms . . . . . . . . . . . . . . . . . . . . . 32
111 F.1. Affine Coordinates . . . . . . . . . . . . . . . . . . . . 32
112 F.2. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 33
113 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 34
115 1. Introduction
117 ECC is a public-key technology that offers performance advantages at
118 higher security levels. It includes an Elliptic Curve version of the
119 Diffie-Hellman key exchange protocol [DH1976] and Elliptic Curve
120 versions of the ElGamal Signature Algorithm [E1985]. The adoption of
121 ECC has been slower than had been anticipated, perhaps due to the
122 lack of freely available normative documents and uncertainty over
123 intellectual property rights.
125 This note contains a description of the fundamental algorithms of ECC
126 over finite fields with characteristic greater than three, based
127 directly on original references. Its intent is to provide the
128 Internet community with a summary of the basic algorithms that
129 predate any specialized or optimized algorithms. The summary is
130 detailed enough for use as a normative reference. The original
131 descriptions and notations were followed as closely as possible.
133 There are several standards that specify or incorporate ECC
134 algorithms, including the Internet Key Exchange (IKE), ANSI X9.62,
135 and IEEE P1363. The algorithms in this note can interoperate with
136 some of the algorithms in these standards, with a suitable choice of
137 parameters and options. The specifics are itemized in Section 7.
139 The rest of the note is organized as follows. Section 2.1,
140 Section 2.2, and Section 2.3 furnish the necessary terminology and
141 notation from modular arithmetic, group theory and the theory of
142 finite fields, respectively. Section 3 defines the groups based on
143 elliptic curves over finite fields of characteristic greater than
144 three. Section 4 presents the fundamental Elliptic Curve Diffie-
145 Hellman (ECDH) algorithm. Section 5 presents elliptic curve versions
146 of the ElGamal signature method. The representation of integers as
147 octet strings is specified in Section 6. Sections 2 through 6,
148 inclusive, contain all of the normative text (the text that defines
149 the norm for implementations conforming to this specification), and
150 all of the following sections are purely informative.
151 Interoperability is discussed in Section 7. Validation testing is
152 described in Section 8. Section 9 reviews intellectual property
153 issues. Section 10 summarizes security considerations. Appendix B
154 describes random number generation, and other appendices provide
155 clarifying details.
157 1.1. Conventions Used In This Document
159 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
160 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
161 document are to be interpreted as described in Appendix A.
163 2. Mathematical Background
165 This section reviews mathematical preliminaries and establishes
166 terminology and notation that are used below.
168 2.1. Modular Arithmetic
170 This section reviews modular arithmetic. Two integers x and y are
171 said to be congruent modulo n if x - y is an integer multiple of n.
173 Two integers x and y are coprime when their greatest common divisor
174 is 1; in this case, there is no third number z > 1 such that z
175 divides x and z divides y.
177 The set Zq = { 0, 1, 2, ..., q-1 } is closed under the operations of
178 modular addition, modular subtraction, modular multiplication, and
179 modular inverse. These operations are as follows.
181 For each pair of integers a and b in Zq, a + b mod q is equal to
182 a + b if a + b < q, and is equal to a + b - q otherwise.
184 For each pair of integers a and b in Zq, a - b mod q is equal to
185 a - b if a - b >= 0, and is equal to a - b + q otherwise.
187 For each pair of integers a and b in Zq, a * b mod q is equal to
188 the remainder of a * b divided by q.
190 For each integer x in Zq that is coprime with q, the inverse of x
191 modulo q is denoted as 1 / x mod q, and can be computed using the
192 extended euclidean algorithm (see Section 4.5.2 of [K1981v2], for
193 example).
195 Algorithms for these operations are well known; for instance, see
196 Chapter 4 of [K1981v2].
198 2.2. Group Operations
200 This section establishes some terminology and notation for
201 mathematical groups, which are needed later on. Background
202 references abound; see [D1966], for example.
204 A group is a set of elements G together with an operation that
205 combines any two elements in G and returns a third element in G. The
206 operation is denoted as * and its application is denoted as a * b,
207 for any two elements a and b in G. The operation is associative, that
208 is, for all a, b and c in G, a * (b * c) is identical to (a * b) * c.
209 Repeated application of the group operation N-1 times to the element
210 a is denoted as a^N, for any element a in G and any positive integer
211 N. That is, a^2, = a * a, a^3 = a * a * a, and so on. The
212 associativity of the group operation ensures that the computation of
213 a^n is unambiguous; any grouping of the terms gives the same result.
215 The above definition of a group operation uses multiplicative
216 notation. Sometimes an alternative called additive notation is used,
217 in which a * b is denoted as a + b, and a^N is denoted as N * a. In
218 multiplicative notation, a^N is called exponentiation, while the
219 equivalent operation in additive notation is called scalar
220 multiplication. In this document, multiplicative notation is used
221 throughout for consistency. Appendix E elucidates the correspondence
222 between the two notations.
224 Every group has a special element called the identity element, which
225 we denote as e. For each element a in G, e * a = a * e = a. By
226 convention, a^0 is equal to the identity element for any a in G.
228 Every group element a has a unique inverse element b such that
229 a * b = b * a = e. The inverse of a is denoted as a^-1 in
230 multiplicative notation. (In additive notation, the inverse of a is
231 denoted as -a.)
233 For any positive integer X, a^(-X) is defined to be (a^-1)^(X).
234 Using this convention, exponentiation behaves as one would expect,
235 namely for any integers X and Y:
237 a^(X+Y) = (a^X)*(a^Y)
239 (a^X)^Y = a^(XY) = (a^Y)^X.
241 In cryptographic applications one typically deals with finite groups
242 (groups with a finite number of elements), and for such groups, the
243 number of elements of the group is also called the order of the
244 group. A group element a is said to have finite order if a^X = e for
245 some positive integer X, and the order of a is the smallest such X.
246 If no such X exists, a is said to have infinite order. All elements
247 of a finite group have a finite order, and the order of an element is
248 always a divisor of the group order.
250 If a group element a has order R, then for any integers X and Y,
252 a^X = a^(X mod R),
254 a^X = a^Y if and only if X is congruent to Y mod R,
256 the set H = { a, a^2, a^3, ... , a^R=e } forms a subgroup of G,
257 called the cyclic subgroup generated by a, and a is said to be a
258 generator of H.
260 Typically there are several group elements that generate H. Any group
261 element of the form a^M, with M relatively prime to R, also generates
262 H. Note that a^M is equal to g^(M modulo R) for any non-negative
263 integer M.
265 Given the element a of order R, and an integer i between 1 and R-1,
266 inclusive, the element a^i can be computed by the "square and
267 multiply" method outlined in Section 2.1 of [M1983] (see also Knuth,
268 Vol. 2, Section 4.6.3.), or other methods.
270 2.3. The Finite Field Fp
272 This section establishes terminology and notation for finite fields
273 with prime characteristic.
275 When p is a prime number, then the set Zp, with the addition,
276 subtraction, multiplication and division operations, is a finite
277 field with characteristic p. Each nonzero element x in Zp has an
278 inverse 1/x. There is a one-to-one correspondence between the
279 integers between zero and p-1, inclusive, and the elements of the
280 field. The field Zp is sometimes denoted as Fp or GF(p).
282 Equations involving field elements do not explicitly denote the "mod
283 p" operation, but it is understood to be implicit. For example, the
284 statement that x, y, and z are in Fp and
286 z = x + y
288 is equivalent to the statement that x, y, and z are in the set
289 { 0, 1, ..., p-1 } and
291 z = x + y mod p.
293 3. Elliptic Curve Groups
295 This note only covers elliptic curves over fields with characteristic
296 greater than three; these are the curves used in Suite B [SuiteB].
297 For other fields, the definition of the elliptic curve group would be
298 different.
300 An elliptic curve over a field Fp is defined by the curve equation
302 y^2 = x^3 + a*x + b,
304 where x, y, a, and b are elements of the field Fp [M1985] and the
305 discriminant is nonzero (as described in Section 3.3.1). A point on
306 an elliptic curve is a pair (x,y) of values in Fp that satisfies the
307 curve equation, or it is a special point (@,@) that represents the
308 identity element (which is called the "point at infinity"). The
309 order of an elliptic curve group is the number of distinct points.
311 Two elliptic curve points (x1,y1) and (x2,y2) are equal whenever
312 x1=x2 and y1=y2, or when both points are the point at infinity. The
313 inverse of the point (x1,y1) is the point (x1,-y1). The point at
314 infinity is its own inverse.
316 The group operation associated with the elliptic curve group is as
317 follows [BC1989]. To an arbitrary pair of points P and Q specified
318 by their coordinates (x1,y1) and (x2,y2) respectively, the group
319 operation assigns a third point P*Q with the coordinates (x3,y3).
320 These coordinates are computed as follows:
322 (x3,y3) = (@,@) when P is not equal to Q and x1 is equal to x2.
324 x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 and
325 y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 when P is not equal to Q and
326 x1 is not equal to x2.
328 (x3,y3) = (@,@) when P is equal to Q and y1 is equal to 0,
330 x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 and
331 y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y1 if P is equal to Q and y1 is
332 not equal to 0.
334 In the above equations, a, x1, x2, x3, y1, y2, and y3 are elements of
335 the field Fp; thus, computation of x3 and y3 in practice must reduce
336 the right-hand-side modulo p. Pseudocode for the group operation is
337 provided in Appendix F.1.
339 The representation of elliptic curve points as a pair of integers in
340 Zp is known as the affine coordinate representation. This
341 representation is suitable as an external data representation for
342 communicating or storing group elements, though the point at infinity
343 must be treated as a special case.
345 Some pairs of integers are not valid elliptic curve points. A valid
346 pair will satisfy the curve equation, while an invalid pair will not.
348 3.1. Homogeneous Coordinates
350 An alternative way to implement the group operation is to use
351 homogeneous coordinates [K1987] (see also [KMOV1991]). This method
352 is typically more efficient because it does not require a modular
353 inversion operation.
355 An elliptic curve point (x,y) (other than the point at infinity
356 (@,@)) is equivalent to a point (X,Y,Z) in homogeneous coordinates
357 whenever x=X/Z mod p and y=Y/Z mod p.
359 Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on an elliptic curve
360 and suppose that the points P1, P2 are not equal to (@,@), P1 is not
361 equal to P2, and P1 is not equal to P2^-1. Then the product
362 P3=(X3,Y3,Z3) = P1 * P2 is given by
364 X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3) mod p
366 Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3 mod p
368 Z3 = v^3 * Z1 * Z2 mod p
370 where u = Y2 * Z1 - Y1 * Z2 mod p and v = X2 * Z1 - X1 * Z2 mod p.
372 When the points P1 and P2 are equal, then (X1/Z1, Y1/Z1) is equal to
373 (X2/Z2, Y2/Z2), which is true if and only if u and v are both equal
374 to zero.
376 The product P3=(X3,Y3,Z3) = P1 * P1 is given by
378 X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1) mod p
380 Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3 mod p
382 Z3 = 8 * (Y1 * Z1)^3 mod p
384 where w = 3 * X1^2 + a * Z1^2 mod p. In the above equations, a, u,
385 v, w, X1, X2, X3, Y1, Y2, Y3, Z1, Z2, and Z3 are integers in the set
386 Fp. Pseudocode for the group operation in homogeneous coordinates is
387 provided in Appendix F.2.
389 When converting from affine coordinates to homogeneous coordinates,
390 it is convenient to set Z to 1. When converting from homogeneous
391 coordinates to affine coordinates, it is necessary to perform a
392 modular inverse to find 1/Z mod p.
394 3.2. Other Coordinates
396 Some other coordinate systems have been described; several are
397 documented in [CC1986], including Jacobi coordinates.
399 3.3. ECC Parameters
401 In cryptographic contexts, an elliptic curve parameter set consists
402 of a cyclic subgroup of an elliptic curve together with a preferred
403 generator of that subgroup. When working over a prime order finite
404 field with characteristic greater than three, an elliptic curve group
405 is completely specified by the following parameters:
407 The prime number p that indicates the order of the field Fp.
409 The value a used in the curve equation.
411 The value b used in the curve equation.
413 The generator g of the subgroup.
415 The order n of the subgroup generated by g.
417 An example of an ECC parameter set is provided in Appendix D.
419 Parameter generation is out of scope for this note.
421 Each elliptic curve point is associated with a particular parameter
422 set. The elliptic curve group operation is only defined between two
423 points in the same group. It is an error to apply the group
424 operation to two elements that are from different groups, or to apply
425 the group operation to a pair of coordinates that is not a valid
426 point. (A pair (x,y) of coordinates in Fp is a valid point only when
427 they satisfy the curve equation.) See Section 10.3 for further
428 information.
430 3.3.1. Discriminant
432 For each elliptic curve group, the discriminant -16*(4*a^3 + 27*b^2)
433 must be nonzero modulo p [S1986]; this requires that
435 4*a^3 + 27*b^2 != 0 mod p.
437 3.3.2. Security
439 Security is highly dependent on the choice of these parameters. This
440 section gives normative guidance on acceptable choices. See also
441 Section 10 for informative guidance.
443 The order of the group generated by g MUST be divisible by a large
444 prime, in order to preclude easy solutions of the discrete logarithm
445 problem [K1987].
447 With some parameter choices, the discrete log problem is
448 significantly easier to solve. This includes parameter sets in which
449 b = 0 and p = 3 (mod 4), and parameter sets in which a = 0 and
450 p = 2 (mod 3) [MOV1993]. These parameter choices are inferior for
451 cryptographic purposes and SHOULD NOT be used.
453 4. Elliptic Curve Diffie-Hellman (ECDH)
455 The Diffie-Hellman (DH) key exchange protocol [DH1976] allows two
456 parties communicating over an insecure channel to agree on a secret
457 key. It was originally defined in terms of operations in the
458 multiplicative group of a field with a large prime characteristic.
459 Massey [M1983] observed that it can be easily generalized so that it
460 is defined in terms of an arbitrary cyclic group. Miller [M1985] and
461 Koblitz [K1987] analyzed the DH protocol over an elliptic curve
462 group. We describe DH following the former reference.
464 Let G be a group, and g be a generator for that group, and let t
465 denote the order of G. The DH protocol runs as follows. Party A
466 chooses an exponent j between 1 and t-1, inclusive, uniformly at
467 random, computes g^j and sends that element to B. Party B chooses an
468 exponent k between 1 and t-1, inclusive, uniformly at random,
469 computes g^k and sends that element to A. Each party can compute
470 g^(j*k); party A computes (g^k)^j, and party B computes (g^j)^k.
472 See Appendix B regarding generation of random integers.
474 4.1. Data Types
476 Each run of the ECDH protocol is associated with a particular
477 parameter set (as defined in Section 3.3), and the public keys g^j
478 and g^k and the shared secret g^(j*k) are elements of the cyclic
479 subgroup associated with the parameter set.
481 An ECDH private key z is an integer in Zt, where t is the order of
482 the subgroup.
484 4.2. Compact Representation
486 As described in the final paragraph of [M1985], the x-coordinate of
487 the shared secret value g^(j*k) is a suitable representative for the
488 entire point whenever exponentiation is used as a one-way function.
489 In the ECDH key exchange protocol, after the element g^(j*k) has been
490 computed, the x-coordinate of that value can be used as the shared
491 secret. We call this compact output.
493 Following [M1985] again, when compact output is used in ECDH, only
494 the x-coordinate of an elliptic curve point needs to be transmitted,
495 instead of both coordinates as in the typical affine coordinate
496 representation. We call this the compact representation. Its
497 mathematical background is explained in Appendix C.
499 ECDH can be used with or without compact output. Both parties in a
500 particular run of the ECDH protocol MUST use the same method. ECDH
501 can be used with or without compact representation. If compact
502 representation is used in a particular run of the ECDH protocol, then
503 compact output MUST be used as well.
505 5. Elliptic Curve ElGamal Signatures
507 5.1. Background
509 The ElGamal signature algorithm was introduced in 1984 [E1984a]
510 [E1984b] [E1985]. It is based on the discrete logarithm problem, and
511 was originally defined for the multiplicative group of the integers
512 modulo a large prime number. It is straightforward to extend it to
513 use other finite groups, such as the multiplicative group of the
514 finite field GF(2^w) [AMV1990] or an elliptic curve group [A1992].
516 An ElGamal signature consists of a pair of components. There are
517 many possible generalizations of ElGamal signature methods that have
518 been obtained by different rearrangements of the equation for the
519 second component; see [HMP1994], [HP1994], [NR1994], [A1992], and
520 [AMV1990]. These generalizations are independent of the mathematical
521 group used, and have been described for the multiplicative group
522 modulo a prime number, the multiplicative group of GF(2^w), and
523 elliptic curve groups [HMP1994][NR1994][AMV1990][A1992].
525 The Digital Signature Algorithm (DSA) [FIPS186] is an important
526 ElGamal signature variant.
528 5.2. Hash Functions
530 ElGamal signatures must use a collision-resistant hash function, so
531 that it can sign messages of arbitrary length and can avoid
532 existential forgery attacks; see Section 10.4. (This is true for all
533 ElGamal variants [HMP1994].) We denote the hash function as h().
534 Its input is a bit string of arbitrary length, and its output is a
535 non-negative integer.
537 Let H() denote a hash function whose output is a fixed-length bit
538 string. To use H in an ElGamal signature method, we define the
539 mapping between that output and the non-negative integers; this
540 realizes the function h() described above. Given a bit string m, the
541 function h(m) is computed as follows:
543 1. H(m) is evaluated; the result is a fixed-length bit string.
545 2. Convert the resulting bit string to an integer i by treating its
546 leftmost (initial) bit as the most significant bit of i, and
547 treating its rightmost (final) bit as the least significant bit
548 of i.
550 5.3. KT-IV Signatures
552 Koyama and Tsuruoka described a signature method based on Elliptic
553 Curve ElGamal, in which the first signature component is the
554 x-coordinate of an elliptic curve point reduced modulo q [KT1994].
555 In this section we recall that method, which we refer to as KT-IV.
557 The algorithm uses an elliptic curve group, as described in
558 Section 3.3, with prime field order p and curve equation parameters a
559 and b. We denote the generator as alpha, and the order of the
560 generator as q. We follow [FIPS186] in checking for exceptional
561 cases.
563 5.3.1. Keypair Generation
565 The private key z is an integer between 1 and q - 1, inclusive,
566 generated uniformly at random. (See Appendix B regarding random
567 integers.) The public key is the group element
568 Y = alpha^z. Each public key is associated with a particular
569 particular parameter set as per Section 3.3.
571 5.3.2. Signature Creation
573 To compute a KT-IV signature for a message m using the private key z:
575 1. Choose an integer k uniformly at random from the set of all
576 integers between 1 and q-1, inclusive. (See Appendix B regarding
577 random integers.)
579 2. Calculate R = (r_x, r_y) = alpha^k.
581 3. Calculate s1 = r_x mod q.
583 4. Check if h(m) + z * s1 = 0 mod q; if so, a new value of k MUST be
584 generated and the signature MUST be recalculated. As an option,
585 one MAY check if s1 = 0; if so, a new value of k SHOULD be
586 generated and the signature SHOULD be recalculated. (It is
587 extremely unlikely that s1 = 0 or h(m) + z * s1 = 0 mod q if
588 signatures are generated properly.)
590 5. Calculate s2 = k / (h(m) + z * s1) mod q.
592 The signature is the ordered pair (s1, s2). Both signature
593 components are non-negative integers.
595 5.3.3. Signature Verification
597 Given the message m, the generator g, the group order q, the public
598 key Y, and the signature (s1, s2) verification is as follows:
600 1. Check to see that 0 < s1 < q and 0 < s2 < q; if either condition
601 is violated, the signature SHALL be rejected.
603 2. Compute the non-negative integers u1 and u2, where
605 u1 = h(m) * s2 mod q, and
607 u2 = s1 * s2 mod q.
609 3. Compute the elliptic curve point R' = alpha^u1 * Y^u2.
611 4. If the x-coordinate of R' mod q is equal to s1, then the
612 signature and message pass the verification; otherwise, they
613 fail.
615 5.4. KT-I Signatures
617 Horster, Michels, and Petersen categorized many different ElGamal
618 signature methods, demonstrated their equivalence, and showed how to
619 convert signatures of one type to another type [HMP1994]. In their
620 terminology, the signature method of Section 5.3 and [KT1994] is a
621 Type IV method, which is why it is denoted as KT-IV.
623 A Type I KT signature method has a second component that is computed
624 in the same manner as that of the Digital Signature Algorithm. In
625 this section, we describe this method, which we refer to as KT-I.
627 5.4.1. Keypair Generation
629 Keypairs and keypair generation are exactly as in Section 5.3.1.
631 5.4.2. Signature Creation
633 To compute a KT-I signature for a message m using the private key z:
635 1. Choose an integer k uniformly at random from the set of all
636 integers between 1 and q-1, inclusive. (See Appendix B regarding
637 random integers.)
639 2. Calculate R = (r_x, r_y) = alpha^k.
641 3. Calculate s1 = r_x mod q.
643 4. Calculate s2 = (h(m) + z * s1) / k mod q.
645 5. As an option, one MAY check if s1 = 0 or s2 = 0. If either
646 s1 = 0 or s2 = 0, a new value of k SHOULD be generated and the
647 signature SHOULD be recalculated. (It is extremely unlikely that
648 s1 = 0 or s2 = 0 if signatures are generated properly.)
650 The signature is the ordered pair (s1, s2). Both signature
651 components are non-negative integers.
653 5.4.3. Signature Verification
655 Given the message m, the public key Y, and the signature (s1, s2)
656 verification is as follows:
658 1. Check to see that 0 < s1 < q and 0 < s2 < q; if either condition
659 is violated the signature SHALL be rejected.
661 2. Compute s2_inv = 1 / s2 mod q.
663 3. Compute the non-negative integers u1 and u2, where
665 u1 = h(m) * s2_inv mod q, and
667 u2 = s1 * s2_inv mod q.
669 4. Compute the elliptic curve point R' = alpha^u1 * Y^u2.
671 5. If the x-coordinate of R' mod q is equal to s1, then the
672 signature and message pass the verification; otherwise, they
673 fail.
675 5.5. Converting KT-IV Signatures to KT-I Signatures
677 A KT-IV signature for a message m and a public key Y can easily be
678 converted into a KT-I signature for the same message and public key.
679 If (s1, s2) is a KT-IV signature for a message m, then
680 (s1, 1/s2 mod q) is a KT-I signature for the same message [HMP1994].
682 The conversion operation uses only public information, and it can be
683 performed by the creator of the pre-conversion KT-IV signature, the
684 verifier of the post-conversion KT-I signature, or by any other
685 entity.
687 An implementation MAY use this method to compute KT-I signatures.
689 5.6. Rationale
691 This subsection is not normative for this specification and is
692 provided only as background information.
694 [HMP1994] presents many generalizations of ElGamal signatures.
695 Equation (5) of that reference shows the general signature equation
697 A = x_A * B + k * C (mod q)
699 where x_A is the private key, k is the secret value, and A, B, and C
700 are determined by the Type of the equation, as shown in Table 1 of
701 [HMP1994]. DSA [FIPS186] is an EG-I.1 signature method (as is KT-I),
702 with A = m, B = -r, and C = s. (Here we use the notation of
703 [HMP1994] in which the first signature component is r and the second
704 signature component is s; in KT-I and KT-IV these components are
705 denoted as s1 and s2 respectively. The private key x_A corresponds
706 to the private key z.) Its signature equation is
708 m = - r * z + s * k (mod q).
710 The signature method of [KT1994] and Section 5.3 is an EG-IV.1
711 method, with A = m * s, B = - r * s, C = 1. Its signature equation
712 is
714 m * s = - r * s * z + k (mod q)
716 The functions f and g mentioned in Table 1 are merely multiplication,
717 as described under the heading "Fifth generalization".
719 In the above equations, we rely on the implicit conversion of the
720 message m from a bit string to an integer. No hash function is shown
721 in these equations, but as described in Section 10.4, a hash function
722 should be applied to the message prior to signing in order to prevent
723 existential forgery attacks.
725 Nyberg and Rueppel [NR1994] studied many different ElGamal signature
726 methods, and defined "strong equivalence" as follows:
728 Two signature methods are called strongly equivalent if the
729 signature of the first scheme can be transformed efficiently into
730 signatures of the second scheme and vice versa, without knowledge
731 of the private key.
733 KT-I and KT-IV signatures are obviously strongly equivalent.
735 A valid signature with s2=0 leaks the secret key, since in that case
736 z = - h(m) / s1 mod q. We follow [FIPS186] in checking for this
737 exceptional case and the case that s1=0. The s2=0 check was
738 suggested by Rivest [R1992] and is discussed in [BS1992].
740 [KT1994] uses "a positive integer q' that does not exceed q" when
741 computing the signature component s1 from the x-coordinate r_x of the
742 elliptic curve point R = (r_x, r_y). The value q' is also used
743 during signature validation when comparing the x-coordinate of a
744 computed elliptic curve point to the value to s1. In this note, we
745 use the simplifying convention that q' = q.
747 6. Converting Between Integers and Octet Strings
749 A method for the conversion between integers and octet strings is
750 specified in this section, following the established conventions of
751 public key cryptography [R1993]. This method allows integers to be
752 represented as octet strings that are suitable for transmission or
753 storage. This method SHOULD be used when representing an elliptic
754 curve point or an elliptic curve coordinate as they are defined in
755 this note.
757 6.1. Octet-String-to-Integer Conversion
759 The octet string S shall be converted to an integer x as follows.
760 Let S1, ..., Sk be the octets of S from first to last. Then the
761 integer x shall satisfy
763 k
764 x = SUM 2^(8(k-i)) Si .
765 i = 1
767 In other words, the first octet of S has the most significance in the
768 integer and the last octet of S has the least significance.
770 Note: the integer x satisfies 0 <= x < 2^(8*k).
772 6.2. Integer-to-Octet-String Conversion
774 The integer x shall be converted to an octet string S of length k as
775 follows. The string S shall satisfy
777 k
778 y = SUM 2^(8(k-i)) Si .
779 i = 1
781 where S1, ..., Sk are the octets of S from first to last.
783 In other words, the first octet of S has the most significance in the
784 integer and the last octet of S has the least significance.
786 7. Interoperability
788 The algorithms in this note can be used to interoperate with some
789 other ECC specifications. This section provides details for each
790 algorithm.
792 7.1. ECDH
794 Section 4 can be used with the Internet Key Exchange (IKE) versions
795 one [RFC2409] or two [RFC4306]. These algorithms are compatible with
796 the ECP groups defined by [RFC4753], [RFC5114], [RFC2409], and
797 [RFC2412]. The group definition in this protocol uses an affine
798 coordinate representation of the public key and uses neither the
799 compact output nor the compact representation of Section 4.2.
800 [RFC4753] describes data formats that are compatible with those of
801 Section 6. Note that some groups indicate that the curve parameter
802 "a" is negative; these values are to be interpreted modulo the order
803 of the field. For example, a parameter of a = -3 is equal to p - 3,
804 where p is the order of the field. The test cases in Section 8 of
805 [RFC4753] can be used to test an implementation; these cases use the
806 multiplicative notation, as does this note. The KEi and KEr payloads
807 are equal to g^j and g^k, respectively, with 64 bits of encoding data
808 prepended to them.
810 The algorithms in Section 4 can be used to interoperate with the IEEE
811 [P1363] and ANSI [X9.62] standards for ECDH based on fields of
812 characteristic greater than three. IEEE P1363 ECDH can be used in a
813 manner that will interoperate with this note, with the following
814 options and parameter choices from that specification:
816 prime curves with a cofactor of 1,
818 the ECSVDP-DH primitive, and
820 the Key Derivation Function must be the "identity" function
821 (equivalently, the KDF step should be omitted and the shared
822 secret value should be output directly).
824 7.2. KT-I and ECDSA
826 The Digital Signature Algorithm (DSA) is based on the discrete
827 logarithm problem over the multiplicative subgroup of the finite
828 field with large prime order [DSA1991][FIPS186]. The Elliptic Curve
829 Digital Signature Algorithm (ECDSA) [P1363] [X9.62] is an elliptic
830 curve version of DSA.
832 KT-I is mathematically and functionally equivalent to ECDSA, and can
833 interoperate with the IEEE [P1363] and ANSI [X9.62] standards for
834 Elliptic Curve DSA (ECDSA) based on fields of characteristic greater
835 than three. KT-I signatures can be verified using the ECDSA
836 verification algorithm, and ECDSA signatures can be verified using
837 the KT-I verification algorithm.
839 8. Validating an Implementation
841 It is essential to validate the implementation of a cryptographic
842 algorithm. This section outlines tests that should be performed on
843 the algorithms defined in this note.
845 A known answer test, or KAT, uses a fixed set of inputs to test an
846 algorithm; the output of the algorithm is compared with the expected
847 output, which is also a fixed value. KATs for ECDH and KT-I are set
848 out in the following subsections.
850 A consistency test generates inputs for one algorithm being tested
851 using a second algorithm that is also being tested, then checks the
852 output of the first algorithm. A signature creation algorithm can be
853 tested for consistency against a signature verification algorithm.
854 Implementations of KT-I should be tested in this way. Their
855 signature generation processes are non-deterministic, and thus cannot
856 be tested using a KAT. Signature verification algorithms, on the
857 other hand, are deterministic and should be tested via a KAT. This
858 combination of tests provides coverage for all of the operations,
859 including keypair generation. Consistency testing should also be
860 applied to ECDH.
862 8.1. ECDH
864 An ECDH implementation can be validated using the known answer test
865 cases from [RFC4753] or [RFC5114]. The correspondence between the
866 notation in RFC 4753 and the notation in this note are summarized in
867 the following table. (Refer to Section 3.3 and Section 4; the
868 generator g is expressed in affine coordinate representation as (gx,
869 gy)).
871 +----------------------+---------------------------------------+
872 | ECDH | RFC 4753 |
873 +----------------------+---------------------------------------+
874 | order p of field Fp | p |
875 | curve coefficient a | -3 |
876 | curve coefficient b | b |
877 | generator g | g=(gx, gy) |
878 | private keys j and k | i and r |
879 | public keys g^j, g^k | g^i = (gix, giy) and g^r = (grx, gry) |
880 +----------------------+---------------------------------------+
882 The correspondence between the notation in RFC 5114 and the notation
883 in this note are summarized in the following table.
885 +-----------------------+---------------------------+
886 | ECDH | RFC 5114 |
887 +-----------------------+---------------------------+
888 | order p of field Fp | p |
889 | curve coefficient a | a |
890 | curve coefficient b | b |
891 | generator g | g=(gx, gy) |
892 | group order n | n |
893 | private keys j and k | dA and dB |
894 | public keys g^j, g^k | g^(dA) = (x_qA, y_qA) and |
895 | | g^(dB) = (x_qB, y_qB) |
896 | shared secret g^(j*k) | g^(dA*dB) = (x_Z, y_Z) |
897 +-----------------------+---------------------------+
899 8.2. KT-I
901 A KT-I implementation can be validated using the known answer test
902 cases from [RFC4754]. The correspondence between the notation in
903 that RFC and the notation in this note are summarized in the
904 following table.
906 +---------------------+------------------+
907 | KT-I | RFC 4754 |
908 +---------------------+------------------+
909 | order p of field Fp | p |
910 | curve coefficient a | -3 |
911 | curve coefficient b | b |
912 | generator alpha | g |
913 | group order q | q |
914 | private key z | w |
915 | public key Y | g^w = (gwx,gwy) |
916 | random k | ephem priv k |
917 | s1 | r |
918 | s2 | s |
919 | s2_inv | sinv |
920 | u1 | u = h*sinv mod q |
921 | u2 | v = r*sinv mod q |
922 +---------------------+------------------+
924 9. Intellectual Property
926 Concerns about intellectual property have slowed the adoption of ECC,
927 because a number of optimizations and specialized algorithms have
928 been patented in recent years.
930 All of the normative references for ECDH (as defined in Section 4)
931 were published during or before 1989, and those for KT-I were
932 published during or before May 1994. All of the normative text for
933 these algorithms is based solely on their respective references.
935 9.1. Disclaimer
937 This document is not intended as legal advice. Readers are advised
938 to consult their own legal advisers if they would like a legal
939 interpretation of their rights.
941 The IETF policies and processes regarding intellectual property and
942 patents are outlined in [RFC3979] and [RFC4879] and at
943 https://datatracker.ietf.org/ipr/about/.
945 10. Security Considerations
947 The security level of an elliptic curve cryptosystem is determined by
948 the cryptanalytic algorithm that is the least expensive for an
949 attacker to implement. There are several algorithms to consider.
951 The Pohlig-Hellman method is a divide-and-conquer technique [PH1978].
953 If the group order n can be factored as
955 n = q1 * q2 * ... * qz,
957 then the discrete log problem over the group can be solved by
958 independently solving a discrete log problem in groups of order q1,
959 q2, ..., qz, then combining the results using the Chinese remainder
960 theorem. The overall computational cost is dominated by that of the
961 discrete log problem in the subgroup with the largest order.
963 Shanks' algorithm [K1981v3] computes a discrete logarithm in a group
964 of order n using O(sqrt(n)) operations and O(sqrt(n)) storage. The
965 Pollard rho algorithm [P1978] computes a discrete logarithm in a
966 group of order n using O(sqrt(n)) operations, with a negligible
967 amount of storage, and can be efficiently parallelized [VW1994].
969 The Pollard lambda algorithm [P1978] can solve the discrete logarithm
970 problem using O(sqrt(w)) operations and O(log(w)) storage, when the
971 exponent is known to lie in an interval of width w.
973 The algorithms described above work in any group. There are
974 specialized algorithms that specifically target elliptic curve
975 groups. There are no known subexponential algorithms against general
976 elliptic curve groups, though there are methods that target certain
977 special elliptic curve groups; see [MOV1993] and [FR1994].
979 10.1. Subgroups
981 A group consisting of a nonempty set of elements S with associated
982 group operation * is a subgroup of the group with the set of elements
983 G, if the latter group uses the same group operation and S is a
984 subset of G. For each elliptic curve equation, there is an elliptic
985 curve group whose group order is equal to the order of the elliptic
986 curve; that is, there is a group that contains every point on the
987 curve.
989 The order m of the elliptic curve is divisible by the order n of the
990 group associated with the generator; that is, for each elliptic curve
991 group, m = n * c for some number c. The number c is called the
992 "cofactor" [P1363]. Each ECC parameter set as in Section 3.3 is
993 associated with a particular cofactor.
995 It is possible and desirable to use a cofactor equal to 1.
997 10.2. Diffie-Hellman
999 Note that the key exchange protocol as defined in Section 4 does not
1000 protect against active attacks; Party A must use some method to
1001 ensure that (g^k) originated with the intended communicant B, rather
1002 than an attacker, and Party B must do the same with (g^j).
1004 It is not sufficient to authenticate the shared secret g^(j*k), since
1005 this leaves the protocol open to attacks that manipulate the public
1006 keys. Instead, the values of the public keys g^x and g^y that are
1007 exchanged should be directly authenticated. This is the strategy
1008 used by protocols that build on Diffie-Hellman and which use end-
1009 entity authentication to protect against active attacks, such as
1010 OAKLEY [RFC2412] and the Internet Key Exchange [RFC2409][RFC4306].
1012 When the cofactor of a group is not equal to 1, there are a number of
1013 attacks that are possible against ECDH. See [VW1996], [AV1996], and
1014 [LL1997].
1016 10.3. Group Representation and Security
1018 The elliptic curve group operation does not explicitly incorporate
1019 the parameter b from the curve equation. This opens the possibility
1020 that a malicious attacker could learn information about an ECDH
1021 private key by submitting a bogus public key [BMM2000]. An attacker
1022 can craft an elliptic curve group G' that has identical parameters to
1023 a group G that is being used in an ECDH protocol, except that b is
1024 different. An attacker can submit a point on G' into a run of the
1025 ECDH protocol that is using group G, and gain information from the
1026 fact that the group operations using the private key of the device
1027 under attack are effectively taking place in G' instead of G.
1029 This attack can gain useful information about an ECDH private key
1030 that is associated with a static public key, that is, a public key
1031 that is used in more than one run of the protocol. However, it does
1032 not gain any useful information against ephemeral keys.
1034 This sort of attack is thwarted if an ECDH implementation does not
1035 assume that each pair of coordinates in Zp is actually a point on the
1036 appropriate elliptic curve.
1038 These considerations also apply when ECDH is used with compact
1039 representation (see Appendix C).
1041 10.4. Signatures
1043 Elliptic curve parameters should only be used if they come from a
1044 trusted source; otherwise, some attacks are possible [AV1996],
1045 [V1996].
1047 If no hash function is used in an ElGamal signature system, then the
1048 system is vulnerable to existential forgeries, in which an attacker
1049 who does not know a private key can generate valid signatures for the
1050 associated public key, but cannot generate a signature for a message
1051 of its own choosing. (See [E1985] for instance.) The use of a
1052 collision-resistant hash function eliminates this vulnerability.
1054 In principle, any collision-resistant hash function is suitable for
1055 use in KT signatures. To facilitate interoperability, we recognize
1056 the following hashes as suitable for use as the function H defined in
1057 Section 5.2:
1059 SHA-256, which has a 256-bit output.
1061 SHA-384, which has a 384-bit output.
1063 SHA-512, which has a 512-bit output.
1065 All of these hash functions are defined in [FIPS180-2].
1067 The number of bits in the output of the hash used in KT signatures
1068 should be equal or close to the number of bits needed to represent
1069 the group order.
1071 11. IANA Considerations
1073 This note has no actions for IANA. This section should be removed by
1074 the RFC editor before publication as an RFC.
1076 12. Acknowledgements
1078 The author expresses his thanks to the originators of elliptic curve
1079 cryptography, whose work made this note possible, and all of the
1080 reviewers, who provided valuable constructive feedback. Thanks are
1081 especially due to Howard Pinder, Andrey Jivsov, Alfred Hoenes (who
1082 contributed the algorithms in Appendix F), Dan Harkins, and Tina
1083 Tsou.
1085 13. References
1087 13.1. Normative References
1089 [AMV1990] Agnew, G., Mullin, R., and S. Vanstone, "Improved Digital
1090 Signature Scheme based on Discrete Exponentiation",
1091 Electronics Letters Vol. 26, No. 14, July, 1990.
1093 [BC1989] Bender, A. and G. Castagnoli, "On the Implementation of
1094 Elliptic Curve Cryptosystems", Advances in Cryptology -
1095 CRYPTO '89 Proceedings Spinger Lecture Notes in Computer
1096 Science (LNCS) volume 435, 1989.
1098 [CC1986] Chudnovsky, D. and G. Chudnovsky, "Sequences of numbers
1099 generated by addition in formal groups and new primality
1100 and factorization tests", Advances in Applied
1101 Mathematics Volume 7, Issue 4, December 1986.
1103 [D1966] Deskins, W., "Abstract Algebra", MacMillan Company New
1104 York, 1966.
1106 [DH1976] Diffie, W. and M. Hellman, "New Directions in
1107 Cryptography", IEEE Transactions in Information
1108 Theory IT-22, pp 644-654, 1976.
1110 [FR1994] Frey, G. and H. Ruck, "A remark concerning m-divisibility
1111 and the discrete logarithm in the divisor class group of
1112 curves.", Mathematics of Computation Vol. 62, No. 206, pp.
1113 865-874, 1994.
1115 [HMP1994] Horster, P., Michels, M., and H. Petersen, "Meta-ElGamal
1116 signature schemes", University of Technology Chemnitz-
1117 Zwickau Department of Computer Science Technical
1118 Report TR-94-5, May 1994.
1120 [K1981v2] Knuth, D., "The Art of Computer Programming, Vol. 2:
1121 Seminumerical Algorithms", Addison Wesley , 1981.
1123 [K1987] Koblitz, N., "Elliptic Curve Cryptosystems", Mathematics
1124 of Computation Vol. 48, 1987, 203-209, 1987.
1126 [KT1994] Koyama, K. and Y. Tsuruoka, "Digital signature system
1127 based on elliptic curve and signer device and verifier
1128 device for said system", Japanese Unexamined Patent
1129 Application Publication H6-43809, February 18, 1994.
1131 [M1983] Massey, J., "Logarithms in finite cyclic groups -
1132 cryptographic issues", Proceedings of the 4th Symposium on
1133 Information Theory , 1983.
1135 [M1985] Miller, V., "Use of elliptic curves in cryptography",
1136 Advances in Cryptology - CRYPTO '85 Proceedings Springer
1137 Lecture Notes in Computer Science (LNCS) volume 218, 1985.
1139 [MOV1993] Menezes, A., Vanstone, S., and T. Okamoto, "Reducing
1140 Elliptic Curve Logarithms to Logarithms in a Finite
1141 Field", IEEE Transactions on Information Theory Vol 39,
1142 No. 5, pp. 1639-1646, September, 1993.
1144 [R1993] RSA Laboratories, "PKCS#1: RSA Encryption Standard",
1145 Technical Note version 1.5, 1993.
1147 [S1986] Silverman, J., "The Arithmetic of Elliptic Curves",
1148 Springer-Verlag New York, 1986.
1150 13.2. Informative References
1152 [A1992] Anderson, J., "Response to the proposed DSS",
1153 Communications of the ACM v.35 n.7 p.50-52, July 1992.
1155 [AV1996] Anderson, R. and S. Vaudenay, "Minding Your P's and Q's",
1156 Advances in Cryptology - ASIACRYPT '96 Proceedings Spinger
1157 Lecture Notes in Computer Science (LNCS) volume 1163,
1158 1996.
1160 [BMM2000] Biehl, I., Meyer, B., and V. Muller, "Differential fault
1161 analysis on elliptic curve cryptosystems", Advances in
1162 Cryptology - CRYPTO 2000 Proceedings Spinger Lecture Notes
1163 in Computer Science (LNCS) volume 1880, 2000.
1165 [BS1992] Branstad, D. and M. Smid, "Response to Comments on the
1166 NIST Proposed Digital Signature Standard", Advances in
1167 Cryptology - CRYPTO '92 Proceedings Springer Lecture Notes
1168 in Computer Science (LNCS) volume 740, August 1992.
1170 [DSA1991] U.S. National Institute of Standards and Technology,
1171 "DIGITAL SIGNATURE STANDARD", Federal Register Vol. 56,
1172 August 1991.
1174 [E1984a] ElGamal, T., "Cryptography and logarithms over finite
1175 fields", Stanford University UMI Order No. DA 8420519,
1176 1984.
1178 [E1984b] ElGamal, T., "Cryptography and logarithms over finite
1179 fields", Advances in Cryptology - CRYPTO '84
1180 Proceedings Springer Lecture Notes in Computer Science
1181 (LNCS) volume 196, 1984.
1183 [E1985] ElGamal, T., "A public key cryptosystem and a signature
1184 scheme based on discrete logarithms", IEEE Transactions on
1185 Information Theory Vol 30, No. 4, pp. 469-472, 1985.
1187 [FIPS180-2]
1188 U.S. National Institute of Standards and Technology,
1189 "SECURE HASH STANDARD", Federal Information Processing
1190 Standard (FIPS) 180-2, August 2002.
1192 [FIPS186] U.S. National Institute of Standards and Technology,
1193 "DIGITAL SIGNATURE STANDARD", Federal Information
1194 Processing Standard FIPS-186, May 1994.
1196 [HP1994] Horster, P. and H. Petersen, "Verallgemeinerte ElGamal-
1197 Signaturen", Proceedings der Fachtagung SIS '94, Verlag
1198 der Fachvereine Zurich, 1994.
1200 [K1981v3] Knuth, D., "The Art of Computer Programming, Vol. 3:
1201 Sorting and Searching", Addison Wesley , 1981.
1203 [KMOV1991]
1204 Koyama, K., Maurer, U., Vanstone, S., and T. Okamoto, "New
1205 Public-Key Schemes Based on Elliptic Curves over the Ring
1206 Zn", Advances in Cryptology - CRYPTO '91
1207 Proceedings Spinger Lecture Notes in Computer Science
1208 (LNCS) volume 576, 1991.
1210 [L1969] Lehmer, D., "Computer technology applied to the theory of
1211 numbers", M.A.A. Studies in Mathematics 180-2, 1969.
1213 [LL1997] Lim, C. and P. Lee, "A Key Recovery Attack on Discrete
1214 Log-based Schemes Using a Prime Order Subgroup", Advances
1215 in Cryptology - CRYPTO '97 Proceedings Spinger Lecture
1216 Notes in Computer Science (LNCS) volume 1294, 1997.
1218 [NR1994] Nyberg, K. and R. Rueppel, "Message Recovery for Signature
1219 Schemes Based on the Discrete Logarithm Problem", Advances
1220 in Cryptology - EUROCRYPT '94 Proceedings Springer Lecture
1221 Notes in Computer Science (LNCS) volume 950, May 1994.
1223 [P1363] "Standard Specifications for Public Key Cryptography",
1224 Institute of Electric and Electronic Engineers
1225 (IEEE) P1363, 2000.
1227 [P1978] Pollard, J., "Monte Carlo methods for index computation
1228 mod p", Mathematics of Computation Vol. 32, 1978.
1230 [PH1978] Pohlig, S. and M. Hellman, "An Improved Algorithm for
1231 Computing Logarithms over GF(p) and its Cryptographic
1232 Significance", IEEE Transactions on Information Theory Vol
1233 24, pp. 106-110, 1978.
1235 [R1988] Rose, H., "A Course in Number Theory", Oxford University
1236 Press , 1988.
1238 [R1992] Rivest, R., "Response to the proposed DSS", Communications
1239 of the ACM v.35 n.7 p.41-47., July 1992.
1241 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
1242 Requirement Levels", BCP 14, RFC 2119, March 1997.
1244 [RFC2409] Harkins, D. and D. Carrel, "The Internet Key Exchange
1245 (IKE)", RFC 2409, November 1998.
1247 [RFC2412] Orman, H., "The OAKLEY Key Determination Protocol",
1248 RFC 2412, November 1998.
1250 [RFC3979] Bradner, S., "Intellectual Property Rights in IETF
1251 Technology", BCP 79, RFC 3979, March 2005.
1253 [RFC4086] Eastlake, D., Schiller, J., and S. Crocker, "Randomness
1254 Requirements for Security", BCP 106, RFC 4086, June 2005.
1256 [RFC4306] Kaufman, C., "Internet Key Exchange (IKEv2) Protocol",
1257 RFC 4306, December 2005.
1259 [RFC4753] Fu, D. and J. Solinas, "ECP Groups For IKE and IKEv2",
1260 RFC 4753, January 2007.
1262 [RFC4754] Fu, D. and J. Solinas, "IKE and IKEv2 Authentication Using
1263 the Elliptic Curve Digital Signature Algorithm (ECDSA)",
1264 RFC 4754, January 2007.
1266 [RFC4879] Narten, T., "Clarification of the Third Party Disclosure
1267 Procedure in RFC 3979", BCP 79, RFC 4879, April 2007.
1269 [RFC5114] Lepinski, M. and S. Kent, "Additional Diffie-Hellman
1270 Groups for Use with IETF Standards", RFC 5114,
1271 January 2008.
1273 [SuiteB] U. S. National Security Agency (NSA), "NSA Suite B
1274 Cryptography", Web Page http://www.nsa.gov/ia/programs/
1275 suiteb_cryptography/index.shtml.
1277 [V1996] Vaudenay, S., "Hidden Collisions on DSS", Advances in
1278 Cryptology - CRYPTO '96 Proceedings Spinger Lecture Notes
1279 in Computer Science (LNCS) volume 1109, 1996.
1281 [VW1994] van Oorschot, P. and M. Wiener, "Parallel Collision Search
1282 with Application to Hash Functions and Discrete
1283 Logarithms", Proceedings of the 2nd ACM Conference on
1284 Computer and communications security pp. 210-218, 1994.
1286 [VW1996] van Oorschot, P. and M. Wiener, "On Diffie-Hellman key
1287 agreement with short exponents", Advances in Cryptology -
1288 EUROCRYPT '96 Proceedings Spinger Lecture Notes in
1289 Computer Science (LNCS) volume 1070, 1996.
1291 [X9.62] "Public Key Cryptography for the Financial Services
1292 Industry: The Elliptic Curve Digital Signature Algorithm
1293 (ECDSA)", American National Standards Institute (ANSI)
1294 X9.62.
1296 Appendix A. Key Words
1298 The definitions of these key words are quoted from [RFC2119] and are
1299 commonly used in Internet standards. They are reproduced in this
1300 note in order to avoid a normative reference from after 1994.
1302 1. MUST - This word, or the terms "REQUIRED" or "SHALL", mean that
1303 the definition is an absolute requirement of the specification.
1305 2. MUST NOT - This phrase, or the phrase "SHALL NOT", mean that the
1306 definition is an absolute prohibition of the specification.
1308 3. SHOULD - This word, or the adjective "RECOMMENDED", mean that
1309 there may exist valid reasons in particular circumstances to
1310 ignore a particular item, but the full implications must be
1311 understood and carefully weighed before choosing a different
1312 course.
1314 4. SHOULD NOT - This phrase, or the phrase "NOT RECOMMENDED" mean
1315 that there may exist valid reasons in particular circumstances
1316 when the particular behavior is acceptable or even useful, but
1317 the full implications should be understood and the case carefully
1318 weighed before implementing any behavior described with this
1319 label.
1321 5. MAY - This word, or the adjective "OPTIONAL", mean that an item
1322 is truly optional. One vendor may choose to include the item
1323 because a particular marketplace requires it or because the
1324 vendor feels that it enhances the product while another vendor
1325 may omit the same item. An implementation which does not include
1326 a particular option MUST be prepared to interoperate with another
1327 implementation which does include the option, though perhaps with
1328 reduced functionality. In the same vein an implementation which
1329 does include a particular option MUST be prepared to interoperate
1330 with another implementation which does not include the option
1331 (except, of course, for the feature the option provides.)
1333 Appendix B. Random Integer Generation
1335 It is easy to generate an integer uniformly at random between zero
1336 and 2^t -1, inclusive, for some positive integer t. Generate a
1337 random bit string that contains exactly t bits, and then convert the
1338 bit string to a non-negative integer by treating the bits as the
1339 coefficients in a base-two expansion of an integer.
1341 It is sometimes necessary to generate an integer r uniformly at
1342 random so that r satisfies a certain property P, for example, lying
1343 within a certain interval. A simple way to do this is with the
1344 rejection method:
1346 1. Generate a candidate number c uniformly at random from a set that
1347 includes all numbers that satisfy property P (plus some other
1348 numbers, preferably not too many)
1350 2. If c satisfies property P, then return c. Otherwise, return to
1351 Step 1.
1353 For example, to generate a number between 1 and n-1, inclusive,
1354 repeatedly generate integers between zero and 2^t - 1, inclusive,
1355 stopping at the first integer that falls within that interval.
1357 Recommendations on how to generate random bit strings are provided in
1358 [RFC4086].
1360 Appendix C. Why Compact Representation Works
1362 In the affine representation, the x-coordinate of the point P^i does
1363 not depend on the y-coordinate of the point P, for any non-negative
1364 exponent i and any point P. This fact can be seen as follows. When
1365 given only the x-coordinate of a point P, it is not possible to
1366 determine exactly what the y-coordinate is, but the y value will be a
1367 solution to the curve equation
1369 y^2 = x^3 + a*x + b (mod p).
1371 There are at most two distinct solutions y = w and y = -w mod p, and
1372 the point P must be either Q=(x,w) or Q^-1=(x,-w). Thus P^n is equal
1373 to either Q^n or (Q^-1)^n = (Q^n)^-1. These values have the same
1374 x-coordinate. Thus, the x-coordinate of a point P^i can be computed
1375 from the x-coordinate of a point P by computing one of the possible
1376 values of the y coordinate of P, then computing the ith power of P,
1377 and then ignoring the y-coordinate of that result.
1379 In general, it is possible to compute a square root modulo p by using
1380 Shanks' method [K1981v2]; simple methods exist for some values of p.
1381 When p = 3 (mod 4), the square roots of z mod p are w and -w mod p,
1382 where
1384 w = z ^ ((p+1)/4) (mod p);
1386 this observation is due to Lehmer [L1969]. When p satisfies this
1387 property, y can be computed from the curve equation, and either y = w
1388 or y = -w mod p, where
1390 w = (x^3 + a*x + b)^((p+1)/4) (mod p).
1392 Square roots modulo p only exist for a quadratic residue modulo p,
1393 [R1988]; if z is not a quadratic residue, then there is no number w
1394 such that w^2 = z (mod p). A simple way to verify that z is a
1395 quadratic residue after computing w is to verify that
1396 w * w = z (mod p). If this relation does not hold for the above
1397 equation, then the value x is not a valid x-coordinate for a valid
1398 elliptic curve point. This is an important consideration when ECDH
1399 is used with compact output; see Section 10.3.
1401 The primes used in the P-256, P-384, and P-521 curves described in
1402 [RFC4753] all have the property that p = 3 (mod 4).
1404 Appendix D. Example ECC Parameter Set
1406 For concreteness, we recall an elliptic curve defined by Solinas and
1407 Fu in [RFC4753] and referred to as P-256, which is believed to
1408 provide a 128-bit security level. We use the notation of
1409 Section 3.3, and express the generator in the affine coordinate
1410 representation g=(gx,gy), where the values gx and gy are in Fp.
1412 p: FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
1414 a: - 3
1416 b: 5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
1418 n: FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551
1420 gx: 6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
1422 gy: 4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
1424 Note that p can also be expressed as
1425 p = 2^(256)-2^(224)+2^(192)+2^(96)-1.
1427 Appendix E. Additive and multiplicative notation
1429 The early publications on elliptic curve cryptography used
1430 multiplicative notation, but most modern publications use additive
1431 notation. This section includes a table mapping between those two
1432 conventions. In this section, a and b are elements of an elliptic
1433 curve group, and N is an integer.
1435 +-------------------------+-----------------------+
1436 | Multiplicative Notation | Additive Notation |
1437 +-------------------------+-----------------------+
1438 | multiplication | addition |
1439 | a * b | a + b |
1440 | squaring | doubling |
1441 | a * a = a^2 | a + a = 2a |
1442 | exponentiation | scalar multiplication |
1443 | a^N = a * a * ... * a | Na = a + a + ... + a |
1444 | inverse | inverse |
1445 | a^-1 | -a |
1446 +-------------------------+-----------------------+
1448 Appendix F. Algorithms
1450 This section contains a pseudocode description of the elliptic curve
1451 group operation. Text that follows the symbol "//" are to be
1452 interpreted as comments rather than instructions.
1454 F.1. Affine Coordinates
1456 To an arbitrary pair of elliptic curve points P and Q specified by
1457 their affine coordinates P=(x1,y1) and Q=(x2,y2), the group operation
1458 assigns a third point R = P*Q with the coordinates (x3,y3). These
1459 coordinates are computed as follows:
1461 if P is (@,@),
1462 R = Q
1463 else if Q is (@,@),
1464 R = P
1465 else if P is not equal to Q and x1 is equal to x2,
1466 R = (@,@)
1467 else if P is not equal to Q and x1 is not equal to x2,
1468 x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 mod p and
1469 y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 mod p
1470 else if P is equal to Q and y1 is equal to 0,
1471 R = (@,@)
1472 else // P is equal to Q and y1 is not equal to 0
1473 x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 mod p and
1474 y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y mod p.
1476 From the first and second case, it follows that the point at infinity
1477 is the neutral element of this operation, which is its own inverse.
1479 From the curve equation it follows that for a given curve point P =
1480 (x,y) distinct from the point at infinity, (x,-y) also is a curve
1481 point, and from the third and the fifth case it follows that this is
1482 the inverse of P, P^-1.
1484 Note: The fifth and sixth case are known as "point squaring".
1486 F.2. Homogeneous Coordinates
1488 An elliptic curve point (x,y) (other than the point at infinity
1489 (@,@)) is equivalent to a point (X,Y,Z) in homogeneous coordinates
1490 (with X, Y, and Z in Fp and not all three being zero at once)
1491 whenever x=X/Z and y=Y/Z. "Homogenous coordinates" means that two
1492 triples (X,Y,Z) and (X',Y',Z') are regarded as "equal" (i.e.
1493 representing the same point) if there is some non-zero s in Fp such
1494 that X'=s*X, Y'=s*Y, and Z'=s*Z. The point at infinity, (@,@) is
1495 regarded as equivalent to the homogenous coordinates (0,1,0), i.e. it
1496 can be represented by any triple (0,Y,0) with non-zero Y in Fp.
1498 Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on the elliptic curve,
1499 and let u = Y2 * Z1 - Y1 * Z2 and v = X2 * Z1 - X1 * Z2.
1501 We observe that the points P1 and P2 are equal if and only if u and v
1502 are both equal to zero. Otherwise, if either P1 or P2 are equal to
1503 the point at infinity, v is zero and u is non-zero (but the converse
1504 implication does not hold).
1506 Then the product P3=(X3,Y3,Z3) = P1 * P2 is given by:
1508 if P1 is the point at infinity,
1509 P3 = P2
1510 else if P2 is the point at infinity,
1511 P3 = P1
1512 else if u is not equal to 0 but v is equal to 0,
1513 P3 = (0,1,0)
1514 else if both u and v are not equal to 0,
1515 X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3)
1516 Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3
1517 Z3 = v^3 * Z1 * Z2
1518 else // P2 equals P1, P3 = P1 * P1
1519 w = 3 * X1^2 + a * Z1^2
1520 X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1)
1521 Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3
1522 Z3 = 8 * (Y1 * Z1)^3
1524 It thus turns out that the point at infinity is the identity element
1525 and for P1=(X,Y,Z) not equal to this point at infinity, P2=(X,-Y,Z)
1526 represents P1^-1.
1528 Authors' Addresses
1530 David A. McGrew
1531 Cisco Systems
1532 510 McCarthy Blvd.
1533 Milpitas, CA 95035
1534 USA
1536 Phone: (408) 525 8651
1537 Email: mcgrew@cisco.com
1538 URI: http://www.mindspring.com/~dmcgrew/dam.htm
1540 Kevin M. Igoe
1541 National Security Agency
1542 Commercial Solutions Center
1543 United States of America
1545 Email: kmigoe@nsa.gov
1546 Margaret Salter
1547 National Security Agency
1548 9800 Savage Rd.
1549 Fort Meade, MD 20755-6709
1550 USA
1552 Email: msalter@restarea.ncsc.mil