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

[Robert Ransom <[e-mail]>]

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.)


Robert Ransom