Misplaced Pages

In mathematics, the Montgomery curve is a form of elliptic curve introduced by Peter L. Montgomery in 1987, 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 K is defined by the equation

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

for certain A, B ∈ K and with B(A − 4) ≠ 0.

Generally this curve is considered over a finite field K (for example, over a finite field of q elements, K = F_q) 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 ${\displaystyle P,Q}$ consists of finding a third one ${\displaystyle R}$ such that ${\displaystyle R=P+Q}$; "doubling" a point consists of computing ${\displaystyle P=P+P}$ (For more information about operations see The group law) and below.

A point ${\displaystyle P=(x,y)}$ on the elliptic curve in the Montgomery form ${\displaystyle By^{2}=x^{3}+Ax^{2}+x}$ can be represented in Montgomery coordinates ${\displaystyle P=(X:Z)}$, where ${\displaystyle P=(X:Z)}$ are projective coordinates and ${\displaystyle x=X/Z}$ for ${\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 ${\displaystyle (x,y)}$ and ${\displaystyle (x,-y)}$ because they are both given by the point ${\displaystyle (X:Z)}$. However, with this representation it is possible to obtain multiples of points, that is, given ${\displaystyle P=(X:Z)}$, to compute ${\displaystyle P=(X_{n}:Z_{n})}$.

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

${\displaystyle X_{m+n}=Z_{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 ${\displaystyle m=n}$, then the operation becomes a "doubling"; the coordinates of ${\displaystyle P_{n}=P_{n}+P_{n}=P_{2n}=(X_{2n}:Z_{2n})}$ are given by the following equations:

${\displaystyle 4X_{n}Z_{n}=(X_{n}+Z_{n})^{2}-(X_{n}-Z_{n})^{2}}$

${\displaystyle X_{2n}=(X_{n}+Z_{n})^{2}(X_{n}-Z_{n})^{2}}$

${\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 ${\displaystyle (A+2)/4}$, so ${\displaystyle A}$ can be chosen in order to have a small D.

Algorithm and example

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

It is assumed that ${\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.

${\displaystyle XX_{1}=X_{1}^{2}\,}$

${\displaystyle X_{2}=(XX_{1}-1)^{2}\,}$

${\displaystyle Z_{2}=4X_{1}(XX_{1}+aX_{1}+1)\,}$

Example

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

Then:

${\displaystyle XX_{1}=X_{1}^{2}=4\,}$

${\displaystyle X_{2}=(XX_{1}-1)^{2}=9\,}$

${\displaystyle Z_{2}=4X_{1}(XX_{1}+AX_{1}+1)=24\,}$

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

Addition

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

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

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

${\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 ${\displaystyle ~x}$ coordinates of ${\displaystyle P_{1}}$, ${\displaystyle P_{2}}$ and ${\displaystyle P_{3}}$. In particular this equation can be re-written as:

${\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:

${\displaystyle -x_{1}-x_{2}-x_{3}=A-Bl^{2}}$.

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

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

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

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

${\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 ${\displaystyle P_{1}}$ on the Montgomery curve ${\displaystyle M_{A,B}}$, the point ${\displaystyle P_{1}}$ represents geometrically the third point of intersection between the curve and the line tangent to ${\displaystyle P_{1}}$; so, to find the coordinates of the point ${\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 ${\displaystyle P_{1}}$, so, if ${\displaystyle M_{A,B}:f(x,y)=0}$ with

${\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:

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

by the implicit function theorem.

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

${\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 ${\displaystyle K}$ be a field with characteristic different from 2.

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

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

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

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

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

with ${\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:

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

The map:

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

${\displaystyle (x,y)\mapsto (u,v)=\left({\frac {1+y}{1-y}},{\frac {1+y}{(1-y)x}}\right)}$

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

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

${\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 ${\displaystyle v=0}$ or ${\displaystyle u+1=0}$ of the ${\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

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

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

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

${\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:

${\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 }$: ${\displaystyle M_{A,B}\rightarrow E_{a,b}}$

${\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 ${\displaystyle \mathbb {F} }$ in Weierstrass form

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

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

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

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

${\displaystyle \psi ^{-1}}$: ${\displaystyle E_{a,b}\rightarrow M_{A,B}}$

${\displaystyle (t,v)\mapsto (x,y)=\left(s(t-\alpha ),sv\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

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

• Elliptic curves
• Elliptic curve cryptography