Re: [Cfrg] 25519 naming

[Andrey Jivsov <[e-mail]>]

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.