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