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

edit
 
A Montgomery curve of equation  

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

 

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

edit

It is possible to do some "operations" between the points of an elliptic curve: "adding" two points   consists of finding a third one   such that  ; "doubling" a point consists of computing   (For more information about operations see The group law) and below.

A point   on the elliptic curve in the Montgomery form   can be represented in Montgomery coordinates  , where   are projective coordinates and   for  .

Notice that this kind of representation for a point loses information: indeed, in this case, there is no distinction between the affine points   and   because they are both given by the point  . However, with this representation it is possible to obtain multiples of points, that is, given  , to compute  .

Now, considering the two points   and  : their sum is given by the point   whose coordinates are:

 
 

If  , then the operation becomes a "doubling"; the coordinates of   are given by the following equations:

 
 
 

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  , so   can be chosen in order to have a small D.

Algorithm and example

edit

The following algorithm represents a doubling of a point   on an elliptic curve in the Montgomery form.

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

 
 
 

Example

edit

Let   be a point on the curve  . In coordinates  , with  ,  .

Then:

 
 
 

The result is the point   such that  .

Addition

edit

Given two points  ,   on the Montgomery curve   in affine coordinates, the point   represents, geometrically the third point of intersection between   and the line passing through   and  . It is possible to find the coordinates   of  , in the following way:

1) consider a generic line   in the affine plane and let it pass through   and   (impose the condition), in this way, one obtains   and  ;

2) intersect the line with the curve  , substituting the   variable in the curve equation with  ; the following equation of third degree is obtained:

 

As it has been observed before, this equation has three solutions that correspond to the   coordinates of  ,   and  . In particular this equation can be re-written as:

 

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

 .

So,   can be written in terms of  ,  ,  ,  , as:

 

4) To find the   coordinate of the point   it is sufficient to substitute the value   in the line  . Notice that this will not give the point   directly. Indeed, with this method one find the coordinates of the point   such that  , but if one needs the resulting point of the sum between   and  , then it is necessary to observe that:   if and only if  . So, given the point  , it is necessary to find  , but this can be done easily by changing the sign to the   coordinate of  . In other words, it will be necessary to change the sign of the   coordinate obtained by substituting the value   in the equation of the line.

Resuming, the coordinates of the point  ,   are:

 
 

Doubling

edit

Given a point   on the Montgomery curve  , the point   represents geometrically the third point of intersection between the curve and the line tangent to  ; so, to find the coordinates of the point   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  , so, if   with

 

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

 

by the implicit function theorem.

So   and the coordinates of the point  ,   are:

 

Equivalence with twisted Edwards curves

edit

Let   be a field with characteristic different from 2.

Let   be an elliptic curve in the Montgomery form:

 

with  ,  

and let   be an elliptic curve in the twisted Edwards form:

 

with  

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  . In particular, the twisted Edwards curve   is birationally equivalent to the Montgomery curve   where  , and  .

The map:

 
 

is a birational equivalence from   to  , with inverse:

 :  
 

Notice that this equivalence between the two curves is not valid everywhere: indeed the map   is not defined at the points   or   of the  .

Equivalence with Weierstrass curves

edit

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

 :  

can be transformed in the following way: divide each term of the equation for   by  , and substitute the variables x and y, with   and   respectively, to get the equation

 

To obtain a short Weierstrass form from here, it is sufficient to replace u with the variable  :

 

finally, this gives the equation:

 

Hence the mapping is given as

 :  
 

In contrast, an elliptic curve over base field   in Weierstrass form

 :  

can be converted to Montgomery form if and only if   has order divisible by four and satisfies the following conditions:[3]

  1.   has at least one root  ; and
  2.   is a quadratic residue in  .

When these conditions are satisfied, then for   we have the mapping

 :  
 .

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

edit
edit