Re: [Cfrg] Elliptic Curves - curve form and coordinate systems (ends on March 12th)

Or maybe I’m misunderstanding.  Are you still figuring that an ECDH implementation will only use the u output from the Montgomery ladder?

In that case, the ladder doesn’t have this added complexity, but I prefer Adam’s suggestion to use a sign bit instead of sending the full v coordinate.  In that case also, ECDH wouldn’t output the sign bit, so it wouldn’t be a completely unified point format, but that’s fine.

Cheers,
— Mike

> On Mar 12, 2015, at 1:26 PM, Michael Hamburg <mike@shiftleft.org> wrote:
> 
> Hi Andrey,
> 
> Have you considered the extra complexity to compute which is the correct v at the end of the Montgomery ladder?  If you want a unified point format that every operation uses, you need a way to compute the sign of v.
> 
> I get 4 u0 v1 v2 = (1 - u1 u2 - u0 u2 + u0 u1) (1 - u1 u2 + u0 u2 - u0 u1) and symmetrically.  This doesn’t require a square root if you know the input’s v coordinate, but it does increase complexity.  At some point you might as well go full decaf, particularly if there’s no trivial patch to existing curve25519() functions.
> 
> Cheers,
> — Mike
> 
>> On Mar 12, 2015, at 1:04 PM, Andrey Jivsov <crypto@brainhub.org> wrote:
>> 
>> I apologize (need more coffee). I meant to write v = SQRT(u^3 + 486662*u^2 + u). The SQRT can be calculated (for almost free) during X/Z calculation by the sender at the end of scalarmult, because the sender must do 1/Z, but there is no apparent way to avoid SQRT for the receiver (unless the received doesn't need v and only works on u). The sign is embedded in v (and v can be adjusted  p-v as needed for signatures; ECDH doesn't care).
>> 
>> On 03/12/2015 12:53 PM, Adam Langley wrote:
>>> On Thu, Mar 12, 2015 at 12:19 PM, Andrey Jivsov <crypto@brainhub.org> wrote:
>>>> I propose the Montgomery curve representation (u, v), which can be used for
>>>> signatures on the same curve.
>>>> 
>>>> "u" is identical to the sec 9 of
>>>> https://tools.ietf.org/html/draft-agl-cfrgcurve-00.
>>>> "v" is calculated (at virtually no additional computational cost) as v = u^3
>>>> + 486662*u^2 + u
>>> I'm going to display my ignorance here, but if "v" can be calculated
>>> from just u with very little cost, why send it at all? The receiver
>>> could equally calculate it if useful, no?
>>> 
>>>> * The format is friendly for crypto algorithms that need to add points (as
>>>> opposed to ECDH only)
>>> Wouldn't they need to know an extra bit? Given a point on the
>>> Montgomery curve, (u,v), the "v" value is v^2, right? Doesn't that
>>> discard the sign of v?
>>> 
>>> 
>>> Cheers
>>> 
>>> AGL
>>> 
>> 
>> _______________________________________________
>> Cfrg mailing list
>> Cfrg@irtf.org
>> http://www.irtf.org/mailman/listinfo/cfrg
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg