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

[Rene Struik <[e-mail]>]

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/

[2] 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), 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]
> https://www.irtf.org/mailman/listinfo/cfrg


-- 
email: [e-mail] | Skype: rstruik
cell: [phone] | US: [phone]