[Cfrg] 25519 naming

["D. J. Bernstein" <[e-mail]>]

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