Montgomery curve

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

Definition[edit]

A Montgomery curve of equation 3y^2=x^3+7x^2+x

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

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

for certain A,B \in K and with B(A^2-4)\neq 0.

Generally this curve is considered over a finite field K (for example over a finite field of q elements, K=\mathbb{F}_q) with characteristic different from 2 and with A\in K\backslash\{-2,2\}, B \in K\backslash\{0\} ; but they are also considered over the rationals with the same restrictions for A and B.

Montgomery arithmetic[edit]

It is possible to do some "operations" between the points of an elliptic curve: "adding" two points P, Q consists on finding a third one R such that R=P+Q; "doubling" a point consists on 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.

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) 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_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

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:


4X_nZ_n = (X_n+Z_n)^2 - (X_n-Z_n)^2


X_{2n} = (X_n+Z_n)^2(X_n-Z_n)^2


Z_{2n} = (4X_nZ_n)((X_n-Z_n)^2+((A+2)/4)(4X_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[edit]

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_1^2 \,
X_3 = (XX_1-1)^2 \,
Z_3 = 4X_1(XX_1+aX_1+1) \,

Example[edit]

Let P_1=(2,\sqrt{3}) be a point on the curve 2y^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_1^2 = 4 \,
X_3 = (XX_1-1)^2 = 9 \,
Z_3 = 4X_1(XX_1+aX_1+1) = 24 \,

The result is the point P_3=(X_3:Z_3)=(9:24) such that P_3=2P_1.

Addition[edit]

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=\frac{y_2-y_1}{x_2-x_1} and m=y_1-(\frac{y_2-y_1}{x_2-x_1})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_3=A-Bl^2.

So, x_3 can be written in terms of x_1, y_1, x_2, y_2, as:

x_3 = B(\frac{y_2-y_1}{x_2-x_1})^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 = \frac{B(y_2-y_1)^2}{(x_2-x_1)^2}-A-x_1-x_2=\frac{B(x_2y_1-x_1y_2)^2}{x_1x_2(x_2-x_1)^2}

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[edit]

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 with

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=-\frac{\frac{\partial f}{\partial x}}{\frac{\partial f}{\partial y }}

by the implicit function theorem.

So l = \frac{3x_1^2 + 2Ax_1 + 1}{2By_1} and the coordinates of the point P_3, P_3=2P_1 are:

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=\frac{(x_1^2-1)^2}{4By_1^2}=\frac{(x_1^2-1)^2}{4x_1(x_1^2+Ax_1+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.

Equivalence with twisted Edwards curves[edit]

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\backslash\{-2,2\}, B \in K\backslash\{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\backslash\{0\}, a\neq d.

The following theorem shows the birational equivalence between Montgomery curves and twisted Edwards curves:[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 = \frac{2(a+d)}{a-d}, and B = \frac{4}{a-d}.

The map:

\psi\,:\,E_{a,d} \rightarrow M_{A,B}

(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} to M_{A,B}, with inverse:

\psi^{-1}: M_{A,B} \rightarrow E_{a,d}

(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 \psi is not defined at the points v = 0 or u + 1 = 0 of the M_{A,B}.

Equivalence with Weierstrass curves[edit]

Any elliptic curve can be written in Weierstrass form.

So, the elliptic curve in the Montogmery 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=\frac{x}{B} and v=\frac{y}{B} respectively, to get the equation

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-\frac{A}{3B}:

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 + \left(\frac{3-A^2}{3B^2}\right)t + \left(\frac{2A^3-9A}{27B^3}\right).

See also[edit]

Notes[edit]

  1. ^ Peter L. Montgomery (1987). "Speeding the Pollard and Elliptic Curve Methods of Factorization". Mathematics of Computation 48 (177): 243–264. JSTOR 2007888. 
  2. ^ Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange and Christiane Peters (2008). Twisted Edwards Curves. Springer-Verlag Berlin Heidelberg. ISBN 978-3-540-68159-5. 

References[edit]

External links[edit]