Montgomery curve explained

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 over a field is defined by the equation

M _{A,B} : By ^{2} = x ^{3} + Ax ^{2} + x

for certain and with .

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

Montgomery arithmetic

It is possible to do some "operations" between the points of an elliptic curve: "adding" two points

P, Q consists of finding a third one R such that R = P + Q ; "doubling" a point consists of computing [ 2 ]P = P + P (For more information about operations see The group law) and below.

A point

P = (x,y) on the elliptic curve in the Montgomery form By ^{2} = x ^{3} + Ax ^{2} + x can be represented in Montgomery coordinates P = (X:Z) , where P = (X:Z) are projective coordinates and x = X/Z for Z\ne 0 .(x,y) and (x, - y) because they are both given by the point (X:Z) . However, with this representation it is possible to obtain multiples of points, that is, given P = (X:Z) , to compute [n]P = (X _{n:Z} _{n)} .

Now, considering the two points

P _{n=[n]P=(X} _{n:Z} _{n)} and 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} ) whose coordinates are:X _{m+n} = Z _{m-n} ((X _{m-Z} _{m)(X} _{n+Z} _{n)+(X} _{m+Z} _{m)(X} _{n-Z} ^{2} ^{n))} Z _{m+n} = X _{m-n} ((X _{m-Z} _{m)(X} _{n+Z} _{n)-(X} _{m+Z} _{m)(X} _{n-Z} ^{2} ^{n))}

If

m = n , then the operation becomes a "doubling"; the coordinates of [ 2 ]P _{n=P} _{n+P} _{n=P} _{2n} = (X _{2n} :Z _{2n} ) are given by the following equations:4 X _{nZ} _{n} = (X _{n+Z} ^{2} ^{n)} - (X _{n-Z} ^{2} ^{n)} X _{2n} = (X _{n+Z} ^{2 (X} ^{n - Z} ^{2} ^{n)} Z _{2n} = ( 4 X _{nZ} _{n)((X} _{n-Z} ^{2+ ((A +2 )/ 4 )( 4 X} ^{nZ} _{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 , so 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)} on an elliptic curve in the Montgomery form.

It is assumed that

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.XX _{1} = X ^{2} _{1} X _{2} = (XX ^{2} _{1-1 )} Z _{2} = 4 X _{1(XX} _{1+aX} _{1+1)}

Example

Let

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

Then:

XX _{1} = X ^{2} _{1} = 4 X _{2} = (XX ^{2} _{1-1 )} = 9 Z _{2} = 4 X _{1(XX} _{1+AX} _{1+1)} = 24

The result is the point

P _{2=(X} _{2:Z} _{2)=(9:24)} such that P _{2=2P} _{1} .

Addition

Given two points

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

1) consider a generic line

~y = lx + m in the affine plane and let it pass through P _{1} and P _{2} (impose the condition), in this way, one obtains l = (y _{2-y} _{1})/(x _{2-x} _{1}) and m = y _{1- \left( (y _{2-y} _{1})/(x _{2-x} _{1})} \right)x _{1} ;

2) intersect the line with the curve

M _{A,B} , substituting the ~y variable in the curve equation with ~y = lx + m ; the following equation of third degree is obtained: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 coordinates of P _{1} , P _{2} and P _{3} . In particular this equation can be re-written as:(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} ^{2} ^{3= A - Bl} .

So,

x _{3} can be written in terms of x _{1} , y _{1} , x _{2} , y _{2} , as:x _{3} = B\left( (y _{2-y} _{1})/(x _{2-x} _{1}) \right) ^{2- A - x} _{1- x} _{2.}

4) To find the

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

Resuming, the coordinates of the point

P _{3=(x} _{3,y} _{3)} , P _{3=P} _{1+P} _{2} are:x _{3} = (B(y _{2- y} ^{2} ^{1 )})/((x _{2- x} ^{2} ^{1 )}) - 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} ^{3} ^{1 )})/((x _{2- x} ^{3} ^{1 )}) - y _{1}

Doubling

Given a point

P _{1} on the Montgomery curve M _{A,B} , the point [ 2 ]P _{1} represents geometrically the third point of intersection between the curve and the line tangent to P _{1} ; so, to find the coordinates of the point 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} , so, if M _{A,B} : f(x,y) =0 withf(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 =- \left. (\partial f)/(\right/ \partial x) (\partial f)/(\partial y)

by the implicit function theorem.

So

l = (3 x ^{2} _{1} + 2 Ax _{1} + 1)/(2 By _{1}) and the coordinates of the point P _{3} , P _{3=2P} _{1} are:\begin{align} x _{3} & = Bl ^{2- A - x} _{1- x} _{1} = (B( 3 x ^{2} _{1+1 )})/(( 2 By ^{2} _{1 )}) - A - x _{1-x} _{1} \\ y _{3} & = ( 2 x _{1+x} ^{3- y} ^{1} \\ & = (( 2 x _{1+x} _{1+A)(3{x} _{1})/(^{2+2Ax}) _{1+1)}{2By} ^{1 } - (B( 3 {x _{1})/(^{2+2Ax})} ^{3 } - y} ^{1 . \end{align}}

Equivalence with twisted Edwards curves

Let

K be a field with characteristic different from 2.

Let

M _{A,B} be an elliptic curve in the Montgomery form:M _{A,B} : Bv ^{2} = u ^{3} + Au ^{2} + u

with

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

and let

E _{a,d} be an elliptic curve in the twisted Edwards form:E _{a,d} : ax ^{2} + y ^{2} = 1 + dx ^{2y} ^{2,}

with

a,d\in K\smallsetminus\{ 0 \}, a ≠ 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 .In particular, the twisted Edwards curve E _{a,d} is birationally equivalent to the Montgomery curve M _{A,B} where A = (2 (a + d))/(a - d) , and B = (4)/(a - d) .

The map:

\psi:E _{a,d} → M _{A,B} (x,y) \mapsto (u,v) = \left( (1+ y)/(, 1- y) (1+ y)/(( 1- y)x) \right)

is a birational equivalence from

E _{a,d} to M _{A,B} , with inverse:\psi ^{-1} : M _{A,B} → E _{a,d} (u,v) \mapsto (x,y) = \left( (u)/(, v) (u -1)/(\right), a = u +1) (A +2)/(B) , d = (A -2)/(B)

Notice that this equivalence between the two curves is not valid everywhere: indeed the map

\psi is not defined at the points v = 0 or u + 1 = 0 of the 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} : By ^{2} = x ^{3} + Ax ^{2} + x,

can be transformed in the following way:divide each term of the equation for

M _{A,B} by B ^{3} , and substitute the variables x and y, with u = (x)/(B) and v = (y)/(B) respectively, to get the equationv ^{2} = u ^{3} + (A)/(B) u ^{2} + (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) :v ^{2} = \left(t - (A)/(3 B) \right) ^{3} + (A)/(\left(t - B) (A)/(3 B) \right) ^{2} + (1)/(\left(t - B ^{2}) (A)/(3 B) \right);

finally, this gives the equation:

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

Hence the mapping is given as

\psi : M _{A,B} → E _{a,b} (x,y) \mapsto (t,v) = \left( (x)/(B) + (A)/(3 B) , (y)/(\right), a = B) (3- A ^{2})/(3 B ^{2}) , b = (2 A ^{3-9A})/(27 B ^{3})

In contrast, an elliptic curve over base field

F in Weierstrass formE _{a,b} : v ^{2} = t ^{3} + at + b

can be converted to Montgomery form if and only if

E _{a,b} has order divisible by four and satisfies the following conditions:^[3] z ^{3} + az + b = 0 has at least one root \alpha \in F ; and3 \alpha ^{2} + a is a quadratic residue in F .

When these conditions are satisfied, then for

s = (\sqrt{ 3 \alpha ^{2} + a}) ^{-1} we have the mapping\psi ^{-1} : E _{a,b} → M _{A,B} (t,v) \mapsto (x,y) = \left(s (t - \alpha), s v\right), A = 3 \alpha s, B = s .

See also

• Curve25519
• Table of costs of operations in elliptic curves – information about the running-time required in a specific case

References

• . 1987 . Speeding the Pollard and Elliptic Curve Methods of Factorization . Mathematics of Computation . 48 . 177 . 243–264 . 2007888 . 10.2307/2007888 . free .
• Book: Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange and Christiane Peters . Progress in Cryptology – AFRICACRYPT 2008 . 5023 . 389–405 . 2008 . Springer-Verlag Berlin Heidelberg . 978-3-540-68159-5 . 10.1007/978-3-540-68164-9_26 . Lecture Notes in Computer Science . Twisted Edwards Curves . http://eprint.iacr.org/2008/013 .
• Wouter Castryck . Steven Galbraith . Reza Rezaeian Farashahi . 2008 . Efficient Arithmetic on Elliptic Curves using a Mixed Edwards-Montgomery Representation .

External links

• Genus-1 curves over large-characteristic fields

Notes and References

1. . 1987 . Speeding the Pollard and Elliptic Curve Methods of Factorization . Mathematics of Computation . 48 . 177 . 243–264 . 2007888 . 10.2307/2007888 . free .
2. Book: Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange and Christiane Peters . Progress in Cryptology – AFRICACRYPT 2008 . 5023 . 389–405 . 2008 . Springer-Verlag Berlin Heidelberg . 978-3-540-68159-5 . 10.1007/978-3-540-68164-9_26 . Lecture Notes in Computer Science . Twisted Edwards Curves . http://eprint.iacr.org/2008/013 .
3. Katsuyuki Okeya, Hiroyuki Kurumatani, and Kouichi Sakurai. 2000. Elliptic Curves with the Montgomery-Form and Their Cryptographic Applications. Public Key Cryptography (PKC2000). 10.1007/978-3-540-46588-1_17. free.