idnits 2.17.00 (12 Aug 2021) /tmp/idnits35505/draft-mcgrew-fundamental-ecc-03.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 1280 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 (May 21, 2010) is 4382 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: November 22, 2010 M. Salter 6 National Security Agency 7 May 21, 2010 9 Fundamental Elliptic Curve Cryptography Algorithms 10 draft-mcgrew-fundamental-ecc-03.txt 12 Abstract 14 This note describes the fundamental algorithms of Elliptic Curve 15 Cryptography (ECC) as they are 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 November 22, 2010. 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. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 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 . . . . . . . . . . . . . . . . . . . . 20 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 . . . . . . . . . . . . 22 99 10.4. Signatures . . . . . . . . . . . . . . . . . . . . . . . . 23 100 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23 101 12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 24 102 13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 24 103 13.1. Normative References . . . . . . . . . . . . . . . . . . . 24 104 13.2. Informative References . . . . . . . . . . . . . . . . . . 25 105 Appendix A. Key Words . . . . . . . . . . . . . . . . . . . . . . 28 106 Appendix B. Random Integer Generation . . . . . . . . . . . . . . 29 107 Appendix C. Why Compact Representation Works . . . . . . . . . . 30 108 Appendix D. Example ECC Parameter Set . . . . . . . . . . . . . . 30 109 Appendix E. Additive and multiplicative notation . . . . . . . . 31 110 Appendix F. Algorithms . . . . . . . . . . . . . . . . . . . . . 31 111 F.1. Affine Coordinates . . . . . . . . . . . . . . . . . . . . 32 112 F.2. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 32 113 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 33 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 fields with characteristic greater than three, based directly on 127 original references. Its intent is to provide the Internet community 128 with a summary of the basic algorithms that predate any specialized 129 or optimized algorithms, which can be used as a normative 130 specification. The original descriptions and notations were followed 131 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 ECDH algorithm. Section 5 145 presents elliptic curve versions of the ElGamal signature method. 146 The representation of integers as octet strings is specified in 147 Section 6. Sections 2 through 6, inclusive, contain all of the 148 normative text (the text that defines the norm for implementations 149 conforming to this specification), and all of the following sections 150 are purely informative. Interoperability is discussed in Section 7. 151 Validation testing is described in Section 8. Section 9 reviews 152 intellectual property issues. Section 10 summarizes security 153 considerations. Appendix B describes random number generation, and 154 other appendices provide clarifying details. 156 1.1. Conventions Used In This Document 158 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 159 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 160 document are to be interpreted as described in Appendix A. 162 2. Mathematical Background 164 This section reviews mathematical preliminaries and establishes 165 terminology and notation that is used below. 167 2.1. Modular Arithmetic 169 This section reviews modular arithmetic. Two integers x and y are 170 said to be congruent modulo n if x - y is an integer multiple of n. 172 Two integers x and y are coprime when their greatest common divisor 173 is 1; in this case, there is no third number z > 1 such that z 174 divides x and z divides y. 176 The set Zq = { 0, 1, 2, ..., q-1 } is closed under the operations of 177 modular addition, modular subtraction, modular multiplication, and 178 modular inverse. These operations are as follows. 180 For each pair of integers a and b in Zq, a + b mod q is equal to 181 a + b if a + b < q, and is equal to a + b - q otherwise. 183 For each pair of integers a and b in Zq, a - b mod q is equal to 184 a - b if a - b >= 0, and is equal to a - b + q otherwise. 186 For each pair of integers a and b in Zq, a * b mod q is equal to 187 the remainder of a * b divided by q. 189 For each integer x in Zq that is coprime with q, the inverse of x 190 modulo q is denoted as 1 / x mod q, and can be computed using the 191 extended euclidean algorithm (see Section 4.5.2 of [K1981v2], for 192 example). 194 Algorithms for these operations are well known; for instance, see 195 Chapter 4 of [K1981v2]. 197 2.2. Group Operations 199 This section establishes some terminology and notation for 200 mathematical groups, which is needed later on. Background references 201 abound; see [D1966], for example. 203 A group is a set of elements G together with an operation that 204 combines any two elements in G and returns a third element in G. The 205 operation is denoted as * and its application is denoted as a * b, 206 for any two elements a and b in G. The operation is associative, that 207 is, for all a, b and c in G, a * (b * c) is identical to (a * b) * c. 208 Repeated application of the group operation N-1 times to the element 209 a is denoted as a^N, for any element a in G and any positive integer 210 N. That is, a^2, = a * a, a^3 = a * a * a, and so on. The 211 associativity of the group operation ensures that the computation of 212 a^n is unambiguous; any grouping of the terms gives the same result. 214 The above definition of a group operation uses multiplicative 215 notation. Sometimes an alternative called additive notation is used, 216 in which a * b is denoted as a + b, and a^N is denoted as N * a. In 217 multiplicative notation, g^N is called exponentiation, while the 218 equivalent operation in additive notation is called scalar 219 multiplication. In this document, multiplicative notation is used 220 throughout for consistency. Appendix E elucidates the correspondence 221 between the two notations. 223 Every group has a special element called the identity element, which 224 we denote as e. For each element a in G, e * a = a * e = a. By 225 convention, a^0 is equal to the identity element for any a in G. 227 Every group element a has a unique inverse element b such that 228 a * b = b * a = e. The inverse of a is denoted as a^-1 in 229 multiplicative notation. (In additive notation, the inverse of a is 230 denoted as -a.) 232 For any positive integer X, a^(-X) is defined to be (a^-1)^(X). 233 Using this convention, exponentiation behaves as one would expect, 234 namely for any integers X and Y: 236 a^(X+Y) = (a^X)*(a^Y) 238 (a^X)^Y = a^(XY) = (a^Y)^X. 240 In cryptographic applications one typically deals with finite groups 241 (groups with a finite number of elements), and for such groups, the 242 number of elements of the group is also called the order of the 243 group. A group element a is said to have finite order if a^X = e for 244 some positive integer X, and the order of a is the smallest such X. 245 If no such X exists, a is said to have infinite order. All elements 246 of a finite group have a finite order, and the order of an element is 247 always a divisor of the group order. 249 If a group element a has order R, then for any integers X and Y, 251 a^X = a^(X mod R), 253 a^X = a^Y if and only if X is congruent to Y mod R, 255 the set H = { a, a^2, a^3, ... , a^R=e } forms a subgroup of G, 256 called the cyclic subgroup generated by a, and a is said to be a 257 generator of H. 259 Typically there are several group elements that generate H. Any group 260 element of the form a^M, with M relatively prime to R, also generates 261 H. Note that a^M is equal to g^(M modulo R) for any non-negative 262 integer M. 264 Given the element a of order R, and an integer i between 1 and R-1, 265 inclusive, the element a^i can be computed by the "square and 266 multiply" method outlined in Section 2.1 of [M1983] (see also Knuth, 267 Vol. 2, Section 4.6.3.), or other methods. 269 2.3. Finite Fields 271 This section establishes terminology and notation for finite fields 272 with prime characteristic. 274 When p is a prime number, then the set Zp, with the addition, 275 subtraction, multiplication and division operations, is a finite 276 field with characteristic p. Each nonzero element x in Zp has an 277 inverse 1/x. There is a one-to-one correspondence between the 278 integers between zero and p-1, inclusive, and the elements of the 279 field. The field Zp is sometimes denoted as Fp or GF(p). 281 Equations involving field elements do not explicitly denote the "mod 282 p" operation, but it is understood to be implicit. For example, the 283 statement that x, y, and z are in Fp and 285 z = x + y 287 is equivalent to the statement that x, y, and z are in the set 288 { 0, 1, ..., p-1 } and 290 z = x + y mod p. 292 3. Elliptic Curve Groups 294 This note only covers elliptic curves over fields with characteristic 295 greater than three; these are the curves used in Suite B [SuiteB]. 296 For other fields, the definition of the elliptic curve group would be 297 different. 299 An elliptic curve over a field Fp is defined by the curve equation 301 y^2 = x^3 + a*x + b, 303 where x, y, a, and b are elements of the field Fp [M1985] and the 304 discriminant is nonzero (as described in Section 3.3.1). A point on 305 an elliptic curve is a pair (x,y) of values in Fp that satisfies the 306 curve equation, or it is a special point (@,@) that represents the 307 identity element (which is called the "point at infinity"). The 308 order of an elliptic curve group is the number of distinct points. 310 Two elliptic curve points (x1,y1) and (x2,y2) are equal whenever 311 x1=x2 and y1=y2, or when both points are the point at infinity. The 312 inverse of the point (x1,y1) is the point (x1,-y1). The point at 313 infinity is its own inverse. 315 The group operation associated with the elliptic curve group is as 316 follows [BC1989]. To an arbitrary pair of points P and Q specified 317 by their coordinates (x1,y1) and (x2,y2) respectively, the group 318 operation assigns a third point P*Q with the coordinates (x3,y3). 319 These coordinates are computed as follows: 321 (x3,y3) = (@,@) when P is not equal to Q and x1 is equal to x2. 323 x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 and 324 y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 when P is not equal to Q and 325 x1 is not equal to x2. 327 (x3,y3) = (@,@) when P is equal to Q and y1 is equal to 0, 329 x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 and 330 y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y1 if P is equal to Q and y1 is 331 not equal to 0. 333 In the above equations, a, x1, x2, x3, y1, y2, and y3 are elements of 334 the field Fp; thus, computation of x3 and y3 in practice must reduce 335 the right-hand-side modulo p. Pseudocode for the group operation is 336 provided in Appendix F.1. 338 The representation of elliptic curve points as a pair of integers in 339 Zp is known as the affine coordinate representation. This 340 representation is suitable as an external data representation for 341 communicating or storing group elements, though the point at infinity 342 must be treated as a special case. 344 Some pairs of integers are not valid elliptic curve points. A valid 345 pair will satisfy the curve equation, while an invalid pair will not. 347 3.1. Homogeneous Coordinates 349 An alternative way to implement the group operation is to use 350 homogeneous coordinates [K1987] (see also [KMOV1991]). This method 351 is typically more efficient because it does not require a modular 352 inversion operation. 354 An elliptic curve point (x,y) (other than the point at infinity 355 (@,@)) is equivalent to a point (X,Y,Z) in homogeneous coordinates 356 whenever x=X/Z mod p and y=Y/Z mod p. 358 Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on an elliptic curve 359 and suppose that the points P1, P2 are not equal to (@,@), P1 is not 360 equal to P2, and P1 is not equal to P2^-1. Then the product 361 P3=(X3,Y3,Z3) = P1 * P2 is given by 363 X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3) mod p 365 Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3 mod p 367 Z3 = v^3 * Z1 * Z2 mod p 369 where u = Y2 * Z1 - Y1 * Z2 mod p and v = X2 * Z1 - X1 * Z2 mod p. 371 When the points P1 and P2 are equal, then (X1/Z1, Y1/Z1) is equal to 372 (X2/Z2, Y2/Z2), which is true if and only if u and v are both equal 373 to zero. 375 The product P3=(X3,Y3,Z3) = P1 * P1 is given by 377 X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1) mod p 379 Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3 mod p 381 Z3 = 8 * (Y1 * Z1)^3 mod p 383 where w = 3 * X1^2 + a * Z1^2 mod p. In the above equations, a, u, 384 v, w, X1, X2, X3, Y1, Y2, Y3, Z1, Z2, and Z3 are integers in the set 385 Fp. Pseudocode for the group operation in homogeneous coordinates is 386 provided in Appendix F.2. 388 When converting from affine coordinates to homogeneous coordinates, 389 it is convenient to set Z to 1. When converting from homogeneous 390 coordinates to affine coordinates, it is necessary to perform a 391 modular inverse to find 1/Z mod p. 393 3.2. Other Coordinates 395 Some other coordinate systems have been described; several are 396 documented in [CC1986], including Jacobi coordinates. 398 3.3. ECC Parameters 400 In cryptographic contexts, an elliptic curve parameter set consists 401 of a cyclic subgroup of an elliptic curve together with a preferred 402 generator of that subgroup. When working over a prime order finite 403 field with characteristic greater than three, an elliptic curve group 404 is completely specified by the following parameters: 406 The prime number p that indicates the order of the field Fp. 408 The value a used in the curve equation. 410 The value b used in the curve equation. 412 The generator g of the subgroup. 414 The order n of the subgroup generated by g. 416 An example of an ECC parameter set is provided in Appendix D. 418 Parameter generation is out of scope for this note. 420 Each elliptic curve point is associated with a particular parameter 421 set. The elliptic curve group operation is only defined between two 422 points in the same group. It is an error to apply the group 423 operation to two elements that are from different groups, or to apply 424 the group operation to a pair of coordinates that is not a valid 425 point. (A pair (x,y) of coordinates in Fp is a valid point only when 426 they satisfy the curve equation.) See Section 10.3 for further 427 information. 429 3.3.1. Discriminant 431 For each elliptic curve group, the discriminant - 16*(4*a^3 + 27*b^2) 432 must be nonzero modulo p [S1986]; this requires that 434 4*a^3 + 27*b^2 != 0 mod p. 436 3.3.2. Security 438 Security is highly dependent on the choice of these parameters. This 439 section gives normative guidance on acceptable choices. See also 440 Section 10 for informative guidance. 442 The order of the group generated by g MUST be divisible by a large 443 prime, in order to preclude easy solutions of the discrete logarithm 444 problem [K1987]. 446 With some parameter choices, the discrete log problem is 447 significantly easier to solve. This includes parameter sets in which 448 b = 0 and p = 3 (mod 4), and parameter sets in which a = 0 and 449 p = 2 (mod 3) [MOV1993]. These parameter choices are inferior for 450 cryptographic purposes and SHOULD NOT be used. 452 4. Elliptic Curve Diffie-Hellman (ECDH) 454 The Diffie-Hellman (DH) key exchange protocol [DH1976] allows two 455 parties communicating over an insecure channel to agree on a secret 456 key. It was originally defined in terms of operations in the 457 multiplicative group of a field with a large prime characteristic. 458 Massey [M1983] observed that it can be easily generalized so that it 459 is defined in terms of an arbitrary mathematical group. Miller 460 [M1985] and Koblitz [K1987] analyzed the DH protocol over an elliptic 461 curve group. We describe DH following the former reference. 463 Let G be a group, and g be a generator for that group, and let t 464 denote the order of G. The DH protocol runs as follows. Party A 465 chooses an exponent j between 1 and t-1, inclusive, uniformly at 466 random, computes g^j and sends that element to B. Party B chooses an 467 exponent k between 1 and t-1, inclusive, uniformly at random, 468 computes g^k and sends that element to A. Each party can compute 469 g^(j*k); party A computes (g^k)^j, and party B computes (g^j)^k. 471 See Appendix B regarding generation of random integers. 473 4.1. Data Types 475 Each run of the ECDH protocol is associated with a particular 476 parameter set (as defined in Section 3.3), and the public keys g^j 477 and g^k and the shared secret g^(j*k) are elements of the cyclic 478 subgroup associated with the parameter set. 480 An ECDH private key z is an integer in Zt, where t is the order of 481 the subgroup. 483 4.2. Compact Representation 485 As described in the final paragraph of [M1985], the x-coordinate of 486 the shared secret value g^(j*k) is a suitable representative for the 487 entire point whenever exponentiation is used as a one-way function. 488 In the ECDH key exchange protocol, after the element g^(j*k) has been 489 computed, the x-coordinate of that value can be used as the shared 490 secret. We call this compact output. 492 Following [M1985] again, when compact output is used in ECDH, only 493 the x-coordinate of an elliptic curve point needs to be transmitted, 494 instead of both coordinates as in the typical affine coordinate 495 representation. We call this the compact representation. Its 496 mathematical background is explained in Appendix C. 498 ECDH can be used with or without compact output. Both parties in a 499 particular run of the ECDH protocol MUST use the same method. ECDH 500 can be used with or without compact representation. If compact 501 representation is used in a particular run of the ECDH protocol, then 502 compact output MUST be used as well. 504 5. Elliptic Curve ElGamal Signatures 506 5.1. Background 508 The ElGamal signature algorithm was introduced in 1984 [E1984a] 509 [E1984b] [E1985]. It is based on the discrete logarithm problem, and 510 was originally defined for the multiplicative group of the integers 511 modulo a large prime number. It is straightforward to extend it to 512 use other finite groups, such as the multiplicative group of the 513 field GF(2^w) [AMV1990] or an elliptic curve group [A1992]. 515 An ElGamal signature consists of a pair of components. There are 516 many possible generalizations of ElGamal signature methods that have 517 been obtained by different rearrangements of the equation for the 518 second component; see [HMP1994], [HP1994], [NR1994], [A1992], and 519 [AMV1990]. These generalizations are independent of the mathematical 520 group used, and have been described for the multiplicative group 521 modulo a prime number, the multiplicative group of GF(2^w), and 522 elliptic curve groups [HMP1994][NR1994][AMV1990][A1992]. 524 The Digital Signature Algorithm (DSA) [FIPS186] is an important 525 ElGamal signature variant. 527 5.2. Hash Functions 529 ElGamal signatures must use a collision-resistant hash function, so 530 that it can sign messages of arbitrary length and can avoid 531 existential forgery attacks; see Section 10.4. (This is true for all 532 ElGamal variants [HMP1994].) We denote the hash function as h(). 533 Its input is a bit string of arbitrary length, and its output is a 534 non-negative integer. 536 Let H() denote a hash function whose output is a fixed-length bit 537 string. To use H in an ElGamal signature method, we define the 538 mapping between that output and the non-negative integers; this 539 realizes the function h() described above. Given a bit string m, the 540 function h(m) is computed as follows: 542 1. H(m) is evaluated; the result is a fixed-length bit string. 544 2. Convert the resulting bit string to an integer i by treating its 545 leftmost (initial) bit as the most significant bit of i, and 546 treating its rightmost (final) bit as the least significant bit 547 of i. 549 5.3. KT-IV Signatures 551 Koyama and Tsuruoka described a signature method based on Elliptic 552 Curve ElGamal, in which the first signature component is the 553 x-coordinate of an elliptic curve point reduced modulo q [KT1994]. 554 In this section we recall that method, which we refer to as KT-IV. 556 The algorithm uses an elliptic curve group, as described in 557 Section 3.3, with prime field order p and curve equation parameters a 558 and b. We denote the generator as alpha, and the order of the 559 generator as q. We follow [FIPS186] in checking for exceptional 560 cases. 562 5.3.1. Keypair Generation 564 The private key z is an integer between 1 and q - 1, inclusive, 565 generated uniformly at random. (See Appendix B regarding random 566 integers.) The public key is the group element 567 Y = alpha^z. Each public key is associated with a particular 568 particular parameter set as per Section 3.3. 570 5.3.2. Signature Creation 572 To compute a KT-IV signature for a message m using the private key z: 574 1. Choose an integer k uniformly at random from the set of all 575 integers between 1 and q-1, inclusive. (See Appendix B regarding 576 random integers.) 578 2. Calculate R = (r_x, r_y) = alpha^k. 580 3. Calculate s1 = r_x mod q. 582 4. Check if h(m) + z * s1 = 0 mod q; if so, a new value of k MUST be 583 generated and the signature MUST be recalculated. As an option, 584 one MAY check if s1 = 0; if so, a new value of k SHOULD be 585 generated and the signature SHOULD be recalculated. (It is 586 extremely unlikely that s1 = 0 or h(m) + z * s1 = 0 mod q if 587 signatures are generated properly.) 589 5. Calculate s2 = k / (h(m) + z * s1) mod q. 591 The signature is the ordered pair (s1, s2). Both signature 592 components are non-negative integers. 594 5.3.3. Signature Verification 596 Given the message m, the public key Y, and the signature (s1, s2) 597 verification is as follows: 599 1. Check to see that 0 < s1 < q and 0 < s2 < q; if either condition 600 is violated, the signature SHALL be rejected. 602 2. Compute the non-negative integers u1 and u2, where 604 u1 = h(m) * s2 mod q, and 606 u2 = s1 * s2 mod q. 608 3. Compute the elliptic curve point R' = alpha^u1 * Y^u2. 610 4. If the x-coordinate of R' mod q is equal to s1, then the 611 signature and message pass the verification; otherwise, they 612 fail. 614 5.4. KT-I Signatures 616 Horster, Michels, and Petersen categorized many different ElGamal 617 signature methods, demonstrated their equivalence, and showed how to 618 convert signatures of one type to another type [HMP1994]. In their 619 terminology, the signature method of Section 5.3 and [KT1994] is a 620 Type IV method, which is why it is denoted as KT-IV. 622 A Type I KT signature method has a second component that is computed 623 in the same manner as that of the Digital Signature Algorithm. In 624 this section, we describe this method, which we refer to as KT-I. 626 5.4.1. Keypair Generation 628 Keypairs and keypair generation are exactly as in Section 5.3.1. 630 5.4.2. Signature Creation 632 To compute a KT-I signature for a message m using the private key z: 634 1. Choose an integer k uniformly at random from the set of all 635 integers between 1 and q-1, inclusive. (See Appendix B regarding 636 random integers.) 638 2. Calculate R = (r_x, r_y) = alpha^k. 640 3. Calculate s1 = r_x mod q. 642 4. Calculate s2 = (h(m) + z * s1) / k mod q. 644 5. As an option, one MAY check if s1 = 0 or s2 = 0. If either 645 s1 = 0 or s2 = 0, a new value of k SHOULD be generated and the 646 signature SHOULD be recalculated. (It is extremely unlikely that 647 s1 = 0 or s2 = 0 if signatures are generated properly.) 649 The signature is the ordered pair (s1, s2). Both signature 650 components are non-negative integers. 652 5.4.3. Signature Verification 654 Given the message m, the public key Y, and the signature (s1, s2) 655 verification is as follows: 657 1. Check to see that 0 < s1 < q and 0 < s2 < q; if either condition 658 is violated the signature SHALL be rejected. 660 2. Compute s2_inv = 1 / s2 mod q. 662 3. Compute the non-negative integers u1 and u2, where 664 u1 = h(m) * s2_inv mod q, and 666 u2 = s1 * s2_inv mod q. 668 4. Compute the elliptic curve point R' = alpha^u1 * Y^u2. 670 5. If the x-coordinate of R' mod q is equal to s1, then the 671 signature and message pass the verification; otherwise, they 672 fail. 674 5.5. Converting KT-IV signatures to KT-I signatures 676 A KT-IV signature for a message m and a public key Y can easily be 677 converted into a KT-I signature for the same message and public key. 678 If (s1, s2) is a KT-IV signature for a message m, then 679 (s1, 1/s2 mod q) is a KT-I signature for the same message [HMP1994]. 681 The conversion operation uses only public information, and it can be 682 performed by the creator of the pre-conversion KT-IV signature, the 683 verifier of the post-conversion KT-I signature, or by any other 684 entity. 686 An implementation MAY use this method to compute KT-I signatures. 688 5.6. Rationale 690 This subsection is not normative for this specification and is 691 provided only as background information. 693 [HMP1994] presents many generalizations of ElGamal signatures. 694 Equation (5) of that reference shows the general signature equation 696 A = x_A * B + k * C (mod q) 698 where x_A is the private key, k is the secret value, and A, B, and C 699 are determined by the Type of the equation, as shown in Table 1 of 700 [HMP1994]. DSA [FIPS186] is an EG-I.1 signature method (as is KT-I), 701 with A = m, B = -r, and C = s. (Here we use the notation of 702 [HMP1994] in which the first signature component is r and the second 703 signature component is s; in KT-I and KT-IV these components are 704 denoted as s1 and s2 respectively. The private key x_A corresponds 705 to the private key z.) Its signature equation is 707 m = - r * z + s * k (mod q). 709 The signature method of [KT1994] and Section 5.3 is an EG-IV.1 710 method, with A = m * s, B = - r * s, C = 1. Its signature equation 711 is 713 m * s = - r * s * z + k (mod q) 715 The functions f and g mentioned in Table 1 are merely multiplication, 716 as described under the heading "Fifth generalization". 718 No hash function is shown in the above equations, but as described in 719 Section 10.4, a hash function should be applied to the message prior 720 to signing in order to prevent existential forgery attacks. 722 Nyberg and Rueppel [NR1994] studied many different ElGamal signature 723 methods, and defined "strong equivalence" as follows: 725 Two signature methods are called strongly equivalent if the 726 signature of the first scheme can be transformed efficiently into 727 signatures of the second scheme and vice versa, without knowledge 728 of the private key. 730 KT-I and KT-IV signatures are obviously strongly equivalent. 732 A valid signature with s2=0 leaks the secret key, since in that case 733 z = - h(m) / s1 mod q. We follow [FIPS186] in checking for this 734 exceptional case and the case that s1=0. The s2=0 check was 735 suggested by Rivest [R1992] and is discussed in [BS1992]. 737 [KT1994] uses "a positive integer q' that does not exceed q" when 738 computing the signature component s1 from the x-coordinate r_x of the 739 elliptic curve point R = (r_x, r_y). The value q' is also used 740 during signature validation when comparing the x-coordinate of a 741 computed elliptic curve point to the value to s1. In this note, we 742 use the simplifying convention that q' = q. 744 6. Converting between integers and octet strings 746 A method for the conversion between integers and octet strings is 747 specified in this section, following the established conventions of 748 public key cryptography [R1993]. This method allows integers to be 749 represented as octet strings that are suitable for transmission or 750 storage. This method SHOULD be used when representing an elliptic 751 curve point or an elliptic curve coordinate as they are defined in 752 this note. 754 6.1. Octet-string-to-integer conversion 756 The octet string S shall be converted to an integer x as follows. 757 Let S1, ..., Sk be the octets of S from first to last. Then the 758 integer x shall satisfy 760 k 761 x = SUM 2^(8(k-i)) Si . 762 i = 1 764 In other words, the first octet of S has the most significance in the 765 integer and the last octet of S has the least significance. 767 Note: the integer x satisfies 0 <= x < 2^(8*k). 769 6.2. Integer-to-octet-string conversion 771 The integer x shall be converted to an octet string S of length k as 772 follows. The string S shall satisfy 774 k 775 y = SUM 2^(8(k-i)) Si . 776 i = 1 778 where S1, ..., Sk are the octets of S from first to last. 780 In other words, the first octet of S has the most significance in the 781 integer and the last octet of S has the least significance. 783 7. Interoperability 785 The algorithms in this note can be used to interoperate with some 786 other ECC specifications. This section provides details for each 787 algorithm. 789 7.1. ECDH 791 Section 4 can be used with the Internet Key Exchange (IKE) versions 792 one [RFC2409] or two [RFC4306]. These algorithms are compatible with 793 the ECP groups defined by [RFC4753], [RFC5114], [RFC2409], and 794 [RFC2412]. The group definition in this protocol uses an affine 795 coordinate representation of the public key and uses neither the 796 compact output nor the compact representation of Section 4.2. 797 [RFC4753] describes data formats that are compatible with those of 798 Section 6. Note that some groups indicate that the curve parameter 799 "a" is negative; these values are to be interpreted modulo the order 800 of the field. For example, a parameter of a = -3 is equal to p - 3, 801 where p is the order of the field. The test cases in Section 8 of 802 [RFC4753] can be used to test an implementation; these cases use the 803 multiplicative notation, as does this note. The KEi and KEr payloads 804 are equal to g^j and g^k, respectively, with 64 bits of encoding data 805 prepended to them. 807 The algorithms in Section 4 can be used to interoperate with the IEEE 808 [P1363] and ANSI [X9.62] standards for ECDH based on fields of 809 characteristic greater than three. IEEE P1363 ECDH can be used in a 810 manner that will interoperate with this note, with the following 811 options and parameter choices from that specification: 813 prime curves with a cofactor of 1, 815 the ECSVDP-DH primitive, and 817 the Key Derivation Function must be the "identity" function 818 (equivalently, the KDF step should be omitted and the shared 819 secret value should be output directly). 821 7.2. KT-I and ECDSA 823 The Digital Signature Algorithm (DSA) is based on the discrete 824 logarithm problem over the multiplicative subgroup of the finite 825 field with large prime order [DSA1991][FIPS186]. The Elliptic Curve 826 Digital Signature Algorithm (ECDSA) [P1363] [X9.62] is an elliptic 827 curve version of DSA. 829 KT-I is mathematically and functionally equivalent to ECDSA, and can 830 interoperate with the IEEE [P1363] and ANSI [X9.62] standards for 831 Elliptic Curve DSA (ECDSA) based on fields of characteristic greater 832 than three. KT-I signatures can be verified using the ECDSA 833 verification algorithm, and ECDSA signatures can be verified using 834 the KT-I verification algorithm. 836 8. Validating an Implementation 838 It is essential to validate the implementation of a cryptographic 839 algorithm. This section outlines tests that should be performed on 840 the algorithms defined in this note. 842 A known answer test, or KAT, uses a fixed set of inputs to test an 843 algorithm; the output of the algorithm is compared with the expected 844 output, which is also a fixed value. KATs for ECDH and KT-I are set 845 out in the following subsections. 847 A consistency test generates inputs for one algorithm being tested 848 using a second algorithm that is also being tested, then checks the 849 output of the first algorithm. A signature creation algorithm can be 850 tested for consistency against a signature verification algorithm. 851 Implementations of KT-I should be tested in this way. Their 852 signature generation processes are non-deterministic, and thus cannot 853 be tested using a KAT. Signature verification algorithms, on the 854 other hand, are deterministic and should be tested via a KAT. This 855 combination of tests provides coverage for all of the operations, 856 including keypair generation. Consistency testing should also be 857 applied to ECDH. 859 8.1. ECDH 861 An ECDH implementation can be validated using the known answer test 862 cases from [RFC4753] or [RFC5114]. The correspondence between the 863 notation in RFC 4753 and the notation in this note are summarized in 864 the following table. (Refer to Section 3.3 and Section 4; the 865 generator g is expressed in affine coordinate representation as (gx, 866 gy)). 868 +----------------------+---------------------------------------+ 869 | ECDH | RFC 4753 | 870 +----------------------+---------------------------------------+ 871 | order p of field Fp | p | 872 | curve coefficient a | -3 | 873 | curve coefficient b | b | 874 | generator g | g=(gx, gy) | 875 | private keys j and k | i and r | 876 | public keys g^j, g^k | g^i = (gix, giy) and g^r = (grx, gry) | 877 +----------------------+---------------------------------------+ 879 The correspondence between the notation in RFC 5114 and the notation 880 in this note are summarized in the following table. 882 +-----------------------+---------------------------+ 883 | ECDH | RFC 5114 | 884 +-----------------------+---------------------------+ 885 | order p of field Fp | p | 886 | curve coefficient a | a | 887 | curve coefficient b | b | 888 | generator g | g=(gx, gy) | 889 | group order n | n | 890 | private keys j and k | dA and dB | 891 | public keys g^j, g^k | g^(dA) = (x_qA, y_qA) and | 892 | | g^(dB) = (x_qB, y_qB) | 893 | shared secret g^(j*k) | g^(dA*dB) = (x_Z, y_Z) | 894 +-----------------------+---------------------------+ 896 8.2. KT-I 898 A KT-I implementation can be validated using the known answer test 899 cases from [RFC4754]. The correspondence between the notation in 900 that RFC and the notation in this note are summarized in the 901 following table. 903 +---------------------+------------------+ 904 | KT-I | RFC 4754 | 905 +---------------------+------------------+ 906 | order p of field Fp | p | 907 | curve coefficient a | -3 | 908 | curve coefficient b | b | 909 | generator alpha | g | 910 | group order q | q | 911 | private key z | w | 912 | public key Y | g^w = (gwx,gwy) | 913 | random k | ephem priv k | 914 | s1 | r | 915 | s2 | s | 916 | s2_inv | sinv | 917 | u1 | u = h*sinv mod q | 918 | u2 | v = r*sinv mod q | 919 +---------------------+------------------+ 921 9. Intellectual Property 923 Concerns about intellectual property have slowed the adoption of ECC, 924 because a number of optimizations and specialized algorithms have 925 been patented in recent years. 927 All of the normative references for ECDH (as defined in Section 4) 928 were published during or before 1989, and those for KT-I were 929 published during or before May, 1994. All of the normative text for 930 these algorithms is based solely on their respective references. 932 9.1. Disclaimer 934 This document is not intended as legal advice. Readers are advised 935 to consult their own legal advisers if they would like a legal 936 interpretation of their rights. 938 The IETF policies and processes regarding intellectual property and 939 patents are outlined in [RFC3979] and [RFC4879] and at 940 https://datatracker.ietf.org/ipr/about/. 942 10. Security Considerations 944 The security level of an elliptic curve cryptosystem is determined by 945 the cryptanalytic algorithm that is the least expensive for an 946 attacker to implement. There are several algorithms to consider. 948 The Pohlig-Hellman method is a divide-and-conquer technique [PH1978]. 949 If the group order n can be factored as 951 n = q1 * q2 * ... * qz, 953 then the discrete log problem over the group can be solved by 954 independently solving a discrete log problem in groups of order q1, 955 q2, ..., qz, then combining the results using the Chinese remainder 956 theorem. The overall computational cost is dominated by that of the 957 discrete log problem in the subgroup with the largest order. 959 Shanks' algorithm [K1981v3] computes a discrete logarithm in a group 960 of order n using O(sqrt(n)) operations and O(sqrt(n)) storage. The 961 Pollard rho algorithm [P1978] computes a discrete logarithm in a 962 group of order n using O(sqrt(n)) operations, with a negligible 963 amount of storage, and can be efficiently parallelized [VW1994]. 965 The Pollard lambda algorithm [P1978] can solve the discrete logarithm 966 problem using O(sqrt(w)) operations and O(log(w)) storage, when the 967 exponent is known to lie in an interval of width w. 969 The algorithms described above work in any group. There are 970 specialized algorithms that specifically target elliptic curve 971 groups. There are no known subexponential algorithms against general 972 elliptic curve groups, though there are methods that target certain 973 special elliptic curve groups; see [MOV1993] and [FR1994]. 975 10.1. Subgroups 977 A group consisting of a nonempty set of elements S with associated 978 group operation * is a subgroup of the group with the set of elements 979 G, if the latter group uses the same group operation and S is a 980 subset of G. For each elliptic curve equation, there is an elliptic 981 curve group whose group order is equal to the order of the elliptic 982 curve; that is, there is a group that contains every point on the 983 curve. 985 The order m of the elliptic curve is divisible by the order n of the 986 group associated with the generator; that is, for each elliptic curve 987 group, m = n * c for some number c. The number c is called the 988 "cofactor" [P1363]. Each ECC parameter set as in Section 3.3 is 989 associated with a particular cofactor. 991 It is possible and desirable to use a cofactor equal to 1. 993 10.2. Diffie-Hellman 995 Note that the key exchange protocol as defined in Section 4 does not 996 protect against active attacks; Party A must use some method to 997 ensure that (g^k) originated with the intended communicant B, rather 998 than an attacker, and Party B must do the same with (g^j). 1000 It is not sufficient to authenticate the shared secret g^(j*k), since 1001 this leaves the protocol open to attacks that manipulate the public 1002 keys. Instead, the values of the public keys g^x and g^y that are 1003 exchanged should be directly authenticated. This is the strategy 1004 used by protocols that build on Diffie-Hellman and which use end- 1005 entity authentication to protect against active attacks, such as 1006 OAKLEY [RFC2412] and the Internet Key Exchange [RFC2409][RFC4306]. 1008 When the cofactor of a group is not equal to 1, there are a number of 1009 attacks that are possible against ECDH. See [VW1996], [AV1996], and 1010 [LL1997]. 1012 10.3. Group Representation and Security 1014 The elliptic curve group operation does not explicitly incorporate 1015 the parameter b from the curve equation. This opens the possibility 1016 that a malicious attacker could learn information about an ECDH 1017 private key by submitting a bogus public key [BMM2000]. An attacker 1018 can craft an elliptic curve group G' that has identical parameters to 1019 a group G that is being used in an ECDH protocol, except that b is 1020 different. An attacker can submit a point on G' into a run of the 1021 ECDH protocol that is using group G, and gain information from the 1022 fact that the group operations using the private key of the device 1023 under attack are effectively taking place in G' instead of G. 1025 This attack can gain useful information about an ECDH private key 1026 that is associated with a static public key, that is, a public key 1027 that is used in more than one run of the protocol. However, it does 1028 not gain any useful information against ephemeral keys. 1030 This sort of attack is thwarted if an ECDH implementation does not 1031 assume that each pair of coordinates in Zp is actually a point on the 1032 appropriate elliptic curve. 1034 These considerations also apply when ECDH is used with compact 1035 representation (see Appendix C). 1037 10.4. Signatures 1039 Elliptic curve parameters should only be used if they come from a 1040 trusted source; otherwise, some attacks are possible [AV1996], 1041 [V1996]. 1043 If no hash function is used in an ElGamal signature system, then the 1044 system is vulnerable to existential forgeries, in which an attacker 1045 who does not know a private key can generate valid signatures for the 1046 associated public key, but cannot generate a signature for a message 1047 of its own choosing. (See [E1985] for instance.) The use of a 1048 collision-resistant hash function eliminates this vulnerability. 1050 In principle, any collision-resistant hash function is suitable for 1051 use in KT signatures. To facilitate interoperability, we recognize 1052 the following hashes as suitable for use as the function H defined in 1053 Section 5.2: 1055 SHA-256, which has a 256-bit output. 1057 SHA-384, which has a 384-bit output. 1059 SHA-512, which has a 512-bit output. 1061 All of these hash functions are defined in [FIPS180-2]. 1063 The number of bits in the output of the hash used in KT signatures 1064 should be equal or close to the number of bits needed to represent 1065 the group order. 1067 11. IANA Considerations 1069 This note has no actions for IANA. This section should be removed by 1070 the RFC editor before publication as an RFC. 1072 12. Acknowledgements 1074 The author expresses his thanks to the originators of elliptic curve 1075 cryptography, whose work made this note possible, and all of the 1076 reviewers, who provided valuable constructive feedback. Thanks are 1077 especially due to Howard Pinder, Andrey Jivsov, Alfred Hoenes (who 1078 contributed the algorithms in Appendix F), and Dan Harkins. 1080 13. References 1082 13.1. Normative References 1084 [AMV1990] Agnew, G., Mullin, R., and S. Vanstone, "Improved Digital 1085 Signature Scheme based on Discrete Exponentiation", 1086 Electronics Letters Vol. 26, No. 14, July, 1990. 1088 [BC1989] Bender, A. and G. Castagnoli, "On the Implementation of 1089 Elliptic Curve Cryptosystems", Advances in Cryptology - 1090 CRYPTO '89 Proceedings Spinger Lecture Notes in Computer 1091 Science (LNCS) volume 435, 1989. 1093 [CC1986] Chudnovsky, D. and G. Chudnovsky, "Sequences of numbers 1094 generated by addition in formal groups and new primality 1095 and factorization tests", Advances in Applied 1096 Mathematics Volume 7, Issue 4, December 1986. 1098 [D1966] Deskins, W., "Abstract Algebra", MacMillan Company New 1099 York, 1966. 1101 [DH1976] Diffie, W. and M. Hellman, "New Directions in 1102 Cryptography", IEEE Transactions in Information 1103 Theory IT-22, pp 644-654, 1976. 1105 [FR1994] Frey, G. and H. Ruck, "A remark concerning m-divisibility 1106 and the discrete logarithm in the divisor class group of 1107 curves.", Mathematics of Computation Vol. 62, No. 206, pp. 1108 865-874, 1994. 1110 [HMP1994] Horster, P., Michels, M., and H. Petersen, "Meta-ElGamal 1111 signature schemes", University of Technology Chemnitz- 1112 Zwickau Department of Computer Science Technical 1113 Report TR-94-5, May 1994. 1115 [K1981v2] Knuth, D., "The Art of Computer Programming, Vol. 2: 1117 Seminumerical Algorithms", Addison Wesley , 1981. 1119 [K1987] Koblitz, N., "Elliptic Curve Cryptosystems", Mathematics 1120 of Computation Vol. 48, 1987, 203-209, 1987. 1122 [KT1994] Koyama, K. and Y. Tsuruoka, "Digital signature system 1123 based on elliptic curve and signer device and verifier 1124 device for said system", Japanese Unexamined Patent 1125 Application Publication H6-43809, February 18, 1994. 1127 [M1983] Massey, J., "Logarithms in finite cyclic groups - 1128 cryptographic issues", Proceedings of the 4th Symposium on 1129 Information Theory , 1983. 1131 [M1985] Miller, V., "Use of elliptic curves in cryptography", 1132 Advances in Cryptology - CRYPTO '85 Proceedings Springer 1133 Lecture Notes in Computer Science (LNCS) volume 218, 1985. 1135 [MOV1993] Menezes, A., Vanstone, S., and T. Okamoto, "Reducing 1136 Elliptic Curve Logarithms to Logarithms in a Finite 1137 Field", IEEE Transactions on Information Theory Vol 39, 1138 No. 5, pp. 1639-1646, September, 1993. 1140 [R1993] RSA Laboratories, "PKCS#1: RSA Encryption Standard", 1141 Technical Note version 1.5, 1993. 1143 [S1986] Silverman, J., "The Arithmetic of Elliptic Curves", 1144 Springer-Verlag New York, 1986. 1146 13.2. Informative References 1148 [A1992] Anderson, J., "Response to the proposed DSS", 1149 Communications of the ACM v.35 n.7 p.50-52, July 1992. 1151 [AV1996] Anderson, R. and S. Vaudenay, "Minding Your P's and Q's", 1152 Advances in Cryptology - ASIACRYPT '96 Proceedings Spinger 1153 Lecture Notes in Computer Science (LNCS) volume 1163, 1154 1996. 1156 [BMM2000] Biehl, I., Meyer, B., and V. Muller, "Differential fault 1157 analysis on elliptic curve cryptosystems", Advances in 1158 Cryptology - CRYPTO 2000 Proceedings Spinger Lecture Notes 1159 in Computer Science (LNCS) volume 1880, 2000. 1161 [BS1992] Branstad, D. and M. Smid, "Response to Comments on the 1162 NIST Proposed Digital Signature Standard", Advances in 1163 Cryptology - CRYPTO '92 Proceedings Springer Lecture Notes 1164 in Computer Science (LNCS) volume 740, August 1992. 1166 [DSA1991] U.S. National Institute of Standards and Technology, 1167 "DIGITAL SIGNATURE STANDARD", Federal Register Vol. 56, 1168 August 1991. 1170 [E1984a] ElGamal, T., "Cryptography and logarithms over finite 1171 fields", Stanford University UMI Order No. DA 8420519, 1172 1984. 1174 [E1984b] ElGamal, T., "Cryptography and logarithms over finite 1175 fields", Advances in Cryptology - CRYPTO '84 1176 Proceedings Springer Lecture Notes in Computer Science 1177 (LNCS) volume 196, 1984. 1179 [E1985] ElGamal, T., "A public key cryptosystem and a signature 1180 scheme based on discrete logarithms", IEEE Transactions on 1181 Information Theory Vol 30, No. 4, pp. 469-472, 1985. 1183 [FIPS180-2] 1184 U.S. National Institute of Standards and Technology, 1185 "SECURE HASH STANDARD", Federal Information Processing 1186 Standard (FIPS) 180-2, August 2002. 1188 [FIPS186] U.S. National Institute of Standards and Technology, 1189 "DIGITAL SIGNATURE STANDARD", Federal Information 1190 Processing Standard FIPS-186, May 1994. 1192 [HP1994] Horster, P. and H. Petersen, "Verallgemeinerte ElGamal- 1193 Signaturen", Proceedings der Fachtagung SIS '94, Verlag 1194 der Fachvereine Zurich, 1994. 1196 [K1981v3] Knuth, D., "The Art of Computer Programming, Vol. 3: 1197 Sorting and Searching", Addison Wesley , 1981. 1199 [KMOV1991] 1200 Koyama, K., Maurer, U., Vanstone, S., and T. Okamoto, "New 1201 Public-Key Schemes Based on Elliptic Curves over the Ring 1202 Zn", Advances in Cryptology - CRYPTO '91 1203 Proceedings Spinger Lecture Notes in Computer Science 1204 (LNCS) volume 576, 1991. 1206 [L1969] Lehmer, D., "Computer technology applied to the theory of 1207 numbers", M.A.A. Studies in Mathematics 180-2, 1969. 1209 [LL1997] Lim, C. and P. Lee, "A Key Recovery Attack on Discrete 1210 Log-based Schemes Using a Prime Order Subgroup", Advances 1211 in Cryptology - CRYPTO '97 Proceedings Spinger Lecture 1212 Notes in Computer Science (LNCS) volume 1294, 1997. 1214 [NR1994] Nyberg, K. and R. Rueppel, "Message Recovery for Signature 1215 Schemes Based on the Discrete Logarithm Problem", Advances 1216 in Cryptology - EUROCRYPT '94 Proceedings Springer Lecture 1217 Notes in Computer Science (LNCS) volume 950, May 1994. 1219 [P1363] "Standard Specifications for Public Key Cryptography", 1220 Institute of Electric and Electronic Engineers 1221 (IEEE) P1363, 2000. 1223 [P1978] Pollard, J., "Monte Carlo methods for index computation 1224 mod p", Mathematics of Computation Vol. 32, 1978. 1226 [PH1978] Pohlig, S. and M. Hellman, "An Improved Algorithm for 1227 Computing Logarithms over GF(p) and its Cryptographic 1228 Significance", IEEE Transactions on Information Theory Vol 1229 24, pp. 106-110, 1978. 1231 [R1988] Rose, H., "A Course in Number Theory", Oxford University 1232 Press , 1988. 1234 [R1992] Rivest, R., "Response to the proposed DSS", Communications 1235 of the ACM v.35 n.7 p.41-47., July 1992. 1237 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1238 Requirement Levels", BCP 14, RFC 2119, March 1997. 1240 [RFC2409] Harkins, D. and D. Carrel, "The Internet Key Exchange 1241 (IKE)", RFC 2409, November 1998. 1243 [RFC2412] Orman, H., "The OAKLEY Key Determination Protocol", 1244 RFC 2412, November 1998. 1246 [RFC3979] Bradner, S., "Intellectual Property Rights in IETF 1247 Technology", BCP 79, RFC 3979, March 2005. 1249 [RFC4086] Eastlake, D., Schiller, J., and S. Crocker, "Randomness 1250 Requirements for Security", BCP 106, RFC 4086, June 2005. 1252 [RFC4306] Kaufman, C., "Internet Key Exchange (IKEv2) Protocol", 1253 RFC 4306, December 2005. 1255 [RFC4753] Fu, D. and J. Solinas, "ECP Groups For IKE and IKEv2", 1256 RFC 4753, January 2007. 1258 [RFC4754] Fu, D. and J. Solinas, "IKE and IKEv2 Authentication Using 1259 the Elliptic Curve Digital Signature Algorithm (ECDSA)", 1260 RFC 4754, January 2007. 1262 [RFC4879] Narten, T., "Clarification of the Third Party Disclosure 1263 Procedure in RFC 3979", BCP 79, RFC 4879, April 2007. 1265 [RFC5114] Lepinski, M. and S. Kent, "Additional Diffie-Hellman 1266 Groups for Use with IETF Standards", RFC 5114, 1267 January 2008. 1269 [SuiteB] U. S. National Security Agency (NSA), "NSA Suite B 1270 Cryptography", Web Page http://www.nsa.gov/ia/programs/ 1271 suiteb_cryptography/index.shtml. 1273 [V1996] Vaudenay, S., "Hidden Collisions on DSS", Advances in 1274 Cryptology - CRYPTO '96 Proceedings Spinger Lecture Notes 1275 in Computer Science (LNCS) volume 1109, 1996. 1277 [VW1994] van Oorschot, P. and M. Wiener, "Parallel Collision Search 1278 with Application to Hash Functions and Discrete 1279 Logarithms", Proceedings of the 2nd ACM Conference on 1280 Computer and communications security pp. 210-218, 1994. 1282 [VW1996] van Oorschot, P. and M. Wiener, "On Diffie-Hellman key 1283 agreement with short exponents", Advances in Cryptology - 1284 EUROCRYPT '96 Proceedings Spinger Lecture Notes in 1285 Computer Science (LNCS) volume 1070, 1996. 1287 [X9.62] "Public Key Cryptography for the Financial Services 1288 Industry: The Elliptic Curve Digital Signature Algorithm 1289 (ECDSA)", American National Standards Institute (ANSI) 1290 X9.62. 1292 Appendix A. Key Words 1294 The definitions of these key words are quoted from [RFC2119] and are 1295 commonly used in Internet standards. They are reproduced in this 1296 note in order to avoid a normative reference from after 1994. 1298 1. MUST - This word, or the terms "REQUIRED" or "SHALL", mean that 1299 the definition is an absolute requirement of the specification. 1301 2. MUST NOT - This phrase, or the phrase "SHALL NOT", mean that the 1302 definition is an absolute prohibition of the specification. 1304 3. SHOULD - This word, or the adjective "RECOMMENDED", mean that 1305 there may exist valid reasons in particular circumstances to 1306 ignore a particular item, but the full implications must be 1307 understood and carefully weighed before choosing a different 1308 course. 1310 4. SHOULD NOT - This phrase, or the phrase "NOT RECOMMENDED" mean 1311 that there may exist valid reasons in particular circumstances 1312 when the particular behavior is acceptable or even useful, but 1313 the full implications should be understood and the case carefully 1314 weighed before implementing any behavior described with this 1315 label. 1317 5. MAY - This word, or the adjective "OPTIONAL", mean that an item 1318 is truly optional. One vendor may choose to include the item 1319 because a particular marketplace requires it or because the 1320 vendor feels that it enhances the product while another vendor 1321 may omit the same item. An implementation which does not include 1322 a particular option MUST be prepared to interoperate with another 1323 implementation which does include the option, though perhaps with 1324 reduced functionality. In the same vein an implementation which 1325 does include a particular option MUST be prepared to interoperate 1326 with another implementation which does not include the option 1327 (except, of course, for the feature the option provides.) 1329 Appendix B. Random Integer Generation 1331 It is easy to generate an integer uniformly at random between zero 1332 and 2^t -1, inclusive, for some positive integer t. Generate a 1333 random bit string that contains exactly t bits, and then convert the 1334 bit string to a non-negative integer by treating the bits as the 1335 coefficients in a base-two expansion of an integer. 1337 It is sometimes necessary to generate an integer r uniformly at 1338 random so that r satisfies a certain property P, for example, lying 1339 within a certain interval. A simple way to do this is with the 1340 rejection method: 1342 1. Generate a candidate number c uniformly at random from a set that 1343 includes all numbers that satisfy property P (plus some other 1344 numbers, preferably not too many) 1346 2. If c satisfies property P, then return c. Otherwise, return to 1347 Step 1. 1349 For example, to generate a number between 1 and n-1, inclusive, 1350 repeatedly generate integers between zero and 2^t - 1, inclusive, 1351 stopping at the first integer that falls within that interval. 1353 Recommendations on how to generate random bit strings are provided in 1354 [RFC4086]. 1356 Appendix C. Why Compact Representation Works 1358 In the affine representation, the x-coordinate of the point P^i does 1359 not depend on the y-coordinate of the point P, for any non-negative 1360 exponent i and any point P. This fact can be seen as follows. When 1361 given only the x-coordinate of a point P, it is not possible to 1362 determine exactly what the y-coordinate is, but the y value will be a 1363 solution to the curve equation 1365 y^2 = x^3 + a*x + b (mod p). 1367 There are at most two distinct solutions y = w and y = -w mod p, and 1368 the point P must be either Q=(x,w) or Q^-1=(x,-w). Thus P^n is equal 1369 to either Q^n or (Q^-1)^n = (Q^n)^-1. These values have the same 1370 x-coordinate. Thus, the x-coordinate of a point P^i can be computed 1371 from the x-coordinate of a point P by computing one of the possible 1372 values of the y coordinate of P, then computing the ith power of P, 1373 and then ignoring the y-coordinate of that result. 1375 In general, it is possible to compute a square root modulo p by using 1376 Shanks' method [K1981v2]; simple methods exist for some values of p. 1377 When p = 3 (mod 4), the square roots of z mod p are w and -w mod p, 1378 where 1380 w = z ^ ((p+1)/4) (mod p); 1382 this observation is due to Lehmer [L1969]. When p satisfies this 1383 property, y can be computed from the curve equation, and either y = w 1384 or y = -w mod p, where 1386 w = (x^3 + a*x + b)^((p+1)/4) (mod p). 1388 Square roots modulo p only exist for a quadratic residue modulo p, 1389 [R1988]; if z is not a quadratic residue, then there is no number w 1390 such that w^2 = z (mod p). A simple way to verify that z is a 1391 quadratic residue after computing w is to verify that 1392 w * w = z (mod p). If this relation does not hold for the above 1393 equation, then the value x is not a valid x-coordinate for a valid 1394 elliptic curve point. This is an important consideration when ECDH 1395 is used with compact output; see Section 10.3. 1397 The primes used in the P-256, P-384, and P-521 curves described in 1398 [RFC4753] all have the property that p = 3 (mod 4). 1400 Appendix D. Example ECC Parameter Set 1402 For concreteness, we recall an elliptic curve defined by Solinas and 1403 Fu in [RFC4753] and referred to as P-256, which is believed to 1404 provide a 128-bit security level. We use the notation of 1405 Section 3.3, and express the generator in the affine coordinate 1406 representation g=(gx,gy), where the values gx and gy are in Fp. 1408 p: FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF 1410 a: - 3 1412 b: 5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B 1414 n: FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551 1416 gx: 6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296 1418 gy: 4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5 1420 Note that p can also be expressed as 1422 p = 2^(256)-2^(224)+2^(192)+2^(96)-1. 1424 Appendix E. Additive and multiplicative notation 1426 The early publications on elliptic curve cryptography used 1427 multiplicative notation, but most modern publications use additive 1428 notation. This section includes a table mapping between those two 1429 conventions. In this section, a and b are elements of an elliptic 1430 curve group, and N is an integer. 1432 +-------------------------+-----------------------+ 1433 | Multiplicative Notation | Additive Notation | 1434 +-------------------------+-----------------------+ 1435 | multiplication | addition | 1436 | a * b | a + b | 1437 | squaring | doubling | 1438 | a * a = a^2 | a + a = 2a | 1439 | exponentiation | scalar multiplication | 1440 | a^N = a * a * ... * a | Na = a + a + ... + a | 1441 | inverse | inverse | 1442 | a^-1 | -a | 1443 +-------------------------+-----------------------+ 1445 Appendix F. Algorithms 1447 This section contains a pseudocode description of the elliptic curve 1448 group operation. Text that follows the symbol "//" are to be 1449 interpreted as comments rather than instructions. 1451 F.1. Affine Coordinates 1453 To an arbitrary pair of elliptic curve points P and Q specified by 1454 their affine coordinates P=(x1,y1) and Q=(x2,y2), the group operation 1455 assigns a third point R = P*Q with the coordinates (x3,y3). These 1456 coordinates are computed as follows: 1458 if P is (@,@), 1459 R = Q 1460 else if Q is (@,@), 1461 R = P 1462 else if P is not equal to Q and x1 is equal to x2, 1463 R = (@,@) 1464 else if P is not equal to Q and x1 is not equal to x2, 1465 x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 mod p and 1466 y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 mod p 1467 else if P is equal to Q and y1 is equal to 0, 1468 R = (@,@) 1469 else // P is equal to Q and y1 is not equal to 0 1470 x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 mod p and 1471 y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y mod p. 1473 From the first and second case, it follows that the point at infinity 1474 is the neutral element of this operation, which is its own inverse. 1476 From the curve equation it follows that for a given curve point P = 1477 (x,y) distinct from the point at infinity, (x,-y) also is a curve 1478 point, and from the third and the fifth case it follows that this is 1479 the inverse of P, P^-1. 1481 Note: The fifth and sixth case are known as "point squaring". 1483 F.2. Homogeneous Coordinates 1485 An elliptic curve point (x,y) (other than the point at infinity 1486 (@,@)) is equivalent to a point (X,Y,Z) in homogeneous coordinates 1487 (with X, Y, and Z in Fp and not all three being zero at once) 1488 whenever x=X/Z and y=Y/Z. "Homogenous coordinates" means that two 1489 triples (X,Y,Z) and (X',Y',Z') are regarded as "equal" (i.e. 1490 representing the same point) if there is some non-zero s in Fp such 1491 that X'=s*X, Y'=s*Y, and Z'=s*Z. The point at infinity, (@,@) is 1492 regarded as equivalent to the homogenous coordinates (0,1,0), i.e. it 1493 can be represented by any triple (0,Y,0) with non-zero Y in Fp. 1495 Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on the elliptic curve, 1496 and let u = Y2 * Z1 - Y1 * Z2 and v = X2 * Z1 - X1 * Z2. 1498 We observe that the points P1 and P2 are equal if and only if u and v 1499 are both equal to zero. Otherwise, if either P1 or P2 are equal to 1500 the point at infinity, v is zero and u is non-zero (but the converse 1501 implication does not hold). 1503 Then the product P3=(X3,Y3,Z3) = P1 * P2 is given by: 1505 if P1 is the point at infinity, 1506 P3 = P2 1507 else if P2 is the point at infinity, 1508 P3 = P1 1509 else if u is not equal to 0 but v is equal to 0, 1510 P3 = (0,1,0) 1511 else if both u and v are not equal to 0, 1512 X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3) 1513 Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3 1514 Z3 = v^3 * Z1 * Z2 1515 else // P2 equals P1, P3 = P1 * P1 1516 w = 3 * X1^2 + a * Z1^2 1517 X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1) 1518 Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3 1519 Z3 = 8 * (Y1 * Z1)^3 1521 It thus turns out that the point at infinity is the identity element 1522 and for P1=(X,Y,Z) not equal to this point at infinity, P2=(X,-Y,Z) 1523 represents P1^-1. 1525 Authors' Addresses 1527 David A. McGrew 1528 Cisco Systems 1529 510 McCarthy Blvd. 1530 Milpitas, CA 95035 1531 USA 1533 Phone: (408) 525 8651 1534 Email: mcgrew@cisco.com 1535 URI: http://www.mindspring.com/~dmcgrew/dam.htm 1537 Kevin M. Igoe 1538 National Security Agency 1539 Commercial Solutions Center 1540 United States of America 1542 Email: kmigoe@nsa.gov 1543 Margaret Salter 1544 National Security Agency 1545 9800 Savage Rd. 1546 Fort Meade, MD 20755-6709 1547 USA 1549 Email: msalter@restarea.ncsc.mil