idnits 2.17.00 (12 Aug 2021) /tmp/idnits44292/draft-mcgrew-fundamental-ecc-00.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 -- The document date (July 6, 2009) is 4701 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 (~~), 1 warning (==), 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 July 6, 2009 5 Expires: January 7, 2010 7 Fundamental Elliptic Curve Cryptography Algorithms 8 draft-mcgrew-fundamental-ecc-00.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 January 7, 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 based 51 on fields of character greater than three are in scope. 53 Table of Contents 55 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 56 2. Mathematical Background . . . . . . . . . . . . . . . . . . . 5 57 2.1. Modular Arithmetic . . . . . . . . . . . . . . . . . . . . 5 58 2.2. Group Operations . . . . . . . . . . . . . . . . . . . . . 5 59 2.3. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 6 60 3. Elliptic Curve Groups . . . . . . . . . . . . . . . . . . . . 7 61 3.1. Homogenous Coordinates . . . . . . . . . . . . . . . . . . 8 62 3.2. Group Parameters . . . . . . . . . . . . . . . . . . . . . 8 63 3.2.1. Security . . . . . . . . . . . . . . . . . . . . . . . 9 64 4. Elliptic Curve Diffie-Hellman (ECDH) . . . . . . . . . . . . . 10 65 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 10 66 4.2. Compact Representation . . . . . . . . . . . . . . . . . . 10 67 5. Elliptic Curve ElGamal Signatures (ECES) . . . . . . . . . . . 12 68 5.1. Keypair Generation . . . . . . . . . . . . . . . . . . . . 12 69 5.2. Signature Creation . . . . . . . . . . . . . . . . . . . . 12 70 5.3. Signature Verification . . . . . . . . . . . . . . . . . . 13 71 5.4. Hash Functions . . . . . . . . . . . . . . . . . . . . . . 13 72 5.5. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 13 73 6. Abbreviated ECES Signatures (AECES) . . . . . . . . . . . . . 15 74 6.1. Keypair Generation . . . . . . . . . . . . . . . . . . . . 15 75 6.2. Signature Creation . . . . . . . . . . . . . . . . . . . . 15 76 6.3. Signature Verification . . . . . . . . . . . . . . . . . . 15 77 7. Interoperability . . . . . . . . . . . . . . . . . . . . . . . 17 78 7.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 79 7.2. ECES, AECES, and ECDSA . . . . . . . . . . . . . . . . . . 17 80 8. Intellectual Property . . . . . . . . . . . . . . . . . . . . 19 81 8.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . 19 82 9. Security Considerations . . . . . . . . . . . . . . . . . . . 20 83 9.1. Subgroups . . . . . . . . . . . . . . . . . . . . . . . . 20 84 9.2. Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . 21 85 9.3. Group Representation and Security . . . . . . . . . . . . 21 86 9.4. Signatures . . . . . . . . . . . . . . . . . . . . . . . . 22 87 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23 88 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 24 89 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 25 90 12.1. Normative References . . . . . . . . . . . . . . . . . . . 25 91 12.2. Informative References . . . . . . . . . . . . . . . . . . 26 92 Appendix A. Random Number Generation . . . . . . . . . . . . . . 29 93 Appendix B. Example Elliptic Curve Group . . . . . . . . . . . . 30 94 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 31 96 1. Introduction 98 ECC is a public-key technology that offers performance advantages at 99 higher security levels. It includes an Elliptic Curve version of 100 Diffie-Hellman key exchange protocol [DH1976] and an Elliptic Curve 101 version of the ElGamal Signature Algorithm [E1985]. The elliptic 102 curve versions of these algorithms are referred to as ECDH and ECES, 103 respectively. The adoption of ECC has been slower than had been 104 anticipated, perhaps due to the lack of freely available normative 105 documents and uncertainty over intellectual property rights. 107 This note contains a description of the fundamental algorithms of ECC 108 over fields with characteristic greater than three, based directly on 109 original references. Its intent is to provide the Internet community 110 with a normative specification of the basic algorithms that predate 111 any specialized or optimized algorithms. 113 The rest of the note is organized as follows. Section 2.1, 114 Section 2.2, and Section 2.3 furnish the necessary terminology and 115 notation from modular arithmetic, group theory and the theory of 116 finite fields, respectively. Section 3 defines the groups based on 117 elliptic curves over finite fields of characteristic greater than 118 three. Section 4 and Section 5 present the fundamental ECDH and ECES 119 algorithms, respectively. Section 6 presents an abbreviated form of 120 ECES. The previous sections contain all of the normative text (the 121 text that defines the norm for implementations conforming to this 122 specification), and all of the following sections are purely 123 informative. Interoperability is discussed in Section 7. Section 8 124 reviews intellectual property issues. Section 9 summarizes security 125 considerations. Appendix A describes random number generation and 126 Appendix B provides an example of an Elliptic Curve group. 128 2. Mathematical Background 130 This section reviews mathematical preliminaries and establishes 131 terminology and notation that is used below. 133 2.1. Modular Arithmetic 135 This section reviews modular arithmetic. Two integers x and y are 136 said to be congruent modulo n if x - y is an integer multiple of n. 138 Two integers x and y are coprime when their greatest common divisor 139 is 1; in this case, there is no third number z such that z divides x 140 and z divides y. 142 The set Zp = { 0, 1, 2, ..., p-1 } is closed under the operations of 143 modular addition, modular subtraction, modular multiplication, and 144 modular inverse. These operations are as follows. 146 For each pair of integers a and b in Zp, a + b mod p is equal to 147 a + b if a + b < p, and is equal to a + b - p otherwise. 149 For each pair of integers a and b in Zp, a - b mod p is equal to 150 a - b if a + b > p, and is equal to a + b otherwise. 152 For each pair of integers a and b in Zp, a * b mod p is equal to 153 the remainder of a * b divided by p. 155 For each integer x in Zp that is coprime with p, the inverse of x 156 modulo p is denoted as 1 / x mod p, and can be computed using the 157 extended euclidean algorithm (see Section 4.5.2 of [K1981v2], for 158 example). 160 Algorithms for these operations are well known; for instance, see 161 Chapter 4 of [K1981v2]. 163 2.2. Group Operations 165 This section establishes some terminology and notation for 166 mathematical groups, which is needed later on. Background references 167 abound; see [D1966], for example. 169 A group is a set of elements G and an associated operation that 170 combines any two elements in G and returns a third element in G. The 171 operation is denoted as * and its application is denoted as a * b, 172 for any two elements a and b in G. Repeated application of the group 173 operation n times to the element a is denoted as a^N, for any element 174 a in G and any positive integer N. That is, a^2, = a * a, 175 a^3 = a * a * a, and so on. 177 The above definition of a group operation uses multiplicative 178 notation. Sometimes an alternative called additive notation is used, 179 in which a * b is denoted as a + b, and a^N is denoted as N * a. In 180 multiplicative notation, g^N is called exponentiation, while the 181 equivalent operation in additive notation is called scalar 182 multiplication. In this document, multiplicative notation is used 183 throughout for consistency. 185 Every group has an special element called the identity element, which 186 we denote as e. For each element a in G, e * a = a * e = a. By 187 convention, a^0 is equal to the identity element for any a in G. 189 A cyclic group of order R is a group that contains the R elements 190 g, g^2, g^3, ..., g^R. The element g is called the generator of the 191 group. The element g^R is equal to the identity element e. Note 192 that g^X is equal to g^(X modulo R) for any non-negative integer X. 194 Given the element a of order N, and an integer i between 1 and N-1, 195 inclusive, the element a^i can be computed by the "square and 196 multiply" method outlined in Section 2.1 of [M1983] (see also Knuth, 197 Vol. 2, Section 4.6.3.), or other methods. 199 2.3. Finite Fields 201 This section establishes terminology and notation for finite fields 202 with prime characteristic. 204 When p is a prime number, then the set Zp, with the associated 205 addition, subtraction, multiplication and division operations, is a 206 finite field with character p. There is a one-to-one correspondence 207 between the integers between zero and p-1 and the elements of the 208 field. The field is denoted as Fp. 210 Equations involving field elements do not include the "mod p" 211 operation, but it is understood to be implicit. For example, the 212 statement that x, y, and z are in Fp and 214 z = x + y 216 is equivalent to the statement that x, y, and z are in Zp and 218 z = x + y mod p. 220 3. Elliptic Curve Groups 222 This note only covers elliptic curves over fields with characteristic 223 greater than three. For other fields, the definition of the elliptic 224 curve group would be different. 226 An elliptic curve over a field F is defined by the curve equation 228 y^2 = x^3 + a*x + b, 230 where x, y, a, and b are elements of the field Fp [M1985]. A point 231 on an elliptic curve is a pair (x,y) of values in Fp that satisfy the 232 curve equation, such that x and y are both in Fp, or it is a special 233 point (@,@) that represents the identity element (which is called the 234 "point at infinity"). The order of an elliptic curve group is the 235 number of distinct points. 237 Two elliptic curve points (x1,y1) and (x2,y2) are equal whenever 238 x1=x2 and y1=y2, or when both points are the point at infinity. 240 The group operation associated with the elliptic curve group is as 241 follows [BC1989]. To an arbitrary pair of points P and Q specified 242 by their coordinates (x1,y1) and (x2,y2) respectively, the group 243 operation assigns a third point P*Q with the coordinates (x3,y3). 244 These coordinates are computed as follows 246 (x3,y3) = (@,@) when P is not equal to Q and x1 is equal to x2. 248 x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 and 249 y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 when P is not equal to Q and 250 x1 is not equal to x2. 252 (x3,y3) = (@,@) when P is equal to Q, P is equal to (0,0) and P is 253 an element of the group. 255 x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 and 256 y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y1 if P is equal to Q. 258 In the above equations, a, x1, x2, x3, y1, y2, and y3 are elements of 259 the field Fp; thus, computation of x3 and y3 in practice use a "mod 260 p" operation. 262 The representation of elliptic curve points as a pair of integers in 263 Zp is known as the affine coordinate representation. This 264 representation is suitable as an external data representation for 265 communicating or storing group elements, though the point at infinity 266 must be treated as a special case. 268 Some pairs of integers are not valid elliptic curve points. A valid 269 pair will satisfy the curve equation, while an invalid pair will not. 271 3.1. Homogenous Coordinates 273 An alternative way to implement the group operation is to use 274 homogeneous coordinates [K1987] (see also [KMOV1991]). This method 275 is typically more efficient because it does not require a modular 276 inverse operation. 278 An elliptic curve point (x,y) is equivalent to a point (X,Y,Z) in 279 homogeneous coordinates whenever x=X/Z and y=Y/Z. 281 Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on an elliptic curve 282 and suppose that the points P1, P2 are not equal to (@,@), P1 is not 283 equal to P2, and P1 is not equal to -P2. Then the product 284 P3=(X3,Y3,Z3) = P1 * P2 is given by 286 X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3), 288 Y3 = z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3), 290 Z3 = 8 * (Y1)^3 * (Z1)^3, 292 where u = Y2 * Z1 - Y1 * Z2 and v = X2 * Z1 - X1 * Z2. 294 The product P3=(X3,Y3,Z3) = P1 * P1 is given by 296 X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1), 298 Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3, 300 Z3 = 8 * (Y1 * Z1)^3. 302 In the above equations, a, u, v, w, X1, X2, X3, Y1, Y2, Y3, Z1, Z2, 303 and Z3 are elements of the field Fp; thus, computation of X3, Y3, and 304 Z3 in practice use a "mod p" operation. 306 When converting from affine coordinates to homogeneous coordinates, 307 it is convenient to set Z to 1. When converting from homogeneous 308 coordinates to affine coordinates, it is necessary to perform a 309 modular inverse to find 1/Z mod p. 311 3.2. Group Parameters 313 An elliptic curve group over a finite field with characteristic 314 greater than three is completely specified by the following 315 parameters: 317 The prime number p that indicates the order of the field Fp. 319 The value a used in the curve equation. 321 The value b used in the curve equation. 323 The generator g of the group. 325 The order n of the group generated by g. 327 An example of an Elliptic Curve Group is provided in Appendix B. 329 Each elliptic curve point is associated with with a particular group, 330 i.e a particular parameter set. Two elliptic curve groups are equal 331 if and only if each of the parameters in the set are equal. The 332 elliptic curve group operation is only defined between two points on 333 the same group. It is an error to apply the group operation to two 334 elements that are from different groups, or to apply the group 335 operation to a pair of coordinates that are not a valid point. See 336 Section 9.3 for further information. 338 3.2.1. Security 340 Security is highly dependent on the choice of these parameters. This 341 section gives normative guidance on acceptable choices. See also 342 Section 9 for more information. 344 The order of the group generated by g should be divisible by a large 345 prime, in order to preclude easy solution of the discrete logarithm 346 problem [K1987] 348 With some parameter choices, the discrete log problem is 349 significantly easier to solve. This includes parameter sets in which 350 b = 0 and p = 3 (mod 4), and parameter sets in which a = 0 and 351 p = 2 (mod 3) [MOV1993]. These parameter choices are inferior for 352 cryptographic purposes and should not be used. 354 4. Elliptic Curve Diffie-Hellman (ECDH) 356 The Diffie-Hellman (DH) key exchange protocol [DH1976] allows two 357 parties communicating over an insecure channel to agree on a secret 358 key. It was originally defined in terms of operations in the 359 multiplicative group of a field with a large prime characteristic. 360 Massey [M1983] observed that it can be easily generalized so that it 361 is defined in terms of an arbitrary mathematical group. Miller 362 [M1985] and Koblitz [K1987] analyzed the DH protocol over an elliptic 363 curve group. We describe DH following the former reference. 365 Let G be a group, and g be a generator for that group, and let t 366 denote the order of G. The DH protocol runs as follows. Party A 367 chooses an exponent j between 1 and t-1 uniformly at random, computes 368 g^j and sends that element to B. Party B chooses an exponent k 369 between 1 and t-1 uniformly at random, computes g^k and sends that 370 element to A. Each party can compute g^(j*k); party A computes 371 (g^k)^j, and party B computes (g^j)^k. 373 See Appendix A regarding generation of random numbers. 375 4.1. Data Types 377 An ECDH private key a is an integer in Zt. 379 The corresponding ECDH public key Y is group element, where Y = g^a. 380 Each public key is associated with a particular group, i.e. a 381 particular parameter set as per Section 3.2. 383 The shared secret computed by both parties is a group element. 385 Each run of the ECDH protocol is associated with a particular group, 386 and both of the public keys and the shared secret are elements of 387 that group. 389 4.2. Compact Representation 391 As described in the final paragraph of [M1985], the x-coordinate of 392 the shared secret value g^(j*k) is a suitable representative for the 393 entire point whenever exponentiation is used as a one-way function. 394 In the ECDH key exchange protocol, after the element g^(j*k) has been 395 computed, the x-coordinate of that value can be used as the shared 396 secret. We call this compact output. 398 Following [M1985] again, when compact output is used in ECDH, only 399 the x-coordinate of an elliptic curve point needs to be transmitted, 400 instead of both coordinates as in the typical affine coordinate 401 representation. We call this the compact representation. 403 ECDH can be used with or without compact output. Both parties in a 404 particular run of the ECDH protocol must use the same method. ECDH 405 can be used with or without compact representation. If compact 406 representation is used in a particular run of the ECDH protocol, then 407 compact output must be used as well. 409 5. Elliptic Curve ElGamal Signatures (ECES) 411 The ElGamal signature algorithm was introduced in 1984 [E1984a] 412 [E1984b] [E1985]. It is based on the discrete logarithm problem in 413 the multiplicative group of the integers modulo a large prime number. 414 It is straightforward to extended it to use an elliptic curve group. 415 In this section we recall a well-specified elliptic curve version of 416 the ElGamal Signature Algorithm, as described in [A1992] and 417 [MV1993]. This signature method is called Elliptic Curve ElGamal 418 Signatures (ECES). 420 The algorithm uses an elliptic curve group, as described in 421 Section 3.2. We denote the generator as alpha, and the order of the 422 generator as n. We follow [MV1993] in describing the algorithms in 423 terms of mathematical groups. 425 ECES uses a collision-resistant hash function, so that it can sign 426 messages of arbitrary length. We denote the hash function as h(). 427 Its input is a bit string of arbitrary length, and its output is an 428 integer between zero and n-1, inclusive. 430 ECES uses a function g() from the set of group elements to the set of 431 integers Zn. This function returns the x-coordinate of the affine 432 coordinate representation of the elliptic curve point. 434 5.1. Keypair Generation 436 The private key a is an integer between 0 and n - 1, inclusive, 437 generated uniformly at random. The public key is the group element 438 Q = alpha^a. 440 5.2. Signature Creation 442 To sign message m, using the private key a: 444 1. First, choose an integer k uniformly at random from the set of 445 all integers k in Zn that are coprime to n. (If n is a prime, 446 then choose an integer uniformly at random between 1 and n-1.) 447 (See Appendix A regarding random integers.) 449 2. Next, compute the group element r = alpha^k. 451 3. Finally, compute the integer s as 453 s = (h(m) + a * g(r)) / k (mod n). 455 4. If s is equal to zero, then the signature creation must be 456 repeated, starting at Step 1 and using a newly chosen k value. 458 The signature for message m is the ordered pair (r, s). Note that 459 the first component is a group element, and the second is a non- 460 negative integer. 462 5.3. Signature Verification 464 To verify the message m and the signature (r,s) using the public key 465 Q: 467 Compute the group element r^s * Q^(-g(r)). 469 Compute the group element alpha^h(m). 471 Verify that the two elements previously computed are the same. If 472 they are identical, then the signature and message pass the 473 verification; otherwise, they fail. 475 5.4. Hash Functions 477 Let H() denote a hash function whose output is a fixed-length bit 478 string. To use H in ECES, we define the mapping between that output 479 and the integers between zero and n-1; this realizes the function h() 480 described above. Given a bit string m, the function h(m) is computed 481 as follows: 483 1. H(m) is evaluated; the result is a fixed-length bit string. 485 2. Convert the resulting bit string to an integer i by treating its 486 leftmost (initial) bit as the most significant bit of i, and 487 treating its rightmost (final) bit as the least significant bit 488 of i. 490 3. After conversion, reduce i modulo n, where n is the group order. 492 5.5. Rationale 494 This subsection is not normative and is provided only as background 495 information. 497 The signature verification will pass whenever the signature is 498 properly generated, because 500 r^s * Q^(-g(r)) = alpha^(k*s - a*g(r)) = alpha^h(m). 502 The reason that the random variable k must be coprime with n is so 503 that 1/k mod n is defined. 505 A valid signature with s=0 leaks the secret key, since in that case a 506 = h(m) / g(r) mod n. We adopt Rivest's suggestion to avoid this 507 problem [R1992]. 509 As described in the final paragraph of [M1985], for it is suitable to 510 use the x-coordinate of a particular elliptic curve point as a 511 representative for that point. This is what the function g() does. 513 6. Abbreviated ECES Signatures (AECES) 515 The ECES system is secure and efficient, but has signatures that are 516 slightly larger than they need to be. Koyama and Tsuruoka described 517 a signature system based on Elliptic Curve ElGamal, but with shorter 518 signatures [KT1994]. Their idea is to include only the x-coordinate 519 of the EC point in the signature, instead of both coordinates. 520 Menezes, Qu, and Vanstone independently developed the same idea, 521 which was the basis for the "Elliptic Curve Signature Scheme with 522 Appendix (ECSSA)" submission to the IEEE 1363 working group 523 [MQV1994]. 525 In this section we describe an Elliptic Curve Signature Scheme that 526 hash a single elliptic curve coordinate in the signature instead of 527 both coordinates. It is based on ECSSA, but with an inversion 528 operation moved from the signature operation to the verification 529 operation, so that the signing operation is more compatible with 530 ECES. (See [AMV1990] and [A1992] for a discussion of these 531 alternatives; the security of the methods is equivalent.) We refer 532 to this scheme as Abbreviated ECES, or AECES. 534 6.1. Keypair Generation 536 Keypairs are the same as for ECES and are as described in 537 Section 5.1. 539 6.2. Signature Creation 541 In this section we describe how to compute the signature for a 542 message m using the private key a. 544 Signature creation is as for ECES, with the following additional 545 step: 547 1. Let the integer s1 be equal to the x-coordinate of r. 549 The signature is the ordered pair (s1, s). Both signature components 550 are non-negative integers. 552 6.3. Signature Verification 554 Given the message m, the public key Q, and the signature (s1,s) 555 verification is as follows: 557 1. Compute the inverse of s modulo q. We denote this value as w. 559 2. Compute the non-negative integers u and v, where 560 u = w * h(m) mod q, and 562 v = w * s1 mod q. 564 3. Compute the elliptic curve point R' = alpha^u * Q^v 566 4. If the x-coordinate of R' is equal to s1, then the signature and 567 message pass the verification; otherwise, they fail. 569 7. Interoperability 571 The algorithms in this note can be used to interoperate with some 572 other ECC specifications. This section provides details for each 573 algorithm. 575 7.1. ECDH 577 Section 4 can be used with the Internet Key Exchange (IKE) versions 578 one [RFC2409] or two [RFC4306]. These algorithms are compatible with 579 the ECP groups for the defined by [RFC4753], [RFC2409], and 580 [RFC2412]. The group definition used in this protocol uses an affine 581 coordinate representation of the public key and uses neither the 582 compact output nor the compact representation of Section 4.2. Note 583 that some groups use a negative curve parameter "a" and express this 584 fact in the curve equation rather than in the parameter. The test 585 cases in Section 8 of [RFC4753] can be used to test an 586 implementation; these cases use the multiplicative notation, as does 587 this note. The KEi and KEr payloads are equal to g^i and g^r, 588 respectively, with 64 bits of encoding data prepended to them. 590 The algorithms in Section 4 can be used to interoperate with the IEEE 591 [P1363] and ANSI [X9.62] standards for ECDH based on fields of 592 characteristic greater than three. 594 7.2. ECES, AECES, and ECDSA 596 The Digital Signature Algorithm (DSA) is based on the discrete 597 logarithm problem over the multiplicative subgroup of the finite 598 field large prime order [DSA1991][FIPS186]. The Elliptic Curve 599 Digital Signature Algorithm (ECDSA) [P1363] [X9.62] is an elliptic 600 curve version of DSA. 602 AECES can interoperate with the IEEE [P1363] and ANSI [X9.62] 603 standards for Elliptic Curve DSA (ECDSA) based on fields of 604 characteristic greater than three. 606 An ECES signature can be converted into an ECDSA signature by 607 discarding the y-coordinate from the elliptic curve point. 609 There is a strong correspondence between ECES signatures and ECDSA 610 signatures. In the notation of Section 5, an ECDSA signature 611 consists of the pair of integers (g(r), s), and signature 612 verification passes if and only if 614 A^(h(m)/s) * Q^(g(r)/s) = r, 616 where the equality of the elliptic curve elements is checked by 617 checking for the equality of their x-coordinates. For valid 618 signatures, (h(m)+a*r)/s mod q = k, and thus the two sides are equal. 619 An ECDSA signature contains only the x-coordinate g(r), but this is 620 sufficient to allow the signatures to be checked with the above 621 method. 623 Whenever the ECES signature (r, s) is valid for a particular message 624 m, and public key Q, then there is a valid ECDSA signature (g(r), s) 625 for the same message and public key. 627 Whenever the ECDSA signature (c, d) is valid for a particular message 628 m, and public key Q, then there is a valid ECES signature for the 629 same message and public key. This signature has the form ((c, f(c)), 630 d), or ((c, q-f(c)), d) where the function f takes as input an 631 integer in Zq and is defined as 633 f(x) = sqrt(x^3 + a*x + b) (mod q). 635 It is possible to compute the square root modulo q, for instance, by 636 using Shanks's method [K1987]. However, it is not as efficient to 637 convert an ECDSA signature (or an AECES signature) to an ECES 638 signature. 640 8. Intellectual Property 642 Concerns about intellectual property have slowed the adoption of ECC, 643 because a number of optimizations and specialized algorithms have 644 been patented in recent years. 646 All of the normative references in this note were published during or 647 before October, 1994, and all of the normative text in this note is 648 based solely on those references. 650 8.1. Disclaimer 652 This document is not intended as legal advice. Readers are advised 653 to consult their own legal advisers if they would like a legal 654 interpretation of their rights. 656 The IETF policies and processes regarding intellectual property and 657 patents are outlined in [RFC3979] and [RFC4879] and at 658 https://datatracker.ietf.org/ipr/about/. 660 9. Security Considerations 662 The security level of an elliptic curve cryptosystem is determined by 663 the cryptanalytic algorithm that is the least expensive for an 664 attacker to implement. There are several algorithms to consider. 666 The Polhig-Hellman method is a divide-and-conquer technique [PH1978]. 667 If the group order n can be factored as 669 n = q1 * q2 * ... * qz, 671 then the discrete log problem over the group can be solved by 672 independently solving a discrete log problem in groups of order q1, 673 q2, ..., qz, then combining the results using the Chinese remainder 674 theorem. The overall computational cost is dominated by that of the 675 discrete log problem in the subgroup with the largest order. 677 Shanks algorithm [K1981v3] computes a discrete logarithm in a group 678 of order n using O(sqrt(n)) operations and O(sqrt(n)) storage. The 679 Pollard rho algorithm [P1978] computes a discrete logarithm in a 680 group of order n using O(sqrt(n)) operations, with a negligible 681 amount of storage, and can be efficiently parallelized. 683 The Pollard lambda algorithm [P1978] can solve the discrete logarithm 684 problem using O(sqrt(w)) operations and O(log(w)) storage, when the 685 exponent belongs to a set of w elements. 687 The algorithms described above work in any group. There are 688 specialized algorithms that specifically target elliptic curve 689 groups. There are no subexponential algorithms against general 690 elliptic curve groups, though there are methods that target certain 691 special elliptic curve groups; see [MOV1993] and [FR1994]. 693 9.1. Subgroups 695 A group consisting of a set of elements S with associated group 696 operation * is a subgroup of the group with the set of elements G, if 697 the latter group uses the same group operation and S is a subset of 698 G. For each elliptic curve equation, there is an elliptic curve group 699 whose group order is equal to the order of the elliptic curve; that 700 is, there is a group that contains every point on the curve. 702 The order m of the elliptic curve is divisible by the order n of the 703 group associated with the generator; that is, for each elliptic curve 704 group, m = n * c for some number c. The number c is called the 705 "cofactor" [P1363]. Each elliptic curve group (e.g. each parameter 706 set as in Section 3.2) is associated with a particular cofactor. 708 It is possible and desirable to use a cofactor equal to 1. 710 It is common to use a "safe prime group" in the conventional Diffie- 711 Hellman protocol over the multiplicative group of the prime field Fp 712 (see Appendix E of [RFC2412] for example). A safe prime group is the 713 subgroup of prime order q of the multiplicative group of Zp, where 714 p-1 = 2*q. The use of safe prime groups simplifies protocol design, 715 implementation and use, because they minimize the effectiveness of 716 some cryptanalytic attacks. Elliptic curve groups with a cofactor of 717 1 have similar benefits. 719 9.2. Diffie-Hellman 721 Note that the key exchange protocol as defined in Section 4 does not 722 protect against active attacks; Party A must use some method to 723 ensure that (g^k) originated with the intended communicant B, rather 724 than an attacker, and Party B must do the same with (g^j). 726 It is not sufficient to authenticate the shared secret g^(j*k), since 727 this leaves the protocol open to attacks that manipulate the public 728 keys. Instead, the values of the public keys g^x and g^y that are 729 exchanged should be directly authenticated. This is the strategy 730 used by protocols that build on Diffie-Hellman and which use end- 731 entity authentication to protect against active attacks, such as 732 OAKLEY [RFC2412] and the Internet Key Exchange [RFC2409][RFC4306]. 734 When the cofactor of a group is not equal to 1, there are a number of 735 attacks that are possible against ECDH. See [VW1996], [AV1996], and 736 [LL1997]. 738 9.3. Group Representation and Security 740 The elliptic curve group operation does not explicitly incorporate 741 the parameter b from the curve equation. This opens the possibility 742 that a malicious attacker could learn information about an ECDH 743 private key by submitting a bogus public key [BMM2000]. An attacker 744 can craft an elliptic curve group G' that has identical parameters to 745 a group G that is being used in an ECDH protocol, except that b is 746 different. An attacker can submit a point on G' into a run of the 747 ECDH protocol that is using group G, and gain information from the 748 fact that the group operations using the private key of the device 749 under attack are effectively taking place in G' instead of G. 751 This attack can gain useful information about an ECDH private key 752 that is associated with a static public key, that is, a public key 753 that is used in more than one run of the protocol. However, it does 754 not gain any useful information against ephemeral keys. 756 This sort of attack is thwarted if an ECDH implementation does not 757 assume that each pair of coordinates in Zp is actually a point on the 758 appropriate elliptic curve. 760 9.4. Signatures 762 Elliptic curve parameters should only be used if they come from a 763 trusted source; otherwise, some attacks are possible [AV1996], 764 [V1996]. 766 In principle, any collision-resistant hash function is suitable for 767 use in ECES. To facilitate interoperability, we recognize the 768 following hashes as suitable for use as the function H defined in 769 Section 5.4: 771 SHA-256, which has a 256-bit output. 773 SHA-384, which has a 384-bit output. 775 SHA-512, which has a 512-bit output. 777 All of these hash functions are defined in [FIPS180-2]. 779 The number of bits in the output of the hash used in ECES should be 780 equal or close to the number of bits needed to represent the group 781 order. 783 10. IANA Considerations 785 This note has no actions for IANA. This section should be removed by 786 the RFC editor before publication as an RFC. 788 11. Acknowledgements 790 The author expresses his thanks to the originators of elliptic curve 791 cryptography, whose work made this note possible. 793 12. References 795 12.1. Normative References 797 [A1992] Anderson, J., "Response to the proposed DSS", 798 Communications of the ACM v.35 n.7 p.50-52, July 1992. 800 [AMV1990] Agnew, G., Mullin, R., and S. Vanstone, "Improved Digital 801 Signature Scheme based on Discrete Exponentiation", 802 Electronics Letters Vol. 26, No. 14, July, 1990. 804 [BC1989] Bender, A. and G. Castagnoli, "On the Implementation of 805 Elliptic Curve Cryptosystems", Advances in Cryptology - 806 CRYPTO '89 Proceedings Spinger Lecture Notes in Computer 807 Science (LNCS) volume 435, 1989. 809 [D1966] Deskins, W., "Abstract Algebra", MacMillan Company , 1966. 811 [DH1976] Diffie, W. and M. Hellman, "New Directions in 812 Cryptography", IEEE Transactions in Information 813 Theory IT-22, pp 644-654, 1976. 815 [E1984a] ElGamal, T., "Cryptography and logarithms over finite 816 fields", Stanford University UMI Order No. DA 8420519, 817 1984. 819 [E1984b] ElGamal, T., "Cryptography and logarithms over finite 820 fields", Advances in Cryptology - CRYPTO '84 821 Proceedings Springer Lecture Notes in Computer Science 822 (LNCS) volume 196, 1984. 824 [E1985] ElGamal, T., "A public key cryptosystem and a signature 825 scheme based on discrete logarithms", IEEE Transactions on 826 Information Theory Vol 30, No. 4, pp. 469-472, 1985. 828 [FR1994] Frey, G. and H. Ruck, "A remark concerning m-divisibility 829 and the discrete logarithm in the divisor class group of 830 curves.", Mathematics of Computation Vol. 62, No. 206, pp. 831 865-874, 1994. 833 [K1981v2] Knuth, D., "The Art of Computer Programming, Vol. 2: 834 Seminumerical Algorithms", Addison Wesley , 1981. 836 [K1987] Koblitz, N., "Elliptic Curve Cryptosystems", Mathematics 837 of Computation Vol. 48, 1987, 203-209, 1987. 839 [M1983] Massey, J., "Logarithms in finite cyclic groups - 840 cryptographic issues", Processings of the 4th Symposium on 841 Information Theory , 1983. 843 [M1985] Miller, V., "Use of elliptic curves in cryptography", 844 Advances in Cryptology - CRYPTO '85 Proceedings Springer 845 Lecture Notes in Computer Science (LNCS) volume 218, 1985. 847 [MOV1993] Menezes, A., Vanstone, S., and T. Okamoto, "Reducing 848 Elliptic Curve Logarithms to Logarithms in a Finite 849 Field", IEEE Transactions on Information Theory Vol 39, 850 No. 5, pp. 1639-1646, September, 1993. 852 [MQV1994] Menezes, A., Qu, M., and S. Vanstone, "Submission to the 853 IEEE P1363 Working Group (Part 6: Elliptic Curve Systems, 854 Draft 2)", Working Document , October, 1994. 856 [MV1993] Menezes, A. and S. Vanstone, "Elliptic Curve Cryptosystems 857 and Their Implementation", Journal of Cryptology Volume 6, 858 No. 4, pp209-224, 1993. 860 [R1992] Rivest, R., "Response to the proposed DSS", Communications 861 of the ACM v.35 n.7 p.41-47., July 1992. 863 12.2. Informative References 865 [AV1996] Anderson, R. and S. Vaudenay, "Minding Your P's and Q's", 866 Advances in Cryptology - ASIACRYPT '96 Proceedings Spinger 867 Lecture Notes in Computer Science (LNCS) volume 1163, 868 1996. 870 [BMM2000] Biehl, I., Meyer, B., and V. Muller, "Differential fault 871 analysis on elliptic curve cryptosystems", Advances in 872 Cryptology - CRYPTO 2000 Proceedings Spinger Lecture Notes 873 in Computer Science (LNCS) volume 1880, 2000. 875 [DSA1991] "DIGITAL SIGNATURE STANDARD", Federal Register Vol. 56, 876 August 1991. 878 [FIPS180-2] 879 "SECURE HASH STANDARD", Federal Information Processing 880 Standard (FIPS) 180-2, August 2002. 882 [FIPS186] "DIGITAL SIGNATURE STANDARD", Federal Information 883 Processing Standard FIPS-186, 1994. 885 [K1981v3] Knuth, D., "The Art of Computer Programming, Vol. 3: 886 Sorting and Searching", Addison Wesley , 1981. 888 [KMOV1991] 889 Koyama, K., Menezes, A., Vanstone, S., and T. Okamoto, 890 "New Public-Key Schemes Based on Elliptic Curves over the 891 Ring Zn", Advances in Cryptology - CRYPTO '91 892 Proceedings Spinger Lecture Notes in Computer Science 893 (LNCS) volume 576, 1991. 895 [KT1994] Koyama, K. and Y. Tsuruoka, "Digital signature system 896 based on elliptic curve and signer device and verifier 897 device for said system", Japanese Unexamined Patent 898 Application Publication H6-43809, 1994. 900 [LL1997] Lim, C. and P. Lee, "A Key Recovery Attack on Discrete 901 Log-based Schemes Using a Prime Order Subgroup", Advances 902 in Cryptology - CRYPTO '97 Proceedings Spinger Lecture 903 Notes in Computer Science (LNCS) volume 1294, 1997. 905 [P1363] "Standard Specifications for Public Key Cryptography", 906 Institute of Electric and Electronic Engineers 907 (IEEE) P1363, 2000. 909 [P1978] Pollard, J., "Monte Carlo methods for index computation 910 mod p", Mathematics of Computation Vol. 32, 1978. 912 [PH1978] Polhig, S. and M. Hellman, "An Improved Algorithm for 913 Computing Logarithms over GF(p) and its Cryptographic 914 Significance", IEEE Transactions on Information Theory Vol 915 24, pp. 106-110, 1978. 917 [RFC2409] Harkins, D. and D. Carrel, "The Internet Key Exchange 918 (IKE)", RFC 2409, November 1998. 920 [RFC2412] Orman, H., "The OAKLEY Key Determination Protocol", 921 RFC 2412, November 1998. 923 [RFC3979] Bradner, S., "Intellectual Property Rights in IETF 924 Technology", BCP 79, RFC 3979, March 2005. 926 [RFC4306] Kaufman, C., "Internet Key Exchange (IKEv2) Protocol", 927 RFC 4306, December 2005. 929 [RFC4753] Fu, D. and J. Solinas, "ECP Groups For IKE and IKEv2", 930 RFC 4753, January 2007. 932 [RFC4879] Narten, T., "Clarification of the Third Party Disclosure 933 Procedure in RFC 3979", BCP 79, RFC 4879, April 2007. 935 [V1996] Vaudenay, S., "Hidden Collisions on DSS", Advances in 936 Cryptology - CRYPTO '96 Proceedings Spinger Lecture Notes 937 in Computer Science (LNCS) volume 1109, 1996. 939 [VW1996] van Oorschot, P. and M. Wiener, "On Diffie-Hellman key 940 agreement with short exponents", Advances in Cryptology - 941 EUROCRYPT '96 Proceedings Spinger Lecture Notes in 942 Computer Science (LNCS) volume 1070, 1996. 944 [X9.62] "Public Key Cryptography for the Financial Services 945 Industry: The Elliptic Curve Digital Signature Algorithm 946 (ECDSA)", American National Standards Institute (ANSI) 947 X9.62. 949 Appendix A. Random Number Generation 951 It is easy to generate an integer uniformly at random between zero 952 and 2^t, for some positive integer t. Generate a random bit string 953 that contains exactly t bits, and then convert the bit string to a 954 non-negative integer by treating the bits as the coefficients in a 955 base-two expansion of an integer. 957 It is sometimes necessary to generate an integer r uniformly at 958 random so that r satisfies a certain property P, for example, lying 959 within a certain interval. A simple way to do this is with the 960 rejection method: 962 1. Generate a candidate number c uniformly at random from a set that 963 includes many numbers that satisfy property P. 965 2. If c satisfies property P, then return c. Otherwise, return to 966 Step 1. 968 For example, to generate a number between 1 and n-1, repeatedly 969 generate integers between zero and 2^t, stopping at the first integer 970 that falls within that interval. 972 Appendix B. Example Elliptic Curve Group 974 For concreteness, we recall an elliptic curve defined by Solinas and 975 Yu in [RFC4753] and referred to as P-256, which is believed to 976 provide a 128-bit security level. We use the notation of 977 Section 3.2, and express the generator in the affine coordinate 978 representation g=(gx,gy), where the values gx and gy are in Zp. 980 p: FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF 982 a: - 3 984 b: 5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B 986 n: FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551 988 gx: 6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296 990 gy: 4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5 992 Note that p can also be expressed as 994 p = 2^(256)-2^(224)+2^(192)+2^(96)-1. 996 Author's Address 998 David A. McGrew 999 Cisco Systems 1000 510 McCarthy Blvd. 1001 Milpitas, CA 95035 1002 US 1004 Phone: (408) 525 8651 1005 Email: mcgrew@cisco.com 1006 URI: http://www.mindspring.com/~dmcgrew/dam.htm