In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
the Montgomery curve is a form of
elliptic curve
In mathematics, an elliptic curve is a smooth, projective, algebraic curve of genus one, on which there is a specified point . An elliptic curve is defined over a field and describes points in , the Cartesian product of with itself. If ...
introduced by
Peter L. Montgomery in 1987, different from the usual
Weierstrass form
In mathematics, an elliptic curve is a smooth, projective, algebraic curve of genus one, on which there is a specified point . An elliptic curve is defined over a field and describes points in , the Cartesian product of with itself. If t ...
. It is used for certain computations, and in particular in different
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
applications.
Definition
![Montgomery curve2](https://upload.wikimedia.org/wikipedia/commons/d/d7/Montgomery_curve2.svg)
A Montgomery curve over a
field
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
is defined by the
equation
In mathematics, an equation is a formula that expresses the equality of two expressions, by connecting them with the equals sign . The word ''equation'' and its cognates in other languages may have subtly different meanings; for example, in ...
:
for certain and with .
Generally this
curve
In mathematics, a curve (also called a curved line in older texts) is an object similar to a line (geometry), line, but that does not have to be Linearity, straight.
Intuitively, a curve may be thought of as the trace left by a moving point (ge ...
is considered over a
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
''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
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all rationa ...
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
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
In mathematics, homogeneous coordinates or projective coordinates, introduced by August Ferdinand Möbius in his 1827 work , are a system of coordinates used in projective geometry, just as Cartesian coordinates are used in Euclidean geometry. T ...
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
In geometry, a coordinate system is a system that uses one or more numbers, or coordinates, to uniquely determine the position of the points or other geometric elements on a manifold such as Euclidean space. The order of the coordinates is sig ...
are:
:
:
If
, then the operation becomes a "doubling"; the coordinates of
are given by the following equations:
:
:
:
The first operation considered above (
addition
Addition (usually signified by the Plus and minus signs#Plus sign, plus symbol ) is one of the four basic Operation (mathematics), operations of arithmetic, the other three being subtraction, multiplication and Division (mathematics), division. ...
) 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
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
Let
be a point on the curve
.
In coordinates
, with
,
.
Then:
:
:
:
The result is the point
such that
.
Addition
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
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
In mathematics, the slope or gradient of a line is a number that describes both the ''direction'' and the ''steepness'' of the line. Slope is often denoted by the letter ''m''; there is no clear answer to the question why the letter ''m'' is use ...
of the line, is given by:
:
by the
implicit function theorem.
So
and the coordinates of the point
,
are:
:
Equivalence with twisted Edwards curves
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
In mathematics, birational geometry is a field of algebraic geometry in which the goal is to determine when two algebraic varieties are isomorphic outside lower-dimensional subsets. This amounts to studying mappings that are given by rational f ...
between Montgomery curves and
twisted Edwards curve
In algebraic geometry, the twisted Edwards curves are plane models of elliptic curves, a generalisation of Edwards curves introduced by Daniel J. Bernstein, Bernstein, Birkner, Joye, Tanja Lange, Lange and Peters in 2008. The curve set is named a ...
:
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
A map is a symbolic depiction emphasizing relationships between elements of some space, such as objects, regions, or themes.
Many maps are static, fixed to paper or some other durable medium, while others are dynamic or interactive. Although ...
:
:
:
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
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:
#
has at least one root
; and
#
is a quadratic residue in
.
When these conditions are satisfied, then for
we have the mapping
:
:
:
.
See also
*
Curve25519
In cryptography, Curve25519 is an elliptic curve used in elliptic-curve cryptography (ECC) offering 128 bits of security (256-bit key size) and designed for use with the elliptic curve Diffie–Hellman (ECDH) key agreement scheme. It is one of th ...
*
Table of costs of operations in elliptic curves
Elliptic curve cryptography is a popular form of public key encryption that is based on the mathematical theory of elliptic curves. Points on an elliptic curve can be added and form a group under this addition operation. This article describes th ...
– information about the running-time required in a specific case
Notes
References
*
*
* {{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
External links
Genus-1 curves over large-characteristic fields
Elliptic curves
Elliptic curve cryptography