Internet Draft W. Ladd
<draft-ladd-safecurves-04.txt> Grad Student
Category: Informational UC Berkeley
Expires 29 September 2014 28 March 2014
Additional Elliptic Curves for IETF protocols
<draft-ladd-safecurves-04.txt>
Status of this Memo
Distribution of this memo is unlimited.
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), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
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."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on 9 July 2014.
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.
Abstract
This Internet Draft explains the mathematics behind and the
Ladd, Watson Expires 29 September 2014 [Page 1]
Internet Draft ladd-safecurves 28 March 2014
parameters of a new family of elliptic curves with efficiency and
security advantages over existing and widely deployed mechanisms.
Ladd, Watson Expires 29 September 2014 [Page 2]
Internet Draft ladd-safecurves 28 March 2014
Table of Contents
1. Introduction ....................................................3
2. Explicit Formulas ...............................................3
3. The Curves ......................................................6
4. Point Encoding ..................................................9
Design Considerations ...........................................
5. Security Considerations .........................................9
6. IANA Considerations .............................................9
7. Acknowledgments ................................................9
8. References .....................................................10
1. Introduction
This document contains a set of elliptic curves over prime fields
with many security and performance advantages. They are twist-secure,
have large prime-order subgroups, high embedding degree, endomorphism
rings of large discriminant, complete formulas, and primes selected
for fast arithmetic. The reader who wishes to learn more about these
properties and their necessity is refered to [SILVERMAN] and
[SAFECURVES].
These curves have been generated in a rigid manner by computer
search. As such there is very little risk that these curves were
selected to exhibit weaknesses to attacks not in the open literature.
The field is the only free choice, and in all circumstances has been
picked to enable highly efficient arithmetic. Proofs of all
properties claimed exist in [SAFECURVES]. It is easier to avoid known
implementation issues with these curves then short Weierstrass
curves.
2. Algorithms and protocols
We assume the reader is familiar with bignum arithmetic. If not
[COHEN] is the resource to consider.
The elliptic-curve Diffie-Hellman key agreement protocol on a curve
with basepoint g of cofactor h and order q is as follows:
Alice picks a random integer a from the range [1,q-1], computes
[a*h]g, and transmits it to Bob.
Bob picks a random integer b from the range [1,q-1], computes [b*h]g,
and transmits it to Alice.
Both Alice and Bob determine [a*b*h^2]g, Alice as [a*h]([b*h]g), and
likewise for Bob. This can be hashed to give a short shared secret.
So far nothing that has been said depends on the curve shape. On
Ladd, Watson Expires 29 September 2014 [Page 3]
Internet Draft ladd-safecurves 28 March 2014
Montgomery curves, curves of the form y^2=x^3+Bx^2+x, one drops the y
coordinate, and so does not distinguish between P and -P. This is
called taking the Kummer variety, and enables faster arithmetic.
On Montgomery curves, curves of the form y^2=x^3+a*x^2+x, the typical
technique is to work over the Kummer variety instead, i.e. drop y
coordinates for use in Diffie-Hellman. Let (X1,Z1), (X2,Z2), (X3,Z3)
be coordinates such that X1/Z1, X2/Z2, X3/Z3 are the x coordinates of
Q-P, P, and Q respectively. Then the equations
A = X2+Z2
AA = A^2
B = X2 - Z2
BB = B^2
E = AA - BB
C = X3 + Z3
D = X3 - Z3
DA = D*A
CB = C*B
X5 = Z1*(DA+CB)^2
Z5 = X1*(DA-CB)^2
X4 = AA*BB
Z4 = E*(BB+a24*E)
gives X4/Z4 as the x coordinate of [2]P, and X5/Z5 as the x
coordinate of P+Q where a24=(a+2)/4. If in calculating [n](X, Z), Z
of the result is zero, this indicates that [n](X,Z) is the point at
infinity, and so the result has x-coordinate 0.
These equations originally appeared in [MONTGOMERY].
To use this to calculate multiplication on the Kummer variety, the
following routine will work to calculate [n]P, given the x coordinate
of P, if [n]P is not the identity of the group. For ECDH this routine
is adequate as returning 0 for the identity is acceptable and does
not lose security.
1: Intilize P_0=[1,0], and P_1=[x_P,1]
2: Iterate over the bits of n from most to least significant
2.1: If the bit is 0, let P_1=P_1+P_0, P_0=2P_0
2.2: If the bit is 1, let P_0=P_1+P_0, P_1=2P_1
3: Write [x_f, z_f]=P_0
4: If z_f is 0, return 0. Otherwise return x_f/z_f.
Note that the difference between P_1 and P_0 is always [x_P, 1], so
the differential addition formula above suffices and in fact Z1 the
constant 1. In implementing the above algorithm the conditionals
should be implemented by means of constant time conditional swaps
rather than jumps to avoid timing and control flow attacks. n should
be represented with a fixed number of bits to further minimize timing
Ladd, Watson Expires 29 September 2014 [Page 4]
Internet Draft ladd-safecurves 28 March 2014
information. Skipping initial zeros is a terrible idea.
The final division can be written as x_f*z_f^(p-1), which will be
correct in all cases.
When using this algorithm, no checks on the x coordinate are required
for the Montgomery curves in this standard: they are designed to
resist all attacks that involve transmitting an invalid x coordinate
in the above algorithm.
On (twisted) Edwards curves, curves of the form a*x^2+y^2=1+d*x^2y^2,
a complete addition formula, which works for doubling as well, is
given by representing points in projective coordinates. The formula
for adding (X1, Y1, Z1) to (X2, Y2, Z2) is then
A = Z1*Z2
B = A^2
C = X1*X2
D = Y1*Y2
E = d*C*D
F = B-E
G = B+E
X3 = A*F*((X1+Y1)*(X2+Y2)-C-D)
Y3 = A*G*(D-a*C)
Z3 = F * G
These formulas are from the [EFD], reporting results in [BL07]. Every
point on an Edwards curve can be represented, so Z=0 does not occur.
This formula can be used for doubling also by letting (X1,Y1,Z1)=
(X2,Y2,Z2). For most of the curves with the exception of Ed25519 a=1,
saving a multiplication.
The Montgomery ladder algorithm from above will work with this
addition and doubling, taking care to represent points as triples,
and check that points lie on the curve going into and out of the
routine. To convert from projective coordinates one takes x=X/Z,
y=Y/Z, and to convert affine to projective one takes (x,y,1).
The above algorithms are not the only algorithms possible. One can
use alternative parameterizations such as inverted Edwards
coordinates to make point operations cheaper, alternative algorithms
such as radix-k or sliding window methods to reduce the number of
additions and increase the number of doublings, and isogenies to
transform Montgomery curves into Edwards curves to take advantage of
these techniques. However, implementors should take care to avoid
timing and cache side-channels when implementing any of these
techniques. More information on some of these techniques is in
[TWIST].
Ladd, Watson Expires 29 September 2014 [Page 5]
Internet Draft ladd-safecurves 28 March 2014
3. The Curves
These curves were selected as follows: first a field was picked which
because of its form permits specialized, faster arithmetic. Then the
curve shape was selected, either Edwards or Montgomery. Lastly, a
computer search was made for the smallest parameter that would let
the curve satisfy security criteria.
One curve, Ed25519, is isomorphic to Curve25519 but is not of the
above form. It is included because of the desire for a curve of size
approximately 2^250 on which addition makes sense for use in
signature schemes.
Since the field GF(p) has no subfields, Weil restriction is not a
concern. The curves not only needed to have a large prime order
subgroup, but the quadratic twist of the curve needed to as well. The
curves also had to satisfy equations prohibiting the existence of
bilinear maps into small fields as well as have no efficiently
evaluatable endomorphisms beyond the negation map.
Because of the curve shapes being used, exceptional cases are less of
an issue then with short Weierstrass curves.
Each curve is given by an equation and a basepoint, together with the
order of the point and the cofactor.
Curve1174 is a curve over GF(2^251-9), formula x^2+y^2=1-1174x^2y^2,
basepoint (158261909772591154195454700645373976338109
1388846394833492296309729998839514,
30375380136041545047641157286514376465
19513534305223422754827055689195992590), order 2^249 -
11332719920821432534773113288178349711, cofactor 4.
Curve25519 is a curve over GF(2^255-19), formula y^2=x^3+486662x^2+x,
basepoint (9, 147816194475895447910205935684099868872646
06134616475288964881837755586237401), order 2^252 +
27742317777372353535851937790883648493, cofactor 8.
Ed25519 is a curve over GF(2^255-19), formula-x^2+y^2=1-
(121665/121666)x^2y^2, basepoint (x, 4/5), where x is less then p/2.
For reference, in the field 2^255-19,
121665/121666=20800338683988658368647408995589388737092878452
977063003340006470870624536394,
4/5=463168356949264781694283940034751631413079938662562256
15783033603165251855960, and the quoted x is
15112221349535400772501151409588531511454012693041857206046113283949
847762202.
Ladd, Watson Expires 29 September 2014 [Page 6]
Internet Draft ladd-safecurves 28 March 2014
E382 is a curve over GF(2^382-105), formula x^2+y^2=1-67254x^2y^2,
basepoint (3914921414754292646847594472454013487047
137431784830634731377862923477302047857640522480241
298429278603678181725699, 17), order 2^380 -
1030303207694556153926491950732314247062623204330168346855, cofactor
4.
M383 is a curve over GF(2^383-187), formula y^2=x^3+2065150x^2+x,
basepoint (12,
473762340189175399766054630037590257683961716725770372563038
9791524463565757299203154901655432096558642117242906494), order 2^380
+ 166236275931373516105219794935542153308039234455761613271, cofactor
8.
Curve3617 is a curve over GF(2^414-17), formula x^2+y^2=1+3617x^2y^2,
basepoint
(17319886477121189177719202498822615443556957307604340815256226
171904769976866975908866528699294134494857887698432266169206165, 34),
order 2^411 -
33364140863755142520810177694098385178984727200411208589594759,
cofactor 8.
Ed448-Goldilocks is a curve over GF(2^448-2^224-1), formula
x^2+y^2=1-39081x^2y^2, basepoint
(1178121612634369467372824843433100646651805353570163734168790821
47939404277809514858788439644911793978499419995990477371552926
308078495, 19), order 2^446 -
13818066809895115352007386748515426880336692474882178609894547503885,
cofactor 4.
M511 is a curve over GF(2^511-187), formula y^2 = x^3+530438x^2+x,
basepoint (5,
25004106455650724233689811491392132522115686851736085900709792642
48275228603899706950518127817176591878667784247582124505430745177
116625808811349787373477), order 2^508 +
107247547596357476240445315140681218420707566274348330289655408
08827675062043, cofactor 8.
E521 is a curve over GF(2^521-1), formula x^2+y^2=1-376014x^2y^2,
basepoint
(1571054894184995387535939749894317568645297350402905821437625
18115230499438118852963259119606760410077267392791511426719338990
5003276673749012051148356041324, 12), order 2^519 -
3375547632585017057891076304187826360719049612140512266186351500
85779108655765, cofactor 4.
4. Point Encoding
Ladd, Watson Expires 29 September 2014 [Page 7]
Internet Draft ladd-safecurves 28 March 2014
We begin by noting that if (b_0, b_1, ... b_{n}) is a sequence of
bytes, that \sum_{i=0}^n b_i*256^i is an integer, and every integer
up to 256^{n+1} can be represented this way. This is the little-
endian representation of an integer, and is unique for a given
integer.
Let (x,y) be a point on M(GF_p), where M is a Montgomery curve. Then
let l be the minimal number of bytes to represent x in little-endian.
A point is represented as l-bytes, representing in little-endian
radix 256 the minimal representative of [x] modulo p. This
representation works for the standard x-coordinate only arithmetic
for ECDH, but cannot be used for protocols requiring addition.
Let (x,y) be a point on E(GF_p), where E is an Edwards curve or
twisted Edwards curve. Let l be the minimial number of bytes to
represent a value of size up to p-1 with the top bit free.
Concretely, if the next power of two above p is 256 to some power, we
need an extra byte, otherwise we do not.
Define the sign bit of x to be one if the encoding of x in little-
endian is lexographically larger then that of -x, and zero otherwise.
Concretely the sign bit one elements of F_q are {1,3,5,... q-2}.
A point is represented as l bytes, l representing in little-endian
radix 256 the minimal representative of [y] modulo p, and the top bit
of the top byte set to equal the sign bit of x. Because we have
always ensured that there is extra room in l than is strictly
required to represent y, we have room for the top bit to be set.
Point encoding is clear in both cases. To decode a point on an
Edwards curve with parameter d, one takes the y value and computes
the valuex^2, then takes the square root. Methods for taking the
square root are sadly highly prime-dependent, but [COHEN] contains a
large number of options. If the square root does not exist, the
encoding is invalid and no further operations should be performed
with the provided data.
These point encodings were selected to be compatible with the
existing high speed software for Curve25519 and Ed25519.
5. Design Considerations
These curves were selected to satisfy a few criteria. First off each
prime is of a form enabling fast software implementations for
arithmetic modulo that prime. Secondly, the prime shapes are picked
so that the addition and doubling formulas have no exceptions. This
ensures that software doesn't have to deal with invalid points
appearing the middle of an operation, leaking information to an
Ladd, Watson Expires 29 September 2014 [Page 8]
Internet Draft ladd-safecurves 28 March 2014
attacker. Thirdly the curve shapes have exceptionally fast formulas.
Fourthly, the parameters of the curves are minimal, except for
Ed25519, ensuring fast arithmetic and rigidity in picking the curve.
Ed25519 is isomorphic to Curve25519, and is useful in implementations
taking advantage of radix-k algorithms or when signatures using a
group of size around 2^250 are required.
Curve25519 implementations using these techniques have set speed
records for ECDH at the 125 bit security level, and signature speed
records. Other curves have not yet been implemented in this manner,
but it is assumed that when mature optimized code is written it will
perform similarly.
For a protocol to use these curves, both parties must agree on which
curves are being used, and on an encoding. The encoding in this
document is highly recommended. Once this is decided, the protocol
need only specify the arithmetic to be done on the points exchanged,
and need not specify how that arithmetic is to be done.
6. Security Considerations
This entire document discusses methods of implementing cryptography
securely. The time for an attacker to break the DLP on these curves
is the square root of the group order with the best known attacks.
These curves are twist-secure, limiting the impact of wrong-curve
attacks on Montgomery ladders.
It is recommended that implementors use the Montgomery ladder on
Montgomery curves with x coordinate only to avoid timing attacks when
Diffie-Hellman is being used. In this mode, curve checks are not
required. On Edwards curves, standard curve (but not group)
membership checks are required for ECDH to be secure. Implementors
should pay attention to the cofactor in the discussion of ECDH in
section 2, and avoid forgetting the cofactor. While the impact is
slight, it should still be avoided.
These curves and cited formulas are complete, avoiding certain
attacks against naive implementations of ECC protocols. They have
cofactor greater than one, occasionally requiring slight adjustments
to protocols such as using multiples of the cofactor as keys for ECDH
or similar representations for signature schemes. These adjustments
are protocol-specific.
This is not an exhaustive discussion of security considerations
relating to the implementation of these curves. Implementors must be
familiar with cryptography to safely implement any cryptographic
standard, and this standard is no exception.
Ladd, Watson Expires 29 September 2014 [Page 9]
Internet Draft ladd-safecurves 28 March 2014
6. IANA Considerations
IANA should assign OIDs to these curves.
7. Acknowledgments
Thanks to Alyssa Rowan and Robert Ransom for catching transcription
and formula errors. Paul Lambert was the guinea pig for
implementation guidelines. Paul Hoffman noticed the cofactor was
missing. Manuel Pegourie-Gonnard noticed suboptimal formulas and
corrected them, as well as inadvertent misstatements and
underspecifications. Thanks to David McGrew for providing editorial
support. Thanks to the various members of the CFRG who provided
advice on the text, and to Michael Hamburg for discussing adaptation
of the point encoding to Ed448-Goldilocks. Jeff "=JeffH" Hodges
recommended Silverman as a reference. Ilari Liusvaara noticed
infelicities of language.
8. References
[BL07] Bernstein, Daniel J and Tanja Lange. ``Faster addition and
doubling on elliptic curves.'' Pages 29-50 in Kurosawa, Advances in
Cryptology:ASIACRYPT 2007. Lecture Notes in Computer Science 4833,
Springer-Verlag Berlin, 2007.
[COHEN] Cohen, Henri. A Course in Computational Algebraic Number
Theory, GTM 138, Springer-Verlag, 1993.
[EFD] Lange, Tanja. Explicit Formula Database.
http://www.hyperelliptic.org/EFD/g1p/index.html
[MONTGOMERY] Montgomery, Peter L. ``Speeding the Pollard and elliptic
curves methods of factorization''. Mathematics of Computation 48
(1987), 243-264. MR 88e:11130.
[SAFECURVES] Berstein, Daniel J, and Tanja Lange. Safecurves.
safecurves.cr.yp.to
[SILVERMAN] Silverman, Joseph H. The Arithmetic of Elliptic Curves,
GTM 106. Springer-Verlag Berlin, 2009.
[TWIST] Bernstein, Daniel J, Peter Birkner, Marc Joye, Tanja Lange,
and Christiane Peters. ``Twisted Edwards Curves''. In Vaudany, Serg.
Avances in Cryptology:AFRICACRYPT 2008. Lecture Notes in Computer
Science 5023. Springer-Verlag, Berlin 2008. Preprint from
http://eprint.iacr.org/2008/013.pdf
Author's Address
Ladd, Watson Expires 29 September 2014 [Page 10]
Internet Draft ladd-safecurves 28 March 2014
Watson Ladd
watsonbladd@gmail.com
Berkeley, CA
Ladd, Watson Expires 29 September 2014 [Page 11]