[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03 04

Internet Draft                                                   W. Ladd
<draft-ladd-safecurves-03.txt>                              Grad Student
Category: Informational                                      UC Berkeley
Expires 19 July 2014                                     15 January 2014

             Additional Elliptic Curves for IETF protocols
                     <draft-ladd-safecurves-03.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 9 July 2014                   [Page 1]


Internet Draft              ladd-safecurves               8 January 2014


   parameters of a new family of elliptic curves with efficiency and
   security advantages over existing and widely deployed mechanisms.

















































Ladd, Watson              Expires 9 July 2014                   [Page 2]


Internet Draft              ladd-safecurves               8 January 2014


Table of Contents

   1. Introduction ....................................................3
   2. Explicit Formulas ...............................................3
   3. The Curves ......................................................6
   4. Point Encoding ..................................................9
   5. Security Considerations .........................................9
   6. IANA Considerations .............................................9
   7. Acknowledgements ................................................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].

   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. Explicit Formulas

   Let p be a prime number. There is a unique field with p elements. Its
   elements can be represented as the set of integers {0, 1, ... p}.
   Fields have three operations: addition, multiplication, and
   multiplicative and additive inverses. They have two distinguished
   elements: 0, and 1.

   To add two numbers, a and b, one computes the integer a+b, and takes
   the remainder on division by p.

   To multiply two numbers a and b, one computes a*b, and takes the
   remainder on division by p.

   Algorithms are in [COHEN].

   To compute the additive inverse of a, one can compute (p-1)*a, and
   again take the remainder.

   To compute the multiplicative inverse of a, written a^(-1) the best
   way to avoid side channel attacks is to calculate a^(p-2), reducing



Ladd, Watson              Expires 9 July 2014                   [Page 3]


Internet Draft              ladd-safecurves               8 January 2014


   each intermediate product modulo p. To take exponents efficiently,
   one uses a square-and-multiply algorithm, i.e. compute a^{2n+1} as
   a*(a^{n})^2, a^{2n} as (a^{n})^2. The multiplicative inverse of 0 is
   undefined.

   0+a=a for all a. a*1=a for all a. a*a^{-1}=1 for all a nonzero.

   The field with p elements is denoted GF(p).

   An abelian group is a set S with two operations: addition and
   inverse, denoted + and unary - respectively, and a distinguished
   element e. a+e=e+a=a, a+-a=e, and addition is commutative.

   [n]a is defined as [0]a=e, [n]a=a+[n-1]a for n a positive integer,
   and extended by taking [-1]a=-a to negative integers.

   Given an element of an abelian group a in A, the order of a is the
   smallest positive integer n such that [n]a=e. The cofactor of a is
   the size of A divided by the order of a. By a classical theorem of
   Lagrange the cofactor is an integer.

   The remainder of this standard defines abelian groups in which for a
   fixed basepoint (denoted p), distinguishing between (g, [a]p, [b]p,
   [ab]p) with a, b picked uniformly at random from nonnegative integers
   less then the order, and (g, [a]g, [b]g, [c]g), is hard without
   spending prohibitive amounts of time. The time required is the square
   root of the order of g.

   These groups are defined over the set of points with coordinates x
   and y satisfying a given equation. They are different from the short
   Weierstrass equations found in many standards.

   On any abelian group if we take the sets {a, -a} with a ranging over
   A, we no longer have a well defined addition. However, we still have
   a well defined multiplication by n map, as -([n]a)=[-n]a. In the
   context of abelian varieties, this is called "taking the Kummer
   variety", and the set of subset is the Kummer variety.

   To take the Kummer variety of an elliptic curve in the form
   y^2=x^3+Ax^2+x, an Edwards curve, one drops the y coordinate.

   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,



Ladd, Watson              Expires 9 July 2014                   [Page 4]


Internet Draft              ladd-safecurves               8 January 2014


   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.

   This protocol will work on a Kummer variety as well.

   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 (X_1,Z_1), (X_2,Z_2),
   (X_3,Z_3) be coordinates such that X_1/Z_1, X_2/Z_2, X_3/Z_3 are the
   x coordinates of P, Q, and P+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 X_4/Z_4 as the x coordinate of [2]Q, and X_5/Z_5 as the x
   coordinate of P+[2]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=[0,1], 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. In implementing the
   above algorithm the conditionals should be implemented by means of
   constant time conditional swaps rather than jumps to avoid timing and



Ladd, Watson              Expires 9 July 2014                   [Page 5]


Internet Draft              ladd-safecurves               8 January 2014


   control flow attacks. n should be represented with a fixed number of
   bits to further minimize timing information. Skipping intial zeros is
   a terrible idea.

   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 (X_1, Y_1, Z_1) to (X_2, Y_2, Z_2) 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 (X_1,Y_1,Z_1)=
   (X_2,Y_2,Z_2). For most of the curves with the exception of T25519
   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.

   The above algorithms are not the only algorithms possible. One can
   use alternative parametrizations 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].

3. The Curves

   These curves were selectd as follows: first a field was picked which



Ladd, Watson              Expires 9 July 2014                   [Page 6]


Internet Draft              ladd-safecurves               8 January 2014


   because of its form permits specialized, faster arithemetic. 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, T25519, 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.

   T25519 is a curve over GF(2^255-19) formula
   121666x^2+y^2=1+121665x^2y^2, basepoint (6,
   158858074951644465347792977535893721270128458670434237
   40362095615172183684671), order 2^252 +
   27742317777372353535851937790883648493, cofactor 8.

   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.




Ladd, Watson              Expires 9 July 2014                   [Page 7]


Internet Draft              ladd-safecurves               8 January 2014


   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

   Let (x,y) be a point on M(GF_p), where M is a Montgomery curve. Then
   let l=ceil[log(p)/log(256)]. A point is represented as l-bytes,
   representing in big-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.




Ladd, Watson              Expires 9 July 2014                   [Page 8]


Internet Draft              ladd-safecurves               8 January 2014


   Let (x,y) be a point on E(GF_p), where E is an Edwards Curve. Let
   l=floor[log(p)/log(256)]+1. A point is represented as l bytes, l
   representing in big-endian radix 256 the minimal representative of
   [y] modulo p, and the top bit of the top byte set to equal the low
   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
   Alternative encodings are used by existing software, and protocol
   designers should be aware of this. Alternative encodings may be
   useful if preexisting software is to be used without changes.

5. 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.

   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.

6. IANA Considerations

   IANA should assign OIDs to these curves.

7. Acknowledgments




Ladd, Watson              Expires 9 July 2014                   [Page 9]


Internet Draft              ladd-safecurves               8 January 2014


   Thanks to Alyssa Rowan and Robert Ransom for catching transcription
   and formula errors. Paul Lambert was the guinea pig for implemention
   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.

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
   Watson Ladd
   watsonbladd@gmail.com
   Berkeley, CA







Ladd, Watson              Expires 9 July 2014                  [Page 10]


Html markup produced by rfcmarkup 1.129d, available from https://tools.ietf.org/tools/rfcmarkup/