idnits 2.17.00 (12 Aug 2021) /tmp/idnits42907/draft-mcgrew-fundamental-ecc-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** The document seems to lack a License Notice according IETF Trust Provisions of 28 Dec 2009, Section 6.b.ii or Provisions of 12 Sep 2009 Section 6.b -- however, there's a paragraph with a matching beginning. Boilerplate error? (You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Feb 2009 rather than one of the newer Notices. See https://trustee.ietf.org/license-info/.) 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 978 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 (October 26, 2009) is 4589 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: 1 error (**), 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 October 26, 2009 5 Expires: April 29, 2010 7 Fundamental Elliptic Curve Cryptography Algorithms 8 draft-mcgrew-fundamental-ecc-01.txt 10 Status of this Memo 12 This Internet-Draft is submitted to IETF in full conformance with the 13 provisions of BCP 78 and BCP 79. 15 Internet-Drafts are working documents of the Internet Engineering 16 Task Force (IETF), its areas, and its working groups. Note that 17 other groups may also distribute working documents as Internet- 18 Drafts. 20 Internet-Drafts are draft documents valid for a maximum of six months 21 and may be updated, replaced, or obsoleted by other documents at any 22 time. It is inappropriate to use Internet-Drafts as reference 23 material or to cite them other than as "work in progress." 25 The list of current Internet-Drafts can be accessed at 26 http://www.ietf.org/ietf/1id-abstracts.txt. 28 The list of Internet-Draft Shadow Directories can be accessed at 29 http://www.ietf.org/shadow.html. 31 This Internet-Draft will expire on April 29, 2010. 33 Copyright Notice 35 Copyright (c) 2009 IETF Trust and the persons identified as the 36 document authors. All rights reserved. 38 This document is subject to BCP 78 and the IETF Trust's Legal 39 Provisions Relating to IETF Documents in effect on the date of 40 publication of this document (http://trustee.ietf.org/license-info). 41 Please review these documents carefully, as they describe your rights 42 and restrictions with respect to this document. 44 Abstract 46 This note describes the fundamental algorithms of Elliptic Curve 47 Cryptography (ECC) as they are defined in some early references. 48 These descriptions may be useful to those who want to implement the 49 fundamental algorithms without using any of the specialized methods 50 that were developed in following years. Only elliptic curves defined 51 over fields of characteristic greater than three are in scope; these 52 curves are those used in Suite B. 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. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 6 62 3. Elliptic Curve Groups . . . . . . . . . . . . . . . . . . . . 8 63 3.1. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 9 64 3.2. Group Parameters . . . . . . . . . . . . . . . . . . . . . 10 65 3.2.1. Security . . . . . . . . . . . . . . . . . . . . . . . 10 66 4. Elliptic Curve Diffie-Hellman (ECDH) . . . . . . . . . . . . . 11 67 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 11 68 4.2. Compact Representation . . . . . . . . . . . . . . . . . . 11 69 5. Elliptic Curve ElGamal Signatures (ECES) . . . . . . . . . . . 13 70 5.1. Keypair Generation . . . . . . . . . . . . . . . . . . . . 13 71 5.2. Signature Creation . . . . . . . . . . . . . . . . . . . . 13 72 5.3. Signature Verification . . . . . . . . . . . . . . . . . . 14 73 5.4. Hash Functions . . . . . . . . . . . . . . . . . . . . . . 14 74 5.5. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 14 75 6. Abbreviated ECES Signatures (AECES) . . . . . . . . . . . . . 16 76 6.1. Keypair Generation . . . . . . . . . . . . . . . . . . . . 16 77 6.2. Signature Creation . . . . . . . . . . . . . . . . . . . . 16 78 6.3. Signature Verification . . . . . . . . . . . . . . . . . . 16 79 7. Interoperability . . . . . . . . . . . . . . . . . . . . . . . 18 80 7.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 81 7.2. ECES, AECES, and ECDSA . . . . . . . . . . . . . . . . . . 18 82 8. Intellectual Property . . . . . . . . . . . . . . . . . . . . 20 83 8.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . 20 84 9. Security Considerations . . . . . . . . . . . . . . . . . . . 21 85 9.1. Subgroups . . . . . . . . . . . . . . . . . . . . . . . . 21 86 9.2. Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . 22 87 9.3. Group Representation and Security . . . . . . . . . . . . 22 88 9.4. Signatures . . . . . . . . . . . . . . . . . . . . . . . . 22 89 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24 90 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 25 91 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 26 92 12.1. Normative References . . . . . . . . . . . . . . . . . . . 26 93 12.2. Informative References . . . . . . . . . . . . . . . . . . 27 94 Appendix A. Key Words . . . . . . . . . . . . . . . . . . . . . . 30 95 Appendix B. Random Number Generation . . . . . . . . . . . . . . 31 96 Appendix C. Example Elliptic Curve Group . . . . . . . . . . . . 32 97 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 33 99 1. Introduction 101 ECC is a public-key technology that offers performance advantages at 102 higher security levels. It includes an Elliptic Curve version of 103 Diffie-Hellman key exchange protocol [DH1976] and an Elliptic Curve 104 version of the ElGamal Signature Algorithm [E1985]. The elliptic 105 curve versions of these algorithms are referred to as ECDH and ECES, 106 respectively. The adoption of ECC has been slower than had been 107 anticipated, perhaps due to the lack of freely available normative 108 documents and uncertainty over intellectual property rights. 110 This note contains a description of the fundamental algorithms of ECC 111 over fields with characteristic greater than three, based directly on 112 original references. Its intent is to provide the Internet community 113 with a normative specification of the basic algorithms that predate 114 any specialized or optimized algorithms. 116 The rest of the note is organized as follows. Section 2.1, 117 Section 2.2, and Section 2.3 furnish the necessary terminology and 118 notation from modular arithmetic, group theory and the theory of 119 finite fields, respectively. Section 3 defines the groups based on 120 elliptic curves over finite fields of characteristic greater than 121 three. Section 4 and Section 5 present the fundamental ECDH and ECES 122 algorithms, respectively. Section 6 presents an abbreviated form of 123 ECES. The previous sections contain all of the normative text (the 124 text that defines the norm for implementations conforming to this 125 specification), and all of the following sections are purely 126 informative. Interoperability is discussed in Section 7. Section 8 127 reviews intellectual property issues. Section 9 summarizes security 128 considerations. Appendix B describes random number generation and 129 Appendix C provides an example of an Elliptic Curve group. 131 1.1. Conventions Used In This Document 133 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 134 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 135 document are to be interpreted as described in Appendix A. 137 2. Mathematical Background 139 This section reviews mathematical preliminaries and establishes 140 terminology and notation that is used below. 142 2.1. Modular Arithmetic 144 This section reviews modular arithmetic. Two integers x and y are 145 said to be congruent modulo n if x - y is an integer multiple of n. 147 Two integers x and y are coprime when their greatest common divisor 148 is 1; in this case, there is no third number z > 1 such that z 149 divides x and z divides y. 151 The set Zq = { 0, 1, 2, ..., q-1 } is closed under the operations of 152 modular addition, modular subtraction, modular multiplication, and 153 modular inverse. These operations are as follows. 155 For each pair of integers a and b in Zq, a + b mod q is equal to 156 a + b if a + b < q, and is equal to a + b - q otherwise. 158 For each pair of integers a and b in Zq, a - b mod q is equal to 159 a - b if a - b >= 0, and is equal to a - b + q otherwise. 161 For each pair of integers a and b in Zq, a * b mod q is equal to 162 the remainder of a * b divided by q. 164 For each integer x in Zq that is coprime with q, the inverse of x 165 modulo q is denoted as 1 / x mod q, and can be computed using the 166 extended euclidean algorithm (see Section 4.5.2 of [K1981v2], for 167 example). 169 Algorithms for these operations are well known; for instance, see 170 Chapter 4 of [K1981v2]. 172 2.2. Group Operations 174 This section establishes some terminology and notation for 175 mathematical groups, which is needed later on. Background references 176 abound; see [D1966], for example. 178 A group is a set of elements G together with an operation that 179 combines any two elements in G and returns a third element in G. The 180 operation is denoted as * and its application is denoted as a * b, 181 for any two elements a and b in G. The operation is associative, that 182 is, for all a, b and c in G, a * (b * c) is identical to (a * b) * c. 183 Repeated application of the group operation N times to the element a 184 is denoted as a^N, for any element a in G and any positive integer N. 186 That is, a^2, = a * a, a^3 = a * a * a, and so on. The associativity 187 of the group operation ensures that the computation of a^n is 188 unambiguous; any grouping of the terms gives the same result. 190 The above definition of a group operation uses multiplicative 191 notation. Sometimes an alternative called additive notation is used, 192 in which a * b is denoted as a + b, and a^N is denoted as N * a. In 193 multiplicative notation, g^N is called exponentiation, while the 194 equivalent operation in additive notation is called scalar 195 multiplication. In this document, multiplicative notation is used 196 throughout for consistency. 198 Every group has an special element called the identity element, which 199 we denote as e. For each element a in G, e * a = a * e = a. By 200 convention, a^0 is equal to the identity element for any a in G. 202 Every group element a has a unique inverse element b such that a * b 203 = b * a = e. The inverse of a is denoted as a^-1 in multiplicative 204 notation. (In additive notation, the inverse of a is denoted as -a.) 206 A cyclic group of order R is a group that contains the R elements 207 g, g^2, g^3, ..., g^R. The element g is called the generator of the 208 group. The element g^R is equal to the identity element e. Note 209 that g^X is equal to g^(X modulo R) for any non-negative integer X. 211 Given the element a of order N, and an integer i between 1 and N-1, 212 inclusive, the element a^i can be computed by the "square and 213 multiply" method outlined in Section 2.1 of [M1983] (see also Knuth, 214 Vol. 2, Section 4.6.3.), or other methods. 216 2.3. Finite Fields 218 This section establishes terminology and notation for finite fields 219 with prime characteristic. 221 When p is a prime number, then the set Zp, with the addition, 222 subtraction, multiplication and division operations, is a finite 223 field with characteristic p. Each nonzero element x in Zp has an 224 inverse 1/x. There is a one-to-one correspondence between the 225 integers between zero and p-1, inclusive, and the elements of the 226 field. The field is denoted as Fp. 228 Equations involving field elements do not explicitly denote the "mod 229 p" operation, but it is understood to be implicit. For example, the 230 statement that x, y, and z are in Fp and 232 z = x + y 234 is equivalent to the statement that x, y, and z are in the set { 0, 235 1, ..., p-1 } and 237 z = x + y mod p. 239 3. Elliptic Curve Groups 241 This note only covers elliptic curves over fields with characteristic 242 greater than three; these are the curves used in Suite B [SuiteB]. 243 For other fields, the definition of the elliptic curve group would be 244 different. 246 An elliptic curve over a field F is defined by the curve equation 248 y^2 = x^3 + a*x + b, 250 where x, y, a, and b are elements of the field Fp, and the 251 discriminant 16*(4*a^3 - 27*b^2) is nonzero [M1985]. A point on an 252 elliptic curve is a pair (x,y) of values in Fp that satisfy the curve 253 equation, such that x and y are both in Fp, or it is a special point 254 (@,@) that represents the identity element (which is called the 255 "point at infinity"). The order of an elliptic curve group is the 256 number of distinct points. 258 Two elliptic curve points (x1,y1) and (x2,y2) are equal whenever 259 x1=x2 and y1=y2, or when both points are the point at infinity. The 260 inverse of the point (x1,y1) is the point (x1,-y1). 262 The group operation associated with the elliptic curve group is as 263 follows [BC1989]. To an arbitrary pair of points P and Q specified 264 by their coordinates (x1,y1) and (x2,y2) respectively, the group 265 operation assigns a third point P*Q with the coordinates (x3,y3). 266 These coordinates are computed as follows 268 (x3,y3) = (@,@) when P is not equal to Q and x1 is equal to x2. 270 x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 and 271 y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 when P is not equal to Q and 272 x1 is not equal to x2. 274 (x3,y3) = (@,@) when P is equal to Q and y1 is equal to 0, 276 x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 and 277 y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y1 if P is equal to Q and y1 is 278 not equal to 0. 280 In the above equations, a, x1, x2, x3, y1, y2, and y3 are elements of 281 the field Fp; thus, computation of x3 and y3 in practice must reduce 282 the right-hand-side modulo p. 284 The representation of elliptic curve points as a pair of integers in 285 Zp is known as the affine coordinate representation. This 286 representation is suitable as an external data representation for 287 communicating or storing group elements, though the point at infinity 288 must be treated as a special case. 290 Some pairs of integers are not valid elliptic curve points. A valid 291 pair will satisfy the curve equation, while an invalid pair will not. 293 3.1. Homogeneous Coordinates 295 An alternative way to implement the group operation is to use 296 homogeneous coordinates [K1987] (see also [KMOV1991]). This method 297 is typically more efficient because it does not require a modular 298 inversion operation. 300 An elliptic curve point (x,y) (other than the point at infinity 301 (@,@)) is equivalent to a point (X,Y,Z) in homogeneous coordinates 302 whenever x=X/Z mod p and y=Y/Z mod p. 304 Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on an elliptic curve 305 and suppose that the points P1, P2 are not equal to (@,@), P1 is not 306 equal to P2, and P1 is not equal to P2^-1. Then the product 307 P3=(X3,Y3,Z3) = P1 * P2 is given by 309 X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3) mod p, 311 Y3 = z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) mod p, 313 Z3 = 8 * (Y1)^3 * (Z1)^3 mod p, 315 where u = Y2 * Z1 - Y1 * Z2 mod p and v = X2 * Z1 - X1 * Z2 mod p. 317 When the points P1 and P2 are equal, then (X1/Z1, Y1/Z1) is equal to 318 (X2/Z2, Y2/Z2), which is true if and only if u and v are both equal 319 to zero. 321 The product P3=(X3,Y3,Z3) = P1 * P1 is given by 323 X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1) mod p, 325 Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3 mod p, 327 Z3 = 8 * (Y1 * Z1)^3 mod p, 329 where w = 3 * X1^2 + a * Z1^2 mod p. In the above equations, a, u, 330 v, w, X1, X2, X3, Y1, Y2, Y3, Z1, Z2, and Z3 are integers in the set 331 Fp. 333 When converting from affine coordinates to homogeneous coordinates, 334 it is convenient to set Z to 1. When converting from homogeneous 335 coordinates to affine coordinates, it is necessary to perform a 336 modular inverse to find 1/Z mod p. 338 3.2. Group Parameters 340 An elliptic curve group over a finite field with characteristic 341 greater than three is completely specified by the following 342 parameters: 344 The prime number p that indicates the order of the field Fp. 346 The value a used in the curve equation. 348 The value b used in the curve equation. 350 The generator g of the group. 352 The order n of the group generated by g. 354 An example of an Elliptic Curve Group is provided in Appendix C. 356 Each elliptic curve point is associated with a particular group, i.e 357 a particular parameter set. Two elliptic curve groups are equal if 358 and only if each of the parameters in the set are equal. The 359 elliptic curve group operation is only defined between two points on 360 the same group. It is an error to apply the group operation to two 361 elements that are from different groups, or to apply the group 362 operation to a pair of coordinates that are not a valid point. See 363 Section 9.3 for further information. 365 3.2.1. Security 367 Security is highly dependent on the choice of these parameters. This 368 section gives normative guidance on acceptable choices. See also 369 Section 9 for informative guidance. 371 The order of the group generated by g MUST be divisible by a large 372 prime, in order to preclude easy solution of the discrete logarithm 373 problem [K1987] 375 With some parameter choices, the discrete log problem is 376 significantly easier to solve. This includes parameter sets in which 377 b = 0 and p = 3 (mod 4), and parameter sets in which a = 0 and 378 p = 2 (mod 3) [MOV1993]. These parameter choices are inferior for 379 cryptographic purposes and SHOULD NOT be used. 381 4. Elliptic Curve Diffie-Hellman (ECDH) 383 The Diffie-Hellman (DH) key exchange protocol [DH1976] allows two 384 parties communicating over an insecure channel to agree on a secret 385 key. It was originally defined in terms of operations in the 386 multiplicative group of a field with a large prime characteristic. 387 Massey [M1983] observed that it can be easily generalized so that it 388 is defined in terms of an arbitrary mathematical group. Miller 389 [M1985] and Koblitz [K1987] analyzed the DH protocol over an elliptic 390 curve group. We describe DH following the former reference. 392 Let G be a group, and g be a generator for that group, and let t 393 denote the order of G. The DH protocol runs as follows. Party A 394 chooses an exponent j between 1 and t-1 uniformly at random, computes 395 g^j and sends that element to B. Party B chooses an exponent k 396 between 1 and t-1 uniformly at random, computes g^k and sends that 397 element to A. Each party can compute g^(j*k); party A computes 398 (g^k)^j, and party B computes (g^j)^k. 400 See Appendix B regarding generation of random numbers. 402 4.1. Data Types 404 An ECDH private key z is an integer in Zt. 406 The corresponding ECDH public key Y is the group element, where Y = 407 g^z. Each public key is associated with a particular group, i.e. a 408 particular parameter set as per Section 3.2. 410 The shared secret computed by both parties is a group element. 412 Each run of the ECDH protocol is associated with a particular group, 413 and both of the public keys and the shared secret are elements of 414 that group. 416 4.2. Compact Representation 418 As described in the final paragraph of [M1985], the x-coordinate of 419 the shared secret value g^(j*k) is a suitable representative for the 420 entire point whenever exponentiation is used as a one-way function. 421 In the ECDH key exchange protocol, after the element g^(j*k) has been 422 computed, the x-coordinate of that value can be used as the shared 423 secret. We call this compact output. 425 Following [M1985] again, when compact output is used in ECDH, only 426 the x-coordinate of an elliptic curve point needs to be transmitted, 427 instead of both coordinates as in the typical affine coordinate 428 representation. We call this the compact representation. 430 ECDH can be used with or without compact output. Both parties in a 431 particular run of the ECDH protocol MUST use the same method. ECDH 432 can be used with or without compact representation. If compact 433 representation is used in a particular run of the ECDH protocol, then 434 compact output MUST be used as well. 436 5. Elliptic Curve ElGamal Signatures (ECES) 438 The ElGamal signature algorithm was introduced in 1984 [E1984a] 439 [E1984b] [E1985]. It is based on the discrete logarithm problem in 440 the multiplicative group of the integers modulo a large prime number. 441 It is straightforward to extend it to use an elliptic curve group. 442 In this section we recall a well-specified elliptic curve version of 443 the ElGamal Signature Algorithm, as described in [A1992] and 444 [MV1993]. This signature method is called Elliptic Curve ElGamal 445 Signatures (ECES). 447 The algorithm uses an elliptic curve group, as described in 448 Section 3.2, with prime field order p, curve equation parameters a 449 and b. We follow [MV1993] in describing the algorithms in terms of 450 mathematical groups, and denoting the generator as alpha, and its 451 order as n. 453 ECES uses a collision-resistant hash function, so that it can sign 454 messages of arbitrary length. We denote the hash function as h(). 455 Its input is a bit string of arbitrary length, and its output is an 456 integer between zero and n-1, inclusive. 458 ECES uses a function g() from the set of group elements to the set of 459 integers Zn. This function returns the x-coordinate of the affine 460 coordinate representation of the elliptic curve point. 462 5.1. Keypair Generation 464 The private key z is an integer between 0 and n - 1, inclusive, 465 generated uniformly at random. The public key is the group element 466 Q = alpha^z. 468 5.2. Signature Creation 470 To sign message m, using the private key z: 472 1. First, choose an integer k uniformly at random from the set of 473 all integers k in Zn that are coprime to n. (If n is a prime, 474 then choose an integer uniformly at random between 1 and n-1.) 475 (See Appendix B regarding random integers.) 477 2. Next, compute the group element r = alpha^k. 479 3. Finally, compute the integer s as 481 s = (h(m) + z * g(r)) / k (mod n). 483 4. If s is equal to zero, then the signature creation MUST be 484 repeated, starting at Step 1 and using a newly chosen k value. 486 The signature for message m is the ordered pair (r, s). Note that 487 the first component is a group element, and the second is a non- 488 negative integer. 490 5.3. Signature Verification 492 To verify the message m and the signature (r,s) using the public key 493 Q: 495 Compute the group element r^s * Q^(-g(r)). 497 Compute the group element alpha^h(m). 499 Verify that the two elements previously computed are the same. If 500 they are identical, then the signature and message pass the 501 verification; otherwise, they fail. 503 5.4. Hash Functions 505 Let H() denote a hash function whose output is a fixed-length bit 506 string. To use H in ECES, we define the mapping between that output 507 and the integers between zero and n-1; this realizes the function h() 508 described above. Given a bit string m, the function h(m) is computed 509 as follows: 511 1. H(m) is evaluated; the result is a fixed-length bit string. 513 2. Convert the resulting bit string to an integer i by treating its 514 leftmost (initial) bit as the most significant bit of i, and 515 treating its rightmost (final) bit as the least significant bit 516 of i. 518 3. After conversion, reduce i modulo n, where n is the group order. 520 5.5. Rationale 522 This subsection is not normative and is provided only as background 523 information. 525 The signature verification will pass whenever the signature is 526 properly generated, because 528 r^s * Q^(-g(r)) = alpha^(k*s - z*g(r)) = alpha^h(m). 530 The reason that the random variable k must be coprime with n is so 531 that 1/k mod n is defined. 533 A valid signature with s=0 leaks the secret key, since in that case a 534 = h(m) / g(r) mod n. We adopt Rivest's suggestion to avoid this 535 problem [R1992]. 537 As described in the final paragraph of [M1985], it is suitable to use 538 the x-coordinate of a particular elliptic curve point as a 539 representative for that point. This is what the function g() does. 541 6. Abbreviated ECES Signatures (AECES) 543 The ECES system is secure and efficient, but has signatures that are 544 slightly larger than they need to be. Koyama and Tsuruoka described 545 a signature system based on Elliptic Curve ElGamal, but with shorter 546 signatures [KT1994]. Their idea is to include only the x-coordinate 547 of the EC point in the signature, instead of both coordinates. 548 Menezes, Qu, and Vanstone independently developed the same idea, 549 which was the basis for the "Elliptic Curve Signature Scheme with 550 Appendix (ECSSA)" submission to the IEEE 1363 working group 551 [MQV1994]. 553 In this section we describe an Elliptic Curve Signature Scheme that 554 uses a single elliptic curve coordinate in the signature instead of 555 both coordinates. It is based on [KT1994] and [MQV1994], but with 556 the finite field inversion operation moved from the signature 557 operation to the verification operation, so that the signing 558 operation is more compatible with ECES. (See [AMV1990] and [A1992] 559 for a discussion of these alternatives; the security of the methods 560 is equivalent.) We refer to this scheme as Abbreviated ECES, or 561 AECES. 563 6.1. Keypair Generation 565 Keypairs are the same as for ECES and are as described in 566 Section 5.1. 568 6.2. Signature Creation 570 In this section we describe how to compute the signature for a 571 message m using the private key z. 573 Signature creation is as for ECES, with the following additional 574 step: 576 1. Let the integer s1 be equal to the x-coordinate of r. 578 The signature is the ordered pair (s1, s). Both signature components 579 are non-negative integers. 581 6.3. Signature Verification 583 Given the message m, the public key Q, and the signature (s1, s) 584 verification is as follows: 586 1. Compute the inverse of s modulo n. We denote this value as w. 588 2. Compute the non-negative integers u and v, where 590 u = w * h(m) mod n, and 592 v = w * s1 mod n. 594 3. Compute the elliptic curve point R' = alpha^u * Q^v 596 4. If the x-coordinate of R' is equal to s1, then the signature and 597 message pass the verification; otherwise, they fail. 599 7. Interoperability 601 The algorithms in this note can be used to interoperate with some 602 other ECC specifications. This section provides details for each 603 algorithm. 605 7.1. ECDH 607 Section 4 can be used with the Internet Key Exchange (IKE) versions 608 one [RFC2409] or two [RFC4306]. These algorithms are compatible with 609 the ECP groups for the defined by [RFC4753], [RFC2409], and 610 [RFC2412]. The group definition used in this protocol uses an affine 611 coordinate representation of the public key and uses neither the 612 compact output nor the compact representation of Section 4.2. Note 613 that some groups use a negative curve parameter "a" and express this 614 fact in the curve equation rather than in the parameter. The test 615 cases in Section 8 of [RFC4753] can be used to test an 616 implementation; these cases use the multiplicative notation, as does 617 this note. The KEi and KEr payloads are equal to g^i and g^r, 618 respectively, with 64 bits of encoding data prepended to them. 620 The algorithms in Section 4 can be used to interoperate with the IEEE 621 [P1363] and ANSI [X9.62] standards for ECDH based on fields of 622 characteristic greater than three. To use IEEE P1363 ECDH in a 623 manner that will interoperate with this specification, the following 624 options and parameter choices should be used: prime curves with a 625 cofactor of 1, the ECSVDP-DH primitive, and the Key Derivation 626 Function must be the "identity" function (equivalently, omit the KDF 627 step and output the shared secret value directly). 629 7.2. ECES, AECES, and ECDSA 631 The Digital Signature Algorithm (DSA) is based on the discrete 632 logarithm problem over the multiplicative subgroup of the finite 633 field large prime order [DSA1991][FIPS186]. The Elliptic Curve 634 Digital Signature Algorithm (ECDSA) [P1363] [X9.62] is an elliptic 635 curve version of DSA. 637 AECES can interoperate with the IEEE [P1363] and ANSI [X9.62] 638 standards for Elliptic Curve DSA (ECDSA) based on fields of 639 characteristic greater than three. 641 An ECES signature can be converted into an ECDSA or AECES signature 642 by discarding the y-coordinate from the elliptic curve point. 644 There is a strong correspondence between ECES signatures and ECDSA or 645 AECES signatures. In the notation of Section 5, an ECDSA (or AECES) 646 signature consists of the pair of integers (g(r), s), and signature 647 verification passes if and only if 649 A^(h(m)/s) * Q^(g(r)/s) = r, 651 where the equality of the elliptic curve elements is checked by 652 checking for the equality of their x-coordinates. For valid 653 signatures, (h(m)+a*r)/s mod q = k, and thus the two sides are equal. 654 An ECDSA (or AECES) signature contains only the x-coordinate g(r), 655 but this is sufficient to allow the signatures to be checked with the 656 above method. 658 Whenever the ECES signature (r, s) is valid for a particular message 659 m, and public key Q, then there is a valid AECES or ECDSA signature 660 (g(r), s) for the same message and public key. 662 Whenever an AECES or ECDSA signature (c, d) is valid for a particular 663 message m, and public key Q, then there is a valid ECES signature for 664 the same message and public key. This signature has the form ((c, 665 f(c)), d), or ((c, q-f(c)), d) where the function f takes as input an 666 integer in Zq and is defined as 668 f(x) = sqrt(x^3 + a*x + b) (mod q). 670 It is possible to compute the square root modulo q, for instance, by 671 using Shanks's method [K1987]. However, it is not as efficient to 672 convert an ECDSA signature (or an AECES signature) to an ECES 673 signature. 675 8. Intellectual Property 677 Concerns about intellectual property have slowed the adoption of ECC, 678 because a number of optimizations and specialized algorithms have 679 been patented in recent years. 681 All of the normative references for ECDH (as defined in Section 4) 682 were published during or before 1989, those for ECES were published 683 during or before 1993, and those for AECES were published during or 684 before October, 1994. All of the normative text for these algorithms 685 is based solely on their respective references. 687 8.1. Disclaimer 689 This document is not intended as legal advice. Readers are advised 690 to consult their own legal advisers if they would like a legal 691 interpretation of their rights. 693 The IETF policies and processes regarding intellectual property and 694 patents are outlined in [RFC3979] and [RFC4879] and at 695 https://datatracker.ietf.org/ipr/about/. 697 9. Security Considerations 699 The security level of an elliptic curve cryptosystem is determined by 700 the cryptanalytic algorithm that is the least expensive for an 701 attacker to implement. There are several algorithms to consider. 703 The Pohlig-Hellman method is a divide-and-conquer technique [PH1978]. 704 If the group order n can be factored as 706 n = q1 * q2 * ... * qz, 708 then the discrete log problem over the group can be solved by 709 independently solving a discrete log problem in groups of order q1, 710 q2, ..., qz, then combining the results using the Chinese remainder 711 theorem. The overall computational cost is dominated by that of the 712 discrete log problem in the subgroup with the largest order. 714 Shanks algorithm [K1981v3] computes a discrete logarithm in a group 715 of order n using O(sqrt(n)) operations and O(sqrt(n)) storage. The 716 Pollard rho algorithm [P1978] computes a discrete logarithm in a 717 group of order n using O(sqrt(n)) operations, with a negligible 718 amount of storage, and can be efficiently parallelized [VW1994]. 720 The Pollard lambda algorithm [P1978] can solve the discrete logarithm 721 problem using O(sqrt(w)) operations and O(log(w)) storage, when the 722 exponent belongs to a set of w elements. 724 The algorithms described above work in any group. There are 725 specialized algorithms that specifically target elliptic curve 726 groups. There are no subexponential algorithms against general 727 elliptic curve groups, though there are methods that target certain 728 special elliptic curve groups; see [MOV1993] and [FR1994]. 730 9.1. Subgroups 732 A group consisting of a nonempty set of elements S with associated 733 group operation * is a subgroup of the group with the set of elements 734 G, if the latter group uses the same group operation and S is a 735 subset of G. For each elliptic curve equation, there is an elliptic 736 curve group whose group order is equal to the order of the elliptic 737 curve; that is, there is a group that contains every point on the 738 curve. 740 The order m of the elliptic curve is divisible by the order n of the 741 group associated with the generator; that is, for each elliptic curve 742 group, m = n * c for some number c. The number c is called the 743 "cofactor" [P1363]. Each elliptic curve group (e.g. each parameter 744 set as in Section 3.2) is associated with a particular cofactor. 746 It is possible and desirable to use a cofactor equal to 1. 748 9.2. Diffie-Hellman 750 Note that the key exchange protocol as defined in Section 4 does not 751 protect against active attacks; Party A must use some method to 752 ensure that (g^k) originated with the intended communicant B, rather 753 than an attacker, and Party B must do the same with (g^j). 755 It is not sufficient to authenticate the shared secret g^(j*k), since 756 this leaves the protocol open to attacks that manipulate the public 757 keys. Instead, the values of the public keys g^x and g^y that are 758 exchanged should be directly authenticated. This is the strategy 759 used by protocols that build on Diffie-Hellman and which use end- 760 entity authentication to protect against active attacks, such as 761 OAKLEY [RFC2412] and the Internet Key Exchange [RFC2409][RFC4306]. 763 When the cofactor of a group is not equal to 1, there are a number of 764 attacks that are possible against ECDH. See [VW1996], [AV1996], and 765 [LL1997]. 767 9.3. Group Representation and Security 769 The elliptic curve group operation does not explicitly incorporate 770 the parameter b from the curve equation. This opens the possibility 771 that a malicious attacker could learn information about an ECDH 772 private key by submitting a bogus public key [BMM2000]. An attacker 773 can craft an elliptic curve group G' that has identical parameters to 774 a group G that is being used in an ECDH protocol, except that b is 775 different. An attacker can submit a point on G' into a run of the 776 ECDH protocol that is using group G, and gain information from the 777 fact that the group operations using the private key of the device 778 under attack are effectively taking place in G' instead of G. 780 This attack can gain useful information about an ECDH private key 781 that is associated with a static public key, that is, a public key 782 that is used in more than one run of the protocol. However, it does 783 not gain any useful information against ephemeral keys. 785 This sort of attack is thwarted if an ECDH implementation does not 786 assume that each pair of coordinates in Zp is actually a point on the 787 appropriate elliptic curve. 789 9.4. Signatures 791 Elliptic curve parameters should only be used if they come from a 792 trusted source; otherwise, some attacks are possible [AV1996], 793 [V1996]. 795 In principle, any collision-resistant hash function is suitable for 796 use in ECES or AECES. To facilitate interoperability, we recognize 797 the following hashes as suitable for use as the function H defined in 798 Section 5.4: 800 SHA-256, which has a 256-bit output. 802 SHA-384, which has a 384-bit output. 804 SHA-512, which has a 512-bit output. 806 All of these hash functions are defined in [FIPS180-2]. 808 The number of bits in the output of the hash used in ECES or AECES 809 should be equal or close to the number of bits needed to represent 810 the group order. 812 10. IANA Considerations 814 This note has no actions for IANA. This section should be removed by 815 the RFC editor before publication as an RFC. 817 11. Acknowledgements 819 The author expresses his thanks to the originators of elliptic curve 820 cryptography, whose work made this note possible, and all of the 821 reviewers, who provided valuable constructive feedback. 823 12. References 825 12.1. Normative References 827 [A1992] Anderson, J., "Response to the proposed DSS", 828 Communications of the ACM v.35 n.7 p.50-52, July 1992. 830 [AMV1990] Agnew, G., Mullin, R., and S. Vanstone, "Improved Digital 831 Signature Scheme based on Discrete Exponentiation", 832 Electronics Letters Vol. 26, No. 14, July, 1990. 834 [BC1989] Bender, A. and G. Castagnoli, "On the Implementation of 835 Elliptic Curve Cryptosystems", Advances in Cryptology - 836 CRYPTO '89 Proceedings Spinger Lecture Notes in Computer 837 Science (LNCS) volume 435, 1989. 839 [D1966] Deskins, W., "Abstract Algebra", MacMillan Company , 1966. 841 [DH1976] Diffie, W. and M. Hellman, "New Directions in 842 Cryptography", IEEE Transactions in Information 843 Theory IT-22, pp 644-654, 1976. 845 [E1984a] ElGamal, T., "Cryptography and logarithms over finite 846 fields", Stanford University UMI Order No. DA 8420519, 847 1984. 849 [E1984b] ElGamal, T., "Cryptography and logarithms over finite 850 fields", Advances in Cryptology - CRYPTO '84 851 Proceedings Springer Lecture Notes in Computer Science 852 (LNCS) volume 196, 1984. 854 [E1985] ElGamal, T., "A public key cryptosystem and a signature 855 scheme based on discrete logarithms", IEEE Transactions on 856 Information Theory Vol 30, No. 4, pp. 469-472, 1985. 858 [FR1994] Frey, G. and H. Ruck, "A remark concerning m-divisibility 859 and the discrete logarithm in the divisor class group of 860 curves.", Mathematics of Computation Vol. 62, No. 206, pp. 861 865-874, 1994. 863 [K1981v2] Knuth, D., "The Art of Computer Programming, Vol. 2: 864 Seminumerical Algorithms", Addison Wesley , 1981. 866 [K1987] Koblitz, N., "Elliptic Curve Cryptosystems", Mathematics 867 of Computation Vol. 48, 1987, 203-209, 1987. 869 [KT1994] Koyama, K. and Y. Tsuruoka, "Digital signature system 870 based on elliptic curve and signer device and verifier 871 device for said system", Japanese Unexamined Patent 872 Application Publication H6-43809, February 18, 1994. 874 [M1983] Massey, J., "Logarithms in finite cyclic groups - 875 cryptographic issues", Proceedings of the 4th Symposium on 876 Information Theory , 1983. 878 [M1985] Miller, V., "Use of elliptic curves in cryptography", 879 Advances in Cryptology - CRYPTO '85 Proceedings Springer 880 Lecture Notes in Computer Science (LNCS) volume 218, 1985. 882 [MOV1993] Menezes, A., Vanstone, S., and T. Okamoto, "Reducing 883 Elliptic Curve Logarithms to Logarithms in a Finite 884 Field", IEEE Transactions on Information Theory Vol 39, 885 No. 5, pp. 1639-1646, September, 1993. 887 [MQV1994] Menezes, A., Qu, M., and S. Vanstone, "Submission to the 888 IEEE P1363 Working Group (Part 6: Elliptic Curve Systems, 889 Draft 2)", Working Document , October, 1994. 891 [MV1993] Menezes, A. and S. Vanstone, "Elliptic Curve Cryptosystems 892 and Their Implementation", Journal of Cryptology Volume 6, 893 No. 4, pp209-224, 1993. 895 [R1992] Rivest, R., "Response to the proposed DSS", Communications 896 of the ACM v.35 n.7 p.41-47., July 1992. 898 12.2. Informative References 900 [AV1996] Anderson, R. and S. Vaudenay, "Minding Your P's and Q's", 901 Advances in Cryptology - ASIACRYPT '96 Proceedings Spinger 902 Lecture Notes in Computer Science (LNCS) volume 1163, 903 1996. 905 [BMM2000] Biehl, I., Meyer, B., and V. Muller, "Differential fault 906 analysis on elliptic curve cryptosystems", Advances in 907 Cryptology - CRYPTO 2000 Proceedings Spinger Lecture Notes 908 in Computer Science (LNCS) volume 1880, 2000. 910 [DSA1991] "DIGITAL SIGNATURE STANDARD", Federal Register Vol. 56, 911 August 1991. 913 [FIPS180-2] 914 "SECURE HASH STANDARD", Federal Information Processing 915 Standard (FIPS) 180-2, August 2002. 917 [FIPS186] "DIGITAL SIGNATURE STANDARD", Federal Information 918 Processing Standard FIPS-186, 1994. 920 [K1981v3] Knuth, D., "The Art of Computer Programming, Vol. 3: 921 Sorting and Searching", Addison Wesley , 1981. 923 [KMOV1991] 924 Koyama, K., Menezes, A., Vanstone, S., and T. Okamoto, 925 "New Public-Key Schemes Based on Elliptic Curves over the 926 Ring Zn", Advances in Cryptology - CRYPTO '91 927 Proceedings Spinger Lecture Notes in Computer Science 928 (LNCS) volume 576, 1991. 930 [LL1997] Lim, C. and P. Lee, "A Key Recovery Attack on Discrete 931 Log-based Schemes Using a Prime Order Subgroup", Advances 932 in Cryptology - CRYPTO '97 Proceedings Spinger Lecture 933 Notes in Computer Science (LNCS) volume 1294, 1997. 935 [P1363] "Standard Specifications for Public Key Cryptography", 936 Institute of Electric and Electronic Engineers 937 (IEEE) P1363, 2000. 939 [P1978] Pollard, J., "Monte Carlo methods for index computation 940 mod p", Mathematics of Computation Vol. 32, 1978. 942 [PH1978] Pohlig, S. and M. Hellman, "An Improved Algorithm for 943 Computing Logarithms over GF(p) and its Cryptographic 944 Significance", IEEE Transactions on Information Theory Vol 945 24, pp. 106-110, 1978. 947 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 948 Requirement Levels", BCP 14, RFC 2119, March 1997. 950 [RFC2409] Harkins, D. and D. Carrel, "The Internet Key Exchange 951 (IKE)", RFC 2409, November 1998. 953 [RFC2412] Orman, H., "The OAKLEY Key Determination Protocol", 954 RFC 2412, November 1998. 956 [RFC3979] Bradner, S., "Intellectual Property Rights in IETF 957 Technology", BCP 79, RFC 3979, March 2005. 959 [RFC4306] Kaufman, C., "Internet Key Exchange (IKEv2) Protocol", 960 RFC 4306, December 2005. 962 [RFC4753] Fu, D. and J. Solinas, "ECP Groups For IKE and IKEv2", 963 RFC 4753, January 2007. 965 [RFC4879] Narten, T., "Clarification of the Third Party Disclosure 966 Procedure in RFC 3979", BCP 79, RFC 4879, April 2007. 968 [SuiteB] "NSA Suite B Cryptography", Web Page http://www.nsa.gov/ 969 ia/programs/suiteb_cryptography/index.shtml. 971 [V1996] Vaudenay, S., "Hidden Collisions on DSS", Advances in 972 Cryptology - CRYPTO '96 Proceedings Spinger Lecture Notes 973 in Computer Science (LNCS) volume 1109, 1996. 975 [VW1994] van Oorschot, P. and M. Wiener, "Parallel Collision Search 976 with Application to Hash Functions and Discrete 977 Logarithms", Proceedings of the 2nd ACM Conference on 978 Computer and communications security pp. 210-218, 1994. 980 [VW1996] van Oorschot, P. and M. Wiener, "On Diffie-Hellman key 981 agreement with short exponents", Advances in Cryptology - 982 EUROCRYPT '96 Proceedings Spinger Lecture Notes in 983 Computer Science (LNCS) volume 1070, 1996. 985 [X9.62] "Public Key Cryptography for the Financial Services 986 Industry: The Elliptic Curve Digital Signature Algorithm 987 (ECDSA)", American National Standards Institute (ANSI) 988 X9.62. 990 Appendix A. Key Words 992 The definitions of these key words are quoted from [RFC2119] and are 993 commonly used in Internet standards. They are reproduced in this 994 note in order to avoid a normative reference from after 1994. 996 1. MUST - This word, or the terms "REQUIRED" or "SHALL", mean that 997 the definition is an absolute requirement of the specification. 999 2. MUST NOT - This phrase, or the phrase "SHALL NOT", mean that the 1000 definition is an absolute prohibition of the specification. 1002 3. SHOULD - This word, or the adjective "RECOMMENDED", mean that 1003 there may exist valid reasons in particular circumstances to 1004 ignore a particular item, but the full implications must be 1005 understood and carefully weighed before choosing a different 1006 course. 1008 4. SHOULD NOT - This phrase, or the phrase "NOT RECOMMENDED" mean 1009 that there may exist valid reasons in particular circumstances 1010 when the particular behavior is acceptable or even useful, but 1011 the full implications should be understood and the case carefully 1012 weighed before implementing any behavior described with this 1013 label. 1015 5. MAY - This word, or the adjective "OPTIONAL", mean that an item 1016 is truly optional. One vendor may choose to include the item 1017 because a particular marketplace requires it or because the 1018 vendor feels that it enhances the product while another vendor 1019 may omit the same item. An implementation which does not include 1020 a particular option MUST be prepared to interoperate with another 1021 implementation which does include the option, though perhaps with 1022 reduced functionality. In the same vein an implementation which 1023 does include a particular option MUST be prepared to interoperate 1024 with another implementation which does not include the option 1025 (except, of course, for the feature the option provides.) 1027 Appendix B. Random Number Generation 1029 It is easy to generate an integer uniformly at random between zero 1030 and 2^t -1, inclusive, for some positive integer t. Generate a 1031 random bit string that contains exactly t bits, and then convert the 1032 bit string to a non-negative integer by treating the bits as the 1033 coefficients in a base-two expansion of an integer. 1035 It is sometimes necessary to generate an integer r uniformly at 1036 random so that r satisfies a certain property P, for example, lying 1037 within a certain interval. A simple way to do this is with the 1038 rejection method: 1040 1. Generate a candidate number c uniformly at random from a set that 1041 includes all numbers that satisfy property P (plus some other 1042 numbers, preferably not too many) 1044 2. If c satisfies property P, then return c. Otherwise, return to 1045 Step 1. 1047 For example, to generate a number between 1 and n-1, inclusive, 1048 repeatedly generate integers between zero and 2^t - 1, inclusive, 1049 stopping at the first integer that falls within that interval. 1051 Appendix C. Example Elliptic Curve Group 1053 For concreteness, we recall an elliptic curve defined by Solinas and 1054 Yu in [RFC4753] and referred to as P-256, which is believed to 1055 provide a 128-bit security level. We use the notation of 1056 Section 3.2, and express the generator in the affine coordinate 1057 representation g=(gx,gy), where the values gx and gy are in Fp. 1059 p: FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF 1061 a: - 3 1063 b: 5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B 1065 n: FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551 1067 gx: 6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296 1069 gy: 4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5 1071 Note that p can also be expressed as 1073 p = 2^(256)-2^(224)+2^(192)+2^(96)-1. 1075 Author's Address 1077 David A. McGrew 1078 Cisco Systems 1079 510 McCarthy Blvd. 1080 Milpitas, CA 95035 1081 US 1083 Phone: (408) 525 8651 1084 Email: mcgrew@cisco.com 1085 URI: http://www.mindspring.com/~dmcgrew/dam.htm