Jacobian curve

In mathematics, the Jacobi curve is a representation of an elliptic curve different from 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.^[1] 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.

Elliptic Curves: Basics

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. Note that the identity element of the group operation is not a point on the affine plane, it only appears in the projective coordinates: then O = (0: 1: 0) is the "point at infinity", that is the neutral element in the group law. Adding and doubling formulas are useful also to compute [n]P, the n-th multiple of a point P on an elliptic curve: this operation is considered the most in elliptic curve cryptography.

An elliptic curve E, over a field K can be put in the Weierstrass form y² = x³ + ax + b, with a, b in K. What will be of importance later are point of order 2, that is P on E such that [2]P = O. If P = (p, 0) is a point on E, then it has order 2; more generally the points of order 2 correspond to the roots of the polynomial f(x) = x³ + ax + b.

From now on, we will use E_a,b to denote the elliptic curve with Weierstrass form y² = x³ + ax + b.

If E_a,b is such that the cubic polynomial x³ + ax + b has three distinct roots in K we can write E_a,b in the Legendre normal form:

E_a,b: y² = x(x + 1)(x + j)

In this case we have three points of order two: (0, 0), (–1, 0), (–j, 0). In this case we use the notation E[j]. Note that j can be expressed in terms of a, b.

Definition: Jacobi intersection

An elliptic curve in P³(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. Let E_a,b be an elliptic curve in the Weierstrass form, we apply the following map to it:

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

We see that the following system of equations holds:

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

The curve E[j] corresponds to the following intersection of surfaces in P³(K):

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

The "special case", E[0], the elliptic curve has a double point and thus it is singular.

S1 is obtained by applying to E[j] the transformation:

ψ: E[j] → 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

For S1, the neutral element of the group is the point (0, 1, 1, 1), that is the image of O = (0: 1: 0) under ψ.

Addition and doubling

Given P₁ = (X₁, Y₁, Z₁, T₁) and P₂ = (X₂, Y₂, Z₂, T₂), two points on S1, the coordinates of the point P₃ = P₁ + P₂ are:

$X_3 = T_1Y_2X_1Z_2 + Z_1X_2Y_1T_2$

$Y_3 = T_1Y_2Y_1T_2 - Z_1X_2X_1Z_2$

$Z_3 = T_1Z_1T_2Z_2 - kX_1Y_1X_2Y_2$

$T_3 = (T_1Y_2)^2 + (Z_1X_2)^2$

These formulas are also valid for doubling: it sufficies to have P₁ = P₂. 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₁ and find P₃ = [2]P₁:

$X_3 = 2Y_1T_1Z_1X_1$

$Y_3 = (T_1Y_1)^2 - (T_1Z_1)^2 + (Z_1Y_1)^2$

$Z_3 = (T_1Z_1)^2 - (T_1Y_1)^2 + (Z_1Y_1)^2$

$T_3 = (T_1Z_1)^2 + (T_1Y_1)^2 - (Z_1Y_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.^[2] In this way it is possible to triple a point with 23 multiplications; indeed [3]P₁ can be obtained by adding P₁ with [2]P₁ with a cost of 7 multiplications for [2]P₁ and 16 for P₁ + [2]P₁^[2]

Example of addition and doubling

Let K = R or C and consider the case:

$\mathbf S1: \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 P₁ and P₂ 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₃, where P₃ = P₁ + P₂ are:

$X_3 = T_1Y_2X_1Z_2 + Z_1X_2Y_1T_2 = 4$

$Y_3 = T_1Y_2Y_1T_2 - Z_1X_2X_1Z_2 = 4\sqrt{15}$

$Z_3 = T_1Z_1T_2Z_2 - kX_1Y_1X_2Y_2 = -8\sqrt{3}$

$T_3 = (T_1Y_2)^2 + (Z_1X_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₃ = [2]P₁:

$X_3 = 2Y_1T_1Z_1X_1 = 0$

$Y_3 = (T_1Y_1)^2 - (T_1Z_1)^2 + (Z_1Y_1)^2 = 12$

$Z_3 = (T_1Z_1)^2 - (T_1Y_1)^2 + (Z_1Y_1)^2 = -12$

$T_3 = (T_1Z_1)^2 + (T_1Y_1)^2 - (Z_1Y_1)^2 = 12$

So, in this case P₃ = [2]P₁ = (0, 12, –12, 12).

Negation

Given the point P₁ = (X₁, Y₁, Z₁, T₁) in S1, its negation is −P₁ = (−X₁, Y₁, Z₁, T₁)

Addition and doubling in affine coordinates

Given two affine points P₁ = (x₁, y₁, z₁) and P₂ = (x₂, y₂, z₂), their sum is a point P₃ with coordinates:

$x_3 = \frac{y_2x_1z_2 + z_1x_2y_1}{(y_2^2 + (z_1x_2)^2)}$

$y_3 = \frac{y_2y_1-z_1x_2x_1z_2}{(y_2^2+(z_1x_2)^2)}$

$z_3 = \frac{z_1z_2-ax_1y_1x_2y_2}{(y_2^2+(z_1x_2)^2)}$

These formulas are valid also for doubling with the condition P₁ = P₂.

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 S1: \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, T, XY, ZT, where:

$x = X/T$

$y = Y/T$

$z = Z/T$

$XY = X\cdot Y$

$ZT = Z\cdot T$

Sometimes these coordinates are used, because they are more convenient (in terms of time-cost) in some specific situations. For 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.9x^2+1$

An elliptic curve in Jacobi quartic form can be obtained from the curve E_a,b in the Weierstrass form with at least one point of order 2. The following transformation f sends each point of E_a,b to a point in the Jacobi coordinates, where (X: Y: Z) = (sX: s²Y: sZ).

f: E_a,b → J

$(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)$^[3]

Applying f to E_a,b, one obtains a curve in J of the following form:

$C :\ Y^2= eX^4-2dX^2Z^2+ Z^4$^[3]

where:

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

are elements in K. C represents an elliptic curve in the Jacobi quartic form, in Jacobi coordinates.

Jacobi quartic in affine coordinates

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

$y^2 = ex^4 + 2ax^2 + 1$,

where often e = 1 is assumed.

Group law

The neutral element of 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_1y_2+y_1x_2}{1-(x_1x_2)^2}$

$y_3 = \frac{((1+(x_1x_2)^2)(y_1y_2+2ax_1x_2)+2x_1x_2({x_1}^2+{x_2}^2))}{(1-(x_1x_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₁ = (X₁: Y₁: Z₁) and P₂ = (X₂: Y₂: Z₂) in C′, the coordinates for the point P₃ = (X₃: Y₃: Z₃), where P₃ = P₁ + P₂, are given in terms of P₁ and P₂ by the formulae:

$X_3 = X_1Z_1Y_2 + Y_1X_2Z_2$

$Y_3 = \left (Z_1^2 Z_2^2 + eX_1^2 X_2^2 \right) \left (Y_1Y_2-2dX_1X_2Z_1Z_2 \right ) \ + \ 2eX_1X_2Z_1Z_2 \left (X_1^2Z_2^2+Z_1^2X_2^2 \right )$

$Z_3 = Z_1^2 Z_2^2 - eX_1^2 X_2^2$

One can use this formula also for doubling, with the condition that P₂ = P₁: in this way the point P₃ = P₁ + P₁ = [2]P₁ 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 ^[4] 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 C 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 the elliptic curve E_4,0, it has a point P of order 2: P = (p, 0) = (0, 0). Therefore a = 4, b = p = 0 so we have e = 1 and d = 1 and the associated Jacobi quartic form is:

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

Choosing two points $P_1=(1:\sqrt{2}:1)$ and $P_2=(2:\sqrt{17}:1)$, it is possible to find their sum P₃ = P₁ + P₂ using the formulae for adding given above:

$X_3 = 1\cdot1\cdot\sqrt{17} + \sqrt{2}\cdot2\cdot1 = \sqrt{17} + 2\sqrt{2}$

$Y_3 = \left (1^2 \cdot 1^2 + 1\cdot 1^2 \cdot 2^2 \right ) \left (\sqrt{2}\cdot \sqrt{17}- 2\cdot 0 \cdot 1 \cdot 2\cdot 1\cdot1 \right ) + 2\cdot 1 \cdot 1 \cdot 2\cdot 1\cdot1 \left (1^2\cdot 1^2+ 1^2 \cdot 2^2 \right) = 5\sqrt{34} + 20$

$Z_3 = 1^2 \cdot 1^2 - 1\cdot 1^2 \cdot 2^2 = -3$.

So

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

Using the same formulae, the point P₄ = [2]P₁ is obtained:

$X_3 = 1\cdot1\cdot\sqrt{2} + \sqrt{2}\cdot1\cdot1 = 2\sqrt{2}$

$Y_3 = \left (1+1\cdot1 \right)\left (\sqrt{2}\cdot\sqrt{2} - 2\cdot 0 \cdot 1 \cdot 1\cdot 1\cdot1 \right ) + 2\cdot1 \left (1^2 \cdot 1^2 + 1^2 \cdot 1^2 \right ) = 8$

$Z_3 = 1^2 \cdot 1^2 - 1 \cdot 1^2 \cdot 1^2 = 0$

So

$P_4=(2\sqrt{2}:8:0)$.

Negation

The negation of a point P₁ = (X₁: Y₁: Z₁) is: −P₁ = (−X₁: Y₁: Z₁)

Alternative coordinates for the Jacobi quartic

There are other systems 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 introduce an additional curve parameter c satisfying a² + c² = 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\cdot X\cdot Z$

the Doubling-oriented XYZ coordinates, with the same additional assumption (a² + c² = 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\cdot X\cdot 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

Notes

1. Olivier Billet, The Jacobi Model of an Elliptic Curve and Side-Channel Analysis
2. P.Y.Liardet and N.P.Smart, Preventing SPA/DPA in ECC Systems Using the Jacobi Form, pag 397
3. Olivier Billet and Marc Joye, The Jacobi Model of an Elliptic Curve and Side-Channel Analysis, pag 37-38
4. Sylvain Duquesne, Improving the Arithmetic of Elliptic Curves in the Jacobi Model-I3M, (UMR CNRS 5149) and Lirmm, (UMR CNRS 5506), Universite Montpellier II

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