Subject: Re: [Cfrg] 25519 naming

From: Andrey Jivsov <[email-masked]>
Date: Tue, 02 Sep 2014 01:18:51 -0700

On 08/25/2014 04:43 PM, D. J. Bernstein wrote:
> It has become increasingly common for "Curve25519" to refer to an
> elliptic curve, while the original paper defined "Curve25519" as an
> X-coordinate DH system using that curve. "Ed25519" unambiguously refers
> to an Edwards-coordinate signature system using that curve.
>
> Kenny and others in Toronto recommended changing terminology to clearly
> separate these three items. Let me suggest the following terminology:
>
>     * "X25519" is the recommended Montgomery-X-coordinate DH function.
>     * "Ed25519" is the recommended Edwards-coordinate signature system.
>     * "Curve25519" is the underlying elliptic curve.
>
> All relevant coordinate systems already have standard names in the
> literature, and I would suggest sticking to those names whenever it's
> necessary to discuss the coordinate systems per se:
>
>     * "Montgomery coordinates" (X,Y) satisfy Y^2 = X^3 + AX^2 + X mod
>       2^255-19, where A = 486662.
>
>     * "Short Weierstrass coordinates" (x,y) satisfy y^2 = x^3 + ax + b
>       where a = 1-A^2/3 and b = 2A^3/27-A/3. An easy transformation to
>       Montgomery coordinates is Y = y and X = x-A/3. The inverse
>       transformation is y = Y and x = X+A/3. Verification script in gp:
>
>          a = 1-A^2/3;
>          b = 2*A^3/27-A/3;
>          montgomery = Y^2-(X^3+A*X^2+X);
>          weierstrass = y^2-(x^3+a*x+b);
>          subst(subst(montgomery,Y,y),X,x-A/3) == weierstrass
>          subst(subst(weierstrass,y,Y),x,X+A/3) == montgomery
>
>     * "Untwisted Edwards coordinates" (x,y) satisfy x^2 + y^2 = 1 +
>       dx^2y^2 where d = (A-2)/(A+2). An easy transformation to Montgomery
>       coordinates is X = (1+y)/(1-y) and Y = sqrt(A+2) X/x. The inverse
>       transformation is x = sqrt(A+2) X/Y and y = (X-1)/(X+1).
>       Verification script:
>
>          A = s^2-2;
>          d = (A-2)/(A+2);
>          edwards = x^2+y^2-(1+d*x^2*y^2);
>          montgomery = Y^2-(X^3+A*X^2+X);
>          subst(subst(montgomery/Y^2,Y,s*X/x),X,(1+y)/(1-y)) == edwards/(y^2-1)
>          subst(subst(edwards/(y^2-1),x,s*X/Y),y,(X-1)/(X+1)) == montgomery/Y^2
>
>     * "-1-twisted Edwards coordinates" (X,Y) satisfy -X^2 + Y^2 = 1 -
>       dX^2Y^2, again with d = (A-2)/(A+2). An easy transformation to
>       untwisted Edwards coordinates is y = Y and x = sqrt(-1) X. The
>       inverse transformation is Y = y and X = -sqrt(-1) x.
>
> X25519 uses the Montgomery X coordinate. Ed25519 uses the -1-twisted
> Edwards X and Y coordinates, with X compressed. It's of course possible
> to instead use short Weierstrass x and y coordinates for everything (as
> required by, e.g., the ANSI and NIST ECDSA standards), but better tuning
> of the coordinate choices produces a measurable gain in speed and a
> larger gain in simplicity.
>
> ---Dan

X25519 performs 9 F(p) multiplications and squares per each bit of a 
scalar, for the total of 2295 F(p) operations, not counting additions. 
Plus there are also 265 operation for an inversion.

According to the above, conversion from -1-twisted Edwards coordinates to X25519 unfortunately involves a F(p) inversion.

    265/2560 ~= 10%

The problem with fixing canonical coordinates seems to be the 10% penalty in conversion from Edwards coordinates to Montgomery due to F(p) inversion.  I wonder if it is possible to not perform the inversion by starting with z!=1 in the Montgomery formula?

This would give us fixed-base optimization and dual key use that comes with Edwards formula and the speed of Montgomery for variable-base ECDH.

---

From: Robert Ransom <[email-masked]>
Date: Tue, 2 Sep 2014 01:28:26 -0700

On 9/2/14, Andrey Jivsov <[email-masked]> wrote:

> According to the above, conversion from -1-twisted Edwards coordinates to
> X25519 unfortunately involves a F(p) inversion.
>
>     265/2560 ~= 10%
>
> The problem with fixing canonical coordinates seems to be the 10% penalty in
> conversion from Edwards coordinates to Montgomery due to F(p) inversion.  I
> wonder if it is possible to not perform the inversion by starting with z!=1
> in the Montgomery formula?

That would cost an extra 1M per scalar bit.  1I to rescale the input
point is *always* faster.

> This would give us fixed-base optimization and dual key use that comes with
> Edwards formula and the speed of Montgomery for variable-base ECDH.

A Montgomery-form x coordinate (or its reciprocal) provides that.
That's why I've been arguing for a point format based on the
Montgomery-form x coordinate for so long, even though no one seems to
be listening.

Robert Ransom

---

From: Andrey Jivsov <[email-masked]>
Date: Tue, 02 Sep 2014 11:05:44 -0700

> point is *always* faster.

Doesn't an inverse require at least 1M (multiply or square) per scalar 
bit as well? Or, are you saying that because more of these Ms in the 
inverse are squares, this provides a small benefit?

> Montgomery-form x coordinate for so long, even though no one seems to

I am interested, especially in a detailed write up.

Without an efficient conversion between coordinates, the point format 
will likely determine the method of the scalar operation.

...

---

From: Robert Ransom <[email-masked]>
Date: Wed, 3 Sep 2014 01:26:18 -0700

> inverse are squares, this provides a small benefit?

An unoptimized inversion by exponentiation would cost up to 1M+1S per
bit of the coordinate-field order.  However:

* All coordinate fields that are currently under serious consideration
allow a structured addition chain for inversion which reduces the
number of multiplications significantly (for Curve25519, 11M+254S).
Since 1S is typically about 0.67M, that's much less than 1M per scalar
bit, even if you don't count the three least significant bits as part
of the scalar.

* All implementations must perform an inversion in order to scale
their output points anyway, so if someone decides to use a random
coordinate field, they will use the Euclidean algorithm to compute
inverses at an even lower cost than that.

> I am interested, especially in a detailed write up.

I just posted a link to one in another thread:
<http://www.ietf.org/mail-archive/web/cfrg/current/msg04800.html>

Robert Ransom