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

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