idnits 2.17.00 (12 Aug 2021) /tmp/idnits36877/draft-black-rpgecc-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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (November 26, 2014) is 2732 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 ---------------------------------------------------------------------------- == Unused Reference: 'ECCP' is defined on line 335, but no explicit reference was found in the text == Unused Reference: 'FPPR' is defined on line 340, but no explicit reference was found in the text == Unused Reference: 'MSR' is defined on line 343, but no explicit reference was found in the text == Unused Reference: 'RFC3279' is defined on line 353, but no explicit reference was found in the text == Unused Reference: 'RFC3552' is defined on line 358, but no explicit reference was found in the text == Unused Reference: 'RFC4050' is defined on line 362, but no explicit reference was found in the text == Unused Reference: 'RFC4492' is defined on line 366, but no explicit reference was found in the text == Unused Reference: 'RFC4754' is defined on line 370, but no explicit reference was found in the text == Unused Reference: 'RFC5226' is defined on line 374, but no explicit reference was found in the text == Unused Reference: 'RFC5480' is defined on line 378, but no explicit reference was found in the text == Unused Reference: 'RFC5753' is defined on line 382, but no explicit reference was found in the text == Unused Reference: 'RFC6090' is defined on line 386, but no explicit reference was found in the text -- Obsolete informational reference (is this intentional?): RFC 4492 (Obsoleted by RFC 8422) -- Obsolete informational reference (is this intentional?): RFC 5226 (Obsoleted by RFC 8126) Summary: 0 errors (**), 0 flaws (~~), 13 warnings (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group B. Black 3 Internet-Draft Microsoft 4 Intended status: Informational J. Bos 5 Expires: May 30, 2015 NXP Semiconductors 6 C. Costello 7 Microsoft Research 8 A. Langley 9 Google Inc 10 P. Longa 11 M. Naehrig 12 Microsoft Research 13 November 26, 2014 15 Rigid Parameter Generation for Elliptic Curve Cryptography 16 draft-black-rpgecc-00 18 Abstract 20 This memo describes algorithms for deterministically generating 21 parameters for elliptic curves over prime fields offering high 22 practical security in cryptographic applications, including Transport 23 Layer Security (TLS) and X.509 certificates. The algorithms can 24 generate domain parameters at any security level for modern (twisted) 25 Edwards curves. 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 May 30, 2015. 44 Copyright Notice 46 Copyright (c) 2014 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 . . . . . . . . . . . . . . . . . . . . . . . . 2 62 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 3 63 2. Scope and Relation to Other Specifications . . . . . . . . . 3 64 3. Security Requirements . . . . . . . . . . . . . . . . . . . . 3 65 4. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 3 66 5. Parameter Generation . . . . . . . . . . . . . . . . . . . . 4 67 5.1. Deterministic Curve Parameter Generation . . . . . . . . 4 68 5.1.1. Twisted Edwards Curves . . . . . . . . . . . . . . . 4 69 5.1.2. Edwards Curves . . . . . . . . . . . . . . . . . . . 5 70 6. Generators . . . . . . . . . . . . . . . . . . . . . . . . . 6 71 7. Test Vectors . . . . . . . . . . . . . . . . . . . . . . . . 6 72 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 7 73 9. Security Considerations . . . . . . . . . . . . . . . . . . . 7 74 10. Intellectual Property Rights . . . . . . . . . . . . . . . . 7 75 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 7 76 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 8 77 12.1. Normative References . . . . . . . . . . . . . . . . . . 8 78 12.2. Informative References . . . . . . . . . . . . . . . . . 8 79 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 9 81 1. 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 twisted 104 Edwards curve -x^2 + y^2 = 1 + dx^2y^2 is used for primes p with p = 105 1 mod 4, and the Edwards curve x^2 + y^2 = 1 + dx^2y^2 is used with 106 primes p with p = 3 mod 4. 108 1.1. 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 2. Scope and Relation to Other Specifications 116 This document specifies a deterministic algorithm for generating 117 elliptic curve domain parameters over prime fields GF(p), with p 118 having a length of twice the desired security level in bits, in 119 (twisted) Edwards form. Furthermore, this document identifies the 120 security and implementation requirements for the generated domain 121 parameters. 123 3. Security Requirements 125 For each curve at a specific security level: 127 1. The domain parameters SHALL be generated in a simple, 128 deterministic manner, without any secret or random inputs. The 129 derivation of the curve parameters is defined in Section 5. 131 2. The trace of Frobenius MUST NOT be in {0, 1} in order to rule out 132 the attacks described in [Smart], [AS], and [S], as in [EBP]. 134 3. MOV Degree: the embedding degree k MUST be greater than (r - 1) / 135 100, as in [EBP]. 137 4. CM Discriminant: discriminant D MUST be greater than 2^100, as in 138 [SC]. 140 4. Notation 142 Throughout this document, the following notation is used: 144 p: Denotes the prime number defining the base field. 145 GF(p): The finite field with p elements. 146 d: An element in the finite field GF(p), different from -1,0. 147 Ed: The elliptic curve Ed/GF(p): x^2 + y^2 = 1 + dx^2y^2 in 148 Edwards form, defined over GF(p) by the parameter d. 149 tEd: The elliptic curve tEd/GF(p): -x^2 + y^2 = 1 + dx^2y^2 in 150 twisted Edwards form, defined over GF(p) by the parameter d. 151 rd: The largest odd divisor of the number of GF(p)-rational 152 points on Ed or tEd. 153 td: The trace of Frobenius of Ed or tEd such that 154 #Ed(GF(p)) = p + 1 - td or #tEd(GF(p)) = p + 1 - td, 155 respectively. 156 rd': The largest odd divisor of the number of GF(p)-rational 157 points on Ed' or tEd'. 158 hd: The index (or cofactor) of the subgroup of order rd in the 159 group of GF(p)-rational points on Ed or tEd. 160 hd': The index (or cofactor) of the subgroup of order rd' in the 161 group of GF(p)-rational points on the non-trivial quadratic 162 twist of Ed or tEd. 163 P: A generator point defined over GF(p) of prime order rd on Ed 164 or tEd. 165 X(P): The x-coordinate of the elliptic curve point P. 166 Y(P): The y-coordinate of the elliptic curve point P. 168 5. Parameter Generation 170 This section describes the generation of the curve parameters, namely 171 the curve parameter d, and a generator point P of the prime order 172 subgroup of the elliptic curve. 174 5.1. Deterministic Curve Parameter Generation 176 5.1.1. Twisted Edwards Curves 178 For a prime p = 1 mod 4, the elliptic curve tEd in twisted Edwards 179 form is determined by the non-square element d from GF(p), different 180 from -1,0 with smallest absolute value such that #tEd(GF(p)) = hd * 181 rd, #tEd'(GF(p)) = hd' * rd', {hd, hd'} = {4, 8} and both subgroup 182 orders rd and rd' are prime. In addition, care must be taken to 183 ensure the MOV degree and CM discriminant requirements from Section 3 184 are met. 186 Input: a prime p, with p = 1 mod 4 187 Output: the parameter d defining the curve tEd 188 1. Set d = 0 189 2. repeat 190 repeat 191 if (d > 0) then 192 d = -d 193 else 194 d = -d + 1 195 end if 196 until d is not a square in GF(p) 197 Compute rd, rd', hd, hd' where #tEd(GF(p)) = hd * rd, 198 #tEd'(GF(p)) = hd' * rd', hd and hd' are powers of 2 and rd, rd' 199 are odd 200 until ((hd + hd' = 12) and rd is prime and rd' is prime) 201 3. Output d 203 GenerateCurveTEdwards 205 5.1.2. Edwards Curves 207 For a prime p = 3 mod 4, the elliptic curve Ed in Edwards form is 208 determined by the non-square element d from GF(p), different from 209 -1,0 with smallest absolute value such that #Ed(GF(p)) = hd * rd, 210 #Ed'(GF(p)) = hd' * rd', hd = hd' = 4, and both subgroup orders rd 211 and rd' are prime. In addition, care must be taken to ensure the MOV 212 degree and CM discriminant requirements from Section 3 are met. 214 Input: a prime p, with p = 3 mod 4 215 Output: the parameter d defining the curve Ed 216 1. Set d = 0 217 2. repeat 218 repeat 219 if (d > 0) then 220 d = -d 221 else 222 d = -d + 1 223 end if 224 until d is not a square in GF(p) 225 Compute rd, rd', hd, hd' where #Ed(GF(p)) = hd * rd, 226 #Ed'(GF(p)) = hd' * rd', hd and hd' are powers of 2 and rd, rd' 227 are odd 228 until ((hd = hd' = 4) and rd is prime and rd' is prime) 229 3. Output d 231 GenerateCurveEdwards 233 6. Generators 235 The generator points P = (X(P),Y(P)) for all curves are selected by 236 taking the smallest positive value x in GF(p) (when represented as an 237 integer) such that (x, y) is on the curve and such that (X(P),Y(P)) = 238 8 * (x, y) has large prime order rd. 240 Input: a prime p and curve parameters d and 241 a = -1 for twisted Edwards (p = 1 mod 4) or 242 a = 1 for Edwards (p = 3 mod 4) 243 Output: a generator point P = (X(P), Y(P)) of order rd 244 1. Set x = 0 and found_gen = false 245 2. while (not found_gen) do 246 x = x + 1 247 while ((d * x^2 = 1 mod p) 248 or ((1 - a * x^2) * (1 - d * x^2) is not a quadratic residue 249 mod p)) do 250 x = x + 1 251 end while 252 Compute an integer s, 0 < s < p, such that 253 s^2 * (1 - d * x^2) = 1 - a * x^2 mod p 254 Set y = min(s, p - s) 256 (X(P), Y(P)) = 8 * (x, y) 258 if ((X(P), Y(P)) has order rd on Ed or tEd, respectively) then 259 found_gen = true 260 end if 261 end while 262 3. Output (X(P),Y(P)) 264 GenerateGen 266 7. Test Vectors 268 The following figures give parameters for twisted Edwards and Edwards 269 curves generated using the algorithms defined in previous sections. 270 All integer values are unsigned. 272 p = 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 273 FFFFFFFFFFED 274 d = 0x15E93 275 r = 0x2000000000000000000000000000000016241E6093B2CE59B6B9 276 8FD8849FAF35 277 x(P) = 0x3B7C1D83A0EF56F1355A0B5471E42537C26115EDE4C948391714 278 C0F582AA22E2 279 y(P) = 0x775BE0DEC362A16E78EFFE0FF4E35DA7E17B31DC1611475CB4BE 280 1DA9A3E5A819 281 h = 0x4 283 p = 2^255 - 19 285 p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 286 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC3 287 d = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 288 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD19F 289 r = 0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE2471A1 290 CB46BE1CF61E4555AAB35C87920B9DCC4E6A3897D 291 x(P) = 0x61B111FB45A9266CC0B6A2129AE55DB5B30BF446E5BE4C005763FFA 292 8F33163406FF292B16545941350D540E46C206BDE 293 y(P) = 0x82983E67B9A6EEB08738B1A423B10DD716AD8274F1425F56830F98F 294 7F645964B0072B0F946EC48DC9D8D03E1F0729392 295 h = 0x4 297 p = 2^384 - 317 299 8. Acknowledgements 301 The authors would like to thank Tolga Acar, Karen Easterbrook and 302 Brian LaMacchia for their contributions to the development of this 303 draft. 305 9. Security Considerations 307 TBD 309 10. Intellectual Property Rights 311 The authors have no knowledge about any intellectual property rights 312 that cover the usage of the domain parameters defined herein. 314 11. IANA Considerations 316 There are no IANA considerations for this document. 318 12. References 320 12.1. Normative References 322 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 323 Requirement Levels", BCP 14, RFC 2119, March 1997. 325 12.2. Informative References 327 [AS] Satoh, T. and K. Araki, "Fermat quotients and the 328 polynomial time discrete log algorithm for anomalous 329 elliptic curves", 1998. 331 [EBP] ECC Brainpool, "ECC Brainpool Standard Curves and Curve 332 Generation", October 2005, . 335 [ECCP] Bos, J., Halderman, J., Heninger, N., Moore, J., Naehrig, 336 M., and E. Wustrow, "Elliptic Curve Cryptography in 337 Practice", December 2013, 338 . 340 [FPPR] Faugere, J., Perret, L., Petit, C., and G. Renault, 2012, 341 . 343 [MSR] Bos, J., Costello, C., Longa, P., and M. Naehrig, 344 "Selecting Elliptic Curves for Cryptography: An Efficiency 345 and Security Analysis", February 2014, 346 . 348 [NIST] National Institute of Standards, "Recommended Elliptic 349 Curves for Federal Government Use", July 1999, 350 . 353 [RFC3279] Bassham, L., Polk, W., and R. Housley, "Algorithms and 354 Identifiers for the Internet X.509 Public Key 355 Infrastructure Certificate and Certificate Revocation List 356 (CRL) Profile", RFC 3279, April 2002. 358 [RFC3552] Rescorla, E. and B. Korver, "Guidelines for Writing RFC 359 Text on Security Considerations", BCP 72, RFC 3552, July 360 2003. 362 [RFC4050] Blake-Wilson, S., Karlinger, G., Kobayashi, T., and Y. 363 Wang, "Using the Elliptic Curve Signature Algorithm 364 (ECDSA) for XML Digital Signatures", RFC 4050, April 2005. 366 [RFC4492] Blake-Wilson, S., Bolyard, N., Gupta, V., Hawk, C., and B. 367 Moeller, "Elliptic Curve Cryptography (ECC) Cipher Suites 368 for Transport Layer Security (TLS)", RFC 4492, May 2006. 370 [RFC4754] Fu, D. and J. Solinas, "IKE and IKEv2 Authentication Using 371 the Elliptic Curve Digital Signature Algorithm (ECDSA)", 372 RFC 4754, January 2007. 374 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 375 IANA Considerations Section in RFCs", BCP 26, RFC 5226, 376 May 2008. 378 [RFC5480] Turner, S., Brown, D., Yiu, K., Housley, R., and T. Polk, 379 "Elliptic Curve Cryptography Subject Public Key 380 Information", RFC 5480, March 2009. 382 [RFC5753] Turner, S. and D. Brown, "Use of Elliptic Curve 383 Cryptography (ECC) Algorithms in Cryptographic Message 384 Syntax (CMS)", RFC 5753, January 2010. 386 [RFC6090] McGrew, D., Igoe, K., and M. Salter, "Fundamental Elliptic 387 Curve Cryptography Algorithms", RFC 6090, February 2011. 389 [S] Semaev, I., "Evaluation of discrete logarithms on some 390 elliptic curves", 1998. 392 [SC] Bernstein, D. and T. Lange, "SafeCurves: choosing safe 393 curves for elliptic-curve cryptography", June 2014, 394 . 396 [SEC1] Certicom Research, "SEC 1: Elliptic Curve Cryptography", 397 September 2000, 398 . 400 [Smart] Smart, N., "The discrete logarithm problem on elliptic 401 curves of trace one", 1999. 403 Authors' Addresses 405 Benjamin Black 406 Microsoft 407 One Microsoft Way 408 Redmond, WA 98115 409 US 411 Email: benblack@microsoft.com 412 Joppe W. Bos 413 NXP Semiconductors 414 Interleuvenlaan 80 415 3001 Leuven 416 Belgium 418 Email: joppe.bos@nxp.com 420 Craig Costello 421 Microsoft Research 422 One Microsoft Way 423 Redmond, WA 98115 424 US 426 Email: craigco@microsoft.com 428 Adam Langley 429 Google Inc 431 Email: agl@google.com 433 Patrick Longa 434 Microsoft Research 435 One Microsoft Way 436 Redmond, WA 98115 437 US 439 Email: plonga@microsoft.com 441 Michael Naehrig 442 Microsoft Research 443 One Microsoft Way 444 Redmond, WA 98115 445 US 447 Email: mnaehrig@microsoft.com