[curves] The great debate over point formats

[Robert Ransom]

On 1/29/14, Mike Hamburg <mike at shiftleft.org> wrote:
>
> On Jan 29, 2014, at 12:20 AM, Robert Ransom <rransom.8774 at gmail.com> wrote:

>> I don't think there's any real need to distinguish encoded points with
>> a sign bit from those which do not have a meaningful sign bit, though.
>> The party who generates a public key is likely to know which
>> protocols it will be used in, and there isn't too much harm if someone
>> else tries to use it in a protocol that its owner doesn't want to
>> participate in.
>
> Right.  I just meant that we'd have to spec at a protocol level, "this
> protocol doesn't use the sign bit, so don't generate one or send it, and in
> particular don't throw one into the hash at the end".  If the sign bit were
> free, we could just have a single "serializePoint" function, but it's not
> free.  So, fine.

This really only matters for shared secrets, and in that case, it's
probably better to always discard the sign bit.  If a point is
transmitted over the network, the recipient can just hash it as is.


>> 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.
>
> Good point.
>
>> 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.
>
>
> In the 3 mod 4 cases, we're starting with an Edwards curve, and the
> Montgomery curve is isomorphic or isogenous to it, at least in the 3 mod 4
> cases.  So I guess we have to choose there, isomorphic or isogenous?  It's
> probably gotta be isomorphic, right?  Do you know how point compression
> would interact with the isogeny, or should I try to work it out?  The
> advantage of the isogenous ones is that d = (A+2)/4 so you can use the
> well-known formulas, but there are obvious advantages to an isomorphism.

I would prefer the isomorphism Ed(1, d) -> Mont(*, 4/d - 2), since the
conversion is both conceptually and technically simpler and there is
no performance cost to using that Montgomery curve in Montgomery form.

> In the 5 mod 8 cases, it's the reverse.  I don't especially care whether
> it's +1 or -1 here.  Talking with Watson and Trevor, we might end up cutting
> all the 5 mod 8 cases except Curve25519, because they were generated under a
> mistaken idea of how Elligator2 works, and they aren't particularly better
> than the 3 mod 4 curves.  In the mean time, I dunno, your suggestion of -1
> because that's how Ed25519 works is fine by me.

My main problem with the ‘Brazil’ curves is that all of them except
M-221 (even the E-* curves) have really *ugly* coordinate fields.
They make the NSA fields look nice by comparison (and at least those
would have the advantage of requiring less extra hardware within a
TPM, as someone mentioned on one of the IETF lists).

The fact that they're choosing new curves to have small-integer
Montgomery parameter instead of small-integer Edwards parameter is a
secondary, though significant, problem.


Robert Ransom