Montgomery curve

In mathematics, the Montgomery curve is a form of elliptic curve introduced by Peter L. Montgomery in 1987,[1] different from the usual Weierstrass form. It is used for certain computations, and in particular in different cryptography applications.

Definition

A Montgomery curve of equation 1 4 y 2 = x 3 + 5 2 x 2 + x {\textstyle {\frac {1}{4}}y^{2}=x^{3}+{\frac {5}{2}}x^{2}+x}

A Montgomery curve over a field K is defined by the equation

M A , B : B y 2 = x 3 + A x 2 + x {\displaystyle M_{A,B}:By^{2}=x^{3}+Ax^{2}+x}

for certain A, BK and with B(A2 − 4) ≠ 0.

Generally this curve is considered over a finite field K (for example, over a finite field of q elements, K = Fq) with characteristic different from 2 and with A ≠ ±2 and B ≠ 0, but they are also considered over the rationals with the same restrictions for A and B.

Montgomery arithmetic

It is possible to do some "operations" between the points of an elliptic curve: "adding" two points P , Q {\displaystyle P,Q} consists of finding a third one R {\displaystyle R} such that R = P + Q {\displaystyle R=P+Q} ; "doubling" a point consists of computing [ 2 ] P = P + P {\displaystyle [2]P=P+P} (For more information about operations see The group law) and below.

A point P = ( x , y ) {\displaystyle P=(x,y)} on the elliptic curve in the Montgomery form B y 2 = x 3 + A x 2 + x {\displaystyle By^{2}=x^{3}+Ax^{2}+x} can be represented in Montgomery coordinates P = ( X : Z ) {\displaystyle P=(X:Z)} , where P = ( X : Z ) {\displaystyle P=(X:Z)} are projective coordinates and x = X / Z {\displaystyle x=X/Z} for Z 0 {\displaystyle Z\neq 0} .

Notice that this kind of representation for a point loses information: indeed, in this case, there is no distinction between the affine points ( x , y ) {\displaystyle (x,y)} and ( x , y ) {\displaystyle (x,-y)} because they are both given by the point ( X : Z ) {\displaystyle (X:Z)} . However, with this representation it is possible to obtain multiples of points, that is, given P = ( X : Z ) {\displaystyle P=(X:Z)} , to compute [ n ] P = ( X n : Z n ) {\displaystyle [n]P=(X_{n}:Z_{n})} .

Now, considering the two points P n = [ n ] P = ( X n : Z n ) {\displaystyle P_{n}=[n]P=(X_{n}:Z_{n})} and P m = [ m ] P = ( X m : Z m ) {\displaystyle P_{m}=[m]P=(X_{m}:Z_{m})} : their sum is given by the point P m + n = P m + P n = ( X m + n : Z m + n ) {\displaystyle P_{m+n}=P_{m}+P_{n}=(X_{m+n}:Z_{m+n})} whose coordinates are:

X m + n = Z m n ( ( X m Z m ) ( X n + Z n ) + ( X m + Z m ) ( X n Z n ) ) 2 {\displaystyle X_{m+n}=Z_{m-n}((X_{m}-Z_{m})(X_{n}+Z_{n})+(X_{m}+Z_{m})(X_{n}-Z_{n}))^{2}}
Z m + n = X m n ( ( X m Z m ) ( X n + Z n ) ( X m + Z m ) ( X n Z n ) ) 2 {\displaystyle Z_{m+n}=X_{m-n}((X_{m}-Z_{m})(X_{n}+Z_{n})-(X_{m}+Z_{m})(X_{n}-Z_{n}))^{2}}

If m = n {\displaystyle m=n} , then the operation becomes a "doubling"; the coordinates of [ 2 ] P n = P n + P n = P 2 n = ( X 2 n : Z 2 n ) {\displaystyle [2]P_{n}=P_{n}+P_{n}=P_{2n}=(X_{2n}:Z_{2n})} are given by the following equations:

4 X n Z n = ( X n + Z n ) 2 ( X n Z n ) 2 {\displaystyle 4X_{n}Z_{n}=(X_{n}+Z_{n})^{2}-(X_{n}-Z_{n})^{2}}
X 2 n = ( X n + Z n ) 2 ( X n Z n ) 2 {\displaystyle X_{2n}=(X_{n}+Z_{n})^{2}(X_{n}-Z_{n})^{2}}
Z 2 n = ( 4 X n Z n ) ( ( X n Z n ) 2 + ( ( A + 2 ) / 4 ) ( 4 X n Z n ) ) {\displaystyle Z_{2n}=(4X_{n}Z_{n})((X_{n}-Z_{n})^{2}+((A+2)/4)(4X_{n}Z_{n}))}

The first operation considered above (addition) has a time-cost of 3M+2S, where M denotes the multiplication between two general elements of the field on which the elliptic curve is defined, while S denotes squaring of a general element of the field.

The second operation (doubling) has a time-cost of 2M + 2S + 1D, where D denotes the multiplication of a general element by a constant; notice that the constant is ( A + 2 ) / 4 {\displaystyle (A+2)/4} , so A {\displaystyle A} can be chosen in order to have a small D.

Algorithm and example

The following algorithm represents a doubling of a point P 1 = ( X 1 : Z 1 ) {\displaystyle P_{1}=(X_{1}:Z_{1})} on an elliptic curve in the Montgomery form.

It is assumed that Z 1 = 1 {\displaystyle Z_{1}=1} . The cost of this implementation is 1M + 2S + 1*A + 3add + 1*4. Here M denotes the multiplications required, S indicates the squarings, and a refers to the multiplication by A.

X X 1 = X 1 2 {\displaystyle XX_{1}=X_{1}^{2}\,}
X 2 = ( X X 1 1 ) 2 {\displaystyle X_{2}=(XX_{1}-1)^{2}\,}
Z 2 = 4 X 1 ( X X 1 + a X 1 + 1 ) {\displaystyle Z_{2}=4X_{1}(XX_{1}+aX_{1}+1)\,}

Example

Let P 1 = ( 2 , 3 ) {\displaystyle P_{1}=(2,{\sqrt {3}})} be a point on the curve 2 y 2 = x 3 x 2 + x {\displaystyle 2y^{2}=x^{3}-x^{2}+x} . In coordinates ( X 1 : Z 1 ) {\displaystyle (X_{1}:Z_{1})} , with x 1 = X 1 / Z 1 {\displaystyle x_{1}=X_{1}/Z_{1}} , P 1 = ( 2 : 1 ) {\displaystyle P_{1}=(2:1)} .

Then:

X X 1 = X 1 2 = 4 {\displaystyle XX_{1}=X_{1}^{2}=4\,}
X 2 = ( X X 1 1 ) 2 = 9 {\displaystyle X_{2}=(XX_{1}-1)^{2}=9\,}
Z 2 = 4 X 1 ( X X 1 + A X 1 + 1 ) = 24 {\displaystyle Z_{2}=4X_{1}(XX_{1}+AX_{1}+1)=24\,}

The result is the point P 2 = ( X 2 : Z 2 ) = ( 9 : 24 ) {\displaystyle P_{2}=(X_{2}:Z_{2})=(9:24)} such that P 2 = 2 P 1 {\displaystyle P_{2}=2P_{1}} .

Addition

Given two points P 1 = ( x 1 , y 1 ) {\displaystyle P_{1}=(x_{1},y_{1})} , P 2 = ( x 2 , y 2 ) {\displaystyle P_{2}=(x_{2},y_{2})} on the Montgomery curve M A , B {\displaystyle M_{A,B}} in affine coordinates, the point P 3 = P 1 + P 2 {\displaystyle P_{3}=P_{1}+P_{2}} represents, geometrically the third point of intersection between M A , B {\displaystyle M_{A,B}} and the line passing through P 1 {\displaystyle P_{1}} and P 2 {\displaystyle P_{2}} . It is possible to find the coordinates ( x 3 , y 3 ) {\displaystyle (x_{3},y_{3})} of P 3 {\displaystyle P_{3}} , in the following way:

1) consider a generic line   y = l x + m {\displaystyle ~y=lx+m} in the affine plane and let it pass through P 1 {\displaystyle P_{1}} and P 2 {\displaystyle P_{2}} (impose the condition), in this way, one obtains l = y 2 y 1 x 2 x 1 {\displaystyle l={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}} and m = y 1 ( y 2 y 1 x 2 x 1 ) x 1 {\displaystyle m=y_{1}-\left({\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}\right)x_{1}} ;

2) intersect the line with the curve M A , B {\displaystyle M_{A,B}} , substituting the   y {\displaystyle ~y} variable in the curve equation with   y = l x + m {\displaystyle ~y=lx+m} ; the following equation of third degree is obtained:

x 3 + ( A B l 2 ) x 2 + ( 1 2 B l m ) x B m 2 = 0. {\displaystyle x^{3}+(A-Bl^{2})x^{2}+(1-2Blm)x-Bm^{2}=0.}

As it has been observed before, this equation has three solutions that correspond to the   x {\displaystyle ~x} coordinates of P 1 {\displaystyle P_{1}} , P 2 {\displaystyle P_{2}} and P 3 {\displaystyle P_{3}} . In particular this equation can be re-written as:

( x x 1 ) ( x x 2 ) ( x x 3 ) = 0 {\displaystyle (x-x_{1})(x-x_{2})(x-x_{3})=0}

3) Comparing the coefficients of the two identical equations given above, in particular the coefficients of the terms of second degree, one gets:

x 1 x 2 x 3 = A B l 2 {\displaystyle -x_{1}-x_{2}-x_{3}=A-Bl^{2}} .

So, x 3 {\displaystyle x_{3}} can be written in terms of x 1 {\displaystyle x_{1}} , y 1 {\displaystyle y_{1}} , x 2 {\displaystyle x_{2}} , y 2 {\displaystyle y_{2}} , as:

x 3 = B ( y 2 y 1 x 2 x 1 ) 2 A x 1 x 2 . {\displaystyle x_{3}=B\left({\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}\right)^{2}-A-x_{1}-x_{2}.}

4) To find the   y {\displaystyle ~y} coordinate of the point P 3 {\displaystyle P_{3}} it is sufficient to substitute the value x 3 {\displaystyle x_{3}} in the line   y = l x + m {\displaystyle ~y=lx+m} . Notice that this will not give the point P 3 {\displaystyle P_{3}} directly. Indeed, with this method one find the coordinates of the point   R {\displaystyle ~R} such that R + P 1 + P 2 = P {\displaystyle R+P_{1}+P_{2}=P_{\infty }} , but if one needs the resulting point of the sum between P 1 {\displaystyle P_{1}} and P 2 {\displaystyle P_{2}} , then it is necessary to observe that: R + P 1 + P 2 = P {\displaystyle R+P_{1}+P_{2}=P_{\infty }} if and only if R = P 1 + P 2 {\displaystyle -R=P_{1}+P_{2}} . So, given the point   R {\displaystyle ~R} , it is necessary to find   R {\displaystyle ~-R} , but this can be done easily by changing the sign to the   y {\displaystyle ~y} coordinate of   R {\displaystyle ~R} . In other words, it will be necessary to change the sign of the   y {\displaystyle ~y} coordinate obtained by substituting the value x 3 {\displaystyle x_{3}} in the equation of the line.

Resuming, the coordinates of the point P 3 = ( x 3 , y 3 ) {\displaystyle P_{3}=(x_{3},y_{3})} , P 3 = P 1 + P 2 {\displaystyle P_{3}=P_{1}+P_{2}} are:

x 3 = B ( y 2 y 1 ) 2 ( x 2 x 1 ) 2 A x 1 x 2 {\displaystyle x_{3}={\frac {B(y_{2}-y_{1})^{2}}{(x_{2}-x_{1})^{2}}}-A-x_{1}-x_{2}}
y 3 = ( 2 x 1 + x 2 + A ) ( y 2 y 1 ) x 2 x 1 B ( y 2 y 1 ) 3 ( x 2 x 1 ) 3 y 1 {\displaystyle y_{3}={\frac {(2x_{1}+x_{2}+A)(y_{2}-y_{1})}{x_{2}-x_{1}}}-{\frac {B(y_{2}-y_{1})^{3}}{(x_{2}-x_{1})^{3}}}-y_{1}}

Doubling

Given a point P 1 {\displaystyle P_{1}} on the Montgomery curve M A , B {\displaystyle M_{A,B}} , the point [ 2 ] P 1 {\displaystyle [2]P_{1}} represents geometrically the third point of intersection between the curve and the line tangent to P 1 {\displaystyle P_{1}} ; so, to find the coordinates of the point P 3 = 2 P 1 {\displaystyle P_{3}=2P_{1}} it is sufficient to follow the same method given in the addition formula; however, in this case, the line y = lx + m has to be tangent to the curve at P 1 {\displaystyle P_{1}} , so, if M A , B : f ( x , y ) = 0 {\displaystyle M_{A,B}:f(x,y)=0} with

f ( x , y ) = x 3 + A x 2 + x B y 2 , {\displaystyle f(x,y)=x^{3}+Ax^{2}+x-By^{2},}

then the value of l, which represents the slope of the line, is given by:

l = f x / f y {\displaystyle l=-\left.{\frac {\partial f}{\partial x}}\right/{\frac {\partial f}{\partial y}}}

by the implicit function theorem.

So l = 3 x 1 2 + 2 A x 1 + 1 2 B y 1 {\displaystyle l={\frac {3x_{1}^{2}+2Ax_{1}+1}{2By_{1}}}} and the coordinates of the point P 3 {\displaystyle P_{3}} , P 3 = 2 P 1 {\displaystyle P_{3}=2P_{1}} are:

x 3 = B l 2 A x 1 x 1 = B ( 3 x 1 2 + 2 A x 1 + 1 ) 2 ( 2 B y 1 ) 2 A x 1 x 1 y 3 = ( 2 x 1 + x 1 + A ) l B l 3 y 1 = ( 2 x 1 + x 1 + A ) ( 3 x 1 2 + 2 A x 1 + 1 ) 2 B y 1 B ( 3 x 1 2 + 2 A x 1 + 1 ) 3 ( 2 B y 1 ) 3 y 1 . {\displaystyle {\begin{aligned}x_{3}&=Bl^{2}-A-x_{1}-x_{1}={\frac {B(3x_{1}^{2}+2Ax_{1}+1)^{2}}{(2By_{1})^{2}}}-A-x_{1}-x_{1}\\y_{3}&=(2x_{1}+x_{1}+A)l-Bl^{3}-y_{1}\\&={\frac {(2x_{1}+x_{1}+A)(3{x_{1}}^{2}+2Ax_{1}+1)}{2By_{1}}}-{\frac {B(3{x_{1}}^{2}+2Ax_{1}+1)^{3}}{(2By_{1})^{3}}}-y_{1}.\end{aligned}}}

Equivalence with twisted Edwards curves

Let K {\displaystyle K} be a field with characteristic different from 2.

Let M A , B {\displaystyle M_{A,B}} be an elliptic curve in the Montgomery form:

M A , B : B v 2 = u 3 + A u 2 + u {\displaystyle M_{A,B}:Bv^{2}=u^{3}+Au^{2}+u}

with A K { 2 , 2 } {\displaystyle A\in K\smallsetminus \{-2,2\}} , B K { 0 } {\displaystyle B\in K\smallsetminus \{0\}}

and let E a , d {\displaystyle E_{a,d}} be an elliptic curve in the twisted Edwards form:

E a , d   :   a x 2 + y 2 = 1 + d x 2 y 2 , {\displaystyle E_{a,d}\ :\ ax^{2}+y^{2}=1+dx^{2}y^{2},\,}

with a , d K { 0 } , a d . {\displaystyle a,d\in K\smallsetminus \{0\},\quad a\neq d.}

The following theorem shows the birational equivalence between Montgomery curves and twisted Edwards curve:[2]

Theorem (i) Every twisted Edwards curve is birationally equivalent to a Montgomery curve over K {\displaystyle K} . In particular, the twisted Edwards curve E a , d {\displaystyle E_{a,d}} is birationally equivalent to the Montgomery curve M A , B {\displaystyle M_{A,B}} where A = 2 ( a + d ) a d {\displaystyle A={\frac {2(a+d)}{a-d}}} , and B = 4 a d {\displaystyle B={\frac {4}{a-d}}} .

The map:

ψ : E a , d M A , B {\displaystyle \psi \,:\,E_{a,d}\rightarrow M_{A,B}}
( x , y ) ( u , v ) = ( 1 + y 1 y , 1 + y ( 1 y ) x ) {\displaystyle (x,y)\mapsto (u,v)=\left({\frac {1+y}{1-y}},{\frac {1+y}{(1-y)x}}\right)}

is a birational equivalence from E a , d {\displaystyle E_{a,d}} to M A , B {\displaystyle M_{A,B}} , with inverse:

ψ 1 {\displaystyle \psi ^{-1}} : M A , B E a , d {\displaystyle M_{A,B}\rightarrow E_{a,d}}
( u , v ) ( x , y ) = ( u v , u 1 u + 1 ) , a = A + 2 B , d = A 2 B {\displaystyle (u,v)\mapsto (x,y)=\left({\frac {u}{v}},{\frac {u-1}{u+1}}\right),a={\frac {A+2}{B}},d={\frac {A-2}{B}}}

Notice that this equivalence between the two curves is not valid everywhere: indeed the map ψ {\displaystyle \psi } is not defined at the points v = 0 {\displaystyle v=0} or u + 1 = 0 {\displaystyle u+1=0} of the M A , B {\displaystyle M_{A,B}} .

Equivalence with Weierstrass curves

Any elliptic curve can be written in Weierstrass form. In particular, the elliptic curve in the Montgomery form

M A , B {\displaystyle M_{A,B}} : B y 2 = x 3 + A x 2 + x , {\displaystyle By^{2}=x^{3}+Ax^{2}+x,}

can be transformed in the following way: divide each term of the equation for M A , B {\displaystyle M_{A,B}} by B 3 {\displaystyle B^{3}} , and substitute the variables x and y, with u = x B {\displaystyle u={\frac {x}{B}}} and v = y B {\displaystyle v={\frac {y}{B}}} respectively, to get the equation

v 2 = u 3 + A B u 2 + 1 B 2 u . {\displaystyle v^{2}=u^{3}+{\frac {A}{B}}u^{2}+{\frac {1}{B^{2}}}u.}

To obtain a short Weierstrass form from here, it is sufficient to replace u with the variable t A 3 B {\displaystyle t-{\frac {A}{3B}}} :

v 2 = ( t A 3 B ) 3 + A B ( t A 3 B ) 2 + 1 B 2 ( t A 3 B ) ; {\displaystyle v^{2}=\left(t-{\frac {A}{3B}}\right)^{3}+{\frac {A}{B}}\left(t-{\frac {A}{3B}}\right)^{2}+{\frac {1}{B^{2}}}\left(t-{\frac {A}{3B}}\right);}

finally, this gives the equation:

v 2 = t 3 + ( 3 A 2 3 B 2 ) t + ( 2 A 3 9 A 27 B 3 ) . {\displaystyle v^{2}=t^{3}+\left({\frac {3-A^{2}}{3B^{2}}}\right)t+\left({\frac {2A^{3}-9A}{27B^{3}}}\right).}

Hence the mapping is given as

ψ {\displaystyle \psi } : M A , B E a , b {\displaystyle M_{A,B}\rightarrow E_{a,b}}
( x , y ) ( t , v ) = ( x B + A 3 B , y B ) , a = 3 A 2 3 B 2 , b = 2 A 3 9 A 27 B 3 {\displaystyle (x,y)\mapsto (t,v)=\left({\frac {x}{B}}+{\frac {A}{3B}},{\frac {y}{B}}\right),a={\frac {3-A^{2}}{3B^{2}}},b={\frac {2A^{3}-9A}{27B^{3}}}}

In contrast, an elliptic curve over base field F {\displaystyle \mathbb {F} } in Weierstrass form

E a , b {\displaystyle E_{a,b}} : v 2 = t 3 + a t + b {\displaystyle v^{2}=t^{3}+at+b}

can be converted to Montgomery form if and only if E a , b {\displaystyle E_{a,b}} has order divisible by four and satisfies the following conditions:[3]

  1. z 3 + a z + b = 0 {\displaystyle z^{3}+az+b=0} has at least one root α F {\displaystyle \alpha \in \mathbb {F} } ; and
  2. 3 α 2 + a {\displaystyle 3\alpha ^{2}+a} is a quadratic residue in F {\displaystyle \mathbb {F} } .

When these conditions are satisfied, then for s = ( 3 α 2 + a ) 1 {\displaystyle s=({\sqrt {3\alpha ^{2}+a}})^{-1}} we have the mapping

ψ 1 {\displaystyle \psi ^{-1}} : E a , b M A , B {\displaystyle E_{a,b}\rightarrow M_{A,B}}
( t , v ) ( x , y ) = ( s ( t α ) , s v ) , A = 3 α s , B = s {\displaystyle (t,v)\mapsto (x,y)=\left(s(t-\alpha ),sv\right),A=3\alpha s,B=s} .

See also

Notes

  1. ^ Peter L. Montgomery (1987). "Speeding the Pollard and Elliptic Curve Methods of Factorization". Mathematics of Computation. 48 (177): 243–264. doi:10.2307/2007888. JSTOR 2007888.
  2. ^ Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange and Christiane Peters (2008). "Twisted Edwards Curves". Progress in Cryptology – AFRICACRYPT 2008. Lecture Notes in Computer Science. Vol. 5023. Springer-Verlag Berlin Heidelberg. pp. 389–405. doi:10.1007/978-3-540-68164-9_26. ISBN 978-3-540-68159-5.{{cite book}}: CS1 maint: multiple names: authors list (link)
  3. ^ Katsuyuki Okeya, Hiroyuki Kurumatani, and Kouichi Sakurai (2000). Elliptic Curves with the Montgomery-Form and Their Cryptographic Applications. Public Key Cryptography (PKC2000). doi:10.1007/978-3-540-46588-1_17.{{cite conference}}: CS1 maint: multiple names: authors list (link)

References

  • Peter L. Montgomery (1987). "Speeding the Pollard and Elliptic Curve Methods of Factorization". Mathematics of Computation. 48 (177): 243–264. doi:10.2307/2007888. JSTOR 2007888.
  • Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange and Christiane Peters (2008). "Twisted Edwards Curves". Progress in Cryptology – AFRICACRYPT 2008. Lecture Notes in Computer Science. Vol. 5023. Springer-Verlag Berlin Heidelberg. pp. 389–405. doi:10.1007/978-3-540-68164-9_26. ISBN 978-3-540-68159-5.{{cite book}}: CS1 maint: multiple names: authors list (link)
  • Wouter Castryck; Steven Galbraith; Reza Rezaeian Farashahi (2008). "Efficient Arithmetic on Elliptic Curves using a Mixed Edwards-Montgomery Representation" (PDF). {{cite journal}}: Cite journal requires |journal= (help)

External links

  • Genus-1 curves over large-characteristic fields