idnits 2.17.1 draft-ladd-safecurves-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (15 January 2014) is 3747 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 1 error (**), 0 flaws (~~), 1 warning (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Draft W. Ladd 3 Grad Student 4 Category: Informational UC Berkeley 5 Expires 19 July 2014 15 January 2014 7 Additional Elliptic Curves for IETF protocols 8 10 Status of this Memo 12 Distribution of this memo is unlimited. 14 This Internet-Draft is submitted in full conformance with the 15 provisions of BCP 78 and BCP 79. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note that 19 other groups may also distribute working documents as Internet- 20 Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six months 23 and may be updated, replaced, or obsoleted by other documents at any 24 time. It is inappropriate to use Internet-Drafts as reference 25 material or to cite them other than as "work in progress." 27 The list of current Internet-Drafts can be accessed at 28 http://www.ietf.org/ietf/1id-abstracts.txt. 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html. 33 This Internet-Draft will expire on 9 July 2014. 35 Copyright Notice 37 Copyright (c) 2014 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. 47 Abstract 49 This Internet Draft explains the mathematics behind and the 50 parameters of a new family of elliptic curves with efficiency and 51 security advantages over existing and widely deployed mechanisms. 53 Table of Contents 55 1. Introduction ....................................................3 56 2. Explicit Formulas ...............................................3 57 3. The Curves ......................................................6 58 4. Point Encoding ..................................................9 59 5. Security Considerations .........................................9 60 6. IANA Considerations .............................................9 61 7. Acknowledgements ................................................9 62 8. References .....................................................10 63 1. Introduction 65 This document contains a set of elliptic curves over prime fields 66 with many security and performance advantages. They are twist-secure, 67 have large prime-order subgroups, high embedding degree, endomorphism 68 rings of large discriminant, complete formulas, and primes selected 69 for fast arithmetic. The reader who wishes to learn more about these 70 properties and their necessity is refered to [SILVERMAN]. 72 These curves have been generated in a rigid manner by computer 73 search. As such there is very little risk that these curves were 74 selected to exhibit weaknesses to attacks not in the open literature. 75 The field is the only free choice, and in all circumstances has been 76 picked to enable highly efficient arithmetic. Proofs of all 77 properties claimed exist in [SAFECURVES]. It is easier to avoid known 78 implementation issues with these curves then short Weierstrass 79 curves. 80 2. Explicit Formulas 82 Let p be a prime number. There is a unique field with p elements. Its 83 elements can be represented as the set of integers {0, 1, ... p}. 84 Fields have three operations: addition, multiplication, and 85 multiplicative and additive inverses. They have two distinguished 86 elements: 0, and 1. 88 To add two numbers, a and b, one computes the integer a+b, and takes 89 the remainder on division by p. 91 To multiply two numbers a and b, one computes a*b, and takes the 92 remainder on division by p. 94 Algorithms are in [COHEN]. 96 To compute the additive inverse of a, one can compute (p-1)*a, and 97 again take the remainder. 99 To compute the multiplicative inverse of a, written a^(-1) the best 100 way to avoid side channel attacks is to calculate a^(p-2), reducing 101 each intermediate product modulo p. To take exponents efficiently, 102 one uses a square-and-multiply algorithm, i.e. compute a^{2n+1} as 103 a*(a^{n})^2, a^{2n} as (a^{n})^2. The multiplicative inverse of 0 is 104 undefined. 106 0+a=a for all a. a*1=a for all a. a*a^{-1}=1 for all a nonzero. 108 The field with p elements is denoted GF(p). 110 An abelian group is a set S with two operations: addition and 111 inverse, denoted + and unary - respectively, and a distinguished 112 element e. a+e=e+a=a, a+-a=e, and addition is commutative. 114 [n]a is defined as [0]a=e, [n]a=a+[n-1]a for n a positive integer, 115 and extended by taking [-1]a=-a to negative integers. 117 Given an element of an abelian group a in A, the order of a is the 118 smallest positive integer n such that [n]a=e. The cofactor of a is 119 the size of A divided by the order of a. By a classical theorem of 120 Lagrange the cofactor is an integer. 122 The remainder of this standard defines abelian groups in which for a 123 fixed basepoint (denoted p), distinguishing between (g, [a]p, [b]p, 124 [ab]p) with a, b picked uniformly at random from nonnegative integers 125 less then the order, and (g, [a]g, [b]g, [c]g), is hard without 126 spending prohibitive amounts of time. The time required is the square 127 root of the order of g. 129 These groups are defined over the set of points with coordinates x 130 and y satisfying a given equation. They are different from the short 131 Weierstrass equations found in many standards. 133 On any abelian group if we take the sets {a, -a} with a ranging over 134 A, we no longer have a well defined addition. However, we still have 135 a well defined multiplication by n map, as -([n]a)=[-n]a. In the 136 context of abelian varieties, this is called "taking the Kummer 137 variety", and the set of subset is the Kummer variety. 139 To take the Kummer variety of an elliptic curve in the form 140 y^2=x^3+Ax^2+x, an Edwards curve, one drops the y coordinate. 142 The elliptic-curve Diffie-Hellman key agreement protocol on a curve 143 with basepoint g of cofactor h and order q is as follows: 145 Alice picks a random integer a from the range [1,q-1], computes 146 [a*h]g, and transmits it to Bob. 148 Bob picks a random integer b from the range [1,q-1], computes [b*h]g, 149 and transmits it to Alice. 151 Both Alice and Bob determine [a*b*h^2]g, Alice as [a*h]([b*h]g), and 152 likewise for Bob. This can be hashed to give a short shared secret. 154 This protocol will work on a Kummer variety as well. 156 On Montgomery curves, curves of the form y^2=x^3+a*x^2+x, the typical 157 technique is to work over the Kummer variety instead, i.e. drop y 158 coordinates for use in Diffie-Hellman. Let (X_1,Z_1), (X_2,Z_2), 159 (X_3,Z_3) be coordinates such that X_1/Z_1, X_2/Z_2, X_3/Z_3 are the 160 x coordinates of P, Q, and P+Q respectively. Then the equations 161 A = X2+Z2 162 AA = A^2 163 B = X2 - Z2 164 BB = B^2 165 E = AA - BB 166 C = X3 + Z3 167 D = X3 - Z3 168 DA = D*A 169 CB = C*B 170 X5 = Z1*(DA+CB)^2 171 Z5 = X1*(DA-CB)^2 172 X4 = AA*BB 173 Z4 = E*(BB+a24*E) 175 gives X_4/Z_4 as the x coordinate of [2]Q, and X_5/Z_5 as the x 176 coordinate of P+[2]Q where a24=(a+2)/4. If in calculating [n](X, Z), 177 Z of the result is zero, this indicates that [n](X,Z) is the point at 178 infinity, and so the result has x-coordinate 0. 180 These equations originally appeared in [MONTGOMERY]. 182 To use this to calculate multiplication on the Kummer variety, the 183 following routine will work to calculate [n]P, given the x coordinate 184 of P, if [n]P is not the identity of the group. For ECDH this routine 185 is adequate as returning 0 for the identity is acceptable and does 186 not lose security. 188 1: Intilize P_0=[0,1], and P_1=[x_P,1] 2: Iterate over the bits of n 189 from most to least significant 2.1: If the bit is 0, let P_1=P_1+P_0, 190 P_0=2P_0 2.2: If the bit is 1, let P_0=P_1+P_0, P_1=2P_1 3: Write 191 [x_f, z_f]=P_0 4: If z_f is 0, return 0. Otherwise return x_f/z_f. 193 Note that the difference between P_1 and P_0 is always [x_P, 1], so 194 the differential addition formula above suffices. In implementing the 195 above algorithm the conditionals should be implemented by means of 196 constant time conditional swaps rather than jumps to avoid timing and 197 control flow attacks. n should be represented with a fixed number of 198 bits to further minimize timing information. Skipping intial zeros is 199 a terrible idea. 201 When using this algorithm, no checks on the x coordinate are required 202 for the Montgomery curves in this standard: they are designed to 203 resist all attacks that involve transmitting an invalid x coordinate 204 in the above algorithm. 206 On (twisted) Edwards curves, curves of the form a*x^2+y^2=1+d*x^2y^2, 207 a complete addition formula, which works for doubling as well, is 208 given by representing points in projective coordinates. The formula 209 for adding (X_1, Y_1, Z_1) to (X_2, Y_2, Z_2) is then 210 A = Z1*Z2 211 B = A^2 212 C = X1*X2 213 D = Y1*Y2 214 E = d*C*D 215 F = B-E 216 G = B+E 217 X3 = A*F*((X1+Y1)*(X2+Y2)-C-D) 218 Y3 = A*G*(D-a*C) 219 Z3 = F * G 221 These formulas are from the [EFD], reporting results in [BL07]. Every 222 point on an Edwards curve can be represented, so Z=0 does not occur. 223 This formula can be used for doubling also by letting (X_1,Y_1,Z_1)= 224 (X_2,Y_2,Z_2). For most of the curves with the exception of T25519 225 a=1, saving a multiplication. 227 The Montgomery ladder algorithm from above will work with this 228 addition and doubling, taking care to represent points as triples, 229 and check that points lie on the curve going into and out of the 230 routine. 232 The above algorithms are not the only algorithms possible. One can 233 use alternative parametrizations such as inverted Edwards coordinates 234 to make point operations cheaper, alternative algorithms such as 235 radix-k or sliding window methods to reduce the number of additions 236 and increase the number of doublings, and isogenies to transform 237 Montgomery curves into Edwards curves to take advantage of these 238 techniques. However, implementors should take care to avoid timing 239 and cache side-channels when implementing any of these techniques. 240 More information on some of these techniques is in [TWIST]. 242 3. The Curves 244 These curves were selectd as follows: first a field was picked which 245 because of its form permits specialized, faster arithemetic. Then the 246 curve shape was selected, either Edwards or Montgomery. Lastly, a 247 computer search was made for the smallest parameter that would let 248 the curve satisfy security criteria. 250 One curve, T25519, is isomorphic to Curve25519 but is not of the 251 above form. It is included because of the desire for a curve of size 252 approximately 2^250 on which addition makes sense for use in 253 signature schemes. 255 Since the field GF(p) has no subfields, Weil restriction is not a 256 concern. The curves not only needed to have a large prime order 257 subgroup, but the quadratic twist of the curve needed to as well. The 258 curves also had to satisfy equations prohibiting the existence of 259 bilinear maps into small fields as well as have no efficiently 260 evaluatable endomorphisms beyond the negation map. 262 Because of the curve shapes being used, exceptional cases are less of 263 an issue then with short Weierstrass curves. 265 Each curve is given by an equation and a basepoint, together with the 266 order of the point and the cofactor. 268 Curve1174 is a curve over GF(2^251-9), formula x^2+y^2=1-1174x^2y^2, 269 basepoint (158261909772591154195454700645373976338109 270 1388846394833492296309729998839514, 271 30375380136041545047641157286514376465 272 19513534305223422754827055689195992590), order 2^249 - 273 11332719920821432534773113288178349711, cofactor 4. 275 Curve25519 is a curve over GF(2^255-19), formula y^2=x^3+486662x^2+x, 276 basepoint (9, 147816194475895447910205935684099868872646 277 06134616475288964881837755586237401), order 2^252 + 278 27742317777372353535851937790883648493, cofactor 8. 280 T25519 is a curve over GF(2^255-19) formula 281 121666x^2+y^2=1+121665x^2y^2, basepoint (6, 282 158858074951644465347792977535893721270128458670434237 283 40362095615172183684671), order 2^252 + 284 27742317777372353535851937790883648493, cofactor 8. 286 E382 is a curve over GF(2^382-105), formula x^2+y^2=1-67254x^2y^2, 287 basepoint (3914921414754292646847594472454013487047 288 137431784830634731377862923477302047857640522480241 289 298429278603678181725699, 17), order 2^380 - 290 1030303207694556153926491950732314247062623204330168346855, cofactor 291 4. 293 M383 is a curve over GF(2^383-187), formula y^2=x^3+2065150x^2+x, 294 basepoint (12, 295 473762340189175399766054630037590257683961716725770372563038 296 9791524463565757299203154901655432096558642117242906494), order 2^380 297 + 166236275931373516105219794935542153308039234455761613271, cofactor 298 8. 300 Curve3617 is a curve over GF(2^414-17), formula x^2+y^2=1+3617x^2y^2, 301 basepoint 302 (17319886477121189177719202498822615443556957307604340815256226 303 171904769976866975908866528699294134494857887698432266169206165, 34), 304 order 2^411 - 305 33364140863755142520810177694098385178984727200411208589594759, 306 cofactor 8. 308 Ed448-Goldilocks is a curve over GF(2^448-2^224-1), formula 309 x^2+y^2=1-39081x^2y^2, basepoint 310 (1178121612634369467372824843433100646651805353570163734168790821 311 47939404277809514858788439644911793978499419995990477371552926 312 308078495, 19), order 2^446 - 313 13818066809895115352007386748515426880336692474882178609894547503885, 314 cofactor 4. 316 M511 is a curve over GF(2^511-187), formula y^2 = x^3+530438x^2+x, 317 basepoint (5, 318 25004106455650724233689811491392132522115686851736085900709792642 319 48275228603899706950518127817176591878667784247582124505430745177 320 116625808811349787373477), order 2^508 + 321 107247547596357476240445315140681218420707566274348330289655408 322 08827675062043, cofactor 8. 324 E521 is a curve over GF(2^521-1), formula x^2+y^2=1-376014x^2y^2, 325 basepoint 326 (1571054894184995387535939749894317568645297350402905821437625 327 18115230499438118852963259119606760410077267392791511426719338990 328 5003276673749012051148356041324, 12), order 2^519 - 329 3375547632585017057891076304187826360719049612140512266186351500 330 85779108655765, cofactor 4. 332 4. Point Encoding 334 Let (x,y) be a point on M(GF_p), where M is a Montgomery curve. Then 335 let l=ceil[log(p)/log(256)]. A point is represented as l-bytes, 336 representing in big-endian radix 256 the minimal representative of 337 [x] modulo p. This representation works for the standard x-coordinate 338 only arithmetic for ECDH, but cannot be used for protocols requiring 339 addition. 341 Let (x,y) be a point on E(GF_p), where E is an Edwards Curve. Let 342 l=floor[log(p)/log(256)]+1. A point is represented as l bytes, l 343 representing in big-endian radix 256 the minimal representative of 344 [y] modulo p, and the top bit of the top byte set to equal the low 345 bit of x. Because we have always ensured that there is extra room in 346 l than is strictly required to represent y, we have room for the top 347 bit to be set. 349 Point encoding is clear in both cases. To decode a point on an 350 Edwards curve with parameter d, one takes the y value and computes 351 Alternative encodings are used by existing software, and protocol 352 designers should be aware of this. Alternative encodings may be 353 useful if preexisting software is to be used without changes. 355 5. Security Considerations 357 This entire document discusses methods of implementing cryptography 358 securely. The time for an attacker to break the DLP on these curves 359 is the square root of the group order with the best known attacks. 360 These curves are twist-secure, limiting the impact of wrong-curve 361 attacks on Montgomery ladders. 363 It is recommended that implementors use the Montgomery ladder on 364 Montgomery curves with x coordinate only to avoid timing attacks when 365 Diffie-Hellman is being used. In this mode, curve checks are not 366 required. On Edwards curves, standard curve (but not group) 367 membership checks are required for ECDH to be secure. Implementors 368 should pay attention to the cofactor in the discussion of ECDH in 369 section 2, and avoid forgetting the cofactor. While the impact is 370 slight, it should still be avoided. 372 These curves and cited formulas are complete, avoiding certain 373 attacks against naive implementations of ECC protocols. They have 374 cofactor greater than one, occasionally requiring slight adjustments 375 to protocols such as using multiples of the cofactor as keys for ECDH 376 or similar representations for signature schemes. 378 This is not an exhaustive discussion of security considerations 379 relating to the implementation of these curves. Implementors must be 380 familiar with cryptography to safely implement any cryptographic 381 standard, and this standard is no exception. 383 6. IANA Considerations 385 IANA should assign OIDs to these curves. 387 7. Acknowledgments 388 Thanks to Alyssa Rowan and Robert Ransom for catching transcription 389 and formula errors. Paul Lambert was the guinea pig for implemention 390 guidelines. Paul Hoffman noticed the cofactor was missing. Manuel 391 Pegourie-Gonnard noticed suboptimal formulas and corrected them, as 392 well as inadvertent misstatements and underspecifications. Thanks to 393 David McGrew for providing editorial support. Thanks to the various 394 members of the CFRG who provided advice on the text, and to Michael 395 Hamburg for discussing adaptation of the point encoding to Ed448- 396 Goldilocks. Jeff "=JeffH" Hodges recommended Silverman as a 397 reference. 399 8. References 401 [BL07] Bernstein, Daniel J and Tanja Lange. ``Faster addition and 402 doubling on elliptic curves.'' Pages 29-50 in Kurosawa, Advances in 403 Cryptology:ASIACRYPT 2007. Lecture Notes in Computer Science 4833, 404 Springer-Verlag Berlin, 2007. 406 [COHEN] Cohen, Henri. A Course in Computational Algebraic Number 407 Theory, GTM 138, Springer-Verlag, 1993. 409 [EFD] Lange, Tanja. Explicit Formula Database. 410 http://www.hyperelliptic.org/EFD/g1p/index.html 412 [MONTGOMERY] Montgomery, Peter L. ``Speeding the Pollard and elliptic 413 curves methods of factorization''. Mathematics of Computation 48 414 (1987), 243-264. MR 88e:11130. 416 [SAFECURVES] Berstein, Daniel J, and Tanja Lange. Safecurves. 417 safecurves.cr.yp.to 419 [SILVERMAN] Silverman, Joseph H. The Arithmetic of Elliptic Curves, 420 GTM 106. Springer-Verlag Berlin, 2009. 422 [TWIST] Bernstein, Daniel J, Peter Birkner, Marc Joye, Tanja Lange, 423 and Christiane Peters. ``Twisted Edwards Curves''. In Vaudany, Serg. 424 Avances in Cryptology:AFRICACRYPT 2008. Lecture Notes in Computer 425 Science 5023. Springer-Verlag, Berlin 2008. Preprint from 426 http://eprint.iacr.org/2008/013.pdf 428 Author's Address 429 Watson Ladd 430 watsonbladd@gmail.com 431 Berkeley, CA