Re: [Cfrg] [TLS] Curve25519 in TLS and Additional Curves in TLS

[Mike Hamburg <[e-mail]>]

On Jan 23, 2014, at 7:17 PM, Robert Ransom <[e-mail]> wrote:

> On 1/23/14, Michael Hamburg <[e-mail]> wrote:
>> On Jan 23, 2014, at 4:59 PM, Andrey Jivsov <[e-mail]> wrote:
>>> 
>>> Wouldn't http://tools.ietf.org/html/draft-jivsov-ecc-compact be another
>>> method?
>>> 
>>> Traditionally the problem was solved by carrying 1 bit and then finding a
>>> place to fit it in and defining what it means, etc. There is another way.
>>> One can adjust the private key to make the coordinate that we drop, x in
>>> this case, be the smallest of the two possibilities.
>>> 
>>> The nice feature of my proposal is that you can still also encode the bit
>>> if you wish so, as you proposed.
>> 
>> This is interesting, but I think it works better with the Edwards
>> x-coordinate instead of the Montgomery y-coordinate.  That is, it applies
>> well to Watson’s (Montgomery x, Edwards x) representation.  This is because
>> not every point you might want to transmit is a public key; it might be the
>> product of something which does not support an easy negation, such as PAKE.
>> In this case, with your proposal, implementers have to send the sign bit,
>> and we have two wire formats again.  But if the Edwards x-coordinate is
>> used, you can also fast-adjust by adding the point of order 2, which maps
>> EdX to -EdX.  (It maps EdY to -EdY and MontX to 1/MontX.)  If the protocol
>> wipes out the cofactor (almost every protocol does for security reasons),
>> then this is more likely to be acceptable than negating the point.
> 
> This makes point encoding to Montgomery-form x slightly less efficient
> and more complex -- instead of computing (for the main coordinate)
> Zinv=1/Z, then x=X*Zinv, this requires XZinv=1/(X*Z), then either
> x=X^2*XZinv or xinv=Z^2*XZinv (conditional on the sign bit of the
> Edwards-form x coordinate).  (I'm omitting the part where Zinv or
> XZinv must be batched with the inversion to compute the Edwards-form x
> coordinate and its sign bit.)
> 
> (It may still be worthwhile; I'm just pointing out exactly what effect
> this would have on implementations.  I should also point out that the
> Montgomery-form x coordinate can't distinguish the identity element
> from the point of order 2.)


You're right.

The part that counts is complexity, though, not speed.  Adding a dozen muls to a 2500-mul computation is less than half a percent.  The bigger the curve, the smaller the fraction.

Furthermore, to be a truly uniform point-encoding format (including for hashes and stuff), you'd have to modify your ladder to figure out which y is correct at the end.  And that's going to be complicated.  Or you could not do that, but then again you'd have to figure out which encoding to use where.  I should probably go work out the formulas and post them at some point...

So yeah.  Upside.  Downside.

-- Mike