ec25519
*******


Twisted Edwards curves
======================

In general, a twisted Edwards curve is a mathematical group on the
points satisfying an equation of the form

   ax^2 + y^2 = 1 + dx^2y^2

For purposes of cryptography the curve is defined on a finite field.

The corresponding group law is

   (x_1,y_1) + (x_2,y_2) = \left( \frac{x_1y_2 + y_1x_2}{1 +
   dx_1x_2y_1y_2} , \frac{y_1y_2 - ax_1x_2}{1 - dx_1x_2y_1y_2} \right)

For further information on twisted Edwards curves see [BBJ+08].


Extended coordinate representation
----------------------------------

Representing a curve point as an coordinate pair (x,y) is rather
inconvenient for calculations on points as reciprocation is a very
expensive operation. [HWCD08] specifies an alternative representation:
the *extended coordinate* representation, which stores a point as a
tuple of four coodinates X, Y, Z and T, satisfying the following
equations:

   x = \frac{X}{Z} \qquad y = \frac{Y}{Z} \qquad x \cdot y =
   \frac{T}{Z}

By storing the denominator of the fractions as Z, consequent group
operations can be performed without having to compute reciprocals
until a canonical representation is needed again. The additional value
T is used to speed up some operations.

The extended coordinate representation of twisted Edwards curves
allows very efficient *strongly unified addition*; the term *strongly
unified addition* denotes that the implementation of the addition
operation can be used to double a point as well, so the special case
of adding a point to itself doesn't have to be implemented
specifically.

As the data of the Explicit-Formulas Database [EFD] suggests, the
extended coordinate representation of twisted Edwards curves allows
strongly unified addition with the least number of operations of all
similar curve types and representations in the database (i. e. 9
multiplications), which is the principal reason a twisted Edwards
curve has been chosen for fastd's handshake.


Point compression
-----------------

As the points of an elliptic curve satisfy a curve equation, it is
possible to transform the coordinates of a point into a more compact
representation for transmission or storage. The twisted Edwards curve
equation can be transformed to:

   y^2 = \frac{1 - ax^2}{1 - dx^2}

As one can easily see, there are at most two possible y values for
each value of x (this rule also holds when the elliptic curve is
defined over a finite field), thus one bit is enough to distinguish
between the two values.

For the curve used by fastd this means: as it is defined over a field
with the cardinality 2^{255} - 19, 255 bit are necessary to store a
coordinate. Point compression allows to conveniently pack the 255 bit
x coordinate with the least significant bit of the y coordinate into a
256 bit representation.

Even though this optimization is quite obvious, it was protected by US
patent 6,141,420 ([VMA00]), which chould have complicated the
operation of fastd when subject to the US patent law. Fortunately, the
patent has expired on 29 July 2014.


The curve used by ec25519
=========================

The curve used by ec25519 is based on Curve25519 (see [Ber06]).

Curve25519 uses a Montgomery curve in a reduced representation, which
allows very fast scalar multiplication, but makes it impossible to
perform simple additions on curve points. Therefore an equivalent
twisted Edwards curve is used for fastd.

Curve25519 is defined by the following equation:

   v^2 = u^3 + 486662u^2 + u

over the prime field F_p for the prime p = 2^{255} - 19.

[BBJ+08] states that for all Montgomery curves

   Bv^2 = u^3 + Au^2 + u

with A \in F_p \setminus \{-2,2\} and B \in F_p \setminus \{0\} there
is a birationally equivalent twisted Edwards curve

   ax^2 + y^2 = 1 + dx^2y^2 \text{ with } a = \frac{A + 2}{B} \text{
   and } d = \frac{A - 2}{B},

thus leading to the following curve equation:

   486664x^2 + y^2 = 1 + 486660x^2y^2


Generator point
---------------

Curve25519 uses a point with

   u = 9

as its generator; the v coordinate is not specified as it is not
needed by the algorithm.

The two possible v coordinates are:

   v1 &= \texttt{0x20ae19a1b8a086b4e01edd2c7748d14c923d4d7e6d7c61b229
   e9c5a27eced3d9} \\ v2 &= \texttt{0x5f51e65e475f794b1fe122d388b72eb
   36dc2b28192839e4dd6163a5d81312c14}

Out of (u,v_1) and (u,v_2), the point (u,v_1) has been arbitrarily
chosen to be used in fastd; using the equivalence between Montgomery
and twisted Edwards curves given by [BBJ+08]

   x &= \frac{u}{v} \\ y &= \frac{u-1}{u+1}

this leads to the coordinates

   x &= \texttt{0x547c4350219f5e19dd26a3d6668b74346a8eb726eb2396e1228
   cfa397ffe6bd4} \\ y &= \texttt{0x666666666666666666666666666666666
   6666666666666666666666666666658}

which specify the generator point G that is used by fastd's
"ec25519-fhmqvc". Like (u,v_1) on the Montgomery curve, the point G =
(x, y) on the twisted Edwards curve has the order

   |G| = 2^{252} + 27742317777372353535851937790883648493


Implementation
==============

The elliptic curve operations used by fastd have been implemented as a
reusable library, *libuecc*, which is developed together with fastd.
Large portions of the implementation, especially arithmetic modulo
2^{255}-19, haven been taken from the original Curve25519
implementation, which has been released in to the public domain by its
author D. J. Bernstein.

Like in the Curve25519 implementation, great care has been taken to
ensure that there are no data-dependent branches or array accesses,
thus making *libuecc* resistant to timing attacks.


Bibliography
============

[BBJ+08] D. J. Bernstein, P. Birkner, M. Joye, T. Lange and
         C. Peters, "Twisted Edwards curves", in Progress in
         Cryptology—AFRICACRYPT 2008, Springer, 2008, pp. 389–405.

[Ber06] D. J. Bernstein, "Curve25519: new Diffie-Hellman speed
        records", in Public Key Cryptography-PKC 2006, Springer, 2006,
        pp. 207–228.

[EFD] D. J. Bernstein and T. Lange, "Explicit-Formulas
      Database—Genus-1 curves over large-characteristic fields".
      [Online] http://hyperelliptic.org/EFD/g1p/index.html

[HWCD08] H. Hisil, K. K.-H. Wong, G. Carter and E. Dawson,
         "Twisted Edwards curves revisited", in Advances in
         Cryptology—ASIACRYPT 2008, Springer, 2008, pp. 326–343.

[VMA00] S. A. Vanstone, R. C. Mullin and G. B. Agnew,
        "Elliptic curve encryption systems", US Patent 6,141,420,
        2000.
