Misplaced Pages

Twisted Hessian curves

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Type of elliptic curve

In mathematics, twisted Hessian curves are a generalization of Hessian curves; they wre introduced in elliptic curve cryptography to speed up the addition and doubling formulas and to have strongly unified arithmetic. In some operations (see the last sections), it is close in speed to Edwards curves. Twisted Hessian curves were introduced by Bernstein, Lange, and Kohel.

Definition

A Twisted Hessian curve of equation 10 x 3 + y 3 + 1 = 15 x y {\displaystyle 10x^{3}+y^{3}+1=15xy}

Let K be a field. The twisted Hessian form in affine coordinates is given by:

a ⋅ x 3 + y 3 + 1 = d ⋅ x ⋅ y {\displaystyle a\cdot x^{3}+y^{3}+1=d\cdot x\cdot y}

and in projective coordinates by

a ⋅ X 3 + Y 3 + Z 3 = d ⋅ X ⋅ Y ⋅ Z , {\displaystyle a\cdot X^{3}+Y^{3}+Z^{3}=d\cdot X\cdot Y\cdot Z,}

where x = X/Z and y = Y/Z and a,d ∈ K. These curves are birationally equivalent to Hessian curves, and Hessian curves are just the special case of twisted Hessian curves in which a = 1.

Considering the equation a · x + y + 1 = d · x · y, note that, if a has a cube root in K, then there exists a unique b such that a = b; otherwise, it is necessary to consider an extension field of K, such as K(a). Then, since bx = ax, defining t = bx, the following equation is needed (in Hessian form) to do the transformation:

t 3 + y 3 + 1 = d ⋅ x ⋅ y {\displaystyle t^{3}+y^{3}+1=d\cdot x\cdot y} .

This means that twisted Hessian curves are birationally equivalent to elliptic curves in Weierstrass form.

Group law

It is interesting to analyze the group law of the elliptic curve, defining the addition and doubling formulas (because the simple power analysis and differential power analysis attacks are based on the running time of these operations). In general, the group law is defined in the following way: if three points lies in the same line then they sum up to zero. So, by this property, the explicit formulas for the group law depend on the curve shape.

Let P = (x1, y1) be a point; its inverse is then −P = (x1/y1, 1/y1) in the plane. In projective coordinates, let P = (X : Y : Z) be a point; then −P = (X1/Y1 : 1/Y1 : Z) is its inverse. Furthermore, the neutral element in affine plane is θ = (0, −1), and in projective coordinates it is θ = (0 : −1 : 1).

In some applications of elliptic curves for cryptography and integer factorization, it is necessary to compute scalar multiples of P, say P for some integer n, and they are based on the double-and-add method, so the addition and doubling formulas are needed. Using affine coordinates, the addition and doubling formulas for this elliptic curve are as follows.

Addition formulas

Let P = (x1, y1) and Q = (x2, y2); then, R = P + Q = (x3, y3), where

x 3 = x 1 − y 1 2 ⋅ x 2 ⋅ y 2 a ⋅ x 1 ⋅ y 1 ⋅ x 2 2 − y 2 {\displaystyle x_{3}={\frac {x_{1}-y_{1}^{2}\cdot x_{2}\cdot y_{2}}{a\cdot x_{1}\cdot y_{1}\cdot x_{2}^{2}-y_{2}}}}

y 3 = y 1 ⋅ y 2 2 − a ⋅ x 1 2 ⋅ x 2 a ⋅ x 1 ⋅ y 1 ⋅ x 2 2 − y 2 {\displaystyle y_{3}={\frac {y_{1}\cdot y_{2}^{2}-a\cdot x_{1}^{2}\cdot x_{2}}{a\cdot x_{1}\cdot y_{1}\cdot x_{2}^{2}-y_{2}}}}

Doubling formulas

Let P = (x, y); then P = (x1, y1), where

x 1 = x − y 3 ⋅ x a ⋅ y ⋅ x 3 − y {\displaystyle x_{1}={\frac {x-y^{3}\cdot x}{a\cdot y\cdot x^{3}-y}}}

y 1 = y 3 − a ⋅ x 3 a ⋅ y ⋅ x 3 − y {\displaystyle y_{1}={\frac {y^{3}-a\cdot x^{3}}{a\cdot y\cdot x^{3}-y}}}

Algorithms and examples

Here some efficient algorithms of the addition and doubling law are given; they can be important in cryptographic computations, and the projective coordinates are used to this purpose.

Addition

A = X 1 ⋅ Z 2 {\displaystyle A=X_{1}\cdot Z_{2}}

B = Z 1 ⋅ Z 2 {\displaystyle B=Z_{1}\cdot Z_{2}}

C = Y 1 X 2 {\displaystyle C=Y_{1}X_{2}}

D = Y 1 ⋅ Y 2 {\displaystyle D=Y_{1}\cdot Y_{2}}

E = Z 1 ⋅ Y 2 {\displaystyle E=Z_{1}\cdot Y_{2}}

F = a ⋅ X 1 ⋅ X 2 {\displaystyle F=a\cdot X_{1}\cdot X_{2}}

X 3 = A ⋅ B − C ⋅ D {\displaystyle X_{3}=A\cdot B-C\cdot D}

Y 3 = D ⋅ E − F ⋅ A {\displaystyle Y_{3}=D\cdot E-F\cdot A}

Z 3 = F ⋅ C − B ⋅ E {\displaystyle Z_{3}=F\cdot C-B\cdot E}

The cost of this algorithm is 12 multiplications, one multiplication by a constant, and 3 additions.

Example:

Let P1 = (1 : −1 : 1) and P2 = (−2 : 1 : 1) be points over a twisted Hessian curve with (a,d) = (2, −2). Then R = P1 + P2 is given by:

A = − 1 ; B = − 1 ; C = − 1 ; D = − 1 ; E = 1 ; F = 2 ; {\displaystyle A=-1;B=-1;C=-1;D=-1;E=1;F=2;}

x 3 = 0 {\displaystyle x_{3}=0}
y 3 = − 3 {\displaystyle y_{3}=-3}
z 3 = − 3 {\displaystyle z_{3}=-3}

That is, R = (0 : −3 : −3).

Doubling

D = X 1 3 {\displaystyle D=X_{1}^{3}}

E = Y 1 3 {\displaystyle E=Y_{1}^{3}}

F = Z 1 3 {\displaystyle F=Z_{1}^{3}}

G = a ⋅ D {\displaystyle G=a\cdot D}

X 3 = X 1 ⋅ ( E − F ) {\displaystyle X_{3}=X_{1}\cdot (E-F)}

Y 3 = Z 1 ⋅ ( G − E ) {\displaystyle Y_{3}=Z_{1}\cdot (G-E)}

Z 3 = Y 1 ⋅ ( F − G ) {\displaystyle Z_{3}=Y_{1}\cdot (F-G)}

The cost of this algorithm is 3 multiplications, one multiplication by a constant, 3 additions, and 3 cubings. This is the best result obtained for this curve.

Example:

Let P = (1 : −1 : 1) be a point over the curve defined by (a,d) = (2, −2) as above; then, R = P = (x3, y3, z3) is given by:

D = 1 ; E = − 1 ; F = 1 ; G = − 4 ; {\displaystyle D=1;E=-1;F=1;G=-4;}

x 3 = − 2 {\displaystyle x_{3}=-2}
y 3 = − 3 {\displaystyle y_{3}=-3}
z 3 = − 5 {\displaystyle z_{3}=-5}

That is, R = (−2 : −3 : 5).

See also

External links

References

  1. "Twisted Hessian curves". Retrieved 28 February 2010.
Categories: