Network Working Group | B. Black |
Internet-Draft | Microsoft |
Intended status: Informational | J. Bos |
Expires: June 24, 2015 | NXP Semiconductors |
C. Costello | |
Microsoft Research | |
A. Langley | |
Google Inc | |
P. Longa | |
M. Naehrig | |
Microsoft Research | |
December 21, 2014 |
Rigid Parameter Generation for Elliptic Curve Cryptography
draft-black-rpgecc-01
This memo describes algorithms for deterministically generating parameters for elliptic curves over prime fields offering high practical security in cryptographic applications, including Transport Layer Security (TLS) and X.509 certificates. The algorithms can generate domain parameters at any security level for modern (twisted) Edwards curves.
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 June 24, 2015.
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.
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 deterministic algorithm for generation of elliptic curves for cryptography. The constraints in the generation process produce curves that 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. The deterministic algorithm operates without any hidden parameters, reliance on randomness or any other processes offering opportunities for manipulation of the resulting curves. The selection between curve models is determined by choosing the curve form that supports the fastest (currently known) complete formulas for each modularity option of the underlying field prime. Specifically, the Edwards curve x^2 + y^2 = 1 + dx^2y^2 is used with primes p with p = 3 mod 4, and the twisted Edwards curve -x^2 + y^2 = 1 + dx^2y^2 is used for primes p with p = 1 mod 4.
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].
This document specifies a deterministic algorithm for generating elliptic curve domain parameters over prime fields GF(p), with p having a length of twice the desired security level in bits, in (twisted) Edwards form.
For each curve at a specific security level:
Throughout this document, the following notation is used:
p: Denotes the prime number defining the base field. GF(p): The finite field with p elements. 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 Edwards form, defined over GF(p) by the parameter d. tEd: The elliptic curve tEd/GF(p): -x^2 + y^2 = 1 + dx^2y^2 in twisted Edwards form, defined over GF(p) by the parameter d. rd: The largest odd divisor of the number of GF(p)-rational points on Ed or tEd. td: The trace of Frobenius of Ed or tEd such that #Ed(GF(p)) = p + 1 - td or #tEd(GF(p)) = p + 1 - td, respectively. rd': The largest odd divisor of the number of GF(p)-rational points on the non-trivial quadratic twist Ed' or tEd'. hd: The index (or cofactor) of the subgroup of order rd in the group of GF(p)-rational points on Ed or tEd. hd': The index (or cofactor) of the subgroup of order rd' in the group of GF(p)-rational points on the non-trivial quadratic twist of Ed or tEd. P: A generator point defined over GF(p) of prime order rd on Ed or tEd. X(P): The x-coordinate of the elliptic curve point P. Y(P): The y-coordinate of the elliptic curve point P.
This section describes the generation of the curve parameters, namely the curve parameter d, and a generator point P of the prime order subgroup of the elliptic curve. Best practice is to use primes with p = 3 mod 4. For compatibility with some deployed implementations, a generation process for primes with p = 1 mod 4 is also provided.
For a prime p = 3 mod 4, the elliptic curve Ed in Edwards form is determined by the non-square element d from GF(p), different from -1,0 with smallest absolute value such that #Ed(GF(p)) = hd * rd, #Ed'(GF(p)) = hd' * rd', hd = hd' = 4, and both subgroup orders rd and rd' are prime. In addition, care must be taken to ensure the MOV degree and CM discriminant requirements from Section 3 are met.
Input: a prime p, with p = 3 mod 4 Output: the parameter d defining the curve Ed 1. Set d = 0 2. repeat repeat if (d > 0) then d = -d else d = -d + 1 end if until d is not a square in GF(p) Compute rd, rd', hd, hd' where #Ed(GF(p)) = hd * rd, #Ed'(GF(p)) = hd' * rd', hd and hd' are powers of 2 and rd, rd' are odd until ((hd = hd' = 4) and rd is prime and rd' is prime) 3. Output d
GenerateCurveEdwards
For a prime p = 1 mod 4, the elliptic curve tEd in twisted Edwards form is determined by the non-square element d from GF(p), different from -1,0 with smallest absolute value such that #tEd(GF(p)) = hd * rd, #tEd'(GF(p)) = hd' * rd', hd = 8, hd' = 4 and both subgroup orders rd and rd' are prime. In addition, care must be taken to ensure the MOV degree and CM discriminant requirements from Section 3 are met.
Input: a prime p, with p = 1 mod 4 Output: the parameter d defining the curve tEd 1. Set d = 0 2. repeat repeat if (d > 0) then d = -d else d = -d + 1 end if until d is not a square in GF(p) Compute rd, rd', hd, hd' where #tEd(GF(p)) = hd * rd, #tEd'(GF(p)) = hd' * rd', hd and hd' are powers of 2 and rd, rd' are odd until (hd = 8 and hd' = 4 and rd is prime and rd' is prime) 3. Output d
GenerateCurveTEdwards
The generator points P = (X(P),Y(P)) for all curves are selected by taking the smallest positive value x in GF(p) (when represented as an integer) such that (x, y) is on the curve and such that (X(P),Y(P)) = 8 * (x, y) has large prime order rd.
Input: a prime p and curve parameters non-square d and a = -1 for twisted Edwards (p = 1 mod 4) or a = 1 for Edwards (p = 3 mod 4) Output: a generator point P = (X(P), Y(P)) of order rd 1. Set x = 0 and found_gen = false 2. while (not found_gen) do x = x + 1 while ((1 - a * x^2) * (1 - d * x^2) is not a quadratic residue mod p) do x = x + 1 end while Compute an integer s, 0 < s < p, such that s^2 * (1 - d * x^2) = 1 - a * x^2 mod p Set y = min(s, p - s) (X(P), Y(P)) = 8 * (x, y) if ((X(P), Y(P)) has order rd on Ed or tEd, respectively) then found_gen = true end if end while 3. Output (X(P),Y(P))
GenerateGen
For applications requiring Montgomery curves, such as x-only point format for elliptic curve Diffie-Hellmann (ECDH) key exchange, isogenies from the generated (twisted) Edwards curves can be produced as described in the following sections.
For a prime p = 3 mod 4, and a given Edwards curve Ed: x^2 + y^2 = 1 + d x^2 y^2 over GF(p) with non-square parameter d, let A = -(4d - 2). Then the Montgomery curve
EM: v^2 = u^3 + Au^2 + u
is isogenous to Ed over GF(p). The following map is a 4-isogeny from Ed to EM over GF(p):
phi: Ed -> EM, (x,y) -> (u,v), where u = y^2 / x^2, v = -y(x^2 + y^2 - 2) / x^3.
The neutral element (0,1) and the point of order two (0,-1) on Ed are mapped to the point at infinity on EM. The dual isogeny is given by
phi_d: EM -> Ed, (u,v) -> (x,y), where x = 4v(u - 1)(u + 1) / (u^4 - 2u^2 + 4v^2 + 1), y = (u^2 + 2v - 1)(u^2 - 2v - 1) / (-u^4 + 2uv^2 + 2Au + 4u^2 + 1).
It holds phi_d(phi((x,y))) = [4](x,y) on Ed and phi(phi_d((u,v))) = [4](u,v) on EM.
For a prime p = 1 mod 4, and a given twisted Edwards curve tEd: -x^2 + y^2 = 1 + d x^2 y^2 over GF(p) with non-square parameter d, let A = 4d + 2. Then the Montgomery curve
EM: v^2 = u^3 + Au^2 + u
is isogenous to tEd over GF(p). Let s in GF(p) be a fixed square root of -1, i.e. s is a solution to the equation s^2 + 1 = 0 over GF(p). Then, the following map is a 4-isogeny from tEd to EM over GF(p):
phi: tEd -> EM, (x,y) -> (u,v), where u = -y^2 / x^2, v = -ys(x^2 - y^2 + 2) / x^3.
The neutral element (0,1) and the point of order two (0,-1) on tEd are mapped to the point at infinity on EM. The dual isogeny is given by
phi_d: EM -> tEd, (u,v) -> (x,y), where x = 4sv(u - 1)(u + 1) / (u^4 - 2u^2 + 4v^2 + 1), y = (u^2 + 2v - 1)(u^2 - 2v - 1) / (-u^4 + 2uv^2 + 2Au + 4u^2 + 1).
It holds phi_d(phi((x,y))) = [4](x,y) on tEd and phi(phi_d((u,v))) = [4](u,v) on EM.
The following figures give parameters for recommended twisted Edwards and Edwards curves at the 128 and 192 bit security levels generated using the algorithms defined in previous sections. All integer values are unsigned.
p = 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFED d = 0x1DB41 r = 0x1000000000000000000000000000000014DEF9DEA2F79CD65812 631A5CF5D3ED x(P) = 0x5C88197130371C6958E48E7C57393BDEDBA29F9231D24B3D4DA2 242EC821CDF1 y(P) = 0x6FEC03B956EC4A0E51A838029242F8B107C27399CC7840C34B95 5E478A8FB7A5 h = 0x8
p = 2^255 - 19, twisted Edwards
The isogenous Montgomery curve for p = 2^255 - 19 is given by A = 0x76D06.
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC3 d = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD19F r = 0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE2471A1 CB46BE1CF61E4555AAB35C87920B9DCC4E6A3897D x(P) = 0x61B111FB45A9266CC0B6A2129AE55DB5B30BF446E5BE4C005763FFA 8F33163406FF292B16545941350D540E46C206BDE y(P) = 0x82983E67B9A6EEB08738B1A423B10DD716AD8274F1425F56830F98F 7F645964B0072B0F946EC48DC9D8D03E1F0729392 h = 0x4
p = 2^384 - 317, Edwards
The isogenous Montgomery curve for p = 2^384 - 317 is given by A = 0xB492.
As defined in [RFC4492], the name space NamedCurve is used for the negotiation of elliptic curve groups for key exchange during TLS session establishment. This document adds new NamedCurve types for the elliptic curves defined in this document:
enum { ietfp255t1(TBD1), ietfp255x1(TBD2), ietfp384e1(TBD3), ietfp384x1(TBD4) } NamedCurve;
These curves are suitable for use with Datagram TLS [RFC6347].
The (twisted) Edwards curves generated by the procedure defined in this draft are suitable for use in signature algorithms such as ECDSA. In compliance with [RFC5480], which only supports named curves, namedCurve OIDs must be defined for the generated curves and points must be represented as (x,y) in either uncompressed or compressed format.
The following object identifiers represent the (twisted) Edwards domain parameter sets defined in this draft:
ietfp255t1 OBJECT IDENTIFIER ::= {[TBDOID] 1} ietfp384e1 OBJECT IDENTIFIER ::= {[TBDOID] 2}
The authors would like to thank Tolga Acar, Karen Easterbrook and Brian LaMacchia for their contributions to the development of this draft.
TBD
The authors have no knowledge about any intellectual property rights that cover either the generation algorithms or the usage of the domain parameters defined herein.
IANA is requested to assign numbers for the curves listed in Section 9 in the "EC Named Curve" [IANA-TLS] registry of the "Transport Layer Security (TLS) Parameters" registry as follows:
Value | Description | DTLS-OK | Reference |
---|---|---|---|
TBD1 | ietfp255t1 | Y | this doc |
TBD2 | ietfp255x1 | Y | this doc |
TBD3 | ietfp384e1 | Y | this doc |
TBD4 | ietfp384x1 | Y | this doc |
[RFC2119] | Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. |