Subject: [Cfrg] curves, coordinates, and computations

From: "D. J. Bernstein" <[email-masked]>
Date: 29 Jul 2014 22:13:12 -0000

I've noticed that quite a few proposed requirements and comments have
been confusing three separate decisions:

   * which _curves_ should be used in protocols such as TLS;
   * which _coordinates_ should be used in protocols; and
   * which _computations_ the implementations will carry out.

For the _curves_ there are several options under discussion:

   * short Weierstrass curves such as NIST P-256, the curve y^2 =
     x^3-3x+c mod 2^256-2^224+2^192+2^96-1, where c is a big
     random-looking number that I won't repeat here;

   * Montgomery curves such as y^2 = x^3+486662x^2+x mod 2^255-19
     (Curve25519);

   * Edwards curves or more generally twisted Edwards curves such as
     x^2+y^2 = 1+3617x^2y^2 mod 2^414-17 (Curve41417) or Microsoft's
     -x^2+y^2 = 1+15342x^2y^2 mod 2^256-189.

For the _coordinates_ sent through the wire there are also several
options, including

   * short-Weierstrass x and y coordinates (often with y compressed);

   * short-Weierstrass x by itself (proposed in the first ECC paper);

   * Montgomery x by itself (used in practically all deployments of
     Curve25519 for one-time DH and for longer-lasting DH);

   * Edwards x and y (increasingly widely deployed in Ed25519
     signatures, with y compressed);

and many more. For the _computations_ there are also several options,
including

   * the Montgomery ladder (typical advertisement: excellent speed
     together with unmatched simplicity),

   * windowed "extended Edwards" scalar multiplication (typical
     advertisement: even faster than Montgomery for keygen), and

   * windowed "Jacobian" scalar multiplication (typical advertisement:
     reusing older software).

There seems to be a common misconception that making a decision at one
of these levels forces the decisions at all of the other levels. In
fact, as I'll describe in detail below, specifying a curve still leaves
tremendous freedom to the protocol designer to choose coordinates:

   * Edwards curves support Edwards coordinates, Montgomery coordinates,
     and short-Weierstrass coordinates.

   * Montgomery curves with points of order 4 (e.g., Curve25519) support
     Edwards coordinates; all Montgomery curves support Montgomery
     coordinates and short-Weierstrass coordinates.

   * Short Weierstrass curves with cofactor 1 (e.g., P-256) have by far
     the worst compatibility---obviously they support short-Weierstrass
     coordinates, but they fail to support Edwards coordinates and fail
     to support Montgomery coordinates.

Furthermore, specifying a curve and coordinates still leaves tremendous
freedom to the implementor to choose a computation. For example, Edwards
curves in short-Weierstrass coordinates support the Montgomery ladder
for scalar multiplication. See

   https://www.imperialviolet.org/2013/05/10/fastercurve25519.html

for another example spelled out in detail. Cofactor-1 short Weierstrass
curves are again the worst case for compatibility; for example, they
don't support the Montgomery ladder, and they don't support
extended-Edwards scalar multiplication.

As a concrete compatibility example, let me take NIST's ECDSA standard,
which NIST defines mostly via reference to ANSI X9.62. The standard is
parametrized by a choice of short Weierstrass curve Y^2 = X^3+aX+b mod p
meeting various criteria (or a binary curve; for simplicity I'll ignore
this option). What's sent through the network as a public key---what
actually matters for interoperability of public keys---is

   * the X-coordinate of a point on the curve Y^2 = X^3+aX+b mod p and
   * the Y-coordinate of the point,

encoded as a string in a specified way, optionally with Y compressed.

Everybody knows that NIST P-256 is compatible with the ECDSA standard.
The NIST P-256 curve y^2 = x^3-3x+c obviously matches the format Y^2 =
X^3+aX+b. One can check that P-256 meets all of the standard criteria.

What about Montgomery curves? For example, does Curve25519 support
ECDSA? Yes, it does. This is a trivial shift of coordinates: substitute
x = X-486662/3 and Y = y into y^2 = x^3+486662x^2+x to obtain

   Y^2 = X^3-(236839902241/3)X+(230521961007359098/27)

which is in exactly the short-Weierstrass format allowed by ECDSA. One
can also check that this curve meets all of the criteria required by the
ECDSA standard: for example, the Curve25519 cofactor 8 is well within
the allowed range of cofactors (FIPS 186-4 says cofactor<=2^14 for
255-bit primes). One standards-compliant way to specify this example of
ECDSA is to specify a = 236839902241/3 etc., not even mentioning the
equation y^2 = x^3+486662x^2+x normally used to define Curve25519.

What about Edwards curves? Does Microsoft's -x^2+y^2 = 1+15342x^2y^2 mod
2^256-189 support ECDSA? The answer is again yes, although getting to a
Weierstrass curve is slightly more complicated; see below.

If you have a complete implementation of standard ECDSA then you can
simply plug these curves into the implementation. You'll get better
speeds with a reduction method specialized to the new primes, raising
the question of what speeds are possible for each prime (see, e.g.,
https://www.imperialviolet.org/2010/12/21/eccspeed.html), and what
simplicity is possible when you don't care about speed, and the
tradeoffs possible between the desiderata of speed and simplicity. But
those issues aren't the topic of this message.

If you have a more limited implementation of ECDSA, for example one
specific to NIST P-256, then you'll certainly need to add code for the
new primes, but there's a good chance that the code has at least a
high-level Jacobian scalar-multiplication layer that works for arbitrary
short-Weierstrass curves. For example, you might have copied the
scalar-multiplication method stated in the ANSI standard, although this
particular method leaks tons of information through timing and is much
slower than other methods---the sort of code (and standard) that ought
to be replaced no matter what happens with the curve choice!

Beyond the benefits of a new prime, using ECDSA with these new curves
gives you access to better scalar-multiplication options. For example,
in the case of Curve25519:

   * Take the short-Weierstrass coordinate X provided as input.
   * Subtract 486662/3 to obtain the Montgomery coordinate x.
   * Use the Montgomery ladder for scalar multiplication. (This is the
     very short code that I displayed in my talk in Toronto.)
   * Add 486662/3. (This gets back to the short-Weierstrass output.)
   * Use a few extra lines to compute the other output y.

This code is considerably simpler, faster, and less error-prone than the
scalar-multiplication procedure in the ANSI standard. This option isn't
available for NIST P-256, so if you have to support both curves then you
might prefer the old-fashioned Jacobian approach, but other people will
still take advantage of the Montgomery-ladder option.

As a fancier example, starting from the Montgomery coordinates x and y
of a Curve25519 point, you can compute Edwards coordinates

   X = sqrt(486664)x/y,
   Y = (x-1)/(x+1)

on the corresponding Edwards curve X^2+Y^2 = 1+(121665/121666)X^2Y^2.
You can then use, e.g., windowed extended-Edwards scalar multiplication.
Compared to Jacobian scalar multiplication this is considerably faster
and has the huge advantage of not having to worry about exceptional
cases in the code. This generalizes to any complete Edwards curve; see
the Bernstein--Lange paper that introduced Edwards-curve cryptography. 

You might be worried about the divisions involved in these conversions
between Edwards coordinates and other coordinates. This is one of the
motivations for EdDSA, and in particular Ed25519, which sends Edwards
coordinates for Curve25519 through the wire (compressed) rather than
sending short Weierstrass coordinates ECDSA-style or sending Montgomery
coordinates. One shouldn't overestimate the speed benefit here---

   * the two divisions in a conversion are trivially merged into one,
   * constant-time division is only about 10% of optimized constant-time
     scalar multiplication, and
   * there are several well-known tricks to merge coordinate-conversion
     divisions into other operations, typically reducing 10% below 1%

---but there's an obvious benefit in simplicity. This isn't compatible
with ECDSA, but ECDSA also has many other problems that motivate doing
something new. (Similarly, sending the Montgomery x-coordinate has clear
benefits for ECDH/ECDHE.) An intermediate transition option would be to
support both Ed25519 and ECDSA with Curve25519, sharing all of the
underlying scalar-multiplication code, with an eye towards eventually
allowing simpler implementations that support only Ed25519.

Similarly,

   (1+y)/(1-y) - 30682/46029, sqrt(-4/15343)(1+y)/((1-y)x)

are ECDSA-compatible coordinates for the Microsoft curve. These two
coordinates satisfy a short Weierstrass equation. So choosing a
twisted-Edwards curve such as the Microsoft curve doesn't rule out
ECDSA, doesn't rule out the Montgomery ladder, etc.

To summarize, all of the _curves_ under discussion support ECDSA. So I'm
quite puzzled by Microsoft's "requirements" that "new curves" must
"support standard ECDHE and ECDSA algorithms" and must "support standard
EC point representations". The most obvious interpretations of these
"requirements" are content-free.

A subsequent Microsoft slide asserts that Montgomery curves ("curve
family: Montgomery") "can't be used with ECDSA". This is simply wrong.
There is no problem using Montgomery _curves_ with ECDSA. The fact that
ECDSA specifies short-Weierstrass _coordinates_ means that sending
Montgomery _coordinates_ would not be standards-compliant, but it's
trivial to send short-Weierstrass _coordinates_ for a Montgomery curve.

It's particularly strange that Microsoft makes this assertion only for
Montgomery curves and not for (twisted) Edwards curves. If Microsoft is
trying to suggest that simply sending the Edwards x and y is compliant
with the ECDSA standard, then a retraction is required; again, the ECDSA
standard specifies short-Weierstrass coordinates. If Microsoft is trying
to suggest that one can use Edwards _curves_ with ECDSA, then this is of
course true, but it's not an advantage of Edwards over Montgomery.

I'm similarly quite puzzled by Nigel Smart insisting on "curves" whose
"definition is in Weierstrass form". If this were actually imposed as a
requirement then all of the curve proposers would go through the trivial
exercise of reformulating all of these curves in Weierstrass form,
elevating style over content. This superficial translation wouldn't
remove the good reasons, or the ability, for new protocols to specify
other _coordinates_ (as in Ed25519), and similarly it wouldn't remove
the extended implementation options that I've described above. The most
flexibility would still be achieved by translated Montgomery curves and
translated Edwards curves.

Nigel also insists on "curves" whose "data format for point transfer" is
"in Weierstrass form". This is a syntax error, asking the curve object
to answer a "data format" question that it doesn't know how to answer. I
understand that Nigel wants protocols to use old-fashioned Weierstrass
coordinates, but he's wrong in suggesting that this could rule out any
of the curves under discussion. (As a side note, I don't know what his
rationale is, while I see important advantages to other choices.)

Let me again emphasize that requiring _curves_ to support ECDSA etc. is
content-free. Every curve under discussion supports ECDSA, and this
clearly isn't going to change. Nigel is wrong in suggesting that this
sort of requirement would exclude Edwards curves, and Microsoft is wrong
in suggesting that this sort of requirement would exclude Montgomery
curves.

Surely a requirement (or desideratum) that confuses people, and that
doesn't actually accomplish anything, should be eliminated. The actual
story is that Montgomery curves and Edwards curves support _extra_
options---options that have undisputed value---while _also_ supporting
the old-fashioned options.

As far as I can see, this confusion is _almost_ the entire source of
opposition to Montgomery curves and/or Edwards curves. The reason I'm
saying "almost" is that I also saw Nigel claiming that cofactor 1 has a
critical security benefit ("vital to avoid mistakes")---but details to
support this claim are missing. Note that

   * IEEE allows cofactors;

   * ANSI allows cofactors;

   * NIST claims that "For efficiency reasons, it is desirable to have
     the cofactor be as small as possible", but NIST allows larger
     cofactors and doesn't claim that smaller cofactors matter for
     _security_; and

   * Certicom's pet SEC 1 standard originally required cofactor<=4 but
     switched in 2009 to allowing larger cofactors.

Post-NIST research has produced overwhelming evidence that properly
chosen curves with larger cofactors, when implemented in the most
natural ways, _eliminate_ several critical pitfalls that nobody knows
how to eliminate for cofactor 1. See

   http://safecurves.cr.yp.to/ladder.html
   http://safecurves.cr.yp.to/twist.html
   http://safecurves.cr.yp.to/complete.html

for summaries and references.

Does anyone have a serious argument against Montgomery and/or Edwards?
I'm not aware of anything. I think there's an overwhelming case for
insisting that each new curve be compatible with the widest range of
options: short Weierstrass coordinates, Jacobian scalarmult, Montgomery
coordinates, Montgomery scalarmult without point validation, Edwards
coordinates, Edwards scalarmult without special cases, etc. This means
requiring each curve to have

   * a point of order 4, to support Edwards coordinates and Montgomery
     coordinates (improving simplicity, speed, and security);

   * a unique point of order 2, to eliminate failure cases in the
     simplest possible way; and
     
   * twist security, so that input validation isn't necessary for
     single-coordinate DH.

Some examples of curves meeting all these criteria are Curve25519,
Curve41417, E-521, and Microsoft's new twisted-Edwards curves---again,
it's wrong to think that Edwards curves aren't Montgomery-compatible or
vice versa. Examples of curves that _don't_ qualify are

   * the NIST curves (which obviously are grandfathered in),
   * the Brainpool curves (ditto), and
   * Microsoft's non-Edwards curves (which I think should be tossed).

Excluding inferior options will obviously simplify the discussion. For
example, if all remaining options automatically support Elligator 1
and/or Elligator 2, then there's no need to discuss which applications
care about this support, and whether Elligator Squared is adequate.

It would also be helpful for CFRG to figure out which range of ECC
mechanisms it's recommending: for example, just a curve choice, or also
coordinate choices for common applications. Since a large part of the
motivation for new curves is to enable better implementations, it makes
sense to carefully consider and document major implementation options,
even though it's ultimately up to the implementor to decide what to do
within the bounds of interoperability.

---Dan