Elliptic Curve Cryptography (ECC) Nothing Up My Sleeve (NUMS) Curves and Curve Generation
draft-black-numscurves-01

Abstract

This memo describes a family of deterministically generated Nothing Up My Sleeve (NUMS) elliptic curves over prime fields offering high practical security in cryptographic applications, including Transport Layer Security (TLS) and X.509 certificates. The domain parameters are defined for both classical Weierstrass curves, for compatibility with existing applications, and modern twisted Edwards curves, allowing further efficiency improvements for a given security level.

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at http://datatracker.ietf.org/drafts/current/.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

This Internet-Draft will expire on January 4, 2015.

Copyright Notice

Copyright (c) 2014 IETF Trust and the persons identified as the document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.

Table of Contents

• 1. Introduction
• 1.1. Requirements Language
• 2. Scope and Relation to Other Specifications
• 3. Requirements
• 3.1. Technical Requirements
• 3.2. Security Requirements
• 4. Notation
• 5. Curve Parameters
• 5.1. Parameters for 256-bit Curves
• 5.2. Parameters for 384-bit Curves
• 5.3. Parameters for 512-bit Curves
• 6. Object Identifiers and ASN.1 Syntax for X.509 Certificates
• 6.1. Object Identifiers
• 6.2. ASN.1 Syntax for X.509 Certificates
• 7. Acknowledgements
• 8. Security Considerations
• 9. Intellectual Property Rights
• 10. IANA Considerations
• 11. References
• 11.1. Normative References
• 11.2. Informative References
• Appendix A. Parameter Generation
• A.1. Prime Generation
• A.2. Deterministic Curve Parameter Generation
• A.2.1. Weierstrass Curves
• A.2.2. Twisted Edwards Curves
• Appendix B. Generators
• Authors' Addresses

1. Introduction

Since the initial standardization of elliptic curve cryptography (ECC) in [SEC1] there has been significant progress related to both efficiency and security of curves and implementations. Notable examples are algorithms protected against certain side-channel attacks, different 'special' prime shapes which allow faster modular arithmetic, and a larger set of curve models from which to choose. There is also concern in the community regarding the generation and potential weaknesses of the curves defined in [NIST].

This memo describes a set of elliptic curves for cryptography, defined in [MSR] which have been specifically chosen to support constant-time, exception-free scalar multiplications that are resistant to a wide range of side-channel attacks including timing and cache attacks, thereby offering high practical security in cryptographic applications. These curves are deterministically generated based on algorithms defined in this document and without any hidden parameters or reliance on randomness, hence they are called Nothing Up My Sleeve (NUMS) curves. The domain parameters are defined for both classical Weierstrass curves, for compatibility with existing applications while delivering better performance and stronger security, and modern twisted Edwards curves, allowing even further efficiency improvements for a given security level.

1.1. Requirements Language

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119].

2. Scope and Relation to Other Specifications

This RFC specifies elliptic curve domain parameters over prime fields GF(p) with p having a length of 256, 384, and 512 bits, in both Weierstrass and twisted Edwards form. These parameters were generated in a transparent and deterministic way and have been shown to resist current cryptanalytic approaches. Furthermore, this document identifies the security and implementation requirements for the parameters, and describes the methods used for the deterministic generation of the parameters.

This document also describes use of the specified parameters in X.509 certificates, in accordance with [RFC3279] and [RFC5480]. It does not address the cryptographic algorithms to be used with the specified parameters nor their application in other standards. However, it is consistent with the following RFCs that specify the usage of ECC in protocols and applications:

• [RFC4050] for XML signatures
• [RFC4492] for TLS
• [RFC4754] for IKE
• [RFC5753] for cryptographic message syntax (CMS)

3. Requirements

3.1. Technical Requirements

1. Applicability to multiple cryptographic algorithms without transformation, in particular key exchange, e.g. Elliptic Curve Diffie-Hellman (ECDH), and digital signature algorithms, e.g., (ECDSA), Schnorr.
2. Multiple security levels using the same curve generation algorithm with only a security parameter change. The curve generation algorithm must be extensible to any security level.
3. Ability to use pre-computation for increased performance. In particular, speed-up in key generation is important when a curve is used with ephemeral key exchange algorithm, such as ECDHE.
4. The bit length of prime and order of curves for a given security level MUST be divisible by 8. Specifically, constructions such as NIST P-521 are to be avoided as they introduce interoperability and implementation problems.

3.2. Security Requirements

For each curve type (twisted Edwards or Weierstrass) at a specific specific security level:

1. The domain parameters SHALL be generated in a simple, deterministic manner, without any secret or random inputs. The derivation of the curve parameters is defined in Appendix A.
2. The curve SHALL NOT restrict the scalars to a small subset. Using full-set scalars prevents implementation pitfalls that might otherwise go unnoticed.
3. The curve selection SHALL include prime order curves with cofactor 1 only. Composite order curves require changes in protocols and in implementations. Additionally, implementations for composite order curves must thwart subgroup attacks.
4. The trace of Frobenius MUST NOT be in {0, 1} in order to rule out the attacks described in [Smart], [AS], and [S], as in [EBP].
5. MOV Degree: the embedding degree k MUST be greater than (r - 1) / 100, as in [EBP].
6. CM Discriminant: discriminant D MUST be greater than 2^100, as in [SC].

4. Notation

Throughout this document, the following notation is used:

      s: Denotes the bit length, here s in {256,384,512}.
      p: Denotes the prime number defining the base field.
      c: A positive integer used in the representation of the prime 
         p = 2^s - c.
  GF(p): The finite field with p elements.
      b: An element in the finite field GF(p), different from -2,2.
     Eb: The elliptic curve Eb/GF(p): 
                y^2 = x^3 - 3x + b 
         in short Weierstrass form, defined over GF(p) by the 
         parameter b.
     rb: The order rb = #Eb(GF(p)) of the group of GF(p)-rational 
         points on Eb.
     tb: The trace of Frobenius tb = p + 1 - rb of Eb.
    rb': The order rb' = #E'b(GF(p)) = p + 1 + tb of the group of
         GF(p)-rational points on the quadratic twist Eb': 
                y^2 = x^3 - 3x - b.
      d: An element in the finite field GF(p), different from -1,0.
     Ed: The elliptic curve Ed/GF(p): -x^2 + y^2 = 1 + dx^2y^2 in 
         twisted Edwards form, defined over GF(p) by the parameter d.
     rd: The subgroup order such that 4 * rd = #Ed(GF(p)) is the 
         order of the group of GF(p)-rational points on Ed.
     td: The trace of Frobenius td = p + 1 - 4 * rd of Ed.
    rd': The subgroup order such that 4 * rd' = #Ed'(GF(p)) = p + 1 + tb
         is the order of the group of GF(p)-rational points on the 
         quadratic twist Ed': 
                -x^2 = y^2 = 1 + (1 / d) * x^2 * y^2.
      P: A generator point defined over GF(p) either of prime order 
         rb in the Weierstrass curve Eb, or of prime order rd on the 
         twisted Edwards curve Ed.
   X(P): The x-coordinate of the elliptic curve point P.
   Y(P): The y-coordinate of the elliptic curve point P.
         

5. Curve Parameters

5.1. Parameters for 256-bit Curves

    p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
          FFFFF43
    a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
          FFFFF40
    b = 0x25581  
    r = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE43C8275EA265C60E43C8275E
          A265C60
 X(P) = 0x01
 Y(P) = 0x696F1853C1E466D7FC82C96CCEEEDD6BD02C2F9375894EC10BF46306C
          2B56C77
    h = 0x01 
          

Curve-Id: numsp256d1

    p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
          FFFFF43
    a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
          FFFFF42 
    d = 0x3BEE  
    r = 0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFBE6AA55AD0A6BC64E5B84E6F1
          122B4AD 
 X(P) = 0x0D 
 Y(P) = 0x7D0AB41E2A1276DBA3D330B39FA046BFBE2A6D63824D303F707F6FB53
          31CADBA
    h = 0x04 
          

Curve-Id: numsp256t1

5.2. Parameters for 384-bit Curves

    p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
          FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC3 
    a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
          FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC0  
    b = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
          FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF77BB  
    r = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD61EAF1EE
          B5D6881BEDA9D3D4C37E27A604D81F67B0E61B9  
 X(P) = 0x02
 Y(P) = 0x3C9F82CB4B87B4DC71E763E0663E5DBD8034ED422F04F82673330DC58
          D15FFA2B4A3D0BAD5D30F865BCBBF503EA66F43
    h = 0x01 
          

Curve-Id: numsp384d1

    p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
          FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC3 
    a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
          FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC2  
    d = 0x5158A 
    r = 0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFECD7D11ED
          5A259A25A13A0458E39F4E451D6D71F70426E25  
 X(P) = 0x08
 Y(P) = 0x749CDABA136CE9B65BD4471794AA619DAA5C7B4C930BFF8EBD798A8AE
          753C6D72F003860FEBABAD534A4ACF5FA7F5BEE
    h = 0x04 
          

Curve-Id: numsp384t1

5.3. Parameters for 512-bit Curves

    p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
          FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
          FFFFFFFFFFFDC7
    a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
          FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
          FFFFFFFFFFFDC4
    b = 0x1D99B  
    r = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
          FFFFFFF5B3CA4FB94E7831B4FC258ED97D0BDC63B568B36607CD243CE
          153F390433555D  
 X(P) = 0x02
 Y(P) = 0x1C282EB23327F9711952C250EA61AD53FCC13031CF6DD336E0B932843
          3AFBDD8CC5A1C1F0C716FDC724DDE537C2B0ADB00BB3D08DC83755B20
          5CC30D7F83CF28 
    h = 0x01 
          

Curve-Id: numsp512d1

    p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
          FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
          FFFFFFFFFFFDC7
    a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
          FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
          FFFFFFFFFFFDC6 
    d = 0x9BAA8 
    r = 0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
          FFFFFFFA7E50809EFDABBB9A624784F449545F0DCEA5FF0CB800F894E
          78D1CB0B5F0189 
 X(P) = 0x20
 Y(P) = 0x7D67E841DC4C467B605091D80869212F9CEB124BF726973F9FF048779
          E1D614E62AE2ECE5057B5DAD96B7A897C1D72799261134638750F4F0C
          B91027543B1C5E
    h = 0x04 
          

Curve-Id: numsp512t1

6. Object Identifiers and ASN.1 Syntax for X.509 Certificates

6.1. Object Identifiers

The root of the tree for the object identifiers defined in this specification is given by:

      [TBDOID]
            

The following object identifiers represent the domain parameters for the curves defined in this draft:

      numsp256d1 OBJECT IDENTIFIER ::= {versionOne 1}

      numsp256t1 OBJECT IDENTIFIER ::= {versionOne 2}

      numsp384d1 OBJECT IDENTIFIER ::= {versionOne 3}

      numsp384t1 OBJECT IDENTIFIER ::= {versionOne 4}

      numsp512d1 OBJECT IDENTIFIER ::= {versionOne 5}

      numsp512t1 OBJECT IDENTIFIER ::= {versionOne 6}
            

6.2. ASN.1 Syntax for X.509 Certificates

The domain parameters for the curves specified in this RFC SHALL be used with X.509 certificates according to [RFC5480]. Specifically, the algorithm field of subjectPublicKeyInfo MUST be one of:

• id-ecPublicKey to indicate that the algorithms that can be used with the subject public key are unrestricted, as required for ECDSA, or
• id-ecDH to indicate that the algorithm that can be used with the subject public key is restricted to the ECDH key agreement algorithm, or
• id-ecMQV indicates that the algorithm that can be used with the subject public key is restricted to the Elliptic Curve Menezes-Qu-Vanstone (ECMQV) key agreement algorithm, and

The field algorithm.parameter of subjectPublicKeyInfo MUST be of type namedCurve. No other values for this field are acceptable.

7. Acknowledgements

The authors would like to thank Brian Lamacchia and Tolga Acar for their help in the development of this draft.

8. Security Considerations

In addition to the discussion in the requirements, [MSR], [SC], and the other reference documents on EC security, users SHOULD match curves with cryptographic functions of similar strength. Specific recommendations for algorithms, per [RFC5480] are as follows:

  PKIX1Algorithms2008 { iso(1) identified-organization(3) dod(6)
    internet(1) security(5) mechanisms(5) pkix(7) id-mod(0) 45 }
            

Input: a bit length s in {256, 384, 512}
Output: a prime p = 2^s - c with p = 3 mod 4
  1. Set c = 1
  2. while (p = 2^s - c is not prime) do
       c = c + 4
     end while
  3. Output p
          

Input: a prime p = 2^s - c with p = 3 mod 4
Output: the parameter b defining the curve Eb
  1. Set b = 1
  2. while (rb is not prime or rb' is not prime) do
       b = b + 1
     end while
  3. if p + 1 < rb then
       b = -b
     end if
  4. Output b
            

Input: a prime p = 2^s - c with p = 3 mod 4
Output: the parameter d defining the curve Ed
  1. Set d = 1
  2. while (rd is not prime or rd' is not prime or 4*rd > p) do
       d = d + 1;
     end while
  3. Output d
            

Input: a prime p, and a Weierstrass curve parameter b
Output: a generator point P = (x(P), y(P)) of order rb
1. Set x = 1
2. while ((x^3 - 3 * x + b) is not a quadratic residue modulo p) do
     x = x + 1
   end while
3. Compute an integer s, 0 < s < p, such that 
        s^2 = x^3 - 3 * x + b mod p
4. Set y = min(s, p - s)
5. Output P = (x, y)
        

Input: a prime p and a twisted Edwards curve parameter d
Output: a generator point P = (x(P), y(P)) of order rd
1. Set x = 1
2. while ((d * x^2 = 1 mod p)  
          or ((1 + x^2) * (1 - d * x^2) is not a quadratic residue 
          modulo p)) do x = x + 1
   end while
3. Compute an integer s, 0 < s < p, such that 
        s^2 * (1 - d * x^2) = 1 + x^2 mod p
4. Set y = min(s, p - s)
5. Output P = (x, y)