[curves] The great debate over point formats

[Robert Ransom]

On 1/29/14, Mike Hamburg <mike at shiftleft.org> wrote:

> The remaining trick is, should the Ed-x-coordinate or its sign bit be used
> universally, even by Montgomery implementations or not?

The bigger question is “Which Edwards curve?”.  As long as the only
Montgomery-form coordinate encoded is x, Montgomery curves are fairly
well-defined given Montgomery A.  But the Edwards form has a
two-dimensional parameter space (a, d), and in many cases there are
multiple reasonable choices of a.

I would choose a=-1 as the encoded form for every curve in every
coordinate field in which -1 is a square, and a=1 otherwise.  This is
consistent with Ed25519; it makes safe, reasonably efficient
implementations more convenient without adversely affecting more
highly optimized implementations (e.g. implementations which use an
a=-1 form of a curve specified with a=1 over a 3mod4 coordinate
field); and it keeps the non-affine coordinates which arise when d/a
is a square away from the point encoding/decoding operations.


Robert Ransom