Subject: [Cfrg] 25519 naming

From: "D. J. Bernstein" <[email-masked]>
Date: 25 Aug 2014 23:43:05 -0000

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

---

From: Tony Arcieri <[email-masked]>
Date: Tue, 26 Aug 2014 14:42:48 -0700

On Mon, Aug 25, 2014 at 4:43 PM, D. J. Bernstein <[email-masked]> wrote:

> X-coordinate DH system using that curve.

Indeed!

https://twitter.com/bascule/status/393221414775312384

> separate these three items.

+1

> Let me suggest the following terminology:
>

Seems good, thank you!

--
Tony Arcieri

---

From: David Leon Gil <[email-masked]>
Date: Wed, 27 Aug 2014 09:18:53 -0400

Cryptographers have, for quite a while, abused notation and
identified different, isomorphic, elliptic forms. Well, abuse of notation
strikes back.

Part of the problem is that calling a transfer of coördinates to a
different form a 'coördinate transform' is confusing. (I suspect that most
people don't have sufficient topology to realize that different forms have
different topologies.)

Mathematicians have a perfectly good terminology already; why not simply
adopt that, and be explicit about the maps used to transfer between forms?

---

From: Dan Brown <[email-masked]>
Date: Wed, 27 Aug 2014 15:28:17 +0000

> -----Original Message-----
> From: D. J. Bernstein
> Sent: Monday, August 25, 2014 7:43 PM
> 
> use short Weierstrass x and y coordinates for everything (as required by,
> e.g., the ANSI and NIST ECDSA standards), 

With an ANSI hat on: 

Just a small clarification, because I think saying "for everything"
overstates the ANSI ECDSA requirements. The quoted statement "for
everything" to me suggests that ANSI requires these formats for
transmission, but that's not strictly true.

While ANSI X9.62 ECDSA and ANSI X9.63 do specify recommended formats such
octet string conversions and some ASN.1 types, using these formats for
transmitting public keys is *not* a requirement to claim compliance to the
algorithms in ANSI X9.62 or ANSI X9.63. (Unless I'm missed something today
in my quick review of these documents, or have forgotten some requirement
text.)   

Of course, it is correct that some conversions *are required* in the
internal algorithm calculations, in order to obtain interoperability:

- Both the ECDSA and ECMQV algorithms specify a required operation that
takes a short Weierstrass x-coordinate of an ephemeral public key and
convert to an integer. 

- Both ECDH and ECMQV algorithms specify a required operation that takes a
short Weierstrass x-coordinate of a shared secret and converts it to a bit
string.

Both ends of the communication must use the same internal conversions to
achieve interoperability.  I think that the choice of short Weierstrass was
mainly motivated by being able to work for any curve.  Recall, that ANSI
optionally users to specify their own curves, even providing an ASN.1 format
to help them out.  (Aside: some IETF specs forbade this general curve
specifying format, so, in a weak sense, it is really IETF disallowing the
curve part of Curve25519, not ANSI ;-)

With ANSI hat off now:

I'm not sure at the moment at the costs or benefits of changing the
algorithm internal conversions with new curves, but here are some tentative
thoughts:

- I think one might be able to separate/tie the curve choice from/to the
internal representations used in the algorithms above, but one would need to
expand the algorithms slightly, and if things are more separated, then add
some mechanisms to negotiate the relevant internals.

- Most of the hard work, i.e. scalar multiplication, can be done in whatever
format is convenient, with wire-format and final algorithm conversions being
done just when needed.

- From a security perspective, these internal conversion functions require
some very mild security properties (e.g. they must not cluster at one output
value) that I think most reasonable alternatives would easily meet, perhaps
with proof.

Regarding NIST requirements: I'm not sure because there are more layers
documents involved, and in particular, there's FIPS 140-3 with the CAVP and
CMVP program and so on, which I think get rather more specific by mandating
formats, which is indeed almost "everything".  Maybe people have been, or
still are, more interested in NIST than in ANSI, anyway. So, another reason
this is a just small clarification.

Best regards,

Dan

---

From: Watson Ladd <[email-masked]>
Date: Wed, 27 Aug 2014 08:52:44 -0700

They all have the same topology. They don't have the same geometry. The
subject you are looking for is algebraic geometry. If we're going to be
annoyingly precise, we should be annoyingly precise.

Well, there is a slight problem: Let X be the curve. Then X has no
coordinates: rather coordinates are a choice of injective map to P^2 or P^1
\times P^1 or something like that. So when someone says "take x+486662/3 to
map onto a curve of the form blah blah" they mean that there is a
commutative triangle with X over P^2 and X over P^2, with the image of the
downwards morphisms lying in the zero locus of the given equation
homogenized, and the thing commutes. (It also all goes over F_p for some
F_p)

The reason X has no coordinates is that a scheme isn't defined to include a
canonical choice, any more than an atlas is a choice of charts in
differential geometry. The definition has already elided all coordinates.

To avoid all this verbiage, which everyone understands (with the usual
criteria about what "everyone" means) we speak in the informal language of
coordinates, and then mentally translate into the language of EGA. I don't
see what's missing from DJBs email in this regard.

Sincerely,
Watson Ladd

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

---

From: David Leon Gil <[email-masked]>
Date: Wed, 27 Aug 2014 14:15:33 -0400

(Yes; I significantly misspoke in my first paragraph: indeed,
different geometries. The perils of curves before coffee.)

> see what's missing from DJBs email in this regard.
'Everyone', for our purposes, should be the 'everyone' who reads RFCs.

These two things are quite different:

- Changing coördinates on the *same* curve (e.g., Jacobian to affine).
- Transferring points to another equivalent curve (e.g., Montgomery to
Weierstrass).

My posit is that eliding this difference is (a small part of) the *cause*
of the confusion djb notes.

It is easy enough to be explicit about the latter. E.g., from the Ed25519
paper (line breaks inserted):

- Curve25519 ... is the Montgomery curve v^2 = u^3 + 486662 u^2 + u over
[Fq25519].
- [...] Curve25519 is birationally equivalent to an Edwards curve,
specifically x^2 + y^2 = 1 + (121665/121666) x^2 y^2; the equivalence is x
= √486664 u / v and y = (u − 1)/(u + 1).
- [T]his Edwards curve is isomorphic to −x^2 + y^2 = 1 − (121665/121666)
x^2 y^2 . . . .

I'd suggest that talking in this way is better than talking about different
curves as 'coordinate systems'.

-dlg

---

From: "D. J. Bernstein" <[email-masked]>
Date: 28 Aug 2014 06:53:53 -0000

The ANSI ECDSA standard specifies elliptic curves mod p to have short
Weierstrass form y^2 = x^3+ax+b (see the "elliptic curves and points"
section), specifies ECDSA public keys as points on such curves ("key
pair generation"), specifies required encodings ("conversions between
data types that SHALL BE USED in the algorithms specified in this
Standard"---emphasis added), and in particular specifies the string
encodings of curve points (x,y) ("point-to-octet-string conversion").

The NIST ECDSA standard simply copies the ANSI formats (e.g., requiring
signatures to be "verified as specified in ANS X9.62"). As for Internet
wire formats, RFC 4492 states that its point formats "are specified in
[7]"; [7] is a normative reference, the ANSI ECDSA standard. RFC 4492
requires exactly these formats to be used on the wire in TLS. An
implementation using a different format wouldn't interoperate with
standard TLS ECDSA. Similar comments apply outside the TLS context.

I'm not saying that these are good standards. I'm also not saying that
it would be difficult for IETF to deviate from the previous standards
and specify a better wire format (as I recommend). I'm simply saying
that various claims here regarding ECDSA compliance are incorrect.

Last month I had already pointed out several serious errors in Microsoft
claims regarding compliance with existing standards such as ECDSA. I was
expecting a response to help move the discussion forward---for example,
withdrawing the claims, or perhaps pinpointing an area of legitimate
dispute if there is one. Instead some of the errors were simply
repeated. This is a disappointingly unproductive pattern. I would hope
to see more responsiveness in the future.

David Leon Gil writes:
  [ regarding short-Weierstrass coordinates, Montgomery coordinates, etc. ]
> I'd suggest that talking in this way is better than talking about
> different curves as 'coordinate systems'.

The word "coordinates" is broader than you think. See, e.g., polar
coordinates.

The distinction between, e.g., short-Weierstrass coordinates and Edwards
coordinates for Curve25519 is much more superficial than the distinction
between, e.g., Curve25519 and NIST P-256. The change of coordinates for
Curve25519 has no effect on field arithmetic (which is most of the code
in a good implementation), has only a small effect on overall efficiency
(since the implementor can change coordinates internally), and has a
provably negligible effect on important security metrics such as
discrete-logarithm difficulty.

It's important for curves to _support_ Montgomery coordinates and
(complete) Edwards coordinates, and there's an extra gain in simplicity
from choosing wire formats carefully (as in X25519 for DH and Ed25519
for signatures), but there are many other issues that transcend the
choice of coordinates and that should be discussed without the
distraction of specifying coordinates.

---Dan