idnits 2.17.1 draft-hoffman-rfc6090bis-02.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 : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The abstract seems to contain references ([RFC6090]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. -- The draft header indicates that this document obsoletes RFC6090, but the abstract doesn't seem to directly say this. It does mention RFC6090 though, so this could be OK. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == 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 (June 29, 2015) is 3224 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) -- Obsolete informational reference (is this intentional?): RFC 5996 (Obsoleted by RFC 7296) Summary: 2 errors (**), 0 flaws (~~), 2 warnings (==), 8 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 Obsoletes: 6090 (if approved) K. Igoe 5 Intended status: Informational M. Salter 6 Expires: December 31, 2015 National Security Agency 7 P. Hoffman 8 VPN Consortium 9 June 29, 2015 11 Fundamental Elliptic Curve Cryptography Algorithms 12 draft-hoffman-rfc6090bis-02 14 Abstract 16 This note describes the fundamental algorithms of Elliptic Curve 17 Cryptography (ECC) as they were defined in some seminal references 18 from 1994 and earlier. These descriptions may be useful for 19 implementing the fundamental algorithms without using any of the 20 specialized methods that were developed in following years. Only 21 elliptic curves defined over fields of characteristic greater than 22 three are in scope; these curves are those used in Suite B. 24 This version of the note incorporates errata that were reported on 25 RFC 6090 [RFC6090]. 27 Status of This Memo 29 This Internet-Draft is submitted in full conformance with the 30 provisions of BCP 78 and BCP 79. 32 Internet-Drafts are working documents of the Internet Engineering 33 Task Force (IETF). Note that other groups may also distribute 34 working documents as Internet-Drafts. The list of current Internet- 35 Drafts is at http://datatracker.ietf.org/drafts/current/. 37 Internet-Drafts are draft documents valid for a maximum of six months 38 and may be updated, replaced, or obsoleted by other documents at any 39 time. It is inappropriate to use Internet-Drafts as reference 40 material or to cite them other than as "work in progress." 42 This Internet-Draft will expire on December 31, 2015. 44 Copyright Notice 46 Copyright (c) 2015 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 Simplified BSD License. 59 Table of Contents 61 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 62 1.1. Conventions Used in This Document . . . . . . . . . . . . 4 63 2. Mathematical Background . . . . . . . . . . . . . . . . . . . 4 64 2.1. Modular Arithmetic . . . . . . . . . . . . . . . . . . . 4 65 2.2. Group Operations . . . . . . . . . . . . . . . . . . . . 5 66 2.3. The Finite Field Fp . . . . . . . . . . . . . . . . . . . 6 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. Discriminant . . . . . . . . . . . . . . . . . . . . 10 72 3.3.2. Security . . . . . . . . . . . . . . . . . . . . . . 10 73 4. Elliptic Curve Diffie-Hellman (ECDH) . . . . . . . . . . . . 10 74 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 11 75 4.2. Compact Representation . . . . . . . . . . . . . . . . . 11 76 5. Elliptic Curve ElGamal Signatures . . . . . . . . . . . . . . 11 77 5.1. Background . . . . . . . . . . . . . . . . . . . . . . . 11 78 5.2. Hash Functions . . . . . . . . . . . . . . . . . . . . . 12 79 5.3. KT-IV Signatures . . . . . . . . . . . . . . . . . . . . 12 80 5.3.1. Keypair Generation . . . . . . . . . . . . . . . . . 13 81 5.3.2. Signature Creation . . . . . . . . . . . . . . . . . 13 82 5.3.3. Signature Verification . . . . . . . . . . . . . . . 13 83 5.4. KT-I Signatures . . . . . . . . . . . . . . . . . . . . . 14 84 5.4.1. Keypair Generation . . . . . . . . . . . . . . . . . 14 85 5.4.2. Signature Creation . . . . . . . . . . . . . . . . . 14 86 5.4.3. Signature Verification . . . . . . . . . . . . . . . 14 87 5.5. Converting KT-IV Signatures to KT-I Signatures . . . . . 15 88 5.6. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 15 89 6. Converting between Integers and Octet Strings . . . . . . . . 16 90 6.1. Octet-String-to-Integer Conversion . . . . . . . . . . . 17 91 6.2. Integer-to-Octet-String Conversion . . . . . . . . . . . 17 92 7. Interoperability . . . . . . . . . . . . . . . . . . . . . . 17 93 7.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . 17 94 7.2. KT-I and ECDSA . . . . . . . . . . . . . . . . . . . . . 18 95 8. Validating an Implementation . . . . . . . . . . . . . . . . 18 96 8.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . 19 97 8.2. KT-I . . . . . . . . . . . . . . . . . . . . . . . . . . 20 98 9. Intellectual Property . . . . . . . . . . . . . . . . . . . . 20 99 9.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . 21 100 10. Security Considerations . . . . . . . . . . . . . . . . . . . 21 101 10.1. Subgroups . . . . . . . . . . . . . . . . . . . . . . . 22 102 10.2. Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . 22 103 10.3. Group Representation and Security . . . . . . . . . . . 22 104 10.4. Signatures . . . . . . . . . . . . . . . . . . . . . . . 23 105 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 24 106 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 24 107 12.1. Normative References . . . . . . . . . . . . . . . . . . 24 108 12.2. Informative References . . . . . . . . . . . . . . . . . 25 109 Appendix A. Key Words . . . . . . . . . . . . . . . . . . . . . 29 110 Appendix B. Random Integer Generation . . . . . . . . . . . . . 29 111 Appendix C. Why Compact Representation Works . . . . . . . . . . 30 112 Appendix D. Example ECC Parameter Set . . . . . . . . . . . . . 31 113 Appendix E. Additive and Multiplicative Notation . . . . . . . . 31 114 Appendix F. Algorithms . . . . . . . . . . . . . . . . . . . . . 32 115 F.1. Affine Coordinates . . . . . . . . . . . . . . . . . . . 32 116 F.2. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 33 117 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 34 119 1. Introduction 121 ECC is a public-key technology that offers performance advantages at 122 higher security levels. It includes an elliptic curve version of the 123 Diffie-Hellman key exchange protocol [DH1976] and elliptic curve 124 versions of the ElGamal Signature Algorithm [E1985]. The adoption of 125 ECC has been slower than had been anticipated, perhaps due to the 126 lack of freely available normative documents and uncertainty over 127 intellectual property rights. 129 This note contains a description of the fundamental algorithms of ECC 130 over finite fields with characteristic greater than three, based 131 directly on original references. Its intent is to provide the 132 Internet community with a summary of the basic algorithms that 133 predate any specialized or optimized algorithms. The summary is 134 detailed enough for use as a normative reference. The original 135 descriptions and notations were followed as closely as possible. 137 This version of the note incorporates verified errata that were 138 reported against RFC 6090. Paragraphs or artwork that has errata 139 applied are marked with "%%%". Thise markings will be removed when 140 this document is published as an RFC. 142 There are several standards that specify or incorporate ECC 143 algorithms, including the Internet Key Exchange (IKE), ANSI X9.62, 144 and IEEE P1363. The algorithms in this note can interoperate with 145 some of the algorithms in these standards, with a suitable choice of 146 parameters and options. The specifics are itemized in Section 7. 148 The rest of the note is organized as follows. Sections 2.1, 2.2, and 149 2.3 furnish the necessary terminology and notation from modular 150 arithmetic, group theory, and the theory of finite fields, 151 respectively. Section 3 defines the groups based on elliptic curves 152 over finite fields of characteristic greater than three. Section 4 153 presents the fundamental Elliptic Curve Diffie-Hellman (ECDH) 154 algorithm. Section 5 presents elliptic curve versions of the ElGamal 155 signature method. The representation of integers as octet strings is 156 specified in Section 6. Sections 2 through 6, inclusive, contain all 157 of the normative text (the text that defines the norm for 158 implementations conforming to this specification), and all of the 159 following sections are purely informative. Interoperability is 160 discussed in Section 7. Validation testing is described in 161 Section 8. Section 9 reviews intellectual property issues. 162 Section 10 summarizes security considerations. Appendix B describes 163 random number generation, and other appendices provide clarifying 164 details. 166 1.1. Conventions Used in This Document 168 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 169 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 170 document are to be interpreted as described in Appendix A. 172 2. Mathematical Background 174 This section reviews mathematical preliminaries and establishes 175 terminology and notation that are used below. 177 2.1. Modular Arithmetic 179 This section reviews modular arithmetic. Two integers x and y are 180 said to be congruent modulo n if x - y is an integer multiple of n. 182 Two integers x and y are coprime when their greatest common divisor 183 is 1; in this case, there is no third number z > 1 such that z 184 divides x and z divides y. 186 The set Zq = { 0, 1, 2, ..., q-1 } is closed under the operations of 187 modular addition, modular subtraction, modular multiplication, and 188 modular inverse. These operations are as follows. 190 For each pair of integers a and b in Zq, a + b mod q is equal to 191 a + b if a + b < q, and is equal to a + b - q otherwise. 193 For each pair of integers a and b in Zq, a - b mod q is equal to 194 a - b if a - b >= 0, and is equal to a - b + q otherwise. 196 For each pair of integers a and b in Zq, a * b mod q is equal to 197 the remainder of a * b divided by q. 199 For each integer x in Zq that is coprime with q, the inverse of x 200 modulo q is denoted as 1/x mod q, and can be computed using the 201 extended Euclidean algorithm (see Section 4.5.2 of [K1981v2], for 202 example). 204 Algorithms for these operations are well known; for instance, see 205 Chapter 4 of [K1981v2]. 207 2.2. Group Operations 209 This section establishes some terminology and notation for 210 mathematical groups, which are needed later on. Background 211 references abound; see [D1966], for example. 213 A group is a set of elements G together with an operation that 214 combines any two elements in G and returns a third element in G. The 215 operation is denoted as * and its application is denoted as a * b, 216 for any two elements a and b in G. The operation is associative, 217 that is, for all a, b, and c in G, a * (b * c) is identical to (a * 218 b) * c. Repeated application of the group operation N-1 times to the 219 element a is denoted as a^N, for any element a in G and any positive 220 integer N. That is, a^2 = a * a, a^3 = a * a * a, and so on. The 221 associativity of the group operation ensures that the computation of 222 a^n is unambiguous; any grouping of the terms gives the same result. 224 %%% The above definition of a group operation uses multiplicative 225 notation. Sometimes an alternative called additive notation is used, 226 in which a * b is denoted as a + b, and a^N is denoted as Na. In 227 multiplicative notation, a^N is called exponentiation, while the 228 equivalent operation in additive notation is called scalar 229 multiplication. In this document, multiplicative notation is used 230 throughout for consistency. Appendix E elucidates the correspondence 231 between the two notations. 233 %%% Every group has a special element called the identity element, 234 which we denote as e. For each element a in G, e * a = a * e = a. 235 By convention, a^0 is equal to the identity element and a^1 is equal 236 to a itself for any a in G. 238 Every group element a has a unique inverse element b such that 239 a * b = b * a = e. The inverse of a is denoted as a^-1 in 240 multiplicative notation. (In additive notation, the inverse of a is 241 denoted as -a.) 243 For any positive integer X, a^(-X) is defined to be (a^-1)^(X). 244 Using this convention, exponentiation behaves as one would expect, 245 namely for any integers X and Y: 247 a^(X+Y) = (a^X)*(a^Y) 249 (a^X)^Y = a^(XY) = (a^Y)^X. 251 In cryptographic applications, one typically deals with finite groups 252 (groups with a finite number of elements), and for such groups, the 253 number of elements of the group is also called the order of the 254 group. A group element a is said to have finite order if a^X = e for 255 some positive integer X, and the order of a is the smallest such X. 256 If no such X exists, a is said to have infinite order. All elements 257 of a finite group have a finite order, and the order of an element is 258 always a divisor of the group order. 260 If a group element a has order R, then for any integers X and Y, 262 a^X = a^(X mod R), 264 a^X = a^Y if and only if X is congruent to Y mod R, 266 the set H = { a, a^2, a^3, ... , a^R=e } forms a subgroup of G, 267 called the cyclic subgroup generated by a, and a is said to be a 268 generator of H. 270 %%% Typically, there are several group elements that generate H. Any 271 group element of the form a^M, with M relatively prime to R, also 272 generates H. Note that a^M is equal to a^(M mod R) for any non- 273 negative integer M. 275 Given the element a of order R, and an integer i between 1 and R-1, 276 inclusive, the element a^i can be computed by the "square and 277 multiply" method outlined in Section 2.1 of [M1983] (see also Knuth, 278 Vol. 2, Section 4.6.3), or other methods. 280 2.3. The Finite Field Fp 282 This section establishes terminology and notation for finite fields 283 with prime characteristic. 285 When p is a prime number, then the set Zp, with the addition, 286 subtraction, multiplication, and division operations, is a finite 287 field with characteristic p. Each nonzero element x in Zp has an 288 inverse 1/x. There is a one-to-one correspondence between the 289 integers between zero and p-1, inclusive, and the elements of the 290 field. The field Zp is sometimes denoted as Fp or GF(p). 292 Equations involving field elements do not explicitly denote the "mod 293 p" operation, but it is understood to be implicit. For example, the 294 statement that x, y, and z are in Fp and 296 z = x + y 298 is equivalent to the statement that x, y, and z are in the set 299 { 0, 1, ..., p-1 } and 301 z = x + y mod p. 303 3. Elliptic Curve Groups 305 This note only covers elliptic curves over fields with characteristic 306 greater than three; these are the curves used in Suite B [SuiteB]. 307 For other fields, the definition of the elliptic curve group would be 308 different. 310 An elliptic curve over a field Fp is defined by the curve equation 312 y^2 = x^3 + a*x + b, 314 where x, y, a, and b are elements of the field Fp [M1985], and the 315 discriminant is nonzero (as described in Section 3.3.1). A point on 316 an elliptic curve is a pair (x,y) of values in Fp that satisfies the 317 curve equation, or it is a special point (@,@) that represents the 318 identity element (which is called the "point at infinity"). The 319 order of an elliptic curve group is the number of distinct points. 321 Two elliptic curve points (x1,y1) and (x2,y2) are equal whenever 322 x1=x2 and y1=y2, or when both points are the point at infinity. The 323 inverse of the point (x1,y1) is the point (x1,-y1). The point at 324 infinity is its own inverse. 326 The group operation associated with the elliptic curve group is as 327 follows [BC1989]. To an arbitrary pair of points P and Q specified 328 by their coordinates (x1,y1) and (x2,y2), respectively, the group 329 operation assigns a third point P*Q with the coordinates (x3,y3). 330 These coordinates are computed as follows: 332 (x3,y3) = (@,@) when P is not equal to Q and x1 is equal to x2. 334 x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 and 335 y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 when P is not equal to Q and 336 x1 is not equal to x2. 338 (x3,y3) = (@,@) when P is equal to Q and y1 is equal to 0. 340 x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 and 341 y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y1 if P is equal to Q and y1 is 342 not equal to 0. 344 In the above equations, a, x1, x2, x3, y1, y2, and y3 are elements of 345 the field Fp; thus, computation of x3 and y3 in practice must reduce 346 the right-hand-side modulo p. Pseudocode for the group operation is 347 provided in Appendix F.1. 349 The representation of elliptic curve points as a pair of integers in 350 Zp is known as the affine coordinate representation. This 351 representation is suitable as an external data representation for 352 communicating or storing group elements, though the point at infinity 353 must be treated as a special case. 355 Some pairs of integers are not valid elliptic curve points. A valid 356 pair will satisfy the curve equation, while an invalid pair will not. 358 3.1. Homogeneous Coordinates 360 An alternative way to implement the group operation is to use 361 homogeneous coordinates [K1987] (see also [KMOV1991]). This method 362 is typically more efficient because it does not require a modular 363 inversion operation. 365 An elliptic curve point (x,y) (other than the point at infinity 366 (@,@)) is equivalent to a point (X,Y,Z) in homogeneous coordinates 367 whenever x=X/Z mod p and y=Y/Z mod p. 369 Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on an elliptic curve, 370 and suppose that the points P1 and P2 are not equal to (@,@), P1 is 371 not equal to P2, and P1 is not equal to P2^-1. Then the product 372 P3=(X3,Y3,Z3) = P1 * P2 is given by 374 X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3) mod p 376 Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3 mod p 378 Z3 = v^3 * Z1 * Z2 mod p 380 where u = Y2 * Z1 - Y1 * Z2 mod p and v = X2 * Z1 - X1 * Z2 mod p. 382 When the points P1 and P2 are equal, then (X1/Z1, Y1/Z1) is equal to 383 (X2/Z2, Y2/Z2), which is true if and only if u and v are both equal 384 to zero. 386 The product P3=(X3,Y3,Z3) = P1 * P1 is given by 388 X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1) mod p 390 Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3 mod p 392 Z3 = 8 * (Y1 * Z1)^3 mod p 394 where w = 3 * X1^2 + a * Z1^2 mod p. In the above equations, a, u, 395 v, w, X1, X2, X3, Y1, Y2, Y3, Z1, Z2, and Z3 are integers in the set 396 Fp. Pseudocode for the group operation in homogeneous coordinates is 397 provided in Appendix F.2. 399 When converting from affine coordinates to homogeneous coordinates, 400 it is convenient to set Z to 1. When converting from homogeneous 401 coordinates to affine coordinates, it is necessary to perform a 402 modular inverse to find 1/Z mod p. 404 3.2. Other Coordinates 406 Some other coordinate systems have been described; several are 407 documented in [CC1986], including Jacobi coordinates. 409 3.3. ECC Parameters 411 In cryptographic contexts, an elliptic curve parameter set consists 412 of a cyclic subgroup of an elliptic curve together with a preferred 413 generator of that subgroup. When working over a prime order finite 414 field with characteristic greater than three, an elliptic curve group 415 is completely specified by the following parameters: 417 The prime number p that indicates the order of the field Fp. 419 The value a used in the curve equation. 421 The value b used in the curve equation. 423 The generator g of the subgroup. 425 The order n of the subgroup generated by g. 427 An example of an ECC parameter set is provided in Appendix D. 429 Parameter generation is out of scope for this note. 431 Each elliptic curve point is associated with a particular parameter 432 set. The elliptic curve group operation is only defined between two 433 points in the same group. It is an error to apply the group 434 operation to two elements that are from different groups, or to apply 435 the group operation to a pair of coordinates that is not a valid 436 point. (A pair (x,y) of coordinates in Fp is a valid point only when 437 it satisfies the curve equation.) See Section 10.3 for further 438 information. 440 3.3.1. Discriminant 442 For each elliptic curve group, the discriminant -16*(4*a^3 + 27*b^2) 443 must be nonzero modulo p [S1986]; this requires that 445 4*a^3 + 27*b^2 != 0 mod p. 447 3.3.2. Security 449 Security is highly dependent on the choice of these parameters. This 450 section gives normative guidance on acceptable choices. See also 451 Section 10 for informative guidance. 453 The order of the group generated by g MUST be divisible by a large 454 prime, in order to preclude easy solutions of the discrete logarithm 455 problem [K1987]. 457 With some parameter choices, the discrete log problem is 458 significantly easier to solve. This includes parameter sets in which 459 b = 0 and p = 3 (mod 4), and parameter sets in which a = 0 and 460 p = 2 (mod 3) [MOV1993]. These parameter choices are inferior for 461 cryptographic purposes and SHOULD NOT be used. 463 4. Elliptic Curve Diffie-Hellman (ECDH) 465 The Diffie-Hellman (DH) key exchange protocol [DH1976] allows two 466 parties communicating over an insecure channel to agree on a secret 467 key. It was originally defined in terms of operations in the 468 multiplicative group of a field with a large prime characteristic. 469 Massey [M1983] observed that it can be easily generalized so that it 470 is defined in terms of an arbitrary cyclic group. Miller [M1985] and 471 Koblitz [K1987] analyzed the DH protocol over an elliptic curve 472 group. We describe DH following the former reference. 474 Let G be a group, and g be a generator for that group, and let t 475 denote the order of G. The DH protocol runs as follows. Party A 476 chooses an exponent j between 1 and t-1, inclusive, uniformly at 477 random, computes g^j, and sends that element to B. Party B chooses 478 an exponent k between 1 and t-1, inclusive, uniformly at random, 479 computes g^k, and sends that element to A. Each party can compute 480 g^(j*k); party A computes (g^k)^j, and party B computes (g^j)^k. 482 See Appendix B regarding generation of random integers. 484 4.1. Data Types 486 Each run of the ECDH protocol is associated with a particular 487 parameter set (as defined in Section 3.3), and the public keys g^j 488 and g^k and the shared secret g^(j*k) are elements of the cyclic 489 subgroup associated with the parameter set. 491 An ECDH private key z is an integer in Zt, where t is the order of 492 the subgroup. 494 4.2. Compact Representation 496 As described in the final paragraph of [M1985], the x-coordinate of 497 the shared secret value g^(j*k) is a suitable representative for the 498 entire point whenever exponentiation is used as a one-way function. 499 In the ECDH key exchange protocol, after the element g^(j*k) has been 500 computed, the x-coordinate of that value can be used as the shared 501 secret. We call this compact output. 503 Following [M1985] again, when compact output is used in ECDH, only 504 the x-coordinate of an elliptic curve point needs to be transmitted, 505 instead of both coordinates as in the typical affine coordinate 506 representation. We call this the compact representation. Its 507 mathematical background is explained in Appendix C. 509 ECDH can be used with or without compact output. Both parties in a 510 particular run of the ECDH protocol MUST use the same method. ECDH 511 can be used with or without compact representation. If compact 512 representation is used in a particular run of the ECDH protocol, then 513 compact output MUST be used as well. 515 5. Elliptic Curve ElGamal Signatures 517 5.1. Background 519 The ElGamal signature algorithm was introduced in 1984 [E1984a] 520 [E1984b] [E1985]. It is based on the discrete logarithm problem, and 521 was originally defined for the multiplicative group of the integers 522 modulo a large prime number. It is straightforward to extend it to 523 use other finite groups, such as the multiplicative group of the 524 finite field GF(2^w) [AMV1990] or an elliptic curve group [A1992]. 526 An ElGamal signature consists of a pair of components. There are 527 many possible generalizations of ElGamal signature methods that have 528 been obtained by different rearrangements of the equation for the 529 second component; see [HMP1994], [HP1994], [NR1994], [A1992], and 530 [AMV1990]. These generalizations are independent of the mathematical 531 group used, and have been described for the multiplicative group 532 modulo a prime number, the multiplicative group of GF(2^w), and 533 elliptic curve groups [HMP1994] [NR1994] [AMV1990] [A1992]. 535 The Digital Signature Algorithm (DSA) [FIPS186] is an important 536 ElGamal signature variant. 538 5.2. Hash Functions 540 ElGamal signatures must use a collision-resistant hash function, so 541 that it can sign messages of arbitrary length and can avoid 542 existential forgery attacks; see Section 10.4. (This is true for all 543 ElGamal variants [HMP1994].) We denote the hash function as h(). 544 Its input is a bit string of arbitrary length, and its output is a 545 non-negative integer. 547 Let H() denote a hash function whose output is a fixed-length bit 548 string. To use H in an ElGamal signature method, we define the 549 mapping between that output and the non-negative integers; this 550 realizes the function h() described above. Given a bit string m, the 551 function h(m) is computed as follows: 553 1. H(m) is evaluated; the result is a fixed-length bit string. 555 2. Convert the resulting bit string to an integer i by treating its 556 leftmost (initial) bit as the most significant bit of i, and 557 treating its rightmost (final) bit as the least significant bit 558 of i. 560 5.3. KT-IV Signatures 562 Koyama and Tsuruoka described a signature method based on Elliptic 563 Curve ElGamal, in which the first signature component is the 564 x-coordinate of an elliptic curve point reduced modulo q [KT1994]. 565 In this section, we recall that method, which we refer to as KT-IV. 567 The algorithm uses an elliptic curve group, as described in 568 Section 3.3, with prime field order p and curve equation parameters a 569 and b. We denote the generator as alpha, and the order of the 570 generator as q. We follow [FIPS186] in checking for exceptional 571 cases. 573 5.3.1. Keypair Generation 575 The private key z is an integer between 1 and q-1, inclusive, 576 generated uniformly at random. (See Appendix B regarding random 577 integers.) The public key is the group element 578 Y = alpha^z. Each public key is associated with a particular 579 parameter set as per Section 3.3. 581 5.3.2. Signature Creation 583 To compute a KT-IV signature for a message m using the private key z: 585 1. Choose an integer k uniformly at random from the set of all 586 integers between 1 and q-1, inclusive. (See Appendix B regarding 587 random integers.) 589 2. Calculate R = (r_x, r_y) = alpha^k. 591 3. Calculate s1 = r_x mod q. 593 4. Check if h(m) + z * s1 = 0 mod q; if so, a new value of k MUST be 594 generated and the signature MUST be recalculated. As an option, 595 one MAY check if s1 = 0; if so, a new value of k SHOULD be 596 generated and the signature SHOULD be recalculated. (It is 597 extremely unlikely that s1 = 0 or h(m) + z * s1 = 0 mod q if 598 signatures are generated properly.) 600 5. Calculate s2 = k/(h(m) + z*s1) mod q. 602 The signature is the ordered pair (s1, s2). Both signature 603 components are non-negative integers. 605 5.3.3. Signature Verification 607 Given the message m, the generator g, the group order q, the public 608 key Y, and the signature (s1, s2), verification is as follows: 610 1. Check to see that 0 < s1 < q and 0 < s2 < q; if either condition 611 is violated, the signature SHALL be rejected. 613 2. Compute the non-negative integers u1 and u2, where 615 u1 = h(m) * s2 mod q, and 617 u2 = s1 * s2 mod q. 619 3. Compute the elliptic curve point R' = alpha^u1 * Y^u2. 621 4. If the x-coordinate of R' mod q is equal to s1, then the 622 signature and message pass the verification; otherwise, they 623 fail. 625 5.4. KT-I Signatures 627 Horster, Michels, and Petersen categorized many different ElGamal 628 signature methods, demonstrated their equivalence, and showed how to 629 convert signatures of one type to another type [HMP1994]. In their 630 terminology, the signature method of Section 5.3 and [KT1994] is a 631 Type IV method, which is why it is denoted as KT-IV. 633 A Type I KT signature method has a second component that is computed 634 in the same manner as that of the Digital Signature Algorithm. In 635 this section, we describe this method, which we refer to as KT-I. 637 5.4.1. Keypair Generation 639 Keypairs and keypair generation are exactly as in Section 5.3.1. 641 5.4.2. Signature Creation 643 To compute a KT-I signature for a message m using the private key z: 645 1. Choose an integer k uniformly at random from the set of all 646 integers between 1 and q-1, inclusive. (See Appendix B regarding 647 random integers.) 649 2. Calculate R = (r_x, r_y) = alpha^k. 651 3. Calculate s1 = r_x mod q. 653 4. Calculate s2 = (h(m) + z*s1)/k mod q. 655 5. As an option, one MAY check if s1 = 0 or s2 = 0. If either 656 s1 = 0 or s2 = 0, a new value of k SHOULD be generated and the 657 signature SHOULD be recalculated. (It is extremely unlikely that 658 s1 = 0 or s2 = 0 if signatures are generated properly.) 660 The signature is the ordered pair (s1, s2). Both signature 661 components are non-negative integers. 663 5.4.3. Signature Verification 665 Given the message m, the public key Y, and the signature (s1, s2), 666 verification is as follows: 668 1. Check to see that 0 < s1 < q and 0 < s2 < q; if either condition 669 is violated, the signature SHALL be rejected. 671 2. Compute s2_inv = 1/s2 mod q. 673 3. Compute the non-negative integers u1 and u2, where 675 u1 = h(m) * s2_inv mod q, and 677 u2 = s1 * s2_inv mod q. 679 4. Compute the elliptic curve point R' = alpha^u1 * Y^u2. 681 5. If the x-coordinate of R' mod q is equal to s1, then the 682 signature and message pass the verification; otherwise, they 683 fail. 685 5.5. Converting KT-IV Signatures to KT-I Signatures 687 A KT-IV signature for a message m and a public key Y can easily be 688 converted into a KT-I signature for the same message and public key. 689 If (s1, s2) is a KT-IV signature for a message m, then 690 (s1, 1/s2 mod q) is a KT-I signature for the same message [HMP1994]. 692 The conversion operation uses only public information, and it can be 693 performed by the creator of the pre-conversion KT-IV signature, the 694 verifier of the post-conversion KT-I signature, or by any other 695 entity. 697 An implementation MAY use this method to compute KT-I signatures. 699 5.6. Rationale 701 This subsection is not normative for this specification and is 702 provided only as background information. 704 [HMP1994] presents many generalizations of ElGamal signatures. 705 Equation (5) of that reference shows the general signature equation 707 A = x_A * B + k * C (mod q) 709 where x_A is the private key, k is the secret value, and A, B, and C 710 are determined by the Type of the equation, as shown in Table 1 of 711 [HMP1994]. DSA [FIPS186] is an EG-I.1 signature method (as is KT-I), 712 with A = m, B = -r, and C = s. (Here we use the notation of 713 [HMP1994] in which the first signature component is r and the second 714 signature component is s; in KT-I and KT-IV these components are 715 denoted as s1 and s2, respectively. The private key x_A corresponds 716 to the private key z.) Its signature equation is 718 m = -r * z + s * k (mod q). 720 The signature method of [KT1994] and Section 5.3 is an EG-IV.1 721 method, with A = m * s, B = -r * s, C = 1. Its signature equation is 723 m * s = -r * s * z + k (mod q) 725 The functions f and g mentioned in Table 1 of [HMP1994] are merely 726 multiplication, as described under the heading "Fifth 727 generalization". 729 In the above equations, we rely on the implicit conversion of the 730 message m from a bit string to an integer. No hash function is shown 731 in these equations, but, as described in Section 10.4, a hash 732 function should be applied to the message prior to signing in order 733 to prevent existential forgery attacks. 735 Nyberg and Rueppel [NR1994] studied many different ElGamal signature 736 methods and defined "strong equivalence" as follows: 738 Two signature methods are called strongly equivalent if the 739 signature of the first scheme can be transformed efficiently into 740 signatures of the second scheme and vice versa, without knowledge 741 of the private key. 743 KT-I and KT-IV signatures are obviously strongly equivalent. 745 A valid signature with s2=0 leaks the secret key, since in that case 746 z = -h(m) / s1 mod q. We follow [FIPS186] in checking for this 747 exceptional case and the case that s1=0. The s2=0 check was 748 suggested by Rivest [R1992] and is discussed in [BS1992]. 750 [KT1994] uses "a positive integer q' that does not exceed q" when 751 computing the signature component s1 from the x-coordinate r_x of the 752 elliptic curve point R = (r_x, r_y). The value q' is also used 753 during signature validation when comparing the x-coordinate of a 754 computed elliptic curve point to the value to s1. In this note, we 755 use the simplifying convention that q' = q. 757 6. Converting between Integers and Octet Strings 759 A method for the conversion between integers and octet strings is 760 specified in this section, following the established conventions of 761 public key cryptography [R1993]. This method allows integers to be 762 represented as octet strings that are suitable for transmission or 763 storage. This method SHOULD be used when representing an elliptic 764 curve point or an elliptic curve coordinate as they are defined in 765 this note. 767 6.1. Octet-String-to-Integer Conversion 769 The octet string S shall be converted to an integer x as follows. 770 Let S1, ..., Sk be the octets of S from first to last. Then the 771 integer x shall satisfy 773 k 774 x = SUM 2^(8(k-i)) Si . 775 i = 1 777 In other words, the first octet of S has the most significance in the 778 integer and the last octet of S has the least significance. 780 Note: the integer x satisfies 0 <= x < 2^(8*k). 782 6.2. Integer-to-Octet-String Conversion 784 %%% The integer x shall be converted to an octet string S of length k 785 as follows. The string S shall satisfy 787 k 788 y = SUM 2^(8(k-i)) Si , 789 i = 1 791 where S1, ..., Sk are the octets of S from first to last. Note that 792 the conversion fails if y >= 2^(8*k). 794 In other words, the first octet of S has the most significance in the 795 integer, and the last octet of S has the least significance. 797 7. Interoperability 799 The algorithms in this note can be used to interoperate with some 800 other ECC specifications. This section provides details for each 801 algorithm. 803 7.1. ECDH 805 Section 4 can be used with the Internet Key Exchange (IKE) versions 806 one [RFC2409] or two [RFC5996]. These algorithms are compatible with 807 the ECP groups defined by [RFC5903], [RFC5114], [RFC2409], and 808 [RFC2412]. The group definition in this protocol uses an affine 809 coordinate representation of the public key. [RFC5903] uses the 810 compact output of Section 4.2, while [RFC4753] (which was obsoleted 811 by RFC 5903) does not. Neither of those RFCs use compact 812 representation. Note that some groups indicate that the curve 813 parameter "a" is negative; these values are to be interpreted modulo 814 the order of the field. For example, a parameter of a = -3 is equal 815 to p - 3, where p is the order of the field. The test cases in 816 Section 8 of [RFC5903] can be used to test an implementation; these 817 cases use the multiplicative notation, as does this note. The KEi 818 and KEr payloads are equal to g^j and g^k, respectively, with 64 bits 819 of encoding data prepended to them. 821 The algorithms in Section 4 can be used to interoperate with the IEEE 822 [P1363] and ANSI [X9.62] standards for ECDH based on fields of 823 characteristic greater than three. IEEE P1363 ECDH can be used in a 824 manner that will interoperate with this note, with the following 825 options and parameter choices from that specification: 827 prime curves with a cofactor of 1, 829 the ECSVDP-DH (Elliptic Curve Secret Value Derivation Primitive, 830 Diffie-Hellman version), 832 the Key Derivation Function (KDF) must be the "identity" function 833 (equivalently, the KDF step should be omitted and the shared 834 secret value should be output directly). 836 7.2. KT-I and ECDSA 838 The Digital Signature Algorithm (DSA) is based on the discrete 839 logarithm problem over the multiplicative subgroup of the finite 840 field with large prime order [DSA1991] [FIPS186]. The Elliptic Curve 841 Digital Signature Algorithm (ECDSA) [P1363] [X9.62] is an elliptic 842 curve version of DSA. 844 %%% For many hash functions KT-I is mathematically and functionally 845 equivalent to ECDSA, and can interoperate with the IEEE [P1363] and 846 ANSI [X9.62] standards for Elliptic Curve DSA (ECDSA) based on fields 847 of characteristic greater than three. KT-I signatures can be 848 verified using the ECDSA verification algorithm, and ECDSA signatures 849 can be verified using the KT-I verification algorithm (refer to 850 Section 10.4). 852 8. Validating an Implementation 854 It is essential to validate the implementation of a cryptographic 855 algorithm. This section outlines tests that should be performed on 856 the algorithms defined in this note. 858 A known answer test, or KAT, uses a fixed set of inputs to test an 859 algorithm; the output of the algorithm is compared with the expected 860 output, which is also a fixed value. KATs for ECDH and KT-I are set 861 out in the following subsections. 863 A consistency test generates inputs for one algorithm being tested 864 using a second algorithm that is also being tested, then checks the 865 output of the first algorithm. A signature creation algorithm can be 866 tested for consistency against a signature verification algorithm. 867 Implementations of KT-I should be tested in this way. Their 868 signature generation processes are non-deterministic, and thus cannot 869 be tested using a KAT. Signature verification algorithms, on the 870 other hand, are deterministic and should be tested via a KAT. This 871 combination of tests provides coverage for all of the operations, 872 including keypair generation. Consistency testing should also be 873 applied to ECDH. 875 8.1. ECDH 877 An ECDH implementation can be validated using the known answer test 878 cases from [RFC5903] or [RFC5114]. The correspondence between the 879 notation in RFC 5903 and the notation in this note is summarized in 880 the following table. (Refer to Sections 3.3 and 4; the generator g 881 is expressed in affine coordinate representation as (gx, gy)). 883 +------------------------+----------------------------------------+ 884 | ECDH | RFC 5903 | 885 +------------------------+----------------------------------------+ 886 | order p of field Fp | p | 887 | curve coefficient a | -3 | 888 | curve coefficient b | b | 889 | generator g | g=(gx, gy) | 890 | private keys j and k | i and r | 891 | public keys g^j, g^k | g^i = (gix, giy) and g^r = (grx, gry) | 892 +------------------------+----------------------------------------+ 894 The correspondence between the notation in RFC 5114 and the notation 895 in this note is summarized in the following table. 897 +--------------------------+-----------------------------+ 898 | ECDH | RFC 5114 | 899 +--------------------------+-----------------------------+ 900 | order p of field Fp | p | 901 | curve coefficient a | a | 902 | curve coefficient b | b | 903 | generator g | g=(gx, gy) | 904 | group order n | n | 905 | private keys j and k | dA and dB | 906 | public keys g^j, g^k | g^(dA) = (x_qA, y_qA) and | 907 | | g^(dB) = (x_qB, y_qB) | 908 | shared secret g^(j*k) | g^(dA*dB) = (x_Z, y_Z) | 909 +--------------------------+-----------------------------+ 911 8.2. KT-I 913 A KT-I implementation can be validated using the known answer test 914 cases from [RFC4754]. The correspondence between the notation in 915 that RFC and the notation in this note is summarized in the following 916 table. 918 +-----------------------+-------------------+ 919 | KT-I | RFC 4754 | 920 +-----------------------+-------------------+ 921 | order p of field Fp | p | 922 | curve coefficient a | -3 | 923 | curve coefficient b | b | 924 | generator alpha | g | 925 | group order q | q | 926 | private key z | w | 927 | public key Y | g^w = (gwx,gwy) | 928 | random k | ephem priv k | 929 | s1 | r | 930 | s2 | s | 931 | s2_inv | sinv | 932 | u1 | u = h*sinv mod q | 933 | u2 | v = r*sinv mod q | 934 +-----------------------+-------------------+ 936 9. Intellectual Property 938 Concerns about intellectual property have slowed the adoption of ECC 939 because a number of optimizations and specialized algorithms have 940 been patented in recent years. 942 All of the normative references for ECDH (as defined in Section 4) 943 were published during or before 1989, and those for KT-I were 944 published during or before May 1994. All of the normative text for 945 these algorithms is based solely on their respective references. 947 9.1. Disclaimer 949 This document is not intended as legal advice. Readers are advised 950 to consult their own legal advisers if they would like a legal 951 interpretation of their rights. 953 The IETF policies and processes regarding intellectual property and 954 patents are outlined in [RFC3979] and [RFC4879] and at 955 https://datatracker.ietf.org/ipr/about/. 957 10. Security Considerations 959 The security level of an elliptic curve cryptosystem is determined by 960 the cryptanalytic algorithm that is the least expensive for an 961 attacker to implement. There are several algorithms to consider. 963 The Pohlig-Hellman method is a divide-and-conquer technique [PH1978]. 964 If the group order n can be factored as 966 n = q1 * q2 * ... * qz, 968 then the discrete log problem over the group can be solved by 969 independently solving a discrete log problem in groups of order q1, 970 q2, ..., qz, then combining the results using the Chinese remainder 971 theorem. The overall computational cost is dominated by that of the 972 discrete log problem in the subgroup with the largest order. 974 Shanks' algorithm [K1981v3] computes a discrete logarithm in a group 975 of order n using O(sqrt(n)) operations and O(sqrt(n)) storage. The 976 Pollard rho algorithm [P1978] computes a discrete logarithm in a 977 group of order n using O(sqrt(n)) operations, with a negligible 978 amount of storage, and can be efficiently parallelized [VW1994]. 980 The Pollard lambda algorithm [P1978] can solve the discrete logarithm 981 problem using O(sqrt(w)) operations and O(log(w)) storage, when the 982 exponent is known to lie in an interval of width w. 984 The algorithms described above work in any group. There are 985 specialized algorithms that specifically target elliptic curve 986 groups. There are no known subexponential algorithms against general 987 elliptic curve groups, though there are methods that target certain 988 special elliptic curve groups; see [MOV1993] and [FR1994]. 990 10.1. Subgroups 992 A group consisting of a nonempty set of elements S with associated 993 group operation * is a subgroup of the group with the set of elements 994 G, if the latter group uses the same group operation and S is a 995 subset of G. For each elliptic curve equation, there is an elliptic 996 curve group whose group order is equal to the order of the elliptic 997 curve; that is, there is a group that contains every point on the 998 curve. 1000 The order m of the elliptic curve is divisible by the order n of the 1001 group associated with the generator; that is, for each elliptic curve 1002 group, m = n * c for some number c. The number c is called the 1003 "cofactor" [P1363]. Each ECC parameter set as in Section 3.3 is 1004 associated with a particular cofactor. 1006 It is possible and desirable to use a cofactor equal to 1. 1008 10.2. Diffie-Hellman 1010 Note that the key exchange protocol as defined in Section 4 does not 1011 protect against active attacks; Party A must use some method to 1012 ensure that (g^k) originated with the intended communicant B, rather 1013 than an attacker, and Party B must do the same with (g^j). 1015 It is not sufficient to authenticate the shared secret g^(j*k), since 1016 this leaves the protocol open to attacks that manipulate the public 1017 keys. Instead, the values of the public keys g^x and g^y that are 1018 exchanged should be directly authenticated. This is the strategy 1019 used by protocols that build on Diffie-Hellman and that use end- 1020 entity authentication to protect against active attacks, such as 1021 OAKLEY [RFC2412] and the Internet Key Exchange [RFC2409] [RFC4306] 1022 [RFC5996]. 1024 When the cofactor of a group is not equal to 1, there are a number of 1025 attacks that are possible against ECDH. See [VW1996], [AV1996], and 1026 [LL1997]. 1028 10.3. Group Representation and Security 1030 The elliptic curve group operation does not explicitly incorporate 1031 the parameter b from the curve equation. This opens the possibility 1032 that a malicious attacker could learn information about an ECDH 1033 private key by submitting a bogus public key [BMM2000]. An attacker 1034 can craft an elliptic curve group G' that has identical parameters to 1035 a group G that is being used in an ECDH protocol, except that b is 1036 different. An attacker can submit a point on G' into a run of the 1037 ECDH protocol that is using group G, and gain information from the 1038 fact that the group operations using the private key of the device 1039 under attack are effectively taking place in G' instead of G. 1041 This attack can gain useful information about an ECDH private key 1042 that is associated with a static public key, i.e., a public key that 1043 is used in more than one run of the protocol. However, it does not 1044 gain any useful information against ephemeral keys. 1046 This sort of attack is thwarted if an ECDH implementation does not 1047 assume that each pair of coordinates in Zp is actually a point on the 1048 appropriate elliptic curve. 1050 These considerations also apply when ECDH is used with compact 1051 representation (see Appendix C). 1053 10.4. Signatures 1055 Elliptic curve parameters should only be used if they come from a 1056 trusted source; otherwise, some attacks are possible [AV1996] 1057 [V1996]. 1059 If no hash function is used in an ElGamal signature system, then the 1060 system is vulnerable to existential forgeries, in which an attacker 1061 who does not know a private key can generate valid signatures for the 1062 associated public key, but cannot generate a signature for a message 1063 of its own choosing. (See [E1985] for instance.) The use of a 1064 collision-resistant hash function eliminates this vulnerability. 1066 In principle, any collision-resistant hash function is suitable for 1067 use in KT signatures. To facilitate interoperability, we recognize 1068 the following hashes as suitable for use as the function H defined in 1069 Section 5.2: 1071 SHA-256, which has a 256-bit output. 1073 SHA-384, which has a 384-bit output. 1075 SHA-512, which has a 512-bit output. 1077 All of these hash functions are defined in [FIPS180-2]. 1079 The number of bits in the output of the hash used in KT signatures 1080 should be equal or close to the number of bits needed to represent 1081 the group order. 1083 11. Acknowledgements 1085 This update to RFC 6090 includes errata that were reported against 1086 that RFC. The authors gratefully acknowledge Annie Yousar and Watson 1087 Ladd for those reports. 1089 The authors also expresses their thanks to the originators of 1090 elliptic curve cryptography, whose work made this note possible, and 1091 all of the reviewers, who provided valuable constructive feedback. 1092 Thanks for RFC 6090 are especially due to Howard Pinder, Andrey 1093 Jivsov, Alfred Hoenes (who contributed the algorithms in Appendix F), 1094 Dan Harkins, and Tina Tsou. 1096 12. References 1098 12.1. Normative References 1100 [AMV1990] Agnew, G., Mullin, R., and S. Vanstone, "Improved Digital 1101 Signature Scheme based on Discrete Exponentiation", 1102 Electronics Letters Vol. 26, No. 14, July, 1990. 1104 [BC1989] Bender, A. and G. Castagnoli, "On the Implementation of 1105 Elliptic Curve Cryptosystems", Advances in Cryptology - 1106 CRYPTO '89 Proceedings, Springer Lecture Notes in Computer 1107 Science (LNCS), volume 435, 1989. 1109 [CC1986] Chudnovsky, D. and G. Chudnovsky, "Sequences of numbers 1110 generated by addition in formal groups and new primality 1111 and factorization tests", Advances in Applied Mathematics, 1112 Volume 7, Issue 4, December 1986. 1114 [D1966] Deskins, W., "Abstract Algebra", MacMillan Company New 1115 York, 1966. 1117 [DH1976] Diffie, W. and M. Hellman, "New Directions in 1118 Cryptography", IEEE Transactions in Information Theory IT- 1119 22, pp. 644-654, 1976. 1121 [FR1994] Frey, G. and H. Ruck, "A remark concerning m-divisibility 1122 and the discrete logarithm in the divisor class group of 1123 curves.", Mathematics of Computation Vol. 62, No. 206, pp. 1124 865-874, 1994. 1126 [HMP1994] Horster, P., Michels, M., and H. Petersen, "Meta-ElGamal 1127 signature schemes", University of Technology Chemnitz- 1128 Zwickau Department of Computer Science, Technical Report 1129 TR-94-5, May 1994. 1131 [K1981v2] Knuth, D., "The Art of Computer Programming, Vol. 2: 1132 Seminumerical Algorithms", Addison Wesley , 1981. 1134 [K1987] Koblitz, N., "Elliptic Curve Cryptosystems", Mathematics 1135 of Computation, Vol. 48, 1987, pp. 203-209, 1987. 1137 [KT1994] Koyama, K. and Y. Tsuruoka, "Digital signature system 1138 based on elliptic curve and signer device and verifier 1139 device for said system", Japanese Unexamined Patent 1140 Application Publication H6-43809, February 18, 1994. 1142 [M1983] Massey, J., "Logarithms in finite cyclic groups - 1143 cryptographic issues", Proceedings of the 4th Symposium on 1144 Information Theory, 1983. 1146 [M1985] Miller, V., "Use of elliptic curves in cryptography", 1147 Advances in Cryptology - CRYPTO '85 Proceedings, Springer 1148 Lecture Notes in Computer Science (LNCS), volume 218, 1149 1985. 1151 [MOV1993] Menezes, A., Vanstone, S., and T. Okamoto, "Reducing 1152 Elliptic Curve Logarithms to Logarithms in a Finite 1153 Field", IEEE Transactions on Information Theory Vol. 39, 1154 No. 5, pp. 1639-1646, September, 1993. 1156 [R1993] RSA Laboratories, , "PKCS#1: RSA Encryption Standard", 1157 Technical Note version 1.5, 1993. 1159 [S1986] Silverman, J., "The Arithmetic of Elliptic Curves", 1160 Springer-Verlag, New York, 1986. 1162 12.2. Informative References 1164 [A1992] Anderson, J., "Response to the proposed DSS", 1165 Communications of the ACM, v. 35, n. 7, p. 50-52, July 1166 1992. 1168 [AV1996] Anderson, R. and S. Vaudenay, "Minding Your P's and Q's", 1169 Advances in Cryptology - ASIACRYPT '96 Proceedings, 1170 Springer Lecture Notes in Computer Science (LNCS), volume 1171 1163, 1996. 1173 [BMM2000] Biehl, I., Meyer, B., and V. Muller, "Differential fault 1174 analysis on elliptic curve cryptosystems", Advances in 1175 Cryptology - CRYPTO 2000 Proceedings, Springer Lecture 1176 Notes in Computer Science (LNCS), volume 1880, 2000. 1178 [BS1992] Branstad, D. and M. Smid, "Response to Comments on the 1179 NIST Proposed Digital Signature Standard", Advances in 1180 Cryptology - CRYPTO '92 Proceedings, Springer Lecture 1181 Notes in Computer Science (LNCS), volume 740, August 1992. 1183 [DSA1991] U.S. National Institute of Standards and Technology, , 1184 "DIGITAL SIGNATURE STANDARD", Federal Register, Vol. 56, 1185 August 1991. 1187 [E1984a] ElGamal, T., "Cryptography and logarithms over finite 1188 fields", Stanford University, UMI Order No. DA 8420519, 1189 1984. 1191 [E1984b] ElGamal, T., "Cryptography and logarithms over finite 1192 fields", Advances in Cryptology - CRYPTO '84 Proceedings, 1193 Springer Lecture Notes in Computer Science (LNCS), volume 1194 196, 1984. 1196 [E1985] ElGamal, T., "A public key cryptosystem and a signature 1197 scheme based on discrete logarithms", IEEE Transactions on 1198 Information Theory, Vol. 30, No. 4, pp. 469-472, 1985. 1200 [FIPS180-2] 1201 U.S. National Institute of Standards and Technology, , 1202 "SECURE HASH STANDARD", Federal Information Processing 1203 Standard (FIPS) 180-2, August 2002. 1205 [FIPS186] U.S. National Institute of Standards and Technology, , 1206 "DIGITAL SIGNATURE STANDARD", Federal Information 1207 Processing Standard FIPS-186, May 1994. 1209 [HP1994] Horster, P. and H. Petersen, "Verallgemeinerte ElGamal- 1210 Signaturen", Proceedings der Fachtagung SIS '94, Verlag 1211 der Fachvereine, Zurich, 1994. 1213 [K1981v3] Knuth, D., "The Art of Computer Programming, Vol. 3: 1214 Sorting and Searching", Addison Wesley, 1981. 1216 [KMOV1991] 1217 Koyama, K., Maurer, U., Vanstone, S., and T. Okamoto, "New 1218 Public-Key Schemes Based on Elliptic Curves over the Ring 1219 Zn", Advances in Cryptology - CRYPTO '91 Proceedings, 1220 Springer Lecture Notes in Computer Science (LNCS), volume 1221 576, 1991. 1223 [L1969] Lehmer, D., "Computer technology applied to the theory of 1224 numbers", M.A.A. Studies in Mathematics, 180-2, 1969. 1226 [LL1997] Lim, C. and P. Lee, "A Key Recovery Attack on Discrete 1227 Log-based Schemes Using a Prime Order Subgroup", Advances 1228 in Cryptology - CRYPTO '97 Proceedings, Springer Lecture 1229 Notes in Computer Science (LNCS), volume 1294, 1997. 1231 [NR1994] Nyberg, K. and R. Rueppel, "Message Recovery for Signature 1232 Schemes Based on the Discrete Logarithm Problem", Advances 1233 in Cryptology - EUROCRYPT '94 Proceedings, Springer 1234 Lecture Notes in Computer Science (LNCS), volume 950, May 1235 1994. 1237 [P1363] "Standard Specifications for Public Key Cryptography", 1238 Institute of Electric and Electronic Engineers (IEEE), 1239 P1363, 2000. 1241 [P1978] Pollard, J., "Monte Carlo methods for index computation 1242 mod p", Mathematics of Computation, Vol. 32, 1978. 1244 [PH1978] Pohlig, S. and M. Hellman, "An Improved Algorithm for 1245 Computing Logarithms over GF(p) and its Cryptographic 1246 Significance", IEEE Transactions on Information Theory, 1247 Vol. 24, pp. 106-110, 1978. 1249 [R1988] Rose, H., "A Course in Number Theory", Oxford University 1250 Press, 1988. 1252 [R1992] Rivest, R., "Response to the proposed DSS", Communications 1253 of the ACM, v. 35, n. 7, p. 41-47, July 1992. 1255 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1256 Requirement Levels", BCP 14, RFC 2119, March 1997. 1258 [RFC2409] Harkins, D. and D. Carrel, "The Internet Key Exchange 1259 (IKE)", RFC 2409, November 1998. 1261 [RFC2412] Orman, H., "The OAKLEY Key Determination Protocol", RFC 1262 2412, November 1998. 1264 [RFC3979] Bradner, S., "Intellectual Property Rights in IETF 1265 Technology", BCP 79, RFC 3979, March 2005. 1267 [RFC4086] Eastlake, D., Schiller, J., and S. Crocker, "Randomness 1268 Requirements for Security", BCP 106, RFC 4086, June 2005. 1270 [RFC4306] Kaufman, C., "Internet Key Exchange (IKEv2) Protocol", RFC 1271 4306, December 2005. 1273 [RFC4753] Fu, D. and J. Solinas, "ECP Groups For IKE and IKEv2", RFC 1274 4753, January 2007. 1276 [RFC4754] Fu, D. and J. Solinas, "IKE and IKEv2 Authentication Using 1277 the Elliptic Curve Digital Signature Algorithm (ECDSA)", 1278 RFC 4754, January 2007. 1280 [RFC4879] Narten, T., "Clarification of the Third Party Disclosure 1281 Procedure in RFC 3979", BCP 79, RFC 4879, April 2007. 1283 [RFC5114] Lepinski, M. and S. Kent, "Additional Diffie-Hellman 1284 Groups for Use with IETF Standards", RFC 5114, January 1285 2008. 1287 [RFC5903] Fu, D. and J. Solinas, "Elliptic Curve Groups modulo a 1288 Prime (ECP Groups) for IKE and IKEv2", RFC 5903, June 1289 2010. 1291 [RFC5996] Kaufman, C., Hoffman, P., Nir, Y., and P. Eronen, 1292 "Internet Key Exchange Protocol Version 2 (IKEv2)", RFC 1293 5996, September 2010. 1295 [RFC6090] McGrew, D., Igoe, K., and M. Salter, "Fundamental Elliptic 1296 Curve Cryptography Algorithms", RFC 6090, February 2011. 1298 [SuiteB] U. S. National Security Agency (NSA), , "NSA Suite B 1299 Cryptography", 2014, 1300 . 1303 [V1996] Vaudenay, S., "Hidden Collisions on DSS", Advances in 1304 Cryptology - CRYPTO '96 Proceedings, Springer Lecture 1305 Notes in Computer Science (LNCS), volume 1109, 1996. 1307 [VW1994] van Oorschot, P. and M. Wiener, "Parallel Collision Search 1308 with Application to Hash Functions and Discrete 1309 Logarithms", Proceedings of the 2nd ACM Conference on 1310 Computer and communications security, pp. 210-218, 1994. 1312 [VW1996] van Oorschot, P. and M. Wiener, "On Diffie-Hellman key 1313 agreement with short exponents", Advances in Cryptology - 1314 EUROCRYPT '96 Proceedings, Springer Lecture Notes in 1315 Computer Science (LNCS), volume 1070, 1996. 1317 [X9.62] "Public Key Cryptography for the Financial Services 1318 Industry: The Elliptic Curve Digital Signature Algorithm 1319 (ECDSA)", American National Standards Institute (ANSI) 1320 X9.62, 2005. 1322 Appendix A. Key Words 1324 The definitions of these key words are quoted from [RFC2119] and are 1325 commonly used in Internet standards. They are reproduced in this 1326 note in order to avoid a normative reference from after 1994. 1328 1. MUST - This word, or the terms "REQUIRED" or "SHALL", means that 1329 the definition is an absolute requirement of the specification. 1331 2. MUST NOT - This phrase, or the phrase "SHALL NOT", means that the 1332 definition is an absolute prohibition of the specification. 1334 3. SHOULD - This word, or the adjective "RECOMMENDED", means that 1335 there may exist valid reasons in particular circumstances to 1336 ignore a particular item, but the full implications must be 1337 understood and carefully weighed before choosing a different 1338 course. 1340 4. SHOULD NOT - This phrase, or the phrase "NOT RECOMMENDED", means 1341 that there may exist valid reasons in particular circumstances 1342 when the particular behavior is acceptable or even useful, but 1343 the full implications should be understood and the case carefully 1344 weighed before implementing any behavior described with this 1345 label. 1347 5. MAY - This word, or the adjective "OPTIONAL", means that an item 1348 is truly optional. One vendor may choose to include the item 1349 because a particular marketplace requires it or because the 1350 vendor feels that it enhances the product while another vendor 1351 may omit the same item. An implementation which does not include 1352 a particular option MUST be prepared to interoperate with another 1353 implementation which does include the option, though perhaps with 1354 reduced functionality. In the same vein an implementation which 1355 does include a particular option MUST be prepared to interoperate 1356 with another implementation which does not include the option 1357 (except, of course, for the feature the option provides.) 1359 Appendix B. Random Integer Generation 1361 It is easy to generate an integer uniformly at random between zero 1362 and (2^t)-1, inclusive, for some positive integer t. Generate a 1363 random bit string that contains exactly t bits, and then convert the 1364 bit string to a non-negative integer by treating the bits as the 1365 coefficients in a base-2 expansion of an integer. 1367 It is sometimes necessary to generate an integer r uniformly at 1368 random so that r satisfies a certain property P, for example, lying 1369 within a certain interval. A simple way to do this is with the 1370 rejection method: 1372 1. Generate a candidate number c uniformly at random from a set that 1373 includes all numbers that satisfy property P (plus some other 1374 numbers, preferably not too many) 1376 2. If c satisfies property P, then return c. Otherwise, return to 1377 Step 1. 1379 For example, to generate a number between 1 and n-1, inclusive, 1380 repeatedly generate integers between zero and (2^t)-1, inclusive, 1381 stopping at the first integer that falls within that interval. 1383 Recommendations on how to generate random bit strings are provided in 1384 [RFC4086]. 1386 Appendix C. Why Compact Representation Works 1388 In the affine representation, the x-coordinate of the point P^i does 1389 not depend on the y-coordinate of the point P, for any non-negative 1390 exponent i and any point P. This fact can be seen as follows. When 1391 given only the x-coordinate of a point P, it is not possible to 1392 determine exactly what the y-coordinate is, but the y value will be a 1393 solution to the curve equation 1395 y^2 = x^3 + a*x + b (mod p). 1397 There are at most two distinct solutions y = w and y = -w mod p, and 1398 the point P must be either Q=(x,w) or Q^-1=(x,-w). Thus P^n is equal 1399 to either Q^n or (Q^-1)^n = (Q^n)^-1. These values have the same 1400 x-coordinate. Thus, the x-coordinate of a point P^i can be computed 1401 from the x-coordinate of a point P by computing one of the possible 1402 values of the y coordinate of P, then computing the ith power of P, 1403 and then ignoring the y-coordinate of that result. 1405 In general, it is possible to compute a square root modulo p by using 1406 Shanks' method [K1981v2]; simple methods exist for some values of p. 1407 When p = 3 (mod 4), the square roots of z mod p are w and -w mod p, 1408 where 1410 w = z ^ ((p+1)/4) (mod p); 1412 this observation is due to Lehmer [L1969]. When p satisfies this 1413 property, y can be computed from the curve equation, and either y = w 1414 or y = -w mod p, where 1416 w = (x^3 + a*x + b)^((p+1)/4) (mod p). 1418 Square roots modulo p only exist for a quadratic residue modulo p, 1419 [R1988]; if z is not a quadratic residue, then there is no number w 1420 such that w^2 = z (mod p). A simple way to verify that z is a 1421 quadratic residue after computing w is to verify that 1422 w * w = z (mod p). If this relation does not hold for the above 1423 equation, then the value x is not a valid x-coordinate for a valid 1424 elliptic curve point. This is an important consideration when ECDH 1425 is used with compact output; see Section 10.3. 1427 The primes used in the P-256, P-384, and P-521 curves described in 1428 [RFC5903] all have the property that p = 3 (mod 4). 1430 Appendix D. Example ECC Parameter Set 1432 For concreteness, we recall an elliptic curve defined by Solinas and 1433 Fu in [RFC5903] and referred to as P-256, which is believed to 1434 provide a 128-bit security level. We use the notation of 1435 Section 3.3, and express the generator in the affine coordinate 1436 representation g=(gx,gy), where the values gx and gy are in Fp. 1438 p: FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF 1440 a: - 3 1442 b: 5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B 1444 n: FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551 1446 gx: 6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296 1448 gy: 4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5 1450 Note that p can also be expressed as 1452 p = 2^(256)-2^(224)+2^(192)+2^(96)-1. 1454 Appendix E. Additive and Multiplicative Notation 1456 The early publications on elliptic curve cryptography used 1457 multiplicative notation, but most modern publications use additive 1458 notation. This section includes a table mapping between those two 1459 conventions. In this section, a and b are elements of an elliptic 1460 curve group, and N is an integer. 1462 +--------------------------+-------------------------+ 1463 | Multiplicative Notation | Additive Notation | 1464 +--------------------------+-------------------------+ 1465 | multiplication | addition | 1466 | a * b | a + b | 1467 | squaring | doubling | 1468 | a * a = a^2 | a + a = 2a | 1469 | exponentiation | scalar multiplication | 1470 | a^N = a * a * ... * a | Na = a + a + ... + a | 1471 | inverse | inverse | 1472 | a^-1 | -a | 1473 +--------------------------+-------------------------+ 1475 Appendix F. Algorithms 1477 This section contains a pseudocode description of the elliptic curve 1478 group operation. Text that follows the symbol "//" is to be 1479 interpreted as comments rather than instructions. 1481 F.1. Affine Coordinates 1483 To an arbitrary pair of elliptic curve points P and Q specified by 1484 their affine coordinates P=(x1,y1) and Q=(x2,y2), the group operation 1485 assigns a third point R = P*Q with the coordinates (x3,y3). These 1486 coordinates are computed as follows: 1488 if P is (@,@), 1489 R = Q 1490 else if Q is (@,@), 1491 R = P 1492 else if P is not equal to Q and x1 is equal to x2, 1493 R = (@,@) 1494 else if P is not equal to Q and x1 is not equal to x2, 1495 x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 mod p and 1496 y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 mod p 1497 else if P is equal to Q and y1 is equal to 0, 1498 R = (@,@) 1499 else // P is equal to Q and y1 is not equal to 0 1500 x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 mod p and 1501 y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y mod p. 1503 From the first and second case, it follows that the point at infinity 1504 is the neutral element of this operation, which is its own inverse. 1506 From the curve equation, it follows that for a given curve point P = 1507 (x,y) distinct from the point at infinity, (x,-y) also is a curve 1508 point, and from the third and the fifth case it follows that this is 1509 the inverse of P, P^-1. 1511 Note: The fifth and sixth case are known as "point squaring". 1513 F.2. Homogeneous Coordinates 1515 An elliptic curve point (x,y) (other than the point at infinity 1516 (@,@)) is equivalent to a point (X,Y,Z) in homogeneous coordinates 1517 (with X, Y, and Z in Fp and not all three being zero at once) 1518 whenever x=X/Z and y=Y/Z. "Homogenous coordinates" means that two 1519 triples (X,Y,Z) and (X',Y',Z') are regarded as "equal" (i.e., 1520 representing the same point) if there is some nonzero s in Fp such 1521 that X'=s*X, Y'=s*Y, and Z'=s*Z. The point at infinity (@,@) is 1522 regarded as equivalent to the homogenous coordinates (0,1,0), i.e., 1523 it can be represented by any triple (0,Y,0) with nonzero Y in Fp. 1525 Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on the elliptic curve, 1526 and let u = Y2 * Z1 - Y1 * Z2 and v = X2 * Z1 - X1 * Z2. 1528 We observe that the points P1 and P2 are equal if and only if u and v 1529 are both equal to zero. Otherwise, if either P1 or P2 are equal to 1530 the point at infinity, v is zero and u is nonzero (but the converse 1531 implication does not hold). 1533 Then, the product P3=(X3,Y3,Z3) = P1 * P2 is given by: 1535 if P1 is the point at infinity, 1536 P3 = P2 1537 else if P2 is the point at infinity, 1538 P3 = P1 1540 %%% 1541 else if P1=-P2 as projective points 1542 P3 = (0,1,0) 1543 else if P1 does not equal P2 1544 X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3) 1545 Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3 1546 Z3 = v^3 * Z1 * Z2 1547 else // P2 equals P1, P3 = P1 * P1 1548 w = 3 * X1^2 + a * Z1^2 1549 X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1) 1550 Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3 1551 Z3 = 8 * (Y1 * Z1)^3 1553 It thus turns out that the point at infinity is the identity element 1554 and for P1=(X,Y,Z) not equal to this point at infinity, P2=(X,-Y,Z) 1555 represents P1^-1. 1557 Authors' Addresses 1559 David A. McGrew 1560 Cisco Systems 1561 510 McCarthy Blvd. 1562 Milpitas, CA 95035 1563 USA 1565 Phone: (408) 525 8651 1566 Email: mcgrew@cisco.com 1567 URI: http://www.mindspring.com/~dmcgrew/dam.htm 1569 Kevin M. Igoe 1570 National Security Agency 1571 Commercial Solutions Center 1572 United States of America 1574 Email: kmigoe@nsa.gov 1576 Margaret Salter 1577 National Security Agency 1578 9800 Savage Rd. 1579 Fort Meade, MD 20755-6709 1580 USA 1582 Email: misalte@nsa.gov 1584 Paul Hoffman 1585 VPN Consortium 1587 Email: paul.hoffman@vpnc.org