Montgomery curve

File:Montgomery curve2.svg

A Montgomery curve over a field {{math|K}} is defined by the equation

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

for certain {{math|A, B ∈ K}} and with {{math|B(A² − 4) ≠ 0}}.

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

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\backslash 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.

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\; \backslash ,$

: $X\_2\; =\; (XX\_1-1)^2\; \backslash ,$

: $Z\_2\; =\; 4X\_1(XX\_1+aX\_1+1)\; \backslash ,$

Let $P\_1=(2,\backslash 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\; \backslash ,$

: $X\_2\; =\; (XX\_1-1)^2\; =\; 9\; \backslash ,$

: $Z\_2\; =\; 4X\_1(XX\_1+AX\_1+1)\; =\; 24\; \backslash ,$

The result is the point $P\_2=(X\_2:Z\_2)=(9:24)$ such that $P\_2=2P\_1$.

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=\backslash frac\{y\_2-y\_1\}\{x\_2-x\_1\}$ and $m=y\_1-\backslash left(\backslash frac\{y\_2-y\_1\}\{x\_2-x\_1\}\backslash 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\_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\backslash left(\backslash frac\{y\_2-y\_1\}\{x\_2-x\_1\}\backslash 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\_\backslash 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\_\backslash 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\; =\; \backslash frac\{B(y\_2-y\_1)^2\}\{(x\_2-x\_1)^2\}-A-x\_1-x\_2$

: $y\_3\; =\; \backslash frac\{(2x\_1+x\_2+A)(y\_2-y\_1)\}\{x\_2-x\_1\}-\backslash frac\{B(y\_2-y\_1)^3\}\{(x\_2-x\_1)^3\}-y\_1$

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=-\backslash left.\backslash frac\{\backslash partial\; f\}\{\backslash partial\; x\}\backslash right/\backslash frac\{\backslash partial\; f\}\{\backslash partial\; y\; \}$

by the implicit function theorem.

So $l\; =\; \backslash frac\{3x\_1^2\; +\; 2Ax\_1\; +\; 1\}\{2By\_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 = \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{align}

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\backslash in\; K\backslash smallsetminus\backslash \{-2,2\backslash \}$, $B\; \backslash in\; K\backslash smallsetminus\backslash \{0\backslash \}$

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

: $E\_\{a,d\}\backslash \; :\backslash \; ax^2\; +\; y^2\; =\; 1\; +\; dx^2y^2,\; \backslash ,$

with $a,d\backslash in\; K\backslash smallsetminus\backslash \{0\backslash \},\; \backslash quad\; a\backslash neq\; d.$

The following theorem shows the birational equivalence between Montgomery curves and twisted Edwards curve:{{cite book

| author = Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange and Christiane Peters

| title = Progress in Cryptology – AFRICACRYPT 2008

| volume = 5023

| pages = 389–405

| year = 2008

| publisher = Springer-Verlag Berlin Heidelberg

| isbn = 978-3-540-68159-5

| doi = 10.1007/978-3-540-68164-9_26

| series = Lecture Notes in Computer Science

| chapter = Twisted Edwards Curves

| chapter-url = http://eprint.iacr.org/2008/013

}}

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\; =\; \backslash frac\{2(a+d)\}\{a-d\}$, and $B\; =\; \backslash frac\{4\}\{a-d\}$.

The map:

: $\backslash psi\backslash ,:\backslash ,E\_\{a,d\}\; \backslash 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:

: $\backslash psi^\{-1\}$: $M\_\{A,B\}\; \backslash 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 $\backslash psi$ is not defined at the points $v\; =\; 0$ or $u\; +\; 1\; =\; 0$ of the $M\_\{A,B\}$.

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=\backslash frac\{x\}\{B\}$ and $v=\backslash frac\{y\}\{B\}$ respectively, to get the equation

: $v^2\; =\; u^3\; +\; \backslash frac\{A\}\{B\}u^2\; +\; \backslash frac\{1\}\{B^2\}u.$

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

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

finally, this gives the equation:

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

Hence the mapping is given as

: $\backslash psi$: $M\_\{A,B\}\; \backslash rightarrow\; E\_\{a,b\}$

: $$

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

: $E\_\{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:{{cite conference

| author = Katsuyuki Okeya, Hiroyuki Kurumatani, and Kouichi Sakurai

| year = 2000

| title = Elliptic Curves with the Montgomery-Form and Their Cryptographic Applications

| conference = Public Key Cryptography (PKC2000)

| doi = 10.1007/978-3-540-46588-1_17

| doi-access = free

}}

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

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

: $\backslash psi^\{-1\}$: $E\_\{a,b\}\; \backslash rightarrow\; M\_\{A,B\}$

: $$

(t,v) \mapsto (x,y) =

\left(s (t-\alpha), s v\right),

A = 3 \alpha s,

B = s

.

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

{{reflist}}

• {{cite journal

| author = Peter L. Montgomery

| year = 1987

| title = Speeding the Pollard and Elliptic Curve Methods of Factorization

| journal = Mathematics of Computation |volume=48 |issue=177 |pages=243–264

| jstor = 2007888

| doi=10.2307/2007888

| doi-access = free

}}

• {{cite book

| author = Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange and Christiane Peters

| title = Progress in Cryptology – AFRICACRYPT 2008

| volume = 5023

| pages = 389–405

| year = 2008

| publisher = Springer-Verlag Berlin Heidelberg

| isbn = 978-3-540-68159-5

| doi = 10.1007/978-3-540-68164-9_26

| series = Lecture Notes in Computer Science

| chapter = Twisted Edwards Curves

| chapter-url = http://eprint.iacr.org/2008/013

}}

• {{cite journal

|author1=Wouter Castryck |author2=Steven Galbraith |author3=Reza Rezaeian Farashahi |year=2008

| title = Efficient Arithmetic on Elliptic Curves using a Mixed Edwards-Montgomery Representation

| url = https://eprint.iacr.org/2008/218.pdf

}}

• [http://hyperelliptic.org/EFD/g1p/index.html Genus-1 curves over large-characteristic fields]

Category:Elliptic curves

Category:Elliptic curve cryptography