Twisted Hessian curves: Difference between revisions
Line 36: | Line 36: | ||
Furthermore, the neutral element (in affine plane) is: <math>\theta=(0,-1)</math> and in projective coordinates: <math> \theta=(0:-1:1) </math>. |
Furthermore, the neutral element (in affine plane) is: <math>\theta=(0,-1)</math> and in projective coordinates: <math> \theta=(0:-1:1) </math>. |
||
In some application of [[elliptic curve cryptography]](e.g. [[Lenstra elliptic curve factorization|ECM]]) it is necessary to compute the scalar multiplications of P, say [n]P for some n |
In some application of [[elliptic curve cryptography]](e.g. [[Lenstra elliptic curve factorization|ECM]]) it is necessary to compute the scalar multiplications of P, say [n]P for some integer n, and they are based on [[Exponentiation by squaring|double-and-add method]]; so the addition and dobling formulas are needed. |
||
The addition and doubling formulas for this [[elliptic curve]] can be defined, using the affine coordinates to simplify the notation: |
The addition and doubling formulas for this [[elliptic curve]] can be defined, using the affine coordinates to simplify the notation: |
Revision as of 16:00, 15 February 2010
The topic of this article may not meet Wikipedia's general notability guideline. (January 2010) |
In mathematics, the Twisted Hessian curve represents a generalization of Hessian curves; it was introduced in elliptic curve cryptography to speed up the addition and doubling formulas. In some operations (see the last sections), it is close in speed to Edwards curves.
Definition
Let be a field, then The twisted Hessian form in affine coordinates is given by:
and in projective coordinates:
where and and in
Note that these curves are birationally equivalent to Hessian curves.
The Hessian curve is just a special case of Twisted Hessian curve, with a=1.
Considering the equation , note that:
if "a" has a cube root in , there exists a unique b such that .Otherwise, it is necessary to consider an extension field of (e.g., ). Then, since , defining , the following equation is needed (in Hessian form) to do the transformation:
.
This means that Twisted Hessian curves are birationally equivalent to elliptic curve 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 SPA and DPA 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 be a point, then its inverse is in the plane. In projective coordinates, let be one point, then is the inverse of P.
Furthermore, the neutral element (in affine plane) is: and in projective coordinates: .
In some application of elliptic curve cryptography(e.g. ECM) it is necessary to compute the scalar multiplications of P, say [n]P for some integer n, and they are based on double-and-add method; so the addition and dobling formulas are needed.
The addition and doubling formulas for this elliptic curve can be defined, using the affine coordinates to simplify the notation:
Addition formulas:
Let and then, is given by the following equations:
Doubling formulas:
Let then is given by the following equations:
Algorithms and examples
In this case, it is dealed with efficient evaluation of the addition and doubling law; for example, for cryptographic computations, and the projective coordinates are used to this purpose.
Addition
The cost of this algorithm is 12 multiplications, one multiplication by a (constant) and 3 additions.
Example:let and be points over a twisted Hessian form with a=2 and d=-2.Then is given by:
That is, .
Doubling
The cost of this algorithm is 3 multiplications, one multiplication by constant, 3 additions and 3 powers (of 3)
(This is the best result obtained for this curve).
Example:
let be a point over the curve defined by a=2 and d=-2 as above, then is given by:
That is .
Internal Link
For more informations about the running-time required in a specific case, see Table of costs of operations in elliptic curves
External Link
http://hyperelliptic.org/EFD/g1p/index.html