[curves] The great debate over point formats
Robert Ransom
rransom.8774 at gmail.com
Wed Jan 29 18:07:34 PST 2014
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
More information about the Curves
mailing list