idnits 2.17.1 draft-mcgrew-fundamental-ecc-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Sep 2009 rather than the newer Notice from 28 Dec 2009. (See https://trustee.ietf.org/license-info/) Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 1193 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 (February 19, 2010) is 5180 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Obsolete informational reference (is this intentional?): RFC 2409 (Obsoleted by RFC 4306) -- Obsolete informational reference (is this intentional?): RFC 3979 (Obsoleted by RFC 8179) -- Obsolete informational reference (is this intentional?): RFC 4306 (Obsoleted by RFC 5996) -- Obsolete informational reference (is this intentional?): RFC 4753 (Obsoleted by RFC 5903) -- Obsolete informational reference (is this intentional?): RFC 4879 (Obsoleted by RFC 8179) Summary: 1 error (**), 0 flaws (~~), 3 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group D. McGrew 3 Internet-Draft Cisco Systems 4 Intended status: Informational K. Igoe 5 Expires: August 23, 2010 National Security Agency 6 February 19, 2010 8 Fundamental Elliptic Curve Cryptography Algorithms 9 draft-mcgrew-fundamental-ecc-02.txt 11 Abstract 13 This note describes the fundamental algorithms of Elliptic Curve 14 Cryptography (ECC) as they are defined in some early references. 15 These descriptions may be useful for implementing the fundamental 16 algorithms without using any of the specialized methods that were 17 developed in following years. Only elliptic curves defined over 18 fields of characteristic greater than three are in scope; these 19 curves are those used in Suite B. 21 Status of this Memo 23 This Internet-Draft is submitted to IETF in full conformance with the 24 provisions of BCP 78 and BCP 79. 26 Internet-Drafts are working documents of the Internet Engineering 27 Task Force (IETF), its areas, and its working groups. Note that 28 other groups may also distribute working documents as Internet- 29 Drafts. 31 Internet-Drafts are draft documents valid for a maximum of six months 32 and may be updated, replaced, or obsoleted by other documents at any 33 time. It is inappropriate to use Internet-Drafts as reference 34 material or to cite them other than as "work in progress." 36 The list of current Internet-Drafts can be accessed at 37 http://www.ietf.org/ietf/1id-abstracts.txt. 39 The list of Internet-Draft Shadow Directories can be accessed at 40 http://www.ietf.org/shadow.html. 42 This Internet-Draft will expire on August 23, 2010. 44 Copyright Notice 46 Copyright (c) 2010 IETF Trust and the persons identified as the 47 document authors. All rights reserved. 49 This document is subject to BCP 78 and the IETF Trust's Legal 50 Provisions Relating to IETF Documents 51 (http://trustee.ietf.org/license-info) in effect on the date of 52 publication of this document. Please review these documents 53 carefully, as they describe your rights and restrictions with respect 54 to this document. Code Components extracted from this document must 55 include Simplified BSD License text as described in Section 4.e of 56 the Trust Legal Provisions and are provided without warranty as 57 described in the BSD License. 59 Table of Contents 61 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 62 1.1. Conventions Used In This Document . . . . . . . . . . . . 4 63 2. Mathematical Background . . . . . . . . . . . . . . . . . . . 5 64 2.1. Modular Arithmetic . . . . . . . . . . . . . . . . . . . . 5 65 2.2. Group Operations . . . . . . . . . . . . . . . . . . . . . 5 66 2.3. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 7 67 3. Elliptic Curve Groups . . . . . . . . . . . . . . . . . . . . 7 68 3.1. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 8 69 3.2. Other Coordinates . . . . . . . . . . . . . . . . . . . . 9 70 3.3. ECC Parameters . . . . . . . . . . . . . . . . . . . . . . 9 71 3.3.1. Security . . . . . . . . . . . . . . . . . . . . . . . 10 72 4. Elliptic Curve Diffie-Hellman (ECDH) . . . . . . . . . . . . . 10 73 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 11 74 4.2. Compact Representation . . . . . . . . . . . . . . . . . . 11 75 5. Elliptic Curve ElGamal Signatures . . . . . . . . . . . . . . 12 76 5.1. Background . . . . . . . . . . . . . . . . . . . . . . . . 12 77 5.2. Hash Functions . . . . . . . . . . . . . . . . . . . . . . 12 78 5.3. KT-IV Signatures . . . . . . . . . . . . . . . . . . . . . 13 79 5.3.1. Keypair Generation . . . . . . . . . . . . . . . . . . 13 80 5.3.2. Signature Creation . . . . . . . . . . . . . . . . . . 13 81 5.3.3. Signature Verification . . . . . . . . . . . . . . . . 13 82 5.4. KT-I Signatures . . . . . . . . . . . . . . . . . . . . . 14 83 5.4.1. Keypair Generation . . . . . . . . . . . . . . . . . . 14 84 5.4.2. Signature Creation . . . . . . . . . . . . . . . . . . 14 85 5.4.3. Signature Verification . . . . . . . . . . . . . . . . 15 86 5.5. Converting KT-IV signatures to KT-I signatures . . . . . . 15 87 5.6. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 15 88 6. Interoperability . . . . . . . . . . . . . . . . . . . . . . . 17 89 6.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 90 6.2. KT-I and ECDSA . . . . . . . . . . . . . . . . . . . . . . 17 91 7. Validating an Implementation . . . . . . . . . . . . . . . . . 18 92 7.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 93 7.2. KT-I . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 94 8. Intellectual Property . . . . . . . . . . . . . . . . . . . . 19 95 8.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . 19 97 9. Security Considerations . . . . . . . . . . . . . . . . . . . 20 98 9.1. Subgroups . . . . . . . . . . . . . . . . . . . . . . . . 20 99 9.2. Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . 21 100 9.3. Group Representation and Security . . . . . . . . . . . . 21 101 9.4. Signatures . . . . . . . . . . . . . . . . . . . . . . . . 22 102 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22 103 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 22 104 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 23 105 12.1. Normative References . . . . . . . . . . . . . . . . . . . 23 106 12.2. Informative References . . . . . . . . . . . . . . . . . . 24 107 Appendix A. Key Words . . . . . . . . . . . . . . . . . . . . . . 27 108 Appendix B. Random Integer Generation . . . . . . . . . . . . . . 27 109 Appendix C. Why Compact Representation Works . . . . . . . . . . 28 110 Appendix D. Example ECC Parameter Set . . . . . . . . . . . . . . 29 111 Appendix E. Additive and multiplicative notation . . . . . . . . 29 112 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 30 114 1. Introduction 116 ECC is a public-key technology that offers performance advantages at 117 higher security levels. It includes an Elliptic Curve version of 118 Diffie-Hellman key exchange protocol [DH1976] and Elliptic Curve 119 versions of the ElGamal Signature Algorithm [E1985]. The adoption of 120 ECC has been slower than had been anticipated, perhaps due to the 121 lack of freely available normative documents and uncertainty over 122 intellectual property rights. 124 This note contains a description of the fundamental algorithms of ECC 125 over fields with characteristic greater than three, based directly on 126 original references. Its intent is to provide the Internet community 127 with a summary of the basic algorithms that predate any specialized 128 or optimized algorithms, which can be used as a normative 129 specification. The original descriptions and notations were followed 130 as closely as possible. 132 There are several standards that specify or incorporate ECC 133 algorithms, including the Internet Key Exchange (IKE), ANSI X9.62, 134 and IEEE P1363. The algorithms in this note can interoperate with 135 some of the algorithms in these standards, with a suitable choice of 136 parameters and options. The specifics are itemized in Section 6. 138 The rest of the note is organized as follows. Section 2.1, 139 Section 2.2, and Section 2.3 furnish the necessary terminology and 140 notation from modular arithmetic, group theory and the theory of 141 finite fields, respectively. Section 3 defines the groups based on 142 elliptic curves over finite fields of characteristic greater than 143 three. Section 4 presents the fundamental ECDH algorithm. Section 5 144 presents elliptic curve versions of the ElGamal signature method. 145 Sections 2 through 5, inclusive, contain all of the normative text 146 (the text that defines the norm for implementations conforming to 147 this specification), and all of the following sections are purely 148 informative. Interoperability is discussed in Section 6. Validation 149 testing is described in Section 7. Section 8 reviews intellectual 150 property issues. Section 9 summarizes security considerations. 151 Appendix B describes random number generation, and other appendices 152 provide clarifying details. 154 1.1. Conventions Used In This Document 156 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 157 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 158 document are to be interpreted as described in Appendix A. 160 2. Mathematical Background 162 This section reviews mathematical preliminaries and establishes 163 terminology and notation that is used below. 165 2.1. Modular Arithmetic 167 This section reviews modular arithmetic. Two integers x and y are 168 said to be congruent modulo n if x - y is an integer multiple of n. 170 Two integers x and y are coprime when their greatest common divisor 171 is 1; in this case, there is no third number z > 1 such that z 172 divides x and z divides y. 174 The set Zq = { 0, 1, 2, ..., q-1 } is closed under the operations of 175 modular addition, modular subtraction, modular multiplication, and 176 modular inverse. These operations are as follows. 178 For each pair of integers a and b in Zq, a + b mod q is equal to 179 a + b if a + b < q, and is equal to a + b - q otherwise. 181 For each pair of integers a and b in Zq, a - b mod q is equal to 182 a - b if a - b >= 0, 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 the remainder of a * b divided by q. 187 For each integer x in Zq that is coprime with q, the inverse of x 188 modulo q is denoted as 1 / x mod q, and can be computed using the 189 extended euclidean algorithm (see Section 4.5.2 of [K1981v2], for 190 example). 192 Algorithms for these operations are well known; for instance, see 193 Chapter 4 of [K1981v2]. 195 2.2. Group Operations 197 This section establishes some terminology and notation for 198 mathematical groups, which is needed later on. Background references 199 abound; see [D1966], for example. 201 A group is a set of elements G together with an operation that 202 combines any two elements in G and returns a third element in G. The 203 operation is denoted as * and its application is denoted as a * b, 204 for any two elements a and b in G. The operation is associative, that 205 is, for all a, b and c in G, a * (b * c) is identical to (a * b) * c. 206 Repeated application of the group operation N-1 times to the element 207 a is denoted as a^N, for any element a in G and any positive integer 208 N. That is, a^2, = a * a, a^3 = a * a * a, and so on. The 209 associativity of the group operation ensures that the computation of 210 a^n is unambiguous; any grouping of the terms gives the same result. 212 The above definition of a group operation uses multiplicative 213 notation. Sometimes an alternative called additive notation is used, 214 in which a * b is denoted as a + b, and a^N is denoted as N * a. In 215 multiplicative notation, g^N is called exponentiation, while the 216 equivalent operation in additive notation is called scalar 217 multiplication. In this document, multiplicative notation is used 218 throughout for consistency. Appendix E elucidates the correspondence 219 between the two notations. 221 Every group has a special element called the identity element, which 222 we denote as e. For each element a in G, e * a = a * e = a. By 223 convention, a^0 is equal to the identity element for any a in G. 225 Every group element a has a unique inverse element b such that 226 a * b = b * a = e. The inverse of a is denoted as a^-1 in 227 multiplicative notation. (In additive notation, the inverse of a is 228 denoted as -a.) 230 For any positive integer X, a^(-X) is defined to be (a^-1)^(X). 231 Using this convention, exponentiation behaves as one would expect, 232 namely for any integers X and Y: 234 a^(X+Y) = (a^X)*(a^Y) 236 (a^X)^Y = a^(XY) = (a^Y)^X. 238 A group element a is said to have finite order if a^X = e for some 239 positive integer X, and the order of a is the smallest such X. If no 240 such X exists, a is said to have infinite order. In cryptographic 241 applications one typically deals with finite groups (groups with a 242 finite number of elements), and all elements of finite groups have 243 finite order. If a group element a has order R, then for any 244 integers X and Y, 246 a^X = a^(X mod R), 248 a^X = a^Y if and only if X is congruent to Y mod R, 250 the set H = { a, a^2, a^3, ... , a^R=e } forms a subgroup of G, 251 called the cyclic subgroup generated by a, and a is said to be a 252 generator of H. 254 Typically there are several group elements that generate H. Any group 255 element of the form a^M, with M relatively prime to R, also generates 256 H. Note that a^M is equal to g^(M modulo R) for any non-negative 257 integer M. 259 Given the element a of order R, and an integer i between 1 and R-1, 260 inclusive, the element a^i can be computed by the "square and 261 multiply" method outlined in Section 2.1 of [M1983] (see also Knuth, 262 Vol. 2, Section 4.6.3.), or other methods. 264 2.3. Finite Fields 266 This section establishes terminology and notation for finite fields 267 with prime characteristic. 269 When p is a prime number, then the set Zp, with the addition, 270 subtraction, multiplication and division operations, is a finite 271 field with characteristic p. Each nonzero element x in Zp has an 272 inverse 1/x. There is a one-to-one correspondence between the 273 integers between zero and p-1, inclusive, and the elements of the 274 field. The field Zp is sometimes denoted as Fp. 276 Equations involving field elements do not explicitly denote the "mod 277 p" operation, but it is understood to be implicit. For example, the 278 statement that x, y, and z are in Fp and 280 z = x + y 282 is equivalent to the statement that x, y, and z are in the set 283 { 0, 1, ..., p-1 } and 285 z = x + y mod p. 287 3. Elliptic Curve Groups 289 This note only covers elliptic curves over fields with characteristic 290 greater than three; these are the curves used in Suite B [SuiteB]. 291 For other fields, the definition of the elliptic curve group would be 292 different. 294 An elliptic curve over a field Fp is defined by the curve equation 296 y^2 = x^3 + a*x + b, 298 where x, y, a, and b are elements of the field Fp [M1985]. A point 299 on an elliptic curve is a pair (x,y) of values in Fp that satisfy the 300 curve equation, such that x and y are both in Fp, or it is a special 301 point (@,@) that represents the identity element (which is called the 302 "point at infinity"). The order of an elliptic curve group is the 303 number of distinct points. 305 Two elliptic curve points (x1,y1) and (x2,y2) are equal whenever 306 x1=x2 and y1=y2, or when both points are the point at infinity. The 307 inverse of the point (x1,y1) is the point (x1,-y1). The point at 308 infinity is its own inverse. 310 The group operation associated with the elliptic curve group is as 311 follows [BC1989]. To an arbitrary pair of points P and Q specified 312 by their coordinates (x1,y1) and (x2,y2) respectively, the group 313 operation assigns a third point P*Q with the coordinates (x3,y3). 314 These coordinates are computed as follows 316 (x3,y3) = (@,@) when P is not equal to Q and x1 is equal to x2. 318 x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 and 319 y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 when P is not equal to Q and 320 x1 is not equal to x2. 322 (x3,y3) = (@,@) when P is equal to Q and y1 is equal to 0, 324 x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 and 325 y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y1 if P is equal to Q and y1 is 326 not equal to 0. 328 In the above equations, a, x1, x2, x3, y1, y2, and y3 are elements of 329 the field Fp; thus, computation of x3 and y3 in practice must reduce 330 the right-hand-side modulo p. 332 The representation of elliptic curve points as a pair of integers in 333 Zp is known as the affine coordinate representation. This 334 representation is suitable as an external data representation for 335 communicating or storing group elements, though the point at infinity 336 must be treated as a special case. 338 Some pairs of integers are not valid elliptic curve points. A valid 339 pair will satisfy the curve equation, while an invalid pair will not. 341 3.1. Homogeneous Coordinates 343 An alternative way to implement the group operation is to use 344 homogeneous coordinates [K1987] (see also [KMOV1991]). This method 345 is typically more efficient because it does not require a modular 346 inversion operation. 348 An elliptic curve point (x,y) (other than the point at infinity 349 (@,@)) is equivalent to a point (X,Y,Z) in homogeneous coordinates 350 whenever x=X/Z mod p and y=Y/Z mod p. 352 Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on an elliptic curve 353 and suppose that the points P1, P2 are not equal to (@,@), P1 is not 354 equal to P2, and P1 is not equal to P2^-1. Then the product 355 P3=(X3,Y3,Z3) = P1 * P2 is given by 357 X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3) mod p 359 Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3 mod p 361 Z3 = v^3 * Z1 * Z2 mod p 363 where u = Y2 * Z1 - Y1 * Z2 mod p and v = X2 * Z1 - X1 * Z2 mod p. 365 When the points P1 and P2 are equal, then (X1/Z1, Y1/Z1) is equal to 366 (X2/Z2, Y2/Z2), which is true if and only if u and v are both equal 367 to zero. 369 The product P3=(X3,Y3,Z3) = P1 * P1 is given by 371 X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1) mod p 373 Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3 mod p 375 Z3 = 8 * (Y1 * Z1)^3 mod p 377 where w = 3 * X1^2 + a * Z1^2 mod p. In the above equations, a, u, 378 v, w, X1, X2, X3, Y1, Y2, Y3, Z1, Z2, and Z3 are integers in the set 379 Fp. 381 When converting from affine coordinates to homogeneous coordinates, 382 it is convenient to set Z to 1. When converting from homogeneous 383 coordinates to affine coordinates, it is necessary to perform a 384 modular inverse to find 1/Z mod p. 386 3.2. Other Coordinates 388 Some other coordinate systems have been described; several are 389 documented in [CC1986], including Jacobi coordinates. 391 3.3. ECC Parameters 393 In cryptographic contexts, an elliptic curve parameter set consists 394 of a cyclic subgroup of an elliptic curve together with a preferred 395 generator of that subgroup. When working over a prime order finite 396 field with characteristic greater than three, an elliptic curve group 397 is completely specified by the following parameters: 399 The prime number p that indicates the order of the field Fp. 401 The value a used in the curve equation. 403 The value b used in the curve equation. 405 The generator g of the subgroup. 407 The order n of the subgroup generated by g. 409 An example of an ECC parameter set is provided in Appendix D. 411 Each elliptic curve point is associated with a particular parameter 412 set. The elliptic curve group operation is only defined between two 413 points in the same group. It is an error to apply the group 414 operation to two elements that are from different groups, or to apply 415 the group operation to a pair of coordinates that is not a valid 416 point. (A pair (x,y) of coordinates in Fp is a valid point only when 417 they satisfy the curve equation.) See Section 9.3 for further 418 information. 420 For each elliptic curve group, the discriminant - 16*(4*a^3 + 27*b^2) 421 must be nonzero modulo p. 423 Parameter generation is out of scope for this note. 425 3.3.1. Security 427 Security is highly dependent on the choice of these parameters. This 428 section gives normative guidance on acceptable choices. See also 429 Section 9 for informative guidance. 431 The order of the group generated by g MUST be divisible by a large 432 prime, in order to preclude easy solution of the discrete logarithm 433 problem [K1987] 435 With some parameter choices, the discrete log problem is 436 significantly easier to solve. This includes parameter sets in which 437 b = 0 and p = 3 (mod 4), and parameter sets in which a = 0 and 438 p = 2 (mod 3) [MOV1993]. These parameter choices are inferior for 439 cryptographic purposes and SHOULD NOT be used. 441 4. Elliptic Curve Diffie-Hellman (ECDH) 443 The Diffie-Hellman (DH) key exchange protocol [DH1976] allows two 444 parties communicating over an insecure channel to agree on a secret 445 key. It was originally defined in terms of operations in the 446 multiplicative group of a field with a large prime characteristic. 447 Massey [M1983] observed that it can be easily generalized so that it 448 is defined in terms of an arbitrary mathematical group. Miller 449 [M1985] and Koblitz [K1987] analyzed the DH protocol over an elliptic 450 curve group. We describe DH following the former reference. 452 Let G be a group, and g be a generator for that group, and let t 453 denote the order of G. The DH protocol runs as follows. Party A 454 chooses an exponent j between 1 and t-1, inclusive, uniformly at 455 random, computes g^j and sends that element to B. Party B chooses an 456 exponent k between 1 and t-1, inclusive, uniformly at random, 457 computes g^k and sends that element to A. Each party can compute 458 g^(j*k); party A computes (g^k)^j, and party B computes (g^j)^k. 460 See Appendix B regarding generation of random integers. 462 4.1. Data Types 464 An ECDH private key z is an integer in Zt. 466 The corresponding ECDH public key Y is the group element, where Y = 467 g^z. Each public key is associated with a particular particular 468 parameter set as per Section 3.3. 470 The shared secret computed by both parties is a group element. 472 Each run of the ECDH protocol is associated with a particular 473 parameter set, and both of the public keys and the shared secret are 474 elements of that group. 476 4.2. Compact Representation 478 As described in the final paragraph of [M1985], the x-coordinate of 479 the shared secret value g^(j*k) is a suitable representative for the 480 entire point whenever exponentiation is used as a one-way function. 481 In the ECDH key exchange protocol, after the element g^(j*k) has been 482 computed, the x-coordinate of that value can be used as the shared 483 secret. We call this compact output. 485 Following [M1985] again, when compact output is used in ECDH, only 486 the x-coordinate of an elliptic curve point needs to be transmitted, 487 instead of both coordinates as in the typical affine coordinate 488 representation. We call this the compact representation. Its 489 mathematical background is explained in Appendix C. 491 ECDH can be used with or without compact output. Both parties in a 492 particular run of the ECDH protocol MUST use the same method. ECDH 493 can be used with or without compact representation. If compact 494 representation is used in a particular run of the ECDH protocol, then 495 compact output MUST be used as well. 497 5. Elliptic Curve ElGamal Signatures 499 5.1. Background 501 The ElGamal signature algorithm was introduced in 1984 [E1984a] 502 [E1984b] [E1985]. It is based on the discrete logarithm problem, and 503 was originally defined for the multiplicative group of the integers 504 modulo a large prime number. It is straightforward to extend it to 505 use other finite groups, such as the multiplicative group of the 506 field GF(2^w) [AMV1990] or an elliptic curve group [A1992]. 508 An ElGamal signature consists of a pair of components. There are 509 many possible generalizations of ElGamal signature methods that have 510 been obtained by different rearrangements of the equation for the 511 second component; see [HMP1994], [HP1994], [NR1994], [A1992], and 512 [AMV1990]. These generalizations are independent of the mathematical 513 group used, and have been described for the multiplicative group 514 modulo a prime number, the multiplicative group of GF(2^w), and 515 elliptic curve groups [HMP1994][NR1994] [AMV1990][A1992]. 517 The Digital Signature Algorithm (DSA) [FIPS186] is an important 518 ElGamal signature variant. 520 5.2. Hash Functions 522 ElGamal signatures must use a collision-resistant hash function, so 523 that it can sign messages of arbitrary length and can avoid 524 existential forgery attacks; see Section 9.4. (This is true for all 525 ElGamal variants [HMP1994].) We denote the hash function as h(). 526 Its input is a bit string of arbitrary length, and its output is a 527 non-negative integer. 529 Let H() denote a hash function whose output is a fixed-length bit 530 string. To use H in an ElGamal signature method, we define the 531 mapping between that output and the non-negative integers; this 532 realizes the function h() described above. Given a bit string m, the 533 function h(m) is computed as follows: 535 1. H(m) is evaluated; the result is a fixed-length bit string. 537 2. Convert the resulting bit string to an integer i by treating its 538 leftmost (initial) bit as the most significant bit of i, and 539 treating its rightmost (final) bit as the least significant bit 540 of i. 542 5.3. KT-IV Signatures 544 Koyama and Tsuruoka described a signature method based on Elliptic 545 Curve ElGamal, in which the first signature component is the 546 x-coordinate of an elliptic curve point reduced modulo q [KT1994]. 547 In this section we recall that method, which we refer to as KT-IV. 549 The algorithm uses an elliptic curve group, as described in 550 Section 3.3, with prime field order p, and curve equation parameters 551 a and b. We denote the generator as alpha, and the order of the 552 generator as q. We follow [FIPS186] in checking for exceptional 553 cases. 555 5.3.1. Keypair Generation 557 The private key z is an integer between 1 and q - 1, inclusive, 558 generated uniformly at random. (See Appendix B regarding random 559 integers.) The public key is the group element 560 Y = alpha^z. Each public key is associated with a particular 561 particular parameter set as per Section 3.3. 563 5.3.2. Signature Creation 565 To compute a KT-IV signature for a message m using the private key z: 567 1. Choose an integer k uniformly at random from the set of all 568 integers between 1 and q-1, inclusive. (See Appendix B regarding 569 random integers.) 571 2. Calculate R = (r_x, r_y) = alpha^k. 573 3. Calculate s1 = r_x mod q. 575 4. Calculate s2 = k / (h(m) + z * s1) mod q. 577 5. As an option, one MAY check if s1 = 0 or s2 = 0. If either 578 s1 = 0 or s2 = 0, a new value of k SHOULD be generated and the 579 signature SHOULD be recalculated. (It is extremely unlikely that 580 s1 = 0 or s2 = 0 if signatures are generated properly.) 582 The signature is the ordered pair (s1, s2). Both signature 583 components are non-negative integers. 585 5.3.3. Signature Verification 587 Given the message m, the public key Y, and the signature (s1, s2) 588 verification is as follows: 590 1. Check to see that 0 < s1 < q and 0 < s2 < q; if either condition 591 is violated, the signature SHALL be rejected. 593 2. Compute the non-negative integers u1 and u2, where 595 u1 = h(m) * s2 mod q, and 597 u2 = s1 * s2 mod q. 599 3. Compute the elliptic curve point R' = alpha^u1 * Y^u2. 601 4. If the x-coordinate of R' mod q is equal to s1, then the 602 signature and message pass the verification; otherwise, they 603 fail. 605 5.4. KT-I Signatures 607 Horster, Michels, and Petersen categorized many different ElGamal 608 signature methods, demonstrated their equivalence, and showed how to 609 convert signatures of one type to another type [HMP1994]. In their 610 terminology, the signature method of Section 5.3 and [KT1994] is a 611 Type IV method, which is why it is denoted as KT-IV. 613 A Type I KT signature method has a second component that is computed 614 in the same manner as that of the Digital Signature Algorithm. In 615 this section, we describe this method, which we refer to as KT-I. 617 5.4.1. Keypair Generation 619 Keypairs and keypair generation are exactly as in Section 5.3.1. 621 5.4.2. Signature Creation 623 To compute a KT-I signature for a message m using the private key z: 625 1. Choose an integer k uniformly at random from the set of all 626 integers between 1 and q-1, inclusive. (See Appendix B regarding 627 random integers.) 629 2. Calculate R = (r_x, r_y) = alpha^k. 631 3. Calculate s1 = r_x mod q. 633 4. Calculate s2 = (h(m) + z * s1) / k mod q. 635 5. As an option, one MAY check if s1 = 0 or s2 = 0. If either 636 s1 = 0 or s2 = 0, a new value of k SHOULD be generated and the 637 signature SHOULD be recalculated. (It is extremely unlikely that 638 s1 = 0 or s2 = 0 if signatures are generated properly.) 640 The signature is the ordered pair (s1, s2). Both signature 641 components are non-negative integers. 643 5.4.3. Signature Verification 645 Given the message m, the public key Y, and the signature (s1, s2) 646 verification is as follows: 648 1. Check to see that 0 < s1 < q and 0 < s2 < q; if either condition 649 is violated the signature SHALL be rejected. 651 2. Compute s2_inv = 1 / s2 mod q. 653 3. Compute the non-negative integers u1 and u2, where 655 u1 = h(m) * s2_inv mod q, and 657 u2 = s1 * s2_inv mod q. 659 4. Compute the elliptic curve point R' = alpha^u1 * Y^u2. 661 5. If the x-coordinate of R' mod q is equal to s1, then the 662 signature and message pass the verification; otherwise, they 663 fail. 665 5.5. Converting KT-IV signatures to KT-I signatures 667 A KT-IV signature for a message m and a public key Y can easily be 668 converted into a KT-I signature for the same message and public key. 669 If (s1, s2) is a KT-IV signature for a message m, then 670 (s1, 1/s2 mod q) is a KT-I signature for the same message [HMP1994]. 672 The conversion operation uses only public information, and it can be 673 performed by the creator of the pre-conversion KT-IV signature, the 674 verifier of the post-conversion KT-I signature, or by any other 675 entity. 677 An implementation MAY use this method to compute KT-I signatures. 679 5.6. Rationale 681 This subsection is not normative for this specification and is 682 provided only as background information. 684 [HMP1994] presents many generalizations of ElGamal signatures. 685 Equation (5) of that reference shows the general signature equation 686 A = x_A * B + k * C (mod q) 688 where x_A is the private key, k is the secret value, and A, B, and C 689 are determined by the Type of the equation, as shown in Table 1 of 690 [HMP1994]. DSA [FIPS186] is an EG-I.1 signature method (as is KT-I), 691 with A = m, B = -r, and C = s. (Here we use the notation of 692 [HMP1994] in which the first signature component is r and the second 693 signature component is s; in KT-I and KT-IV these components are 694 denoted as s1 and s2 respectively. The private key x_A corresponds 695 to the private key z.) Its signature equation is 697 m = - r * z + s * k (mod q). 699 The signature method of [KT1994] and Section 5.3 is an EG-IV.1 700 method, with A = m * s, B = - r * s, C = 1. Its signature equation 701 is 703 m * s = - r * s * z + k (mod q) 705 The functions f and g mentioned in Table 1 are merely multiplication, 706 as described under the heading "Fifth generalization". 708 No hash function is shown in the above equations, but as described in 709 Section 9.4, a hash function should be applied to the message prior 710 to signing in order to prevent existential forgery attacks. 712 Nyberg and Rueppel [NR1994] studied many different ElGamal signature 713 methods, and defined "strong equivalence" as follows: 715 Two signature methods are called strongly equivalent if the 716 signature of the first scheme can be transformed efficiently into 717 signatures of the second scheme and vice versa, without knowledge 718 of the private key. 720 KT-I and KT-IV signatures are obviously strongly equivalent. 722 A valid signature with s2=0 leaks the secret key, since in that case 723 z = - h(m) / s1 mod q. We follow [FIPS186] in checking for this 724 exceptional case and the case that s1=0. The s2=0 check was 725 suggested by Rivest [R1992] and is discussed in [BS1992]. 727 [KT1994] uses "a positive integer q' that does not exceed q" when 728 computing the signature component s1 from the x-coordinate r_x of the 729 elliptic curve point R = (r_x, r_y). The value q' is also used 730 during signature validation when comparing the x-coordinate of a 731 computed elliptic curve point to the value to s1. In this note, we 732 use the simplifying convention that q' = q. 734 6. Interoperability 736 The algorithms in this note can be used to interoperate with some 737 other ECC specifications. This section provides details for each 738 algorithm. 740 6.1. ECDH 742 Section 4 can be used with the Internet Key Exchange (IKE) versions 743 one [RFC2409] or two [RFC4306]. These algorithms are compatible with 744 the ECP groups defined by [RFC4753], [RFC2409], and [RFC2412]. The 745 group definition used in this protocol uses an affine coordinate 746 representation of the public key and uses neither the compact output 747 nor the compact representation of Section 4.2. Note that some groups 748 use a negative curve parameter "a" and express this fact in the curve 749 equation rather than in the parameter. The test cases in Section 8 750 of [RFC4753] can be used to test an implementation; these cases use 751 the multiplicative notation, as does this note. The KEi and KEr 752 payloads are equal to g^j and g^k, respectively, with 64 bits of 753 encoding data prepended to them. 755 The algorithms in Section 4 can be used to interoperate with the IEEE 756 [P1363] and ANSI [X9.62] standards for ECDH based on fields of 757 characteristic greater than three. IEEE P1363 ECDH can be used in a 758 manner that will interoperate with this note, with the following 759 options and parameter choices from that specification: 761 prime curves with a cofactor of 1, 763 the ECSVDP-DH primitive, and 765 the Key Derivation Function must be the "identity" function 766 (equivalently, the KDF step should be omitted and the shared 767 secret value should be output directly). 769 6.2. KT-I and ECDSA 771 The Digital Signature Algorithm (DSA) is based on the discrete 772 logarithm problem over the multiplicative subgroup of the finite 773 field with large prime order [DSA1991][FIPS186]. The Elliptic Curve 774 Digital Signature Algorithm (ECDSA) [P1363] [X9.62] is an elliptic 775 curve version of DSA. 777 KT-I is mathematically and functionally equivalent to ECDSA, and can 778 interoperate with the IEEE [P1363] and ANSI [X9.62] standards for 779 Elliptic Curve DSA (ECDSA) based on fields of characteristic greater 780 than three. KT-I signatures can be verified using the ECDSA 781 verification algorithm, and ECDSA signatures can be verified using 782 the KT-I verification algorithm. 784 7. Validating an Implementation 786 It is essential to validate the implementation of a cryptographic 787 algorithm. This section outlines tests that should be performed on 788 the algorithms defined in this note. 790 A known answer test, or KAT, uses a fixed set of inputs to test an 791 algorithm; the output of the algorithm is compared with the expected 792 output, which is also a fixed value. KATs for ECDH and KT-I are set 793 out in the following subsections. 795 A consistency test generates inputs for one algorithm being tested 796 using a second algorithm that is also being tested, then checks the 797 output of the first algorithm. A signature creation algorithm can be 798 tested for consistency against a signature verification algorithm. 799 Implementations of KT-I should be tested in this way. Their 800 signature generation processes are non-deterministic, and thus cannot 801 be tested using a KAT. Signature verification algorithms, on the 802 other hand, are deterministic and should be tested via a KAT. This 803 combination of tests provides coverage for all of the operations, 804 including keypair generation. Consistency testing should also be 805 applied to ECDH. 807 7.1. ECDH 809 An ECDH implementation can be validated using the known answer test 810 cases from [RFC4753]. The correspondence between the notation in 811 that RFC and the notation in this note are summarized in the 812 following table. (Refer to Section 3.3 and Section 4), and express 813 the generator g in the affine coordinate representation as (gx, gy). 815 +----------------------+---------------------------------------+ 816 | ECDH | RFC 4753 | 817 +----------------------+---------------------------------------+ 818 | order p of field Fp | p | 819 | curve coefficient a | -3 | 820 | curve coefficient b | b | 821 | generator g | g=(gx, gy) | 822 | private keys j and k | i and r | 823 | public keys g^j, g^k | g^i = (gix, giy) and g^r = (grx, gry) | 824 +----------------------+---------------------------------------+ 826 7.2. KT-I 828 A KT-I implementation can be validated using the known answer test 829 cases from [RFC4754]. The correspondence between the notation in 830 that RFC and the notation in this note are summarized in the 831 following table. 833 +---------------------+------------------+ 834 | KT-I | RFC 4754 | 835 +---------------------+------------------+ 836 | order p of field Fp | p | 837 | curve coefficient a | -3 | 838 | curve coefficient b | b | 839 | generator alpha | g | 840 | group order q | q | 841 | private key z | w | 842 | public key Y | g^w = (gwx,gwy) | 843 | random k | ephem priv k | 844 | s1 | r | 845 | s2 | s | 846 | s2_inv | sinv | 847 | u1 | u = h*sinv mod q | 848 | u2 | v = r*sinv mod q | 849 +---------------------+------------------+ 851 8. Intellectual Property 853 Concerns about intellectual property have slowed the adoption of ECC, 854 because a number of optimizations and specialized algorithms have 855 been patented in recent years. 857 All of the normative references for ECDH (as defined in Section 4) 858 were published during or before 1989, and those for KT-I were 859 published during or before May, 1994. All of the normative text for 860 these algorithms is based solely on their respective references. 862 8.1. Disclaimer 864 This document is not intended as legal advice. Readers are advised 865 to consult their own legal advisers if they would like a legal 866 interpretation of their rights. 868 The IETF policies and processes regarding intellectual property and 869 patents are outlined in [RFC3979] and [RFC4879] and at 870 https://datatracker.ietf.org/ipr/about/. 872 9. Security Considerations 874 The security level of an elliptic curve cryptosystem is determined by 875 the cryptanalytic algorithm that is the least expensive for an 876 attacker to implement. There are several algorithms to consider. 878 The Pohlig-Hellman method is a divide-and-conquer technique [PH1978]. 879 If the group order n can be factored as 881 n = q1 * q2 * ... * qz, 883 then the discrete log problem over the group can be solved by 884 independently solving a discrete log problem in groups of order q1, 885 q2, ..., qz, then combining the results using the Chinese remainder 886 theorem. The overall computational cost is dominated by that of the 887 discrete log problem in the subgroup with the largest order. 889 Shanks algorithm [K1981v3] computes a discrete logarithm in a group 890 of order n using O(sqrt(n)) operations and O(sqrt(n)) storage. The 891 Pollard rho algorithm [P1978] computes a discrete logarithm in a 892 group of order n using O(sqrt(n)) operations, with a negligible 893 amount of storage, and can be efficiently parallelized [VW1994]. 895 The Pollard lambda algorithm [P1978] can solve the discrete logarithm 896 problem using O(sqrt(w)) operations and O(log(w)) storage, when the 897 exponent is known to lie in an interval of width w. 899 The algorithms described above work in any group. There are 900 specialized algorithms that specifically target elliptic curve 901 groups. There are no known subexponential algorithms against general 902 elliptic curve groups, though there are methods that target certain 903 special elliptic curve groups; see [MOV1993] and [FR1994]. 905 9.1. Subgroups 907 A group consisting of a nonempty set of elements S with associated 908 group operation * is a subgroup of the group with the set of elements 909 G, if the latter group uses the same group operation and S is a 910 subset of G. For each elliptic curve equation, there is an elliptic 911 curve group whose group order is equal to the order of the elliptic 912 curve; that is, there is a group that contains every point on the 913 curve. 915 The order m of the elliptic curve is divisible by the order n of the 916 group associated with the generator; that is, for each elliptic curve 917 group, m = n * c for some number c. The number c is called the 918 "cofactor" [P1363]. Each ECC parameter set as in Section 3.3 is 919 associated with a particular cofactor. 921 It is possible and desirable to use a cofactor equal to 1. 923 9.2. Diffie-Hellman 925 Note that the key exchange protocol as defined in Section 4 does not 926 protect against active attacks; Party A must use some method to 927 ensure that (g^k) originated with the intended communicant B, rather 928 than an attacker, and Party B must do the same with (g^j). 930 It is not sufficient to authenticate the shared secret g^(j*k), since 931 this leaves the protocol open to attacks that manipulate the public 932 keys. Instead, the values of the public keys g^x and g^y that are 933 exchanged should be directly authenticated. This is the strategy 934 used by protocols that build on Diffie-Hellman and which use end- 935 entity authentication to protect against active attacks, such as 936 OAKLEY [RFC2412] and the Internet Key Exchange [RFC2409][RFC4306]. 938 When the cofactor of a group is not equal to 1, there are a number of 939 attacks that are possible against ECDH. See [VW1996], [AV1996], and 940 [LL1997]. 942 9.3. Group Representation and Security 944 The elliptic curve group operation does not explicitly incorporate 945 the parameter b from the curve equation. This opens the possibility 946 that a malicious attacker could learn information about an ECDH 947 private key by submitting a bogus public key [BMM2000]. An attacker 948 can craft an elliptic curve group G' that has identical parameters to 949 a group G that is being used in an ECDH protocol, except that b is 950 different. An attacker can submit a point on G' into a run of the 951 ECDH protocol that is using group G, and gain information from the 952 fact that the group operations using the private key of the device 953 under attack are effectively taking place in G' instead of G. 955 This attack can gain useful information about an ECDH private key 956 that is associated with a static public key, that is, a public key 957 that is used in more than one run of the protocol. However, it does 958 not gain any useful information against ephemeral keys. 960 This sort of attack is thwarted if an ECDH implementation does not 961 assume that each pair of coordinates in Zp is actually a point on the 962 appropriate elliptic curve. 964 These considerations also apply when ECDH is used with compact 965 representation (see Appendix C). 967 9.4. Signatures 969 Elliptic curve parameters should only be used if they come from a 970 trusted source; otherwise, some attacks are possible [AV1996], 971 [V1996]. 973 If no hash function is used in an ElGamal signature system, then the 974 system is vulnerable to existential forgeries, in which an attacker 975 who does not know a private key can generate valid signatures for the 976 associated public key, but cannot generate a signature for a message 977 of its own choosing. (See [E1985] for instance.) The use of a 978 collision-resistant hash function eliminates this vulnerability. 980 In principle, any collision-resistant hash function is suitable for 981 use in KT signatures. To facilitate interoperability, we recognize 982 the following hashes as suitable for use as the function H defined in 983 Section 5.2: 985 SHA-256, which has a 256-bit output. 987 SHA-384, which has a 384-bit output. 989 SHA-512, which has a 512-bit output. 991 All of these hash functions are defined in [FIPS180-2]. 993 The number of bits in the output of the hash used in KT signatures 994 should be equal or close to the number of bits needed to represent 995 the group order. 997 10. IANA Considerations 999 This note has no actions for IANA. This section should be removed by 1000 the RFC editor before publication as an RFC. 1002 11. Acknowledgements 1004 The author expresses his thanks to the originators of elliptic curve 1005 cryptography, whose work made this note possible, and all of the 1006 reviewers, who provided valuable constructive feedback. Thanks are 1007 especially due to Howard Pinder and Andrey Jivsov. 1009 12. References 1010 12.1. Normative References 1012 [AMV1990] Agnew, G., Mullin, R., and S. Vanstone, "Improved Digital 1013 Signature Scheme based on Discrete Exponentiation", 1014 Electronics Letters Vol. 26, No. 14, July, 1990. 1016 [BC1989] Bender, A. and G. Castagnoli, "On the Implementation of 1017 Elliptic Curve Cryptosystems", Advances in Cryptology - 1018 CRYPTO '89 Proceedings Spinger Lecture Notes in Computer 1019 Science (LNCS) volume 435, 1989. 1021 [CC1986] Chudnovsky, D. and G. Chudnovsky, "Sequences of numbers 1022 generated by addition in formal groups and new primality 1023 and factorization tests", Advances in Applied 1024 Mathematics Volume 7, Issue 4, December 1986. 1026 [D1966] Deskins, W., "Abstract Algebra", MacMillan Company New 1027 York, 1966. 1029 [DH1976] Diffie, W. and M. Hellman, "New Directions in 1030 Cryptography", IEEE Transactions in Information 1031 Theory IT-22, pp 644-654, 1976. 1033 [FR1994] Frey, G. and H. Ruck, "A remark concerning m-divisibility 1034 and the discrete logarithm in the divisor class group of 1035 curves.", Mathematics of Computation Vol. 62, No. 206, pp. 1036 865-874, 1994. 1038 [HMP1994] Horster, P., Michels, M., and H. Petersen, "Meta-ElGamal 1039 signature schemes", University of Technology Chemnitz- 1040 Zwickau Department of Computer Science Technical 1041 Report TR-94-5, May 1994. 1043 [K1981v2] Knuth, D., "The Art of Computer Programming, Vol. 2: 1044 Seminumerical Algorithms", Addison Wesley , 1981. 1046 [K1987] Koblitz, N., "Elliptic Curve Cryptosystems", Mathematics 1047 of Computation Vol. 48, 1987, 203-209, 1987. 1049 [KT1994] Koyama, K. and Y. Tsuruoka, "Digital signature system 1050 based on elliptic curve and signer device and verifier 1051 device for said system", Japanese Unexamined Patent 1052 Application Publication H6-43809, February 18, 1994. 1054 [M1983] Massey, J., "Logarithms in finite cyclic groups - 1055 cryptographic issues", Proceedings of the 4th Symposium on 1056 Information Theory , 1983. 1058 [M1985] Miller, V., "Use of elliptic curves in cryptography", 1059 Advances in Cryptology - CRYPTO '85 Proceedings Springer 1060 Lecture Notes in Computer Science (LNCS) volume 218, 1985. 1062 [MOV1993] Menezes, A., Vanstone, S., and T. Okamoto, "Reducing 1063 Elliptic Curve Logarithms to Logarithms in a Finite 1064 Field", IEEE Transactions on Information Theory Vol 39, 1065 No. 5, pp. 1639-1646, September, 1993. 1067 12.2. Informative References 1069 [A1992] Anderson, J., "Response to the proposed DSS", 1070 Communications of the ACM v.35 n.7 p.50-52, July 1992. 1072 [AV1996] Anderson, R. and S. Vaudenay, "Minding Your P's and Q's", 1073 Advances in Cryptology - ASIACRYPT '96 Proceedings Spinger 1074 Lecture Notes in Computer Science (LNCS) volume 1163, 1075 1996. 1077 [BMM2000] Biehl, I., Meyer, B., and V. Muller, "Differential fault 1078 analysis on elliptic curve cryptosystems", Advances in 1079 Cryptology - CRYPTO 2000 Proceedings Spinger Lecture Notes 1080 in Computer Science (LNCS) volume 1880, 2000. 1082 [BS1992] Branstad, D. and M. Smid, "Response to Comments on the 1083 NIST Proposed Digital Signature Standard", Advances in 1084 Cryptology - CRYPTO '92 Proceedings Springer Lecture Notes 1085 in Computer Science (LNCS) volume 740, August 1992. 1087 [DSA1991] "DIGITAL SIGNATURE STANDARD", Federal Register Vol. 56, 1088 August 1991. 1090 [E1984a] ElGamal, T., "Cryptography and logarithms over finite 1091 fields", Stanford University UMI Order No. DA 8420519, 1092 1984. 1094 [E1984b] ElGamal, T., "Cryptography and logarithms over finite 1095 fields", Advances in Cryptology - CRYPTO '84 1096 Proceedings Springer Lecture Notes in Computer Science 1097 (LNCS) volume 196, 1984. 1099 [E1985] ElGamal, T., "A public key cryptosystem and a signature 1100 scheme based on discrete logarithms", IEEE Transactions on 1101 Information Theory Vol 30, No. 4, pp. 469-472, 1985. 1103 [FIPS180-2] 1104 "SECURE HASH STANDARD", Federal Information Processing 1105 Standard (FIPS) 180-2, August 2002. 1107 [FIPS186] "DIGITAL SIGNATURE STANDARD", Federal Information 1108 Processing Standard FIPS-186, May 1994. 1110 [HP1994] Horster, P. and H. Petersen, "Verallgemeinerte ElGamal- 1111 Signaturen", Proceedings der Fachtagung SIS '94, Verlag 1112 der Fachvereine Zurich, 1994. 1114 [K1981v3] Knuth, D., "The Art of Computer Programming, Vol. 3: 1115 Sorting and Searching", Addison Wesley , 1981. 1117 [KMOV1991] 1118 Koyama, K., Maurer, U., Vanstone, S., and T. Okamoto, "New 1119 Public-Key Schemes Based on Elliptic Curves over the Ring 1120 Zn", Advances in Cryptology - CRYPTO '91 1121 Proceedings Spinger Lecture Notes in Computer Science 1122 (LNCS) volume 576, 1991. 1124 [L1969] "Computer technology applied to the theory of numbers", 1125 M.A.A. Studies in Mathematics 180-2, 1969. 1127 [LL1997] Lim, C. and P. Lee, "A Key Recovery Attack on Discrete 1128 Log-based Schemes Using a Prime Order Subgroup", Advances 1129 in Cryptology - CRYPTO '97 Proceedings Spinger Lecture 1130 Notes in Computer Science (LNCS) volume 1294, 1997. 1132 [NR1994] Nyberg, K. and R. Rueppel, "Message Recovery for Signature 1133 Schemes Based on the Discrete Logarithm Problem", Advances 1134 in Cryptology - EUROCRYPT '94 Proceedings Springer Lecture 1135 Notes in Computer Science (LNCS) volume 950, May 1994. 1137 [P1363] "Standard Specifications for Public Key Cryptography", 1138 Institute of Electric and Electronic Engineers 1139 (IEEE) P1363, 2000. 1141 [P1978] Pollard, J., "Monte Carlo methods for index computation 1142 mod p", Mathematics of Computation Vol. 32, 1978. 1144 [PH1978] Pohlig, S. and M. Hellman, "An Improved Algorithm for 1145 Computing Logarithms over GF(p) and its Cryptographic 1146 Significance", IEEE Transactions on Information Theory Vol 1147 24, pp. 106-110, 1978. 1149 [R1988] Rose, H., "A Course in Number Theory", Oxford University 1150 Press , 1988. 1152 [R1992] Rivest, R., "Response to the proposed DSS", Communications 1153 of the ACM v.35 n.7 p.41-47., July 1992. 1155 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1156 Requirement Levels", BCP 14, RFC 2119, March 1997. 1158 [RFC2409] Harkins, D. and D. Carrel, "The Internet Key Exchange 1159 (IKE)", RFC 2409, November 1998. 1161 [RFC2412] Orman, H., "The OAKLEY Key Determination Protocol", 1162 RFC 2412, November 1998. 1164 [RFC3979] Bradner, S., "Intellectual Property Rights in IETF 1165 Technology", BCP 79, RFC 3979, March 2005. 1167 [RFC4086] Eastlake, D., Schiller, J., and S. Crocker, "Randomness 1168 Requirements for Security", BCP 106, RFC 4086, June 2005. 1170 [RFC4306] Kaufman, C., "Internet Key Exchange (IKEv2) Protocol", 1171 RFC 4306, December 2005. 1173 [RFC4753] Fu, D. and J. Solinas, "ECP Groups For IKE and IKEv2", 1174 RFC 4753, January 2007. 1176 [RFC4754] Fu, D. and J. Solinas, "IKE and IKEv2 Authentication Using 1177 the Elliptic Curve Digital Signature Algorithm (ECDSA)", 1178 RFC 4754, January 2007. 1180 [RFC4879] Narten, T., "Clarification of the Third Party Disclosure 1181 Procedure in RFC 3979", BCP 79, RFC 4879, April 2007. 1183 [SuiteB] "NSA Suite B Cryptography", Web Page http://www.nsa.gov/ 1184 ia/programs/suiteb_cryptography/index.shtml. 1186 [V1996] Vaudenay, S., "Hidden Collisions on DSS", Advances in 1187 Cryptology - CRYPTO '96 Proceedings Spinger Lecture Notes 1188 in Computer Science (LNCS) volume 1109, 1996. 1190 [VW1994] van Oorschot, P. and M. Wiener, "Parallel Collision Search 1191 with Application to Hash Functions and Discrete 1192 Logarithms", Proceedings of the 2nd ACM Conference on 1193 Computer and communications security pp. 210-218, 1994. 1195 [VW1996] van Oorschot, P. and M. Wiener, "On Diffie-Hellman key 1196 agreement with short exponents", Advances in Cryptology - 1197 EUROCRYPT '96 Proceedings Spinger Lecture Notes in 1198 Computer Science (LNCS) volume 1070, 1996. 1200 [X9.62] "Public Key Cryptography for the Financial Services 1201 Industry: The Elliptic Curve Digital Signature Algorithm 1202 (ECDSA)", American National Standards Institute (ANSI) 1203 X9.62. 1205 Appendix A. Key Words 1207 The definitions of these key words are quoted from [RFC2119] and are 1208 commonly used in Internet standards. They are reproduced in this 1209 note in order to avoid a normative reference from after 1994. 1211 1. MUST - This word, or the terms "REQUIRED" or "SHALL", mean that 1212 the definition is an absolute requirement of the specification. 1214 2. MUST NOT - This phrase, or the phrase "SHALL NOT", mean that the 1215 definition is an absolute prohibition of the specification. 1217 3. SHOULD - This word, or the adjective "RECOMMENDED", mean that 1218 there may exist valid reasons in particular circumstances to 1219 ignore a particular item, but the full implications must be 1220 understood and carefully weighed before choosing a different 1221 course. 1223 4. SHOULD NOT - This phrase, or the phrase "NOT RECOMMENDED" mean 1224 that there may exist valid reasons in particular circumstances 1225 when the particular behavior is acceptable or even useful, but 1226 the full implications should be understood and the case carefully 1227 weighed before implementing any behavior described with this 1228 label. 1230 5. MAY - This word, or the adjective "OPTIONAL", mean that an item 1231 is truly optional. One vendor may choose to include the item 1232 because a particular marketplace requires it or because the 1233 vendor feels that it enhances the product while another vendor 1234 may omit the same item. An implementation which does not include 1235 a particular option MUST be prepared to interoperate with another 1236 implementation which does include the option, though perhaps with 1237 reduced functionality. In the same vein an implementation which 1238 does include a particular option MUST be prepared to interoperate 1239 with another implementation which does not include the option 1240 (except, of course, for the feature the option provides.) 1242 Appendix B. Random Integer Generation 1244 It is easy to generate an integer uniformly at random between zero 1245 and 2^t -1, inclusive, for some positive integer t. Generate a 1246 random bit string that contains exactly t bits, and then convert the 1247 bit string to a non-negative integer by treating the bits as the 1248 coefficients in a base-two expansion of an integer. 1250 It is sometimes necessary to generate an integer r uniformly at 1251 random so that r satisfies a certain property P, for example, lying 1252 within a certain interval. A simple way to do this is with the 1253 rejection method: 1255 1. Generate a candidate number c uniformly at random from a set that 1256 includes all numbers that satisfy property P (plus some other 1257 numbers, preferably not too many) 1259 2. If c satisfies property P, then return c. Otherwise, return to 1260 Step 1. 1262 For example, to generate a number between 1 and n-1, inclusive, 1263 repeatedly generate integers between zero and 2^t - 1, inclusive, 1264 stopping at the first integer that falls within that interval. 1266 Recommendations on how to generate random bit strings are provided in 1267 [RFC4086]. 1269 Appendix C. Why Compact Representation Works 1271 In the affine representation, the x-coordinate of the point P^i does 1272 not depend on the y-coordinate of the point P, for any non-negative 1273 exponent i and any point P. This fact can be seen as follows. When 1274 given only the x-coordinate of a point P, it is not possible to 1275 determine exactly what the y-coordinate is, but the y value will be a 1276 solution to the curve equation 1278 y^2 = x^3 + a*x + b (mod p). 1280 There are at most two distinct solutions y = w and y = -w mod p, and 1281 the point P must be either Q=(x,w) or Q^-1=(x,-w). Thus P^n is equal 1282 to either Q^n or (Q^-1)^n = (Q^n)^-1. These values have the same 1283 x-coordinate. Thus, the x-coordinate of a point P^i can be computed 1284 from the x-coordinate of a point P by computing one of the possible 1285 values of the y coordinate of P, then computing the ith power of P, 1286 and then ignoring the y-coordinate of that result. 1288 In general, it is possible to compute a square root modulo p by using 1289 Shanks's method [K1987]; simple methods exist for some values of p. 1290 When p = 3 (mod 4), the square roots of z mod p are w and -w mod p, 1291 where 1293 w = z ^ ((p+1)/4) (mod p); 1295 this observation is due to Lehmer [L1969]. When p satisfies this 1296 property, y can be computed from the curve equation, and either y = w 1297 or y = -w mod p, where 1299 w = (x^3 + a*x + b)^((p+1)/4) (mod p). 1301 Square roots modulo p only exist for a quadratic residue modulo p, 1302 [R1988]; if z is not a quadratic residue, then there is no number w 1303 such that w^2 = z (mod p). A simple way to verify that z is a 1304 quadratic residue after computing w is to verify that 1305 w * w = z (mod p). If this relation does not hold for the above 1306 equation, then the value x is not a valid x-coordinate for a valid 1307 elliptic curve point. This is an important consideration when ECDH 1308 is used with compact output; see Section 9.3. 1310 The primes used in the P-256, P-384, and P-521 curves described in 1311 [RFC4753] all have the property that p = 3 (mod 4). 1313 Appendix D. Example ECC Parameter Set 1315 For concreteness, we recall an elliptic curve defined by Solinas and 1316 Fu in [RFC4753] and referred to as P-256, which is believed to 1317 provide a 128-bit security level. We use the notation of 1318 Section 3.3, and express the generator in the affine coordinate 1319 representation g=(gx,gy), where the values gx and gy are in Fp. 1321 p: FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF 1323 a: - 3 1325 b: 5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B 1327 n: FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551 1329 gx: 6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296 1331 gy: 4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5 1333 Note that p can also be expressed as 1335 p = 2^(256)-2^(224)+2^(192)+2^(96)-1. 1337 Appendix E. Additive and multiplicative notation 1339 The early publications on elliptic curve cryptography used 1340 multiplicative notation, but most modern publications use additive 1341 notation. This section includes a table mapping between those two 1342 conventions. In this section, a and b are elements of an elliptic 1343 curve group, and N is an integer. 1345 +-------------------------+-----------------------+ 1346 | Multiplicative Notation | Additive Notation | 1347 +-------------------------+-----------------------+ 1348 | multiplication | addition | 1349 | a * b | a + b | 1350 | squaring | doubling | 1351 | a * a = a^2 | a + a = 2a | 1352 | exponentiation | scalar multiplication | 1353 | a^N = a * a * ... * a | Na = a + a + ... + a | 1354 | inverse | inverse | 1355 | a^-1 | -a | 1356 +-------------------------+-----------------------+ 1358 Authors' Addresses 1360 David A. McGrew 1361 Cisco Systems 1362 510 McCarthy Blvd. 1363 Milpitas, CA 95035 1364 USA 1366 Phone: (408) 525 8651 1367 Email: mcgrew@cisco.com 1368 URI: http://www.mindspring.com/~dmcgrew/dam.htm 1370 Kevin M. Igoe 1371 National Security Agency 1372 Commercial Solutions Center 1373 United States of America 1375 Email: kmigoe@nsa.gov