Jacobian curve

In mathematics, the Jacobi curve is a representantion of an elliptic curve different than the usual one (Weierstrass equation). Sometimes it is used in cryptography instead of the Weierstrass form because it can provide a defence against simple and differential power analysis style (SPA) attacks; it is possible, indeed, to use the general addition formula also for doubling a point on an elliptic curve of this form: in this way the two operations become indistinguishable from some side-channel information. The Jacobi curve offers also faster arithmetic compared to the Weierstrass curve.

The Jacobi curve can be of two types: the Jacobi intersection, that is given by an intersection of two surfaces, and the Jacobi quartic.

Definition: Jacobi intersection

Let $K$ be a field. An elliptic curve in the projective space $\mathbb {P} ^{3}$ over $K$ can be represented as the intersection of two quadric surfaces:

$Q:\{Q_{1}(X_{0},X_{1},X_{2},X_{3})=0\}\cap \{Q_{2}(X_{0},X_{1},X_{2},X_{3})=0\}$

It is possible to define the Jacobi form of an elliptic curve as the intersection of two quadrics, using the following map applied to the usual Weierstrass curve $E:$ $y^{2}=x^{3}+ax+b$, $a,b\in K$ :

$\Phi :(x,y)\mapsto (X,Y,Z,T)=(x,y,1,x^{2})$

This map sends the point $(x,y)\in E$ to the point $(X,Y,Z,T)$ that satisfies the following system of equations:

$\mathbf {S} :{\begin{cases}X^{2}-TZ=0\\Y^{2}-aXY-bZ^{2}-TX=0\end{cases}}$

The map $\Phi$ can be applied to an elliptic curve in the Weirstrass form $E:$ $y^{2}=x^{3}+ax+b$ with three points of order two: this means that the polynomial $f(x)=x^{3}+ax+b$ has three roots in the field $K$. Suppose that the roots are $0,-1,j$, with $j\in K$, then the three points of order two are: (0,0), (-1,0), (-j,0) and the curve $E$ can, thus, be written as:

$E\ :\ y^{2}=x(x+1)(x+j),$

where $O=(0:1:0)$ is the "point at infinity", that is the neutral element in the group law.

The curve $E$ corresponds to the following intersection of surfaces in $\mathbb {P} ^{3}$:

$\mathbf {S} 1:{\begin{cases}X^{2}+Y^{2}-T^{2}=0\\kX^{2}+Z^{2}-T^{2}=0\end{cases}}$.

The "special case" is when j=0: the elliptic curve has a double point and thus it is singular.

S1 is obtained by applying to $E$ the transformation:

$\psi$: $E\rightarrow S1$

$(x,y)\mapsto (X,Y,Z,T)=(-2y,x^{2}-j,x^{2}+2jx+j,x^{2}+2x+j)$

$O=(0:1:0)\mapsto (0,1,1,1)$

Group law

(See also The group law).

Given an elliptic curve, it is possible to do some "operations" between its points: for example one can add two points P and Q obtaining the point P+Q that belongs to the curve ; given a point P on the elliptic curve, it is possible to "double" P, that means find [2]P=P+P (the square brackets are used to indicate [n]P, the point P added n times), and also find the negation of P, that means find -P. In this way, the points of an elliptic curve forms a group. Adding and doubling formulas are usefull also to compute [n]P, the nth multple of a point P on an elliptic curve: this operation is considered the most in elliptic curve cryptography.

For S1, the neutral element of the group is the point $(0,1,1,1)$, that is the image of $0=(0:1:0)$ by $\psi$.

Addition and doubling

Given $P_{1}=(X_{1},Y_{1},Z_{1},T_{1})$ and $P_{2}=(X_{2},Y_{2},Z_{2},T_{2})$, two points on $S1$, the coordinates of the point $P_{3}=P_{1}+P_{2}$ are:

$X_{3}=T_{1}Y_{2}X_{1}Z_{2}+Z_{1}X_{2}Y_{1}T_{2}$

$Y_{3}=T_{1}Y_{2}Y_{1}T_{2}-Z_{1}X_{2}X_{1}Z_{2}$

$Z_{3}=T_{1}Z_{1}T_{2}Z_{2}-kX_{1}Y_{1}X_{2}Y_{2}$

$T_{3}=(T_{1}Y_{2})^{2}+(Z_{1}X_{2})^{2}$

These formulas are also valid for doubling: it sufficies to have $P_{1}=P_{2}$. So adding or doubling points in $S1$ are operations that both require 16 multiplications plus one multiplication by a constant ($k$).

It is also possible to use the following formulas for doubling the point $P_{1}$ and find $P_{3}=[2]P_{1}$:

$X_{3}=2Y_{1}T_{1}Z_{1}X_{1}$

$Y_{3}=(T_{1}Y_{1})^{2}-(T_{1}Z_{1})^{2}+(Z_{1}Y_{1})^{2}$

$Z_{3}=(T_{1}Z_{1})^{2}-(T_{1}Y_{1})^{2}+(Z_{1}Y_{1})^{2}$

$T_{3}=(T_{1}Z_{1})^{2}+(T_{1}Y_{1})^{2}-(Z_{1}Y_{1})^{2}$

Using these formulas 8 multiplications are needed to double a point. However there are even more efficient “strategies” for doubling that require only 7 multiplications. In this way it is possible to triple a point with 23 multiplications; indeed $[3]P_{1}$ can be obtained by adding $P_{1}$ with $[2]P_{1}$ with a cost of 7 multiplications for $[2]P_{1}$ and 16 for $P_{1}+[2]P_{1}$

Example of addition and doubling

Let the field $K=\mathbb {R}$, or $K=\mathbb {C}$. Consider the case:

$\mathbf {S} 1:{\begin{cases}X^{2}+Y^{2}-T^{2}=0\\4X^{2}+Z^{2}-T^{2}=0\end{cases}}$

Consider the points $P_{1}=(1,{\sqrt {3}},0,2)$ and $P_{2}=(1,2,1,{\sqrt {5}})$: it is easy to verify that $P1$ and $P2$ belong to S1 (it is sufficient to see that these points satisfy both equations of the system S1).

Using the formulas given above for adding two points, the coordinates for $P_{3}$, where $P_{3}=P_{1}+P_{2}$ are:

$X_{3}=T_{1}Y_{2}X_{1}Z_{2}+Z_{1}X_{2}Y_{1}T_{2}=4$

$Y_{3}=T_{1}Y_{2}Y_{1}T_{2}-Z_{1}X_{2}X_{1}Z_{2}=4{\sqrt {15}}$

$Z_{3}=T_{1}Z_{1}T_{2}Z_{2}-k^{2}X_{1}Y_{1}X_{2}Y_{2}=-8{\sqrt {3}}$

$T_{3}=(T_{1}Y_{2})^{2}+(Z_{1}X_{2})^{2}=16$

The resulting point is $P_{3}=(4,4{\sqrt {15}},-8{\sqrt {3}},16)$.

With the formulas given above for doubling, it is possible to find the point $P_{3}=[2]P_{1}$:

$X_{3}=2Y_{1}T_{1}Z_{1}X_{1}=0$

$Y_{3}=(T_{1}Y_{1})^{2}-(T_{1}Z_{1})^{2}+(Z_{1}Y_{1})^{2}=12$

$Z_{3}=(T_{1}Z_{1})^{2}-(T_{1}Y_{1})^{2}+(Z_{1}Y_{1})^{2}=-12$

$T_{3}=(T_{1}Z_{1})^{2}+(T_{1}Y_{1})^{2}-(Z_{1}Y_{1})^{2}=12$

So, in this case $P_{3}=[2]P_{1}=(0,12,-12,12)$.

Negation

Given the point $P_{1}=(X_{1},Y_{1},Z_{1},T_{1})$ in $S1$, its negation $(0,1,1,1)$ is:

$-P_{1}=(-X_{1},Y_{1},Z_{1},T_{1}).\,$

Addition and doubling in affine coordinates

Given two affine points $P_{1}=(x_{1},y_{1},z_{1})$ and $P_{2}=(x_{2},y_{2},z_{2})$, their sum is a point $P_{3}$ with coordinates:

$x_{3}={\frac {y_{2}x_{1}z_{2}+z_{1}x_{2}y_{1}}{(y_{2}^{2}+(z_{1}x_{2})^{2})}}$

$y_{3}={\frac {y_{2}y_{1}-z_{1}x_{2}x_{1}z_{2}}{(y_{2}^{2}+(z_{1}x_{2})^{2})}}$

$z_{3}={\frac {z_{1}z_{2}-ax_{1}y_{1}x_{2}y_{2}}{(y_{2}^{2}+(z_{1}x_{2})^{2})}}$

These formulas are valid also for doubling with the condition $P_{1}=P_{2}$.

Extended coordinates

There is another kind of coordinate system with which a point in the Jacobi intersection can be represented.

Given the following elliptic curve in the Jacobi intersection form:

$\mathbf {S} 1:{\begin{cases}x^{2}+y^{2}=1\\kx^{2}+z^{2}=1\end{cases}}$

the extended coordinates describe a point $P=(x,y,z)$ with the variables $X,Y,Z,N,XY,ZN$, where:

$x=X/N$

$y=Y/N$

$z=Z/N$

$XY=X*Y$

$ZN=Z*N$

Sometimes these coordinates are used, because they are more convenient (in terms of time-cost) in some specific situations.

To have more information about the operations based on the use of these coordinates see http://hyperelliptic.org/EFD/g1p/auto-jintersect-extended.html

Definition: Jacobi quartic

A Jacobi quartic of equation $y^{2}=x^{4}-(1,9)x^{2}+1$

Let $K$ be a field. An elliptic curve in Jacobi quartic form can be obtained from a curve $C$ in the Weierstrass form with one point of order 2:

$C:y^{2}=x^{3}+ax+b,\,$

with $a,b\in K$.

Let $P=(p,0)$ be a root of $y^{2}=x^{3}+ax+b$, then P is a point of order 2 of the elliptic curve; let $O$ be the point at infinity.

The following transformation $f$ sends each point of $C$ to a point in the projective space

$f$ : $C\rightarrow \mathbb {P} ^{2}$

$(p,0)\mapsto (0:-1:1)$

$(x,y)\neq (p,0)\mapsto (2(x-p):(2x+p)(x-p)^{2}-y^{2}:y)$

$O\mapsto (0:1:1)$

Applying $f$ to $C$, one obtains a curve in $\mathbb {P} ^{2}$ of the following form:

$C'\ :\ Y^{2}=eX^{4}-2dX^{2}Z^{2}+Z^{4}$

where $e={\frac {-(3p^{2}+4a)}{16}},d={\frac {3p}{4}},e,d\in K$.

C' represents an elliptic curve in the Jacobi quartic form, in projective coordinates.

Jacobi quartic in affine coordinates

The general form of a Jacobi quartic curve in affine coordinates is:

$y^{2}=x^{4}+2ax^{2}+1$

Group law

The neutral element of the the group law of $C'$ is the projective point $(0:1:1)$.

Addition and doubling in affine coordinates

Given two affine points $P_{1}=(x_{1},y_{1})$ and $P_{2}=(x_{2},y_{2})$, their sum is a point $P_{3}=(x_{3},y_{3})$, such that:

$x_{3}={\frac {x_{1}y_{2}+y_{1}x_{2}}{1-(x_{1}x_{2})^{2}}}$

$y_{3}={\frac {((1+(x_{1}x_{2})^{2})(y_{1}y_{2}+2ax_{1}x_{2})+2x_{1}x_{2}({x_{1}}^{2}+{x_{2}}^{2}))}{(1-(x_{1}x_{2})^{2})^{2}}}$

As in the Jacobi intersections, also in this case it is possible to use this formula for doubling as well.

Addition and doubling in projective coordinates

Given two points $P_{1}=(X_{1}:Y_{1}:Z_{1})$ and $P_{2}=(X_{2}:Y_{2}:Z_{2})$ in $C'$, the coordinates for the point $P_{3}=(X_{3}:Y_{3}:Z_{3})$, where $P_{3}=P_{1}+P_{2}$, are given in terms of $P_{1}$ and $P_{2}$ by the formulae:

$X_{3}=X_{1}Z_{1}Y_{2}+Y_{1}X_{2}Z_{2}$

$Y_{3}=[(Z_{1}Z_{2})^{2}+e(X_{1}X_{2})^{2}][Y_{1}Y_{2}-2dX_{1}X_{2}Z_{1}Z_{2}]+2eX_{1}X_{2}Z_{1}Z_{2}(X_{1}^{2}Z_{2}^{2}+Z_{1}^{2}X_{2}^{2})$

$Z_{3}=(Z_{1}Z_{2})^{2}-e(X_{1}X_{2})^{2}$

One can use this formula also for doubling, with the condition that $P_{2}=P_{1}$: in this way the point $P_{3}=P_{1}+P_{1}=[2]P_{1}$ is obtained.

The number of multiplications required to add two points is 13 plus 3 multiplications by constants: in particular there are two multiplications by the constant $e$ and one by the constant $d$.

There are some "strategies" to reduce the operations required for adding and doubling points: the number of multiplications can be decreased to 11 plus 3 multiplications by constants (see section 3 for more details).

The number of multiplications can be reduced by working on the constants $e$ and $d$: the elliptic curve in the Jacobi form can be modified in order to have a smaller number of operations for adding and doubling. So, for example, if the constant $d$ in E’ is significantly small, the multiplication by $d$ can be cancelled; however the best option is to reduce $e$: if it is small, not only one, but two multiplications are neglected.

Example of addition and doubling

Consider an elliptic curve in the Weierstrass form in affine coordinates over the field $K=\mathbb {R}$, or $K=\mathbb {C}$, with $a=4$ and $b=0$:

$C\ :\ y^{2}=x^{3}+4x$

$C$ has a point $P$ of order 2: $P=(p,0)=(0,0)$.

Applying the function $\psi$ to $E$, the following elliptic curve in projective Jacobi quartic form is obtained:

$C'\ :\ Y^{2}=X^{4}+Z^{4}$

where $e={\frac {-(3p^{2}+4a)}{16}}=1$ and $d={\frac {3p}{4}}=0$.

Choosing two points $P_{1}=(1:{\sqrt {2}}:1)$ and $P2=(2:{\sqrt {17}}:1)$, it is possible to find their sum $P_{3}=P_{1}+P_{2}$ using the formulae for adding given above:

$X_{3}=X_{1}Z_{1}Y_{2}+Y_{1}X_{2}Z_{2}={\sqrt {17}}+2{\sqrt {2}}$

$Y_{3}=[(Z_{1}Z_{2})^{2}+e(X_{1}X_{2})^{2}][Y_{1}Y_{2}-2dX_{1}X_{2}Z_{1}Z_{2}]+2eX_{1}X_{2}Z_{1}Z_{2}(X_{1}^{2}Z_{2}^{2}+Z_{1}^{2}X_{2}^{2})=5{\sqrt {34}}+20$

$Z_{3}=(Z_{1}Z_{2})^{2}-e(X_{1}X_{2})^{2}=-3$.

So $P_{3}=({\sqrt {17}}+2{\sqrt {2}}:5{\sqrt {34}}+20:-3)$.

Using the same formulae, the point $P_{3}=[2]P_{1}$ is obtained:

$X_{3}=1\cdot 1\cdot {\sqrt {2}}+{\sqrt {2}}\cdot 1\cdot 1=2{\sqrt {2}}$

$Y_{3}=[1+1\cdot 1]\cdot [{\sqrt {2}}\cdot {\sqrt {2}}]+2\cdot 1\cdot (1^{4}+1^{4})=8$

$Z_{3}=1^{4}-1\cdot (1\cdot 1)^{2}=0$

so, $P_{3}=(2{\sqrt {2}}:8:0)$.

Negation

The negation of a point $P_{1}=(X_{1}:Y_{1}:Z_{1})$ is:

$-P_{1}=(-X_{1}:Y_{1}:Z_{1})$

Alternative coordinates for the Jacobi quartic

There are other system of coordinates that can be used to represent a point in a Jacobi quartic: they are used to obtain fast computations in certain cases. For more information about the time-cost required in the operations with these coordinates see http://hyperelliptic.org/EFD/g1p/auto-jquartic.html

Given an affine Jacobi quartic

$y^{2}=x^{4}+2ax^{2}+1$

the Doubling-oriented XXYZZ coordinates are used with the additional assumption:

$a^{2}+c^{2}=1$

and they represent a point (x,y) as (X, XX, Y, Z, ZZ, R), such that:

$x=X/Z$

$y=Y/ZZ$

$XX=X^{2}$

$ZZ=Z^{2}$

$R=2*X*Z$

the Doubling-oriented XYZ coordinates, with the same additional assumption ($a^{2}+c^{2}=1$), represent a point (x,y) with (X, Y, Z) satisfying the following equations:

$x=X/Z$

$y=Y/Z^{2}$

Using the XXYZZ coordinates there is no additional assumption, and they represent a point (x,y) as (X,XX,Y,Z,ZZ) such that:

$x=X/Z$

$y=Y/ZZ$

$XX=X^{2}$

$ZZ=Z^{2}$

while the XXYZZR coordinates represent (x,y) as (X,XX,Y,Z,ZZ,R) such that:

$x=X/Z$

$y=Y/ZZ$

$XX=X^{2}$

$ZZ=Z^{2}$

$R=2*X*Z$

with the XYZ coordinates the point (x,y) is given by (X,Y,Z), with:

$x=X/Z$

$y=Y/Z^{2}$.

See also

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

External links

• http://hyperelliptic.org/EFD/g1p/index.html

References

• Olivier Billet, Marc Joye (2003). The Jacobi Model of an Elliptic Curve and the Side-Channel Analysis (PDF). Springer-Verlag Berlin Heidelberg 2003. ISBN 978-3-540-40111-7.
• P.Y.Liardet, N.P. Smart (2001). Preventing SPA/DPA in ECC Systems Using the Jacobi Form (PDF). Springer-Verlag Berlin Heidelberg 2001. ISBN 978-3-540-42521-2.
• http://hyperelliptic.org/EFD/index.html