idnits 2.17.1 draft-irtf-cfrg-curves-00.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 a Security Considerations section. ** 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.) ** There are 7 instances of too long lines in the document, the longest one being 11 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (January 28, 2015) is 3376 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 452 -- Looks like a reference, but probably isn't: '1' on line 344 -- Looks like a reference, but probably isn't: '2' on line 344 -- Looks like a reference, but probably isn't: '31' on line 452 Summary: 3 errors (**), 0 flaws (~~), 1 warning (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 CFRG A. Langley 3 Internet-Draft Google 4 Intended status: Informational January 28, 2015 5 Expires: August 1, 2015 7 Elliptic Curves for Security 8 draft-irtf-cfrg-curves-00 10 Abstract 12 This memo describes an algorithm for deterministically generating 13 parameters for elliptic curves over prime fields offering high 14 practical security in cryptographic applications, including Transport 15 Layer Security (TLS) and X.509 certificates. It also specifies a 16 specific curve at the ~128-bit security level. 18 Status of This Memo 20 This Internet-Draft is submitted in full conformance with the 21 provisions of BCP 78 and BCP 79. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF). Note that other groups may also distribute 25 working documents as Internet-Drafts. The list of current Internet- 26 Drafts is at http://datatracker.ietf.org/drafts/current/. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 This Internet-Draft will expire on August 1, 2015. 35 Copyright Notice 37 Copyright (c) 2015 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents 42 (http://trustee.ietf.org/license-info) in effect on the date of 43 publication of this document. Please review these documents 44 carefully, as they describe your rights and restrictions with respect 45 to this document. Code Components extracted from this document must 46 include Simplified BSD License text as described in Section 4.e of 47 the Trust Legal Provisions and are provided without warranty as 48 described in the Simplified BSD License. 50 Table of Contents 52 1. Note on authorship . . . . . . . . . . . . . . . . . . . . . 2 53 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 54 3. Requirements Language . . . . . . . . . . . . . . . . . . . . 3 55 4. Security Requirements . . . . . . . . . . . . . . . . . . . . 3 56 5. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 3 57 6. Parameter Generation . . . . . . . . . . . . . . . . . . . . 4 58 6.1. Edwards Curves . . . . . . . . . . . . . . . . . . . . . 4 59 6.2. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 5 60 6.3. Generators . . . . . . . . . . . . . . . . . . . . . . . 6 61 7. Recommended Curves . . . . . . . . . . . . . . . . . . . . . 7 62 8. Wire-format of field elements . . . . . . . . . . . . . . . . 8 63 9. Elliptic Curve Diffie-Hellman . . . . . . . . . . . . . . . . 9 64 9.1. Diffie-Hellman protocol . . . . . . . . . . . . . . . . . 11 65 10. Test vectors . . . . . . . . . . . . . . . . . . . . . . . . 11 66 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 12 67 11.1. Normative References . . . . . . . . . . . . . . . . . . 12 68 11.2. Informative References . . . . . . . . . . . . . . . . . 12 69 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 13 71 1. Note on authorship 73 This document is a merging of "draft-black-rpgecc-01" (by Benjamin 74 Black, Joppe W. Bos, Craig Costello, Patrick Longa and Michael 75 Naehrig) and "draft-turner-thecurve25519function-01" (by Watson Ladd, 76 Rich Salz and Sean Turner). They are the actual authors of the words 77 and figures, but authorship also implies support and so are not 78 listed as authors until they have confirmed that they support this 79 document. None the less, they deserve any credit for the contents. 81 2. Introduction 83 Since the initial standardization of elliptic curve cryptography 84 (ECC) in [SEC1] there has been significant progress related to both 85 efficiency and security of curves and implementations. Notable 86 examples are algorithms protected against certain side-channel 87 attacks, different 'special' prime shapes which allow faster modular 88 arithmetic, and a larger set of curve models from which to choose. 89 There is also concern in the community regarding the generation and 90 potential weaknesses of the curves defined in [NIST]. 92 This memo describes a deterministic algorithm for generation of 93 elliptic curves for cryptography. The constraints in the generation 94 process produce curves that support constant-time, exception-free 95 scalar multiplications that are resistant to a wide range of side- 96 channel attacks including timing and cache attacks, thereby offering 97 high practical security in cryptographic applications. The 98 deterministic algorithm operates without any hidden parameters, 99 reliance on randomness or any other processes offering opportunities 100 for manipulation of the resulting curves. The selection between 101 curve models is determined by choosing the curve form that supports 102 the fastest (currently known) complete formulas for each modularity 103 option of the underlying field prime. Specifically, the Edwards 104 curve x^2 + y^2 = 1 + dx^2y^2 is used with primes p with p = 3 mod 4, 105 and the twisted Edwards curve -x^2 + y^2 = 1 + dx^2y^2 is used for 106 primes p with p = 1 mod 4. 108 3. Requirements Language 110 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 111 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 112 document are to be interpreted as described in RFC 2119 [RFC2119]. 114 4. Security Requirements 116 For each curve at a specific security level: 118 1. The domain parameters SHALL be generated in a simple, 119 deterministic manner, without any secret or random inputs. The 120 derivation of the curve parameters is defined in Section 6. 122 2. The trace of Frobenius MUST NOT be in {0, 1} in order to rule out 123 the attacks described in [Smart], [AS], and [S], as in [EBP]. 125 3. MOV Degree: the embedding degree k MUST be greater than (r - 1) / 126 100, as in [EBP]. 128 4. CM Discriminant: discriminant D MUST be greater than 2^100, as in 129 [SC]. 131 5. Notation 133 Throughout this document, the following notation is used: 135 p Denotes the prime number defining the underlying field. 137 GF(p) The finite field with p elements. 139 d An element in the finite field GF(p), not equal to -1 or zero. 141 Ed An Edwards curve: an elliptic curve over GF(p) with equation x^2 + 142 y^2 = 1 + dx^2y^2. 144 tEd A twisted Edwards curve where a=-1: an elliptic curve over GF(p) 145 with equation -x^2 + y^2 = 1 + dx^2y^2. 147 oddDivisor The largest odd divisor of the number of GF(p)-rational 148 points on a (twisted) Edwards curve. 150 oddDivisor' The largest odd divisor of the number of GF(p)-rational 151 points on the non-trivial quadratic twist of a (twisted) Edwards 152 curve. 154 cofactor The cofactor of the subgroup of order oddDivisor in the 155 group of GF(p)-rational points of a (twisted) Edwards curve. 157 cofactor' The cofactor of the subgroup of order oddDivisor in the 158 group of GF(p)-rational points on the non-trivial quadratic twist 159 of a (twisted) Edwards curve. 161 trace The trace of Frobenius of Ed or tEd such that #Ed(GF(p)) = p + 162 1 - trace or #tEd(GF(p)) = p + 1 - trace, respectively. 164 P A generator point defined over GF(p) of prime order oddDivisor on 165 Ed or tEd. 167 X(P) The x-coordinate of the elliptic curve point P. 169 Y(P) The y-coordinate of the elliptic curve point P. 171 6. Parameter Generation 173 This section describes the generation of the curve parameter, namely 174 d, of the elliptic curve. The input to this process is p, the prime 175 that defines the underlying field. The size of p determines the 176 amount of work needed to compute a discrete logarithm in the elliptic 177 curve group and choosing a precise p depends on many implementation 178 concerns. The performance of the curve will be dominated by 179 operations in GF(p) and thus carefully choosing a value that allows 180 for easy reductions on the intended architecture is critical for 181 performance. This document does not attempt to articulate all these 182 considerations. 184 6.1. Edwards Curves 186 For p = 3 mod 4, the elliptic curve Ed in Edwards form is determined 187 by the non-square element d from GF(p) (not equal to -1 or zero) with 188 smallest absolute value such that #Ed(GF(p)) = cofactor * oddDivisor, 189 #Ed'(GF(p)) = cofactor' * oddDivisor', cofactor = cofactor' = 4, and 190 both subgroup orders oddDivisor and oddDivisor' are prime. In 191 addition, care must be taken to ensure the MOV degree and CM 192 discriminant requirements from Section 4 are met. 194 These cofactors are chosen because they are minimal. 196 Input: a prime p, with p = 3 mod 4 197 Output: the parameter d defining the curve Ed 198 1. Set d = 0 199 2. repeat 200 repeat 201 if (d > 0) then 202 d = -d 203 else 204 d = -d + 1 205 end if 206 until d is not a square in GF(p) 208 Compute oddDivisor, oddDivisor', cofactor and cofactor' where #Ed(GF(p)) = 209 cofactor * oddDivisor, #Ed'(GF(p)) = cofactor' * oddDivisor', cofactor and 210 cofactor' are powers of 2 and oddDivisor, oddDivisor' are odd. 211 until ((cofactor = cofactor' = 4), oddDivisor is prime and oddDivisor' is prime) 212 3. Output d 214 GenerateCurveEdwards 216 6.2. Twisted Edwards Curves 218 For a prime p = 1 mod 4, the elliptic curve tEd in twisted Edwards 219 form is determined by the non-square element d from GF(p) (not equal 220 to -1 or zero) with smallest absolute value such that #tEd(GF(p)) = 221 cofactor * oddDivisor, #tEd'(GF(p)) = cofactor' * oddDivisor', 222 cofactor = 8, cofactor' = 4 and both subgroup orders oddDivisor and 223 oddDivisor' are prime. In addition, care must be taken to ensure the 224 MOV degree and CM discriminant requirements from Section 4 are met. 226 These cofactors are chosen so that they are minimal such that the 227 cofactor of the main curve is greater than the cofactor of the twist. 228 It's not possible in this case for the cofactors to be equal, but it 229 is possible for the twist cofactor to be larger. The latter is 230 considered dangerous because algorithms that depend on the cofactor 231 of the curve may be vulnerable if a point on the twist is accepted. 233 Input: a prime p, with p = 1 mod 4 234 Output: the parameter d defining the curve tEd 235 1. Set d = 0 236 2. repeat 237 repeat 238 if (d > 0) then 239 d = -d 240 else 241 d = -d + 1 242 end if 243 until d is not a square in GF(p) 245 Compute oddDivisor, oddDivisor', cofactor, cofactor' where #tEd(GF(p)) = 246 cofactor * oddDivisor, #tEd'(GF(p)) = cofactor' * oddDivisor', cofactor 247 and cofactor' are powers of 2 and oddDivisor, oddDivisor' are odd. 248 until (cofactor = 8 and cofactor' = 4 and rd is prime and rd' is prime) 249 3. Output d 251 GenerateCurveTEdwards 253 6.3. Generators 255 Any point with the correct order will serve as a generator for the 256 group. The following algorithm computes a possible generator by 257 taking the smallest positive value x in GF(p) (when represented as an 258 integer) such that (x, y) is on the curve and such that (X(P),Y(P)) = 259 8 * (x, y) has large prime order oddDivisor. 261 Input: a prime p and curve parameters non-square d and 262 a = -1 for twisted Edwards (p = 1 mod 4) or 263 a = 1 for Edwards (p = 3 mod 4) 264 Output: a generator point P = (X(P), Y(P)) of order oddDivisor 265 1. Set x = 0 and found_gen = false 266 2. while (not found_gen) do 267 x = x + 1 268 while ((1 - a * x^2) * (1 - d * x^2) is not a quadratic 269 residue mod p) do 270 x = x + 1 271 end while 272 Compute an integer s, 0 < s < p, such that 273 s^2 * (1 - d * x^2) = 1 - a * x^2 mod p 274 Set y = min(s, p - s) 276 (X(P), Y(P)) = 8 * (x, y) 278 if ((X(P), Y(P)) has order oddDivisor on Ed or tEd, respectively) then 279 found_gen = true 280 end if 281 end while 282 3. Output (X(P),Y(P)) 284 GenerateGen 286 7. Recommended Curves 288 For the ~128-bit security level, the prime 2^255-19 is recommended 289 for performance over a wide-range of architectures. This prime is 290 congruent to 1 mod 4 and the above procedure results in the following 291 twisted Edwards curve, called "intermediate25519": 293 p 2^255-19 295 d 121665 297 order 2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed 299 cofactor 8 301 In order to be compatible with widespread existing practice, the 302 recommended curve is an isogeny of this curve. An isogeny is a 303 "renaming" of the points on the curve and thus cannot affect the 304 security of the curve: 306 p 2^255-19 307 d 370957059346694393431380835087545651895421138798432190163887855330 308 85940283555 310 order 2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed 312 cofactor 8 314 X(P) 151122213495354007725011514095885315114540126930418572060461132 315 83949847762202 317 Y(P) 463168356949264781694283940034751631413079938662562256157830336 318 03165251855960 320 The d value in the this curve is much larger than the generated curve 321 and this might slow down some implementations. If this is a problem 322 then implementations are free to calculate on the original curve, 323 with small d as the isogeny map can be merged into the affine 324 transform without any performance impact. 326 The latter curve is isomorphic to a Montgomery curve defined by v^2 = 327 u^3 + 486662u^2 + u where the maps are: 329 (u, v) = ((1+y)/(1-y), sqrt(-1)*sqrt(486664)*u/x) 330 (x, y) = (sqrt(-1)*sqrt(486664)*u/v, (u-1)/(u+1) 332 The base point maps onto the Montgomery curve such that u = 9, v = 14 333 781619447589544791020593568409986887264606134616475288964881837755586 334 237401. 336 The Montgomery curve defined here is equal to the one defined in 337 [curve25519] and the isomorphic twisted Edwards curve is equal to the 338 one defined in [ed25519]. 340 8. Wire-format of field elements 342 When transmitting field elements in the Diffie-Hellman protocol 343 below, they MUST be encoded as an array of bytes, x, in little-endian 344 order such that x[0] + 256 * x[1] + 256^2 * x[2] + ... + 256^n * x[n] 345 is congruent to the value modulo p and x[n] is minimal. On receiving 346 such an array, implementations MUST mask the (8-log2(p)%8)%8 most- 347 significant bits in the final byte. This is done to preserve 348 compatibility with point formats which reserve the sign bit for use 349 in other protocols and to increase resistance to implementation 350 fingerprinting. 352 (NOTE: draft-turner-thecurve25519function also says "Implementations 353 MUST reject numbers in the range [2^255-19, 2^255-1], inclusive." but 354 I'm not aware of any implementations that do so.) 356 9. Elliptic Curve Diffie-Hellman 358 This section describes how to perform Diffie-Hellman using curves 359 generated by the above procedure. For safety reasons, Diffie-Hellman 360 is performed on the Montgomery isomorphism of the curve and the 361 public values transmitted are u coordinates. 363 Let U denote the projection map from a point (u,v) on E, to u, 364 extended so that U of the point at infinity is zero. U is surjective 365 onto GF(p) if the v coordinate takes on values in GF(p) and in a 366 quadratic extension of GF(p). 368 Then DH(s, U(Q)) = U(sQ) is a function defined for all integers s and 369 elements U(Q) of GF(p). Proper implementations use a restricted set 370 of integers for s and only u-coordinates of points Q defined over 371 GF(p). The remainder of this section describes how to compute this 372 function quickly and securely, and use it in a Diffie- Hellman 373 scheme. 375 Let s be a 255 bits long integer, where s = sum s_i * 2^i with s_i in 376 {0, 1}. 378 Computing DH(s, u) is done by the following procedure, taken from 379 [curve25519] based on formulas from [montgomery]. All calculations 380 are performed in GF(p), i.e., they are performed modulo p. The 381 parameter a24 is a24 = (486662 - 2) / 4 = 121665. 383 x_1 = u 384 x_2 = 0 385 z_2 = 1 386 x_3 = u 387 z_3 = 1 388 For t = 254 down to 0: 389 // Conditional swap; see text below. 390 (x_2, x_3) = cswap (s_t, x_2, x_3) 391 (z_2, z_3) = cswap (s_t, z_2, z_3) 392 A = x_2 + z_2 393 AA = A^2 394 B = x_2 - z_2 395 BB = B^2 396 E = AA - BB 397 C = x_3 + z_3 398 D = x_3 - z_3 399 DA = D * A 400 CB = C * B 401 x_3 = (DA + CB)^2 402 z_3 = x_1 * (DA - CB)^2 403 x_2 = AA * BB 404 z_2 = E * (AA + a24 * E) 405 // Conditional swap; see text below. 406 (x_2, x_3) = cswap (s_t, x_2, x_3) 407 (z_2, z_3) = cswap (s_t, z_2, z_3) 408 Return x_2 * (z_2^(p - 1)) 410 In implementing this procedure, due to the existence of side-channels 411 in commodity hardware, it is important that the pattern of memory 412 accesses and jumps not depend on the values of any of the bits of s. 413 It is also important that the arithmetic used not leak information 414 about the integers modulo p (such as having b * c distinguishable 415 from c * c). 417 The cswap instruction SHOULD be implemented in constant time 418 (independent of s_t) as follows: 420 cswap(s_t, x_2, x_3) 421 dummy = s_t * (x_2 - x_3) 422 x_2 = x_2 - dummy 423 x_3 = x_3 + dummy 424 Return (x_2, x_3) 426 where s_t is 1 or 0. Alternatively, an implementation MAY use the 427 following: 429 cswap(s_t, x_2, x_3) 430 dummy = mask(s_t) AND (x_2 XOR x_3) 431 x_2 = x_2 XOR dummy 432 x_3 = x_3 XOR dummy 433 Return (x_2, x_3) 435 where mask(s_t) is the all-1 or all-0 word of the same length as x_2 436 and x_3, computed, e.g., as mask(s_t) = 1 - s_t. The latter version 437 is often more efficient. 439 9.1. Diffie-Hellman protocol 441 The DH function can be used in an ECDH protocol with the recommended 442 curve as follows: 444 Alice generates 32 random bytes in f[0] to f[31]. She masks the 445 three rightmost bits of f[0] and the leftmost bit of f[31] to zero 446 and sets the second leftmost bit of f[31] to 1. This means that f is 447 of the form 2^254 + 8 * {0, 1, ..., 2^(251) - 1} as a little-endian 448 integer. 450 Alice then transmits K_A = DH(f, 9) to Bob, where 9 is the number 9. 452 Bob similarly generates 32 random bytes in g[0] to g[31], applies the 453 same masks, computes K_B = DH(g, 9) and transmits it to Alice. 455 Alice computes DH(f, DH(g, 9)); Bob computes DH(g, DH(f, 9)) using 456 their generated values and the received input. 458 Both of them now share K = DH(f, DH(g, 9)) = DH(g, DH(f, 9)) as a 459 shared secret. Alice and Bob can then use a key-derivation function, 460 such as hashing K, to compute a key. 462 10. Test vectors 464 The following test vectors are taken from [nacl]. All numbers are 465 shown as little-endian hexadecimal byte strings: 467 Alice's private key, f: 469 77 07 6d 0a 73 18 a5 7d 3c 16 c1 72 51 b2 66 45 470 df 4c 2f 87 eb c0 99 2a b1 77 fb a5 1d b9 2c 2a 472 Alice's public key, DH(f, 9): 474 85 20 f0 09 89 30 a7 54 74 8b 7d dc b4 3e f7 5a 475 0d bf 3a 0d 26 38 1a f4 eb a4 a9 8e aa 9b 4e 6a 477 Bob's private key, g: 479 5d ab 08 7e 62 4a 8a 4b 79 e1 7f 8b 83 80 0e e6 480 6f 3b b1 29 26 18 b6 fd 1c 2f 8b 27 ff 88 e0 eb 482 Bob's public key, DH(g, 9): 484 de 9e db 7d 7b 7d c1 b4 d3 5b 61 c2 ec e4 35 37 485 3f 83 43 c8 5b 78 67 4d ad fc 7e 14 6f 88 2b 4f 487 Their shared secret, K: 489 4a 5d 9d 5b a4 ce 2d e1 72 8e 3b f4 80 35 0f 25 490 e0 7e 21 c9 47 d1 9e 33 76 f0 9b 3c 1e 16 17 42 492 11. References 494 11.1. Normative References 496 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 497 Requirement Levels", BCP 14, RFC 2119, March 1997. 499 11.2. Informative References 501 [AS] Satoh, T. and K. Araki, "Fermat quotients and the 502 polynomial time discrete log algorithm for anomalous 503 elliptic curves", 1998. 505 [EBP] ECC Brainpool, "ECC Brainpool Standard Curves and Curve 506 Generation", October 2005, . 509 [NIST] National Institute of Standards, "Recommended Elliptic 510 Curves for Federal Government Use", July 1999, 511 . 514 [S] Semaev, I., "Evaluation of discrete logarithms on some 515 elliptic curves", 1998. 517 [SC] Bernstein, D. and T. Lange, "SafeCurves: choosing safe 518 curves for elliptic-curve cryptography", June 2014, 519 . 521 [SEC1] Certicom Research, "SEC 1: Elliptic Curve Cryptography", 522 September 2000, 523 . 525 [Smart] Smart, N., "The discrete logarithm problem on elliptic 526 curves of trace one", 1999. 528 [curve25519] 529 Bernstein, D., "Curve25519 -- new Diffie-Hellman speed 530 records", 2006, 531 . 534 [ed25519] Bernstein, D., Duif, N., Lange, T., Schwabe, P., and B. 535 Yang, "High-speed high-security signatures", 2011, 536 . 538 [montgomery] 539 Montgomery, P., "Speeding the Pollard and elliptic curve 540 methods of factorization", 1983, 541 . 544 [nacl] Bernstein, D., "Cryptography in NaCl", 2009, 545 . 547 Author's Address 549 Adam Langley 550 Google 551 345 Spear St 552 San Francisco, CA 94105 553 US 555 Email: agl@google.com