Montgomery curve

From formulasearchengine
Revision as of 11:12, 29 December 2013 by en>Bender235
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Template:Cleanup

The tripling-oriented Doche–Icart–Kohel curve is a form of an elliptic curve that has been used lately in cryptography; it is a particular type of Weierstrass curve. At certain conditions some operations, as adding, doubling or tripling points, are faster to compute using this form. The Tripling oriented Doche–Icart–Kohel curve, often called with the abbreviation 3DIK has been introduced by Christophe Doche, Thomas Icart, and David R. Kohel in [1]

Definition

A tripling-oriented Doche–Icart–Kohel curve of equation y2=x33x26x3

Let K be a field of characteristic different form 2 and 3.

An elliptic curve in tripling oriented Doche–Icart–Kohel form is defined by the equation:

Ta:y2=x3+3a(x+1)2

with aK.

A general point P on Ta has affine coordinates (x,y). The "point at infinity" represents the neutral element for the group law and it is written in projective coordinates as O = (0:1:0). The negation of a point P = (xy) with respect to this neutral element is −P = (x, −y).

The group law

Consider an elliptic curve in the Tripling-oriented Doche-Icart-Kohel form in affine coordinates:

Ta:y2=x3+3a(x+1)2

with a0,94.

As in other forms of elliptic curves, it is possible to define some "operations" between points, such as adding points, or doubling (See also The group law). In the following sections formulas to add, negate and doubling points are given. The addition and doubling formulas are often used for other operations: given a point P on an elliptic curve it is possible to compute [n]P, where n is an integer, using addition and doubling; computing multiples of points is important in elliptic curve cryptography and in Lenstra elliptic curve factorization.

Addition

Given P1=(x1,y1) and P2=(x2,y2) on Ta, the point P3=(x3,y3)=P1+P2 has coordinates:

x3=(x13+(x23a)x12+(x22+6ax2)x1+(y122y2y1+(x233ax22+y22)))(x122x2x1+x22)
y3=((y1+2y2)x13+(3ay1+(3y2x2+3ay2))x12+((3x22+6ax2)y16ay2x2)x1+(y133y2y12+(2x233ax22+3y22)y1+(y2x23+3ay2x22y23)))(x13+3x2x123x22x1+x23)

Doubling

Given a point P1=(x1,y1) on Ta, the point P3=(x3,y3)=2P1 has coordinates:

x3=94y12x14+9y12ax13+(9y12a2+9y12a)x12+(18y12a22)x1+9y12a23a
y3=278y13x16814y13ax15+(812y13a2814y13a)x14+(27y13a381y13a2+92y1)x13+(81y13a3812y13a2+272y1a)x12+(81y13a3+9y1a2+9y1a)x1+(27y13a3+9y1a2y1)

Negation

Given a point P1=(x1,y1) on Ta, its negation with respect to the neutral element (0:1:0) is P1=(x1,y1).

There are also other formulas given in [2] for Tripling-oriented Doche–Icart–Kohel curves for fast tripling operation and mixed-addition.

New Jacobian coordinates

For computing on these curves points are usually represented in new Jacobian coordinates (Jn):

a point in the new Jacobian coordinates is of the form P=(X:Y:Z:Z2); moreover:

P=(X:Y:Z:Z2)=(λ2X:λ3Y:λZ:λ2Z2),

for any λK.

This means, for example, that the point P=(X:Y:Z:Z2) and the point Q=(4X:8Y:2Z:4Z2) (for λ=2) are actually the same.

So, an affine point P=(x,y) on Ta is written in the new Jacobian coordinates as P=(X:Y:Z:Z2), where x=X/Z2 and y=Y/Z3; in this way, the equation for Ta becomes:

Ta:Y2=X3+3aZ2(X+Z2)2.

The term Z2 of a point on the curve makes the mixed addition (that is the addition between two points in different systems of coordinates) more efficient.

The neutral element in new Jacobian coordinates is (1:1:0:0).

Algorithms and examples

Addition

The following algorithm represents the sum of two points P1 and P2 on an elliptic curve in the Tripling-oriented Doche-Icart-Kohel form. The result is a point P3=(X3,Y3,Z3,ZZ3). It is assumed that Z2=1 and that a3=3a. The cost of this implementation is 7M + 4S + 1*a3 + 10add + 3*2 + 1*4, where M indicates the multiplications, S the squarings, a3 indicates the multiplication by the constant a3, add represents the number of additions required.

A=X2ZZ1

B=Y2ZZ1Z1

C=X1A

D=2(Y1B)

F=C2

F4=4F

Z3=(Z1+C)2ZZ1F

E=Z32

G=CF4

H=AF4

X3=D2G2Ha3E

Y3=D(HX3)2BG

ZZ3=E

Example

Let P1=(1,13) and P2=(0,3) affine points on the elliptic curve over :

y2=x3+3(x+1)2.

Then:

A=X2ZZ1=0

B=Y2ZZ1Z1=3

C=X1A=1

D=2(Y1B)=2(133)

F=C2=1

F4=4F=4

Z3=(Z1+C)2ZZ1F=2

E=Z32=4

G=CF4=4

H=AF4=0

X3=D2G2Ha3E=48839

Y3=D(HX3)2BG=296314413

ZZ3=E=4

Notice that in this case Z1=Z2=1. The resulting point is P3=(X3,Y3,Z3,ZZ3)=(48839,296314413,2,4), that in affine coordinates is P3=(12239,3731813).

Doubling

The following algorithm represents the doubling of a point P1 on an elliptic curve in the Tripling-oriented Doche-Icart-Kohel form. It is assumed that a3=3a, a2=2a. The cost of this implementation is 2M + 7S + 1*a2 + 1*a3 + 12add + 2*2 + 1*3 + 1*8; here M represents the multiplications, S the squarings, a2 and a3 indicates the multiplications by the constants a2 and a3 respectively, and add indicates the additions.

A=X12

B=a2ZZ1(X1+ZZ1)

C=3(A+B)

D=Y12

E=D2

Z3=(Y1+Z1)2DZZ1

ZZ3=Z32

F=2((X1+D)2AE)

X3=C2a3ZZ32F

Y3=C(FX3)8E

Example

Let P1=(0,3) be a point on y2=x3+3(x+1)2.

Then:

A=X12=0

B=a2ZZ1(X1+ZZ1)=2

C=3(A+B)=6

D=Y12=3

E=D2=9

Z3=(Y1+Z1)2DZZ1=23

ZZ3=Z32=12

F=2((X1+D)2AE)=0

X3=C2a3ZZ32F=0

Y3=C(FX3)8E=72

Notice that here the point is in affine coordinates, so Z1=1. The resulting point is P3=(0,72,23,12), that in affine coordinates is P3=(0,3).

Equivalence with Weierstrass form

Any elliptic curve is birationally equivalent to another written in the Weierstrass form.

The following twisted tripling-oriented Doche-Icart-Kohel curve:

Ta,λ: y2=x3+3λa(x+λ)2

can be transformed into the Weierstrass form by the map:

(x,y)(xλa,y).

In this way Ta,λ becomes:

y2=x33λ2a(a2)x+λ3a(2a26a+3).

Conversely, given an elliptic curve in the Weierstrass form:

Ec,d: y2=x3+cx2+d,

it is possible to find the "corresponding" Tripling-oriented Doche–Icart–Kohel curve, using the following relation:

λ=3d(a2)a(2a26a+3)

where a is a root of the polynomial 6912a(a2)3j(4a9).

Here j=6912c34c3+27d2 is the j-invariant of the elliptic curve Ec,d.

Notice that in this case the map given is not only a birational equivalence, but an isomorphism between curves.

Internal link

For more informations about the running-time required in a specific case, see Table of costs of operations in elliptic curves

External links

Notes

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.

References

  1. Christophe Doche, Thomas Icart, and David R. Kohel, Efficient Scalar Multiplication by Isogeny Decompositions
  2. Christophe Doche, Thomas Icart, and David R. Kohel, Efficient Scalar Multiplication by Isogeny Decompositions, pag 198-199