idnits 2.17.1 draft-black-numscurves-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 : ---------------------------------------------------------------------------- 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 (August 26, 2014) is 3531 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'TBDOID' is mentioned on line 337, but not defined == Unused Reference: 'ECCP' is defined on line 434, but no explicit reference was found in the text == Unused Reference: 'FPPR' is defined on line 439, but no explicit reference was found in the text == Unused Reference: 'RFC3552' is defined on line 457, but no explicit reference was found in the text == Unused Reference: 'RFC5226' is defined on line 473, 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 (~~), 6 warnings (==), 3 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: February 27, 2015 NXP Semiconductors 6 C. Costello 7 P. Longa 8 M. Naehrig 9 Microsoft Research 10 August 26, 2014 12 Elliptic Curve Cryptography (ECC) Nothing Up My Sleeve (NUMS) Curves and 13 Curve Generation 14 draft-black-numscurves-02 16 Abstract 18 This memo describes a family of deterministically generated Nothing 19 Up My Sleeve (NUMS) elliptic curves over prime fields offering high 20 practical security in cryptographic applications, including Transport 21 Layer Security (TLS) and X.509 certificates. The domain parameters 22 are defined for both classical Weierstrass curves, for compatibility 23 with existing applications, and modern twisted Edwards curves, 24 allowing further efficiency improvements for a given security level. 26 Status of This Memo 28 This Internet-Draft is submitted in full conformance with the 29 provisions of BCP 78 and BCP 79. 31 Internet-Drafts are working documents of the Internet Engineering 32 Task Force (IETF). Note that other groups may also distribute 33 working documents as Internet-Drafts. The list of current Internet- 34 Drafts is at http://datatracker.ietf.org/drafts/current/. 36 Internet-Drafts are draft documents valid for a maximum of six months 37 and may be updated, replaced, or obsoleted by other documents at any 38 time. It is inappropriate to use Internet-Drafts as reference 39 material or to cite them other than as "work in progress." 41 This Internet-Draft will expire on February 27, 2015. 43 Copyright Notice 45 Copyright (c) 2014 IETF Trust and the persons identified as the 46 document authors. All rights reserved. 48 This document is subject to BCP 78 and the IETF Trust's Legal 49 Provisions Relating to IETF Documents 50 (http://trustee.ietf.org/license-info) in effect on the date of 51 publication of this document. Please review these documents 52 carefully, as they describe your rights and restrictions with respect 53 to this document. Code Components extracted from this document must 54 include Simplified BSD License text as described in Section 4.e of 55 the Trust Legal Provisions and are provided without warranty as 56 described in the Simplified BSD License. 58 Table of Contents 60 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 61 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 3 62 2. Scope and Relation to Other Specifications . . . . . . . . . 3 63 3. Requirements . . . . . . . . . . . . . . . . . . . . . . . . 4 64 3.1. Technical Requirements . . . . . . . . . . . . . . . . . 4 65 3.2. Security Requirements . . . . . . . . . . . . . . . . . . 4 66 4. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 5 67 5. Curve Parameters . . . . . . . . . . . . . . . . . . . . . . 5 68 5.1. Parameters for 256-bit Curves . . . . . . . . . . . . . . 5 69 5.2. Parameters for 384-bit Curves . . . . . . . . . . . . . . 6 70 5.3. Parameters for 512-bit Curves . . . . . . . . . . . . . . 7 71 6. Object Identifiers and ASN.1 Syntax for X.509 Certificates . 8 72 6.1. Object Identifiers . . . . . . . . . . . . . . . . . . . 8 73 6.2. ASN.1 Syntax for X.509 Certificates . . . . . . . . . . . 8 74 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 9 75 8. Security Considerations . . . . . . . . . . . . . . . . . . . 9 76 9. Intellectual Property Rights . . . . . . . . . . . . . . . . 9 77 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 78 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 10 79 11.1. Normative References . . . . . . . . . . . . . . . . . . 10 80 11.2. Informative References . . . . . . . . . . . . . . . . . 10 81 Appendix A. Parameter Generation . . . . . . . . . . . . . . . . 12 82 A.1. Prime Generation . . . . . . . . . . . . . . . . . . . . 12 83 A.2. Deterministic Curve Parameter Generation . . . . . . . . 12 84 A.2.1. Weierstrass Curves . . . . . . . . . . . . . . . . . 12 85 A.2.2. Twisted Edwards Curves . . . . . . . . . . . . . . . 13 86 Appendix B. Generators . . . . . . . . . . . . . . . . . . . . . 13 87 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 14 89 1. Introduction 91 Since the initial standardization of elliptic curve cryptography 92 (ECC) in [SEC1] there has been significant progress related to both 93 efficiency and security of curves and implementations. Notable 94 examples are algorithms protected against certain side-channel 95 attacks, different 'special' prime shapes which allow faster modular 96 arithmetic, and a larger set of curve models from which to choose. 97 There is also concern in the community regarding the generation and 98 potential weaknesses of the curves defined in [NIST]. 100 This memo describes a set of elliptic curves for cryptography, 101 defined in [MSR] which have been specifically chosen to support 102 constant-time, exception-free scalar multiplications that are 103 resistant to a wide range of side-channel attacks including timing 104 and cache attacks, thereby offering high practical security in 105 cryptographic applications. These curves are deterministically 106 generated based on algorithms defined in this document and without 107 any hidden parameters or reliance on randomness, hence they are 108 called Nothing Up My Sleeve (NUMS) curves. The domain parameters are 109 defined for both classical Weierstrass curves, for compatibility with 110 existing applications while delivering better performance and 111 stronger security, and modern twisted Edwards curves, allowing even 112 further efficiency improvements for a given security level. 114 1.1. Requirements Language 116 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 117 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 118 document are to be interpreted as described in RFC 2119 [RFC2119]. 120 2. Scope and Relation to Other Specifications 122 This RFC specifies elliptic curve domain parameters over prime fields 123 GF(p) with p having a length of 256, 384, and 512 bits, in both 124 Weierstrass and twisted Edwards form. These parameters were 125 generated in a transparent and deterministic way and have been shown 126 to resist current cryptanalytic approaches. Furthermore, this 127 document identifies the security and implementation requirements for 128 the parameters, and describes the methods used for the deterministic 129 generation of the parameters. 131 This document also describes use of the specified parameters in X.509 132 certificates, in accordance with [RFC3279] and [RFC5480]. It does 133 not address the cryptographic algorithms to be used with the 134 specified parameters nor their application in other standards. 135 However, it is consistent with the following RFCs that specify the 136 usage of ECC in protocols and applications: 138 o [RFC4050] for XML signatures 140 o [RFC4492] for TLS 142 o [RFC4754] for IKE 143 o [RFC5753] for cryptographic message syntax (CMS) 145 3. Requirements 147 3.1. Technical Requirements 149 1. Applicability to multiple cryptographic algorithms without 150 transformation, in particular key exchange, e.g. Elliptic Curve 151 Diffie-Hellman (ECDH), and digital signature algorithms, e.g., 152 (ECDSA), Schnorr. 154 2. Multiple security levels using the same curve generation 155 algorithm with only a security parameter change. The curve 156 generation algorithm must be extensible to any security level. 158 3. Ability to use pre-computation for increased performance. In 159 particular, speed-up in key generation is important when a curve 160 is used with ephemeral key exchange algorithm, such as ECDHE. 162 4. The bit length of prime and order of curves for a given security 163 level MUST be divisible by 8. Specifically, constructions such 164 as NIST P-521 are to be avoided as they introduce 165 interoperability and implementation problems. 167 3.2. Security Requirements 169 For each curve type (twisted Edwards or Weierstrass) at a specific 170 specific security level: 172 1. The domain parameters SHALL be generated in a simple, 173 deterministic manner, without any secret or random inputs. The 174 derivation of the curve parameters is defined in Appendix A. 176 2. The curve SHALL NOT restrict the scalars to a small subset. 177 Using full-set scalars prevents implementation pitfalls that 178 might otherwise go unnoticed. 180 3. The curve selection SHALL include prime order curves with 181 cofactor 1 only. Composite order curves require changes in 182 protocols and in implementations. Additionally, implementations 183 for composite order curves must thwart subgroup attacks. 185 4. The trace of Frobenius MUST NOT be in {0, 1} in order to rule out 186 the attacks described in [Smart], [AS], and [S], as in [EBP]. 188 5. MOV Degree: the embedding degree k MUST be greater than (r - 1) / 189 100, as in [EBP]. 191 6. CM Discriminant: discriminant D MUST be greater than 2^100, as in 192 [SC]. 194 4. Notation 196 Throughout this document, the following notation is used: 198 s: Denotes the bit length, here s in {256,384,512}. 199 p: Denotes the prime number defining the base field. 200 c: A positive integer used in the representation of the prime 201 p = 2^s - c. 202 GF(p): The finite field with p elements. 203 b: An element in the finite field GF(p), different from -2,2. 204 Eb: The elliptic curve Eb/GF(p): 205 y^2 = x^3 - 3x + b 206 in short Weierstrass form, defined over GF(p) by the 207 parameter b. 208 rb: The order rb = #Eb(GF(p)) of the group of GF(p)-rational 209 points on Eb. 210 tb: The trace of Frobenius tb = p + 1 - rb of Eb. 211 rb': The order rb' = #E'b(GF(p)) = p + 1 + tb of the group of 212 GF(p)-rational points on the quadratic twist Eb': 213 y^2 = x^3 - 3x - b. 214 d: An element in the finite field GF(p), different from -1,0. 215 Ed: The elliptic curve Ed/GF(p): -x^2 + y^2 = 1 + dx^2y^2 in 216 twisted Edwards form, defined over GF(p) by the parameter d. 217 rd: The subgroup order such that 4 * rd = #Ed(GF(p)) is the 218 order of the group of GF(p)-rational points on Ed. 219 td: The trace of Frobenius td = p + 1 - 4 * rd of Ed. 220 rd': The subgroup order such that 4 * rd' = #Ed'(GF(p)) = p + 1 + tb 221 is the order of the group of GF(p)-rational points on the 222 quadratic twist Ed': 223 -x^2 = y^2 = 1 + (1 / d) * x^2 * y^2. 224 P: A generator point defined over GF(p) either of prime order 225 rb in the Weierstrass curve Eb, or of prime order rd on the 226 twisted Edwards curve Ed. 227 X(P): The x-coordinate of the elliptic curve point P. 228 Y(P): The y-coordinate of the elliptic curve point P. 230 5. Curve Parameters 232 5.1. Parameters for 256-bit Curves 233 p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 234 FFFFF43 235 a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 236 FFFFF40 237 b = 0x25581 238 r = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE43C8275EA265C6020AB20294 239 751A825 240 X(P) = 0x01 241 Y(P) = 0x696F1853C1E466D7FC82C96CCEEEDD6BD02C2F9375894EC10BF46306C 242 2B56C77 243 h = 0x01 245 Curve-Id: numsp256d1 247 p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 248 FFFFF43 249 a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 250 FFFFF42 251 d = 0x3BEE 252 r = 0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFBE6AA55AD0A6BC64E5B84E6F1 253 122B4AD 254 X(P) = 0x0D 255 Y(P) = 0x7D0AB41E2A1276DBA3D330B39FA046BFBE2A6D63824D303F707F6FB53 256 31CADBA 257 h = 0x04 259 Curve-Id: numsp256t1 261 5.2. Parameters for 384-bit Curves 263 p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 264 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC3 265 a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 266 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC0 267 b = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 268 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF77BB 269 r = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD61EAF1EE 270 B5D6881BEDA9D3D4C37E27A604D81F67B0E61B9 271 X(P) = 0x02 272 Y(P) = 0x3C9F82CB4B87B4DC71E763E0663E5DBD8034ED422F04F82673330DC58 273 D15FFA2B4A3D0BAD5D30F865BCBBF503EA66F43 274 h = 0x01 276 Curve-Id: numsp384d1 278 p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 279 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC3 280 a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 281 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC2 282 d = 0x5158A 283 r = 0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFECD7D11ED 284 5A259A25A13A0458E39F4E451D6D71F70426E25 285 X(P) = 0x08 286 Y(P) = 0x749CDABA136CE9B65BD4471794AA619DAA5C7B4C930BFF8EBD798A8AE 287 753C6D72F003860FEBABAD534A4ACF5FA7F5BEE 288 h = 0x04 290 Curve-Id: numsp384t1 292 5.3. Parameters for 512-bit Curves 294 p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 295 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 296 FFFFFFFFFFFDC7 297 a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 298 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 299 FFFFFFFFFFFDC4 300 b = 0x1D99B 301 r = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 302 FFFFFFF5B3CA4FB94E7831B4FC258ED97D0BDC63B568B36607CD243CE 303 153F390433555D 304 X(P) = 0x02 305 Y(P) = 0x1C282EB23327F9711952C250EA61AD53FCC13031CF6DD336E0B932843 306 3AFBDD8CC5A1C1F0C716FDC724DDE537C2B0ADB00BB3D08DC83755B20 307 5CC30D7F83CF28 308 h = 0x01 310 Curve-Id: numsp512d1 312 p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 313 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 314 FFFFFFFFFFFDC7 315 a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 316 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 317 FFFFFFFFFFFDC6 318 d = 0x9BAA8 319 r = 0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 320 FFFFFFFA7E50809EFDABBB9A624784F449545F0DCEA5FF0CB800F894E 321 78D1CB0B5F0189 322 X(P) = 0x20 323 Y(P) = 0x7D67E841DC4C467B605091D80869212F9CEB124BF726973F9FF048779 324 E1D614E62AE2ECE5057B5DAD96B7A897C1D72799261134638750F4F0C 325 B91027543B1C5E 326 h = 0x04 328 Curve-Id: numsp512t1 330 6. Object Identifiers and ASN.1 Syntax for X.509 Certificates 332 6.1. Object Identifiers 334 The root of the tree for the object identifiers defined in this 335 specification is given by: 337 [TBDOID] 339 The following object identifiers represent the domain parameters for 340 the curves defined in this draft: 342 numsp256d1 OBJECT IDENTIFIER ::= {versionOne 1} 344 numsp256t1 OBJECT IDENTIFIER ::= {versionOne 2} 346 numsp384d1 OBJECT IDENTIFIER ::= {versionOne 3} 348 numsp384t1 OBJECT IDENTIFIER ::= {versionOne 4} 350 numsp512d1 OBJECT IDENTIFIER ::= {versionOne 5} 352 numsp512t1 OBJECT IDENTIFIER ::= {versionOne 6} 354 6.2. ASN.1 Syntax for X.509 Certificates 356 The domain parameters for the curves specified in this RFC SHALL be 357 used with X.509 certificates according to [RFC5480]. Specifically, 358 the algorithm field of subjectPublicKeyInfo MUST be one of: 360 o id-ecPublicKey to indicate that the algorithms that can be used 361 with the subject public key are unrestricted, as required for 362 ECDSA, or 364 o id-ecDH to indicate that the algorithm that can be used with the 365 subject public key is restricted to the ECDH key agreement 366 algorithm, or 368 o id-ecMQV indicates that the algorithm that can be used with the 369 subject public key is restricted to the Elliptic Curve Menezes-Qu- 370 Vanstone (ECMQV) key agreement algorithm, and 372 The field algorithm.parameter of subjectPublicKeyInfo MUST be of type 373 namedCurve. No other values for this field are acceptable. 375 7. Acknowledgements 377 The authors would like to thank Brian Lamacchia and Tolga Acar for 378 their help in the development of this draft. 380 8. Security Considerations 382 In addition to the discussion in the requirements, [MSR], [SC], and 383 the other reference documents on EC security, users SHOULD match 384 curves with cryptographic functions of similar strength. Specific 385 recommendations for algorithms, per [RFC5480] are as follows: 387 +-------------------+-----------+-------------------+---------------+ 388 | Minimum Bits of | EC Key | Message Digest | Curves | 389 | Security | Size | Algorithm | | 390 +-------------------+-----------+-------------------+---------------+ 391 | 128 | 256 | SHA-256 | numsp256d1/t1 | 392 | 192 | 384 | SHA-384 | numsp384d1/t1 | 393 | 256 | 512 | SHA-512 | numsp512d1/t1 | 394 +-------------------+-----------+-------------------+---------------+ 396 Table 1 398 9. Intellectual Property Rights 400 The authors have no knowledge about any intellectual property rights 401 that cover the usage of the domain parameters defined herein. 402 However, readers should be aware that implementations based on these 403 domain parameters may require use of inventions covered by patent 404 rights. 406 10. IANA Considerations 408 IANA is requested to allocate an object identifier for elliptic 409 curves under the PKIX root declared in [RFC5480]: 411 PKIX1Algorithms2008 { iso(1) identified-organization(3) dod(6) 412 internet(1) security(5) mechanisms(5) pkix(7) id-mod(0) 45 } 414 IANA is further requested to allocate object identifiers under this 415 new elliptic curve root for the named curves in Section 6.1. 417 11. References 419 11.1. Normative References 421 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 422 Requirement Levels", BCP 14, RFC 2119, March 1997. 424 11.2. Informative References 426 [AS] Satoh, T. and K. Araki, "Fermat quotients and the 427 polynomial time discrete log algorithm for anomalous 428 elliptic curves", 1998. 430 [EBP] ECC Brainpool, "ECC Brainpool Standard Curves and Curve 431 Generation", October 2005, . 434 [ECCP] Bos, J., Halderman, J., Heninger, N., Moore, J., Naehrig, 435 M., and E. Wustrow, "Elliptic Curve Cryptography in 436 Practice", December 2013, 437 . 439 [FPPR] Faugere, J., Perret, L., Petit, C., and G. Renault, 2012, 440 . 442 [MSR] Bos, J., Costello, C., Longa, P., and M. Naehrig, 443 "Selecting Elliptic Curves for Cryptography: An Efficiency 444 and Security Analysis", February 2014, 445 . 447 [NIST] National Institute of Standards, "Recommended Elliptic 448 Curves for Federal Government Use", July 1999, 449 . 452 [RFC3279] Bassham, L., Polk, W., and R. Housley, "Algorithms and 453 Identifiers for the Internet X.509 Public Key 454 Infrastructure Certificate and Certificate Revocation List 455 (CRL) Profile", RFC 3279, April 2002. 457 [RFC3552] Rescorla, E. and B. Korver, "Guidelines for Writing RFC 458 Text on Security Considerations", BCP 72, RFC 3552, July 459 2003. 461 [RFC4050] Blake-Wilson, S., Karlinger, G., Kobayashi, T., and Y. 462 Wang, "Using the Elliptic Curve Signature Algorithm 463 (ECDSA) for XML Digital Signatures", RFC 4050, April 2005. 465 [RFC4492] Blake-Wilson, S., Bolyard, N., Gupta, V., Hawk, C., and B. 466 Moeller, "Elliptic Curve Cryptography (ECC) Cipher Suites 467 for Transport Layer Security (TLS)", RFC 4492, May 2006. 469 [RFC4754] Fu, D. and J. Solinas, "IKE and IKEv2 Authentication Using 470 the Elliptic Curve Digital Signature Algorithm (ECDSA)", 471 RFC 4754, January 2007. 473 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 474 IANA Considerations Section in RFCs", BCP 26, RFC 5226, 475 May 2008. 477 [RFC5480] Turner, S., Brown, D., Yiu, K., Housley, R., and T. Polk, 478 "Elliptic Curve Cryptography Subject Public Key 479 Information", RFC 5480, March 2009. 481 [RFC5753] Turner, S. and D. Brown, "Use of Elliptic Curve 482 Cryptography (ECC) Algorithms in Cryptographic Message 483 Syntax (CMS)", RFC 5753, January 2010. 485 [S] Semaev, I., "Evaluation of discrete logarithms on some 486 elliptic curves", 1998. 488 [SC] Bernstein, D. and T. Lange, "SafeCurves: choosing safe 489 curves for elliptic-curve cryptography", June 2014, 490 . 492 [SEC1] Certicom Research, "SEC 1: Elliptic Curve Cryptography", 493 September 2000, 494 . 496 [Smart] Smart, N., "The discrete logarithm problem on elliptic 497 curves of trace one", 1999. 499 Appendix A. Parameter Generation 501 This section describes the generation of the curve parameters, namely 502 the base field prime p, the curve parameters b and d for the 503 Weierstrass and twisted Edwards curves, respectively, and a generator 504 point P of the prime order subgroup of the elliptic curve. 506 A.1. Prime Generation 508 For a given bitlength s in {256, 384, 512}, a prime p is selected as 509 a pseudo-Mersenne prime of the form p = 2^s - c for a positive 510 integer c. Each prime is determined by the smallest positive integer 511 c such that p = 2^s - c is prime and p = 3 mod 4. 513 Input: a bit length s in {256, 384, 512} 514 Output: a prime p = 2^s - c with p = 3 mod 4 515 1. Set c = 1 516 2. while (p = 2^s - c is not prime) do 517 c = c + 4 518 end while 519 3. Output p 521 GenerateP 523 A.2. Deterministic Curve Parameter Generation 525 A.2.1. Weierstrass Curves 527 For a given bitlength s in {256, 384, 512} and a corresponding prime 528 p = 2^s - c selected according to Section A.1, the elliptic curve Eb 529 in short Weierstrass form is determined by the element b from GF(p), 530 different from -2,2 with smallest absolute value (when represented as 531 an integer in the interval [-(p - 1) / 2, (p - 1) / 2]) such that 532 both group orders rb and rb' are prime, and the group order rb < p, 533 i.e. tb > 1. In addition, care must be taken to ensure the MOV 534 degree and CM discriminant requirements from Section 3.2 are met. 536 Input: a prime p = 2^s - c with p = 3 mod 4 537 Output: the parameter b defining the curve Eb 538 1. Set b = 1 539 2. while (rb is not prime or rb' is not prime) do 540 b = b + 1 541 end while 542 3. if p + 1 < rb then 543 b = -b 544 end if 545 4. Output b 547 GenerateCurveWeierstrass 549 A.2.2. Twisted Edwards Curves 551 For a given bitlength s in {256, 384, 512} and a corresponding prime 552 p = 2^s - c selected according to Section A.1, the elliptic curve Ed 553 in twisted Edwards form is determined by the element d from GF(p), 554 different from -1,0 with smallest value (when represented as a 555 positive integer) such that both subgroup orders rd and rd' are 556 prime, and the group order 4 * rd < p, i.e. td > 1. In addition, 557 care must be taken to ensure the MOV degree and CM discriminant 558 requirements from Section 3.2 are met. 560 Input: a prime p = 2^s - c with p = 3 mod 4 561 Output: the parameter d defining the curve Ed 562 1. Set d = 1 563 2. while (rd is not prime or rd' is not prime or 4*rd > p) do 564 d = d + 1; 565 end while 566 3. Output d 568 GenerateCurveTEdwards 570 Appendix B. Generators 572 The generator points on all six curves are selected as the points of 573 order rb and rd, respectively, with the smallest value for x(P) when 574 represented as a positive integer. 576 Input: a prime p, and a Weierstrass curve parameter b 577 Output: a generator point P = (x(P), y(P)) of order rb 578 1. Set x = 1 579 2. while ((x^3 - 3 * x + b) is not a quadratic residue modulo p) do 580 x = x + 1 581 end while 582 3. Compute an integer s, 0 < s < p, such that 583 s^2 = x^3 - 3 * x + b mod p 584 4. Set y = min(s, p - s) 585 5. Output P = (x, y) 587 GenerateGenWeierstrass 589 Input: a prime p and a twisted Edwards curve parameter d 590 Output: a generator point P = (x(P), y(P)) of order rd 591 1. Set x = 1 592 2. while ((d * x^2 = 1 mod p) 593 or ((1 + x^2) * (1 - d * x^2) is not a quadratic residue 594 modulo p)) do x = x + 1 595 end while 596 3. Compute an integer s, 0 < s < p, such that 597 s^2 * (1 - d * x^2) = 1 + x^2 mod p 598 4. Set y = min(s, p - s) 599 5. Output P = (x, y) 601 GenerateGenTEdwards 603 Authors' Addresses 605 Benjamin Black 606 Microsoft 607 One Microsoft Way 608 Redmond, WA 98115 609 US 611 Email: benblack@microsoft.com 613 Joppe W. Bos 614 NXP Semiconductors 615 Interleuvenlaan 80 616 3001 Leuven 617 Belgium 619 Email: joppe.bos@nxp.com 620 Craig Costello 621 Microsoft Research 622 One Microsoft Way 623 Redmond, WA 98115 624 US 626 Email: craigco@microsoft.com 628 Patrick Longa 629 Microsoft Research 630 One Microsoft Way 631 Redmond, WA 98115 632 US 634 Email: plonga@microsoft.com 636 Michael Naehrig 637 Microsoft Research 638 One Microsoft Way 639 Redmond, WA 98115 640 US 642 Email: mnaehrig@microsoft.com