Schlieren imaging: Difference between revisions
en>Magioladitis m clean up using AWB (8279) |
en>Settles1 mNo edit summary |
||
Line 1: | Line 1: | ||
{{Multiple issues| | |||
{{expert-subject|Mathematics|date=December 2009}} | |||
{{refimprove|date=December 2009}} | |||
{{cleanup|date=January 2010}} | |||
}} | |||
In [[mathematics]], the '''Jacobi curve''' is a representation of an [[elliptic curve]] different than the usual one ([[elliptic curve|Weierstrass equation]]). Sometimes it is used in [[cryptography]] instead of the Weierstrass form because it can provide a defence against [[Power analysis#Simple and differential power analysis|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.<ref>Olivier Billet, ''The Jacobi Model of an Elliptic Curve and Side-Channel Analysis''</ref> 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 [[Elliptic curve#The group law|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 (mathematics)|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 [[identity element|neutral element]] in the [[Elliptic curve#The group law|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 (mathematics)|field]] ''K'' can be put in the [[Elliptic curve|Weierstrass form]] ''y''<sup>2</sup> = ''x''<sup>3</sup> + ''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''<sup>3</sup> + ''ax'' + ''b''. | |||
From now on, we will use ''E<sub>a,b</sub>'' to denote the elliptic curve with Weierstrass form ''y''<sup>2</sup> = ''x''<sup>3</sup> + ''ax'' + ''b''. | |||
If ''E<sub>a,b</sub>'' is such that the cubic polynomial ''x''<sup>3</sup> + ''ax'' + ''b'' has three distinct roots in ''K'' we can write ''E<sub>a,b</sub>'' in the '''Legendre normal form''': | |||
:''E<sub>a,b</sub>:'' ''y''<sup>2</sup> = ''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 [[projective space|'''P'''<sup>3</sup>(''K'')]] can be represented as the [[Intersection (set theory)|intersection]] of two [[Quadric|quadric surfaces]]: | |||
: <math> Q: \{Q_1(X_0,X_1,X_2,X_3)=0\} \cap \{Q_2(X_0,X_1,X_2,X_3)=0\} </math> | |||
It is possible to define the Jacobi form of an elliptic curve as the intersection of two quadrics. Let ''E<sub>a,b</sub>'' be an elliptic curve in the Weierstrass form, we apply the following [[map (mathematics)|map]] to it: | |||
: <math>\Phi: (x,y) \mapsto (X,Y,Z,T) = (x,y,1,x^2) </math> | |||
We see that the following [[simultaneous equations|system of equations]] holds: | |||
:<math>\mathbf S: \begin{cases} | |||
X^2-TZ=0\\ | |||
Y^2-aXZ-bZ^2-TX=0 | |||
\end{cases}</math> | |||
The curve ''E[j]'' corresponds to the following intersection of [[surface]]s in '''P'''<sup>3</sup>(''K''): | |||
:<math>\mathbf S1: | |||
\begin{cases} | |||
X^2+Y^2-T^2=0\\ | |||
kX^2+Z^2-T^2=0 | |||
\end{cases}</math>. | |||
The "special case", ''E[0]'', the elliptic curve has a double point and thus it is [[singular point of an algebraic variety|singular]]. | |||
'''S1''' is obtained by applying to ''E[j]'' the [[map (mathematics)|transformation]]: | |||
:ψ: ''E[j]'' → '''S1''' | |||
: <math>(x,y) \mapsto (X,Y,Z,T)=(-2y,x^2-j,x^2+2jx+j,x^2+2x+j)</math> | |||
: <math>O=(0:1:0) \mapsto (0,1,1,1)</math> | |||
===Group law=== | |||
For '''S1''', the [[identity element|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''<sub>1</sub> = (''X''<sub>1</sub>, ''Y''<sub>1</sub>, ''Z''<sub>1</sub>, ''T''<sub>1</sub>) and ''P''<sub>2</sub> = (''X''<sub>2</sub>, ''Y''<sub>2</sub>, ''Z''<sub>2</sub>, ''T''<sub>2</sub>), two points on '''S1''', the [[Coordinate system|coordinates]] of the point ''P''<sub>3</sub> = ''P''<sub>1</sub> + ''P''<sub>2</sub> are: | |||
: <math>X_3 = T_1Y_2X_1Z_2 + Z_1X_2Y_1T_2</math> | |||
: <math>Y_3 = T_1Y_2Y_1T_2 - Z_1X_2X_1Z_2</math> | |||
: <math>Z_3 = T_1Z_1T_2Z_2 - kX_1Y_1X_2Y_2</math> | |||
: <math>T_3 = (T_1Y_2)^2 + (Z_1X_2)^2</math> | |||
These formulas are also valid for doubling: it sufficies to have ''P''<sub>1</sub> = ''P''<sub>2</sub>. 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''<sub>1</sub> and find ''P''<sub>3</sub> = [2]''P''<sub>1</sub>: | |||
: <math>X_3 = 2Y_1T_1Z_1X_1</math> | |||
: <math>Y_3 = (T_1Y_1)^2 - (T_1Z_1)^2 + (Z_1Y_1)^2</math> | |||
: <math>Z_3 = (T_1Z_1)^2 - (T_1Y_1)^2 + (Z_1Y_1)^2</math> | |||
: <math>T_3 = (T_1Z_1)^2 + (T_1Y_1)^2 - (Z_1Y_1)^2</math> | |||
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.<ref name="P.Y.Liardet and N.P.Smart">P.Y.Liardet and N.P.Smart, ''Preventing SPA/DPA in ECC Systems Using the Jacobi Form'', pag 397</ref> In this way it is possible to triple a point with 23 multiplications; indeed [3]''P''<sub>1</sub> can be obtained by adding ''P''<sub>1</sub> with [2]''P''<sub>1</sub> with a cost of 7 multiplications for [2]''P''<sub>1</sub> and 16 for ''P''<sub>1</sub> + [2]''P''<sub>1</sub><ref name="P.Y.Liardet and N.P.Smart"/> | |||
====Example of addition and doubling==== | |||
Let ''K'' = '''R''' or '''C''' and consider the case: | |||
:<math>\mathbf S1: | |||
\begin{cases} | |||
X^2+Y^2-T^2=0\\ | |||
4X^2+Z^2-T^2=0 | |||
\end{cases}</math> | |||
Consider the points <math>P_1=(1,\sqrt{3},0,2)</math> and <math>P_2=(1,2,1,\sqrt{5})</math>: it is easy to verify that ''P''<sub>1</sub> and ''P''<sub>2</sub> belong to '''S1''' (it is sufficient to see that these points satisfy both equations of the [[system of equations|system]] '''S1'''). | |||
Using the formulas given above for adding two points, the coordinates for ''P''<sub>3</sub>, where ''P''<sub>3</sub> = ''P''<sub>1</sub> + ''P''<sub>2</sub> are: | |||
: <math> X_3 = T_1Y_2X_1Z_2 + Z_1X_2Y_1T_2 = 4 </math> | |||
: <math> Y_3 = T_1Y_2Y_1T_2 - Z_1X_2X_1Z_2 = 4\sqrt{15}</math> | |||
: <math> Z_3 = T_1Z_1T_2Z_2 - kX_1Y_1X_2Y_2 = -8\sqrt{3}</math> | |||
: <math> T_3 = (T_1Y_2)^2 + (Z_1X_2)^2 = 16</math> | |||
The resulting point is <math>P_3=(4,4\sqrt{15},-8\sqrt{3},16)</math>. | |||
With the formulas given above for doubling, it is possible to find the point ''P''<sub>3</sub> = [2]''P''<sub>1</sub>: | |||
: <math> X_3 = 2Y_1T_1Z_1X_1 = 0</math> | |||
: <math> Y_3 = (T_1Y_1)^2 - (T_1Z_1)^2 + (Z_1Y_1)^2 = 12</math> | |||
: <math> Z_3 = (T_1Z_1)^2 - (T_1Y_1)^2 + (Z_1Y_1)^2 = -12</math> | |||
: <math> T_3 = (T_1Z_1)^2 + (T_1Y_1)^2 - (Z_1Y_1)^2 = 12</math> | |||
So, in this case ''P''<sub>3</sub> = [2]''P''<sub>1</sub> = (0, 12, –12, 12). | |||
====Negation==== | |||
Given the point ''P''<sub>1</sub> = (''X''<sub>1</sub>, ''Y''<sub>1</sub>, ''Z''<sub>1</sub>, ''T''<sub>1</sub>) in '''S1''', its [[additive inverse|negation]] is −''P''<sub>1</sub> = (−''X''<sub>1</sub>, ''Y''<sub>1</sub>, ''Z''<sub>1</sub>, ''T''<sub>1</sub>) | |||
====Addition and doubling in affine coordinates==== | |||
Given two affine points ''P''<sub>1</sub> = (''x''<sub>1</sub>, ''y''<sub>1</sub>, ''z''<sub>1</sub>) and ''P''<sub>2</sub> = (''x''<sub>2</sub>, ''y''<sub>2</sub>, ''z''<sub>2</sub>), their sum is a point ''P''<sub>3</sub> with coordinates: | |||
:<math>x_3 = \frac{y_2x_1z_2 + z_1x_2y_1}{(y_2^2 + (z_1x_2)^2)}</math> | |||
:<math>y_3 = \frac{y_2y_1-z_1x_2x_1z_2}{(y_2^2+(z_1x_2)^2)}</math> | |||
:<math>z_3 = \frac{z_1z_2-ax_1y_1x_2y_2}{(y_2^2+(z_1x_2)^2)}</math> | |||
These formulas are valid also for doubling with the condition ''P''<sub>1</sub> = ''P''<sub>2</sub>. | |||
====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: | |||
:<math>\mathbf S1: | |||
\begin{cases} | |||
x^2+y^2=1\\ | |||
kx^2+z^2=1 | |||
\end{cases}</math> | |||
the '''extended coordinates''' describe a point ''P'' = ''(x, y, z)'' with the variables ''X, Y, Z, T, XY, ZT'', where: | |||
:<math>x = X/T</math> | |||
:<math>y = Y/T</math> | |||
:<math>z = Z/T</math> | |||
:<math>XY = X\cdot Y</math> | |||
:<math>ZT = Z\cdot T</math> | |||
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== | |||
[[Image:JacobianQuartic.svg|300px|right|thumb|A Jacobi quartic of [[equation]] <math>y^2=x^4-1.9x^2+1</math>]] | |||
An elliptic curve in '''Jacobi quartic''' form can be obtained from the curve ''E<sub>a,b</sub>'' in the Weierstrass form with at least one point of order 2. The following [[map (mathematics)|transformation]] ''f'' sends each point of ''E<sub>a,b</sub>'' to a point in the Jacobi coordinates, where ''(X: Y: Z)'' = ''(sX: s<sup>2</sup>Y: sZ)''. | |||
: ''f:'' ''E<sub>a,b</sub>'' → '''J''' | |||
: <math>(p,0) \mapsto (0:-1:1)</math> | |||
: <math>(x,y)\neq (p,0) \mapsto (2(x-p) : (2x+p)(x-p)^2- y^2: y)</math> | |||
: <math>O \mapsto (0 :1 :1)</math><ref name="Olivier Billet and Marc Joye">Olivier Billet and Marc Joye, ''The Jacobi Model of an Elliptic Curve and Side-Channel Analysis'', pag 37-38</ref> | |||
Applying ''f'' to ''E<sub>a,b</sub>'', one obtains a curve in '''J''' of the following form: | |||
: <math>C :\ Y^2= eX^4-2dX^2Z^2+ Z^4</math><ref name="Olivier Billet and Marc Joye"/> | |||
where: | |||
:<math>e=\frac{-( 3p^2+4a)}{16}, \ \ d=\frac{3p}{4}</math>. | |||
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: | |||
:<math>y^2 = ex^4 + 2ax^2 + 1</math>, | |||
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 <math>P_1=(x_1,y_1)</math> and <math>P_2=(x_2,y_2)</math>, their sum is a point <math>P_3=(x_3,y_3)</math>, such that: | |||
:<math>x_3 = \frac{x_1y_2+y_1x_2}{1-(x_1x_2)^2}</math> | |||
:<math>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}</math> | |||
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''<sub>1</sub> = (''X''<sub>1</sub>: ''Y''<sub>1</sub>: ''Z''<sub>1</sub>) and ''P''<sub>2</sub> = (''X''<sub>2</sub>: ''Y''<sub>2</sub>: ''Z''<sub>2</sub>) in ''C′'', the coordinates for the point ''P''<sub>3</sub> = (''X''<sub>3</sub>: ''Y''<sub>3</sub>: ''Z''<sub>3</sub>), where ''P''<sub>3</sub> = ''P''<sub>1</sub> + ''P''<sub>2</sub>, are given in terms of ''P''<sub>1</sub> and ''P''<sub>2</sub> by the formulae: | |||
: <math>X_3 = X_1Z_1Y_2 + Y_1X_2Z_2</math> | |||
: <math>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 )</math> | |||
: <math>Z_3 = Z_1^2 Z_2^2 - eX_1^2 X_2^2 </math> | |||
One can use this formula also for doubling, with the condition that ''P''<sub>2</sub> = ''P''<sub>1</sub>: in this way the point ''P''<sub>3</sub> = ''P''<sub>1</sub> + ''P''<sub>1</sub> = [2]''P''<sub>1</sub> 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 <ref>Sylvain Duquesne, ''Improving the Arithmetic of Elliptic Curves in the Jacobi Model''-I3M, (UMR CNRS 5149) and Lirmm, (UMR CNRS 5506), Universite Montpellier II</ref> 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<sub>4,0</sub>'', 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: | |||
: <math>C:\ Y^2 = X^4 + Z^4</math> | |||
Choosing two points <math>P_1=(1:\sqrt{2}:1)</math> and <math>P_2=(2:\sqrt{17}:1)</math>, it is possible to find their sum ''P''<sub>3</sub> = ''P''<sub>1</sub> + ''P''<sub>2</sub> using the formulae for adding given above: | |||
: <math>X_3 = 1\cdot1\cdot\sqrt{17} + \sqrt{2}\cdot2\cdot1 = \sqrt{17} + 2\sqrt{2}</math> | |||
: <math>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</math> | |||
: <math>Z_3 = 1^2 \cdot 1^2 - 1\cdot 1^2 \cdot 2^2 = -3</math>. | |||
So | |||
:<math>P_3=(\sqrt{17}+2\sqrt{2}:5\sqrt{34}+20:-3)</math>. | |||
Using the same formulae, the point ''P''<sub>4</sub> = [2]''P''<sub>1</sub> is obtained: | |||
:<math>X_3 = 1\cdot1\cdot\sqrt{2} + \sqrt{2}\cdot1\cdot1 = 2\sqrt{2}</math> | |||
:<math>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</math> | |||
:<math>Z_3 = 1^2 \cdot 1^2 - 1 \cdot 1^2 \cdot 1^2 = 0</math> | |||
So | |||
:<math>P_4=(2\sqrt{2}:8:0)</math>. | |||
====Negation==== | |||
The negation of a point ''P''<sub>1</sub> = (''X''<sub>1</sub>: ''Y''<sub>1</sub>: ''Z''<sub>1</sub>) is: −''P''<sub>1</sub> = (−''X''<sub>1</sub>: ''Y''<sub>1</sub>: ''Z''<sub>1</sub>) | |||
===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 | |||
:<math>y^2 = x^4 + 2ax^2 + 1</math> | |||
the '''Doubling-oriented ''XXYZZ'' coordinates''' introduce an additional curve parameter ''c'' satisfying ''a''<sup>2</sup> + ''c''<sup>2</sup> = 1 and they represent a point ''(x, y)'' as ''(X, XX, Y, Z, ZZ, R)'', such that: | |||
:<math>x = X/Z</math> | |||
:<math>y = Y/ZZ</math> | |||
:<math>XX = X^2</math> | |||
:<math>ZZ = Z^2</math> | |||
:<math>R = 2\cdot X\cdot Z</math> | |||
the '''Doubling-oriented ''XYZ'' coordinates''', with the same additional assumption (''a''<sup>2</sup> + ''c''<sup>2</sup> = 1), represent a point ''(x, y)'' with ''(X, Y, Z)'' satisfying the following equations: | |||
:<math>x = X/Z</math> | |||
:<math>y = Y/Z^2</math> | |||
Using the '''''XXYZZ'' coordinates''' there is no additional assumption, and they represent a point ''(x, y)'' as ''(X, XX, Y, Z, ZZ)'' such that: | |||
:<math>x = X/Z</math> | |||
:<math>y = Y/ZZ</math> | |||
:<math>XX = X^2</math> | |||
:<math>ZZ = Z^2</math> | |||
while the '''XXYZZR coordinates''' represent ''(x, y)'' as ''(X, XX, Y, Z, ZZ, R)'' such that: | |||
:<math>x = X/Z</math> | |||
:<math>y = Y/ZZ</math> | |||
:<math>XX = X^2</math> | |||
:<math>ZZ = Z^2</math> | |||
:<math>R = 2\cdot X\cdot Z</math> | |||
with the '''XYZ coordinates''' the point ''(x, y)'' is given by ''(X, Y, Z)'', with: | |||
:<math>x = X/Z</math> | |||
:<math>y = Y/Z^2</math>. | |||
==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 == | |||
{{reflist}} | |||
==References== | |||
* {{cite book | |||
| author = Olivier Billet, Marc Joye | |||
| year = 2003 | |||
| title = The Jacobi Model of an Elliptic Curve and the Side-Channel Analysis | |||
| publisher = Springer-Verlag Berlin Heidelberg 2003 | |||
| url = http://www.springerlink.com/content/p0013kgt6xpulkvb/fulltext.pdf | |||
| isbn = 978-3-540-40111-7 | |||
}} | |||
* {{cite book | |||
| author = P.Y. Liardet, [[Nigel Smart (Cryptographer)|N.P. Smart]] | |||
| year = 2001 | |||
| title = Preventing SPA/DPA in ECC Systems Using the Jacobi Form | |||
| publisher = Springer-Verlag Berlin Heidelberg 2001 | |||
| url = http://www.springerlink.com/content/h3bhhlxn9qbg05pj/fulltext.pdf | |||
| isbn = 978-3-540-42521-2 | |||
}} | |||
*http://hyperelliptic.org/EFD/index.html | |||
[[Category:Elliptic curves]] | |||
[[Category:Elliptic curve cryptography]] |
Latest revision as of 22:06, 9 November 2013
Template:Multiple issues In mathematics, the Jacobi curve is a representation 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.[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 y2 = x3 + 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) = x3 + ax + b.
From now on, we will use Ea,b to denote the elliptic curve with Weierstrass form y2 = x3 + ax + b.
If Ea,b is such that the cubic polynomial x3 + ax + b has three distinct roots in K we can write Ea,b in the Legendre normal form:
- Ea,b: y2 = 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 P3(K) can be represented as the intersection of two quadric surfaces:
It is possible to define the Jacobi form of an elliptic curve as the intersection of two quadrics. Let Ea,b be an elliptic curve in the Weierstrass form, we apply the following map to it:
We see that the following system of equations holds:
The curve E[j] corresponds to the following intersection of surfaces in P3(K):
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:
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 P1 = (X1, Y1, Z1, T1) and P2 = (X2, Y2, Z2, T2), two points on S1, the coordinates of the point P3 = P1 + P2 are:
These formulas are also valid for doubling: it sufficies to have P1 = P2. 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 P1 and find P3 = [2]P1:
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]P1 can be obtained by adding P1 with [2]P1 with a cost of 7 multiplications for [2]P1 and 16 for P1 + [2]P1[2]
Example of addition and doubling
Let K = R or C and consider the case:
Consider the points and : 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 P3, where P3 = P1 + P2 are:
With the formulas given above for doubling, it is possible to find the point P3 = [2]P1:
So, in this case P3 = [2]P1 = (0, 12, –12, 12).
Negation
Given the point P1 = (X1, Y1, Z1, T1) in S1, its negation is −P1 = (−X1, Y1, Z1, T1)
Addition and doubling in affine coordinates
Given two affine points P1 = (x1, y1, z1) and P2 = (x2, y2, z2), their sum is a point P3 with coordinates:
These formulas are valid also for doubling with the condition P1 = P2.
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:
the extended coordinates describe a point P = (x, y, z) with the variables X, Y, Z, T, XY, ZT, where:
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
An elliptic curve in Jacobi quartic form can be obtained from the curve Ea,b in the Weierstrass form with at least one point of order 2. The following transformation f sends each point of Ea,b to a point in the Jacobi coordinates, where (X: Y: Z) = (sX: s2Y: sZ).
- f: Ea,b → J
- [3]
Applying f to Ea,b, one obtains a curve in J of the following form:
where:
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:
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 and , their sum is a point , such that:
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 P1 = (X1: Y1: Z1) and P2 = (X2: Y2: Z2) in C′, the coordinates for the point P3 = (X3: Y3: Z3), where P3 = P1 + P2, are given in terms of P1 and P2 by the formulae:
One can use this formula also for doubling, with the condition that P2 = P1: in this way the point P3 = P1 + P1 = [2]P1 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 E4,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:
Choosing two points and , it is possible to find their sum P3 = P1 + P2 using the formulae for adding given above:
So
Using the same formulae, the point P4 = [2]P1 is obtained:
So
Negation
The negation of a point P1 = (X1: Y1: Z1) is: −P1 = (−X1: Y1: Z1)
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
the Doubling-oriented XXYZZ coordinates introduce an additional curve parameter c satisfying a2 + c2 = 1 and they represent a point (x, y) as (X, XX, Y, Z, ZZ, R), such that:
the Doubling-oriented XYZ coordinates, with the same additional assumption (a2 + c2 = 1), represent a point (x, y) with (X, Y, Z) satisfying the following equations:
Using the XXYZZ coordinates there is no additional assumption, and they represent a point (x, y) as (X, XX, Y, Z, ZZ) such that:
while the XXYZZR coordinates represent (x, y) as (X, XX, Y, Z, ZZ, R) such that:
with the XYZ coordinates the point (x, y) is given by (X, Y, Z), with:
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
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
- 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
My blog: http://www.primaboinca.com/view_profile.php?userid=5889534 - 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
My blog: http://www.primaboinca.com/view_profile.php?userid=5889534 - http://hyperelliptic.org/EFD/index.html
- ↑ Olivier Billet, The Jacobi Model of an Elliptic Curve and Side-Channel Analysis
- ↑ 2.0 2.1 P.Y.Liardet and N.P.Smart, Preventing SPA/DPA in ECC Systems Using the Jacobi Form, pag 397
- ↑ 3.0 3.1 Olivier Billet and Marc Joye, The Jacobi Model of an Elliptic Curve and Side-Channel Analysis, pag 37-38
- ↑ Sylvain Duquesne, Improving the Arithmetic of Elliptic Curves in the Jacobi Model-I3M, (UMR CNRS 5149) and Lirmm, (UMR CNRS 5506), Universite Montpellier II