Re: [Cfrg] Montgomery ladder and field operations (was: Re: Efficient side channel resistance for X25519..)

[Mike Hamburg <[e-mail]>]

Hi all,

Sorry for the slow response, I haven’t been up to date on email and haven’t checked CFRG in a while.

The formulas for recovering a y-coordinate from the Montgomery ladder without square roots can also be found in my paper:

https://eprint.iacr.org/2012/309.pdf

Appendex A.3.  If you homogenize those formulas, IIRC you will get either DA+-CB terms, or something very similar.

Regards,
— Mike Hamburg

> On Nov 10, 2019, at 8:36 AM, Rene Struik <[e-mail]> wrote:
> 
> Hi Phil:
> 
> This follows directly from the addition laws:
> 
> Let P1:=(u1, v1) and P2:=(u2, v2) be distinct affine points of the Montgomery curve M_{A,B} and let Q:=P1 + P2, where Q is not the identity element. Then Q:=(u, v), where 
> 
>     u + u1 + u2 = B*lambda^2 - A and v + v1 = lambda*(u1 - u), where lambda:=(v2 - v1)/(u2 - u1).
> 
> From this, it follows that 
> 
>     u*(u2-u1)^2=B*(v2-v1)^2-A*(u2-u1)^2 = B*(v1^2+v2^2)-2*B*v1*v2-A*(u2-u1)^2=-2B*v1*v2-u1*(u2^2+A*u2+1)-u2*(u1^2+A*u1+1).
> 
> It follows that if P=(u, v), P1=k*P=(u1, v1), and P2=(k+1)*P=(u2, v2) are distinct affine points of the Montgomery curve M_{A,B} and if v is nonzero, then the v-coordinate of P1 can be expressed in terms of the u-coordinates of P, P1, and P2, and the v-coordinate of P.
> 
> One can compute a square root of a nonzero square x in GF(q) and the inverse of a nonzero element y of GF(q) by first computing s:=1/sqrt(x*y^2)=1/(y*sqrt(x)) and then observing that t:=s*x*y=sqrt(x) and t*s=(+/-)1/y. Here, the (+/-)-sign is due to square roots being unique up to sign.    
> 
> See also [1], where Appendices C.1, C.2, and C.3 give recovery rules for Weierstrass curves, Montgomery curves, and twisted Edwards curves, and where Appendices L.1 and L.2 give details for computing square roots and inverses (including "Montgomery's trick").
> 
> I added y-coordinate recovery in version 2 of [1] after you posed a similar question on the saag mailing list (Oct 3, 2018 [2]). 
> 
> [1] https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/ <https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/>
> [2] https://mailarchive.ietf.org/arch/msg/saag/x4rKzfOB3E7RKQceiGfxAUrFfDQ <https://mailarchive.ietf.org/arch/msg/saag/x4rKzfOB3E7RKQceiGfxAUrFfDQ>
> I hope this helps. 
> 
> Rene
> 
> 
> On 11/9/2019 5:23 PM, Phillip Hallam-Baker wrote:
>> cc'd Mike himself in the hope he might take pity on us here... :-)
>> 
>> Seems to me that this should be possible. But the argument is a little more abbreviated than I can follow.
>> 
>> " This means that it is enough to compute ±1/ √ au0u1u2. This will allow us to determine av0/u0 to adjust the sign of the square root. It will allow us to check whether av2/u2 is negative, in which case we should output 1/ √ au2 instead of p u2/a. Furthermore, the input point s0 is p u0/a, and the modified Montgomery ladder state contains either √ au1 or √ au2, depending on the last bit of the ladder. This allows us to compute p u2/a or its inverse from the ladder state and 1/ √ au0u1u2 with no additional field exponents. In the actual computation, u1 and u2 are given in projective form, but this does not greatly complicate matters because the equations are nearly homogeneous."
>> 
>> My implementation of the ladder already has these values...
>> 
>>                 var x_3rt = (DA + CB);
>>                 x_3 = (x_3rt * x_3rt).Mod(P);
>> 
>>                 var z_3rt = (DA - CB);
>>                 z_3 = (x_1 * (z_3rt * z_3rt)).Mod(P);
>> 
>> The paper suggests that the sign of the y point is somehow encoded there... but how?
>> 
>> 
>> 
>> On Sat, Nov 9, 2019 at 2:07 PM Riad S. Wahby <[e-mail] <mailto:[e-mail]>> wrote:
>> Phillip Hallam-Baker <[e-mail] <mailto:[e-mail]>> wrote:
>> > I can make the code work but I am not a number theorist so if anyone could
>> > help, I would appreciate it.
>> 
>> This is more like a vague memory than a clear answer (sorry):
>> 
>> In Mike Hamburg's Decaf paper (https://ia.cr/2015/673 <https://ia.cr/2015/673>), Appx. B
>> describes a method of recovering the y-coordinate while avoiding
>> an extra square-root computation, essentially by remembering some
>> intermediate values during the ladder computation.
>> 
>> I haven't thought at all about whether a similar trick can be used
>> in the non-Decaf context, but it might be worth taking a look.
>> 
>> (As a general comment---and from your email, it appears we're in
>> agreement---masking via randomization is good, but probably it's
>> best to think of it as insurance: a masked implementation that's
>> non-constant-time is toast in the face of randomness failures.)
>> 
>> -=rsw
>> 
>> 
>> _______________________________________________
>> Cfrg mailing list
>> [e-mail] <mailto:[e-mail]>
>> https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>
> 
> -- 
> email: [e-mail] <mailto:[e-mail]> | Skype: rstruik
> cell: [phone] | US: [phone]