Cryptography on an elliptical curve

Abstract

A cryptographic calculation includes obtaining a point P(X,Y) from a parameter t on an elliptical curve Y.sup.2=f(X); and from polynomials X1(t), X2(t), X3(t) and U(t) satisfying: f(X1(t)).Math.f(X2(t)).Math.f(X3(t))=U(t).sup.2 in Fq, with q=3 mod 4. Firstly a value of the parameter t is obtained. Next, the point P is determined by: (i) calculating X1=X1(t), X2=X2(t), X3=X3(t) and U=U(t); (ii) if the term f(X1).Math.f(X2) is a square, then testing whether the term f(X3) is a square in Fq and if so calculating the square root of f(X3) in order to obtain the point P(X3); (iii) otherwise, testing whether the term f(X1) is a square and, if so, calculating the square root of f(X1) in order to obtain the point P(X1); (iv) otherwise, calculating the square root of f(X2) in order to obtain the point P(X2). This point P is useful in a cryptographic application.

Claims

1. An electronic component configured to execute a cryptographic calculation and to obtain a point P(X,Y) from at least one parameter t, on an elliptical curve that satisfies the equation: Y.sup.2=f(X) and from polynomials X.sub.1(t), X.sub.2(t), X.sub.3(t) and U(t) satisfying the following Skalba equality: f(X1(t)).Math.f(X2(t)).Math.f(X3(t))=U(t).sup.2 in a finite field F.sub.q, regardless of the parameter t, q satisfying the equation q=3 mod 4, wherein said electronic component is configured to: obtain a value of the parameter t; and determine the point P by: (i) calculating X.sub.1=X.sub.1(t), X.sub.2=X.sub.2(t), X.sub.3=X.sub.3(t) and U=U(t); (ii) if the term f(X1).Math.f(X2) is a squared term in the finite field Fq then testing whether the term f(X.sub.3) is a squared term in the finite field Fq and calculating the square root of the term f(X.sub.3), the point P having X.sub.3 as abscissa and the square root of the term f(X3) as ordinate; (iii) otherwise, testing whether the term f(X.sub.1) is a squared term in the finite field Fq and in this case, calculating the square root of the term f(X.sub.1), the point P having X.sub.1 as abscissa and the square root of the term f(X.sub.1) as ordinate; and (iv) otherwise, calculating the square root of the term f(X.sub.2), the point P having X.sub.2 as abscissa and the square root of the term f(X.sub.2) as ordinate; wherein said electronic component is further configured to use said point P in a cryptographic application selected from the group consisting of encryption or hashing or signature or authentication or identification, wherein the cryptographic calculation is an application of authentication or identification by a checking entity, and wherein obtaining the value of the parameter t further comprises: /a/ generating a random value; /b/ obtaining an encrypted value by encrypting said random value based on an encryption function using an encryption key determined from a password or identifier corresponding to the parameter; and /c/ transmitting the encrypted value to the checking entity.

2. The electronic component according to claim 1, wherein in order to determine the point P said electronic component is further configured to: calculate R.sub.1 such that: $R_1={\left(f\left(X_1\right).Math.f\left(X_2\right)\right)}^{\frac{q+1}{4}};$ if R.sub.1.sup.2 is equal to f(X1).Math.f(X.sub.2), then decide whether the term f(X1).Math.f(X.sub.2)is a squared term in the field F.sub.q; and test whether the term f(X.sub.1) is a squared term in the finite field F.sub.q by: calculating R.sub.2 such that: $R_2^{}={f\left(X_1\right)}^{q-1-\frac{q+1}{4}};$ calculating R.sub.3 such that:
R.sub.3=R.sub.2.sup.2; and calculating R.sub.4 such that:
R.sub.4=R.sub.3.Math.f(X.sub.1) if R.sub.4 is not equal to 1, obtain the square roof of the term f(X.sub.2) from the following equation:
{square root over (f(X.sub.2))}=R.sub.1.Math.R.sub.2.

3. The electronic component according to claim 1, wherein the polynomials that satisfy Skalba's equality are expressed in Jacobian coordinates according to which the point P(X,Y) is written P(X,Y,Z) such that:
X=X.Math.Z.sup.2,
Y=Y.Math.Z.sup.3 wherein the function f is written f.sub.z(X) and satisfies :
f.sub.z(X)=X.sup.3+a.Math.X.Math.Z.sup.4+b.Math.Z.sup.6 with the elliptical curve satisfying the equation:
Y.sup.2=f.sub.z(X) in which the polynomials that satisfy Skalba's equality expressed in Jacobian coordinates are X.sub.1 (t), X.sub.2(t), X.sub.3(t), Z(t) and U(t) and satisfy Skalba's equality in Jacobian coordinates:
U(t).sup.2=f.sub.Z(t)(X.sub.1(t)).Math.f.sub.Z(t)(X.sub.2(t)).Math.f.sub.Z(t)(X.sub.3,(t)) and in which Z(t) is determined in such a way that operations of inversion are transformed into operations of multiplication.

4. The electronic component according to claim 1, wherein the polynomials that satisfy Skalba's equality are such that it is possible to set a value of X.sub.3(t) for any possible t, such that f(X.sub.3(t)) is never a squared term in Fq, and wherein when determining the point P, the term f(X.sub.1).Math.f(X.sub.2) is not a squared term in the finite field F.sub.q, wherein determining the point P further comprises testing whether the term f(X.sub.1) is a squared term in the finite field F.sub.q by: calculating R.sub.2 such that: $R_2^{}={f\left(X_1\right)}^{q-1-\frac{q+1}{4}};$ calculating R.sub.3 such that:
R.sub.3=R.sub.2.sup.2; and calculating R.sub.4 such that:
R.sub.4=R.sub.3.Math.f(X.sub.1) wherein, if R.sub.4 is not equal to 1, determining the point P further comprises obtaining the square root of the term f(X.sub.2) according to the following equation:
{square root over (f(X.sub.2))}=R.sub.1.Math.R.sub.2 where $R_1={\left(f\left(X_1\right).Math.f\left(X_2\right)\right)}^{\frac{q+1}{4}}$ in which R1 is obtained beforehand from the following equation: $R_1={\left(f\left(X\right).Math.f\left(X_2\right)\right)}^{\frac{q+1}{4}}=U.Math.{f\left(u\right)}^{q-1-\frac{q+1}{4}}.$

5. The electronic component according to claim 4, wherein the polynomials that satisfy Skalba's equality are expressed in Jacobian coordinates according to which the point P(X,Y) is written P(X,Y,Z) such that:
X=X.Math.Z.sup.2,
Y=Y.Math.Z.sup.3 where the function f is written f.sub.z(X) and satisfies:
f.sub.z(X)=X.sup.3+a.Math.X.Math.Z.sup.4+b.Math.Z.sup.6 with the elliptical curve satisfying the equation:
Y.sup.2=f.sub.z(X) in which the polynomials that satisfy Skalba's equality expressed in Jacobian coordinates are X1(t), X2(t), Z(t) and U(t) and satisfy Skalba's equality in Jacobian coordinates:
U(t).sup.2=f.sub.Z(t)(X.sub.1(t)).Math.f.sub.Z(t)(X.sub.2(t)).Math.f(X.sub.3(t)) and in which Z(t) is determined in such a way that operations of inversion are transformed into operations of multiplication.

6. The electronic component according to claim 1, wherein obtaining the value of the parameter t comprises obtaining the value of the parameter t as a function of a password or an identifier.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The invention will also be better understood with the aid of the following figures:

(2) FIG. 1 shows the main steps of a method of execution of a cryptographic calculation according to one embodiment of the present invention;

(3) FIG. 2 shows a method of execution of a cryptographic calculation in detail according to one embodiment of the present invention;

(4) FIG. 3 shows a method of execution of a cryptographic calculation in detail according to one embodiment of the present invention in the particular case of Ulas polynomials;

(5) FIG. 4 shows the processing steps performed by an electronic component used to execute the cryptographic calculation according to one embodiment of the present invention;

(6) FIG. 5 is a block diagram showing the elements of an electronic component used to perform the processing shown in FIGS. 1-4.

DETAILED DESCRIPTION OF THE DRAWINGS

(7) FIG. 1 shows the main steps of a method of execution of a calculation according to one embodiment of the present invention.

(8) These main steps are suitable for determining a point on an elliptical curve with the aim of using said point in a cryptographic application. A cryptographic calculation of this kind can be executed in an electronic component in a secure manner, i.e. without the determination of this point giving any information on the point determined. FIGS. 4 and 5 provide further details regarding the processing performed by the electronic component (FIG. 4), and the elements used to implement the electronic component (FIG. 5).

(9) This calculation comprises, in a finite field Fq, where q is equal to 3 mod 4, a step of obtaining a point P(X,Y) on an elliptical curve satisfying the equation:
Y.sup.2=f(X)

(10) A point P(X,Y) has its abscissa X which corresponds to one of X1(t), X2(t) and X3(t), for a value of t obtained, such that:
f(X.sub.1(t)).Math.f(X.sub.2(t)).Math.f(X.sub.3(t))=U.sup.2(t)(2)

(11) where X1(t), X2(t), X3(t) and U(t) are polynomials satisfying Skalba's equation in the finite field Fq.

(12) More precisely, the polynomials that satisfy Skalba's equality, as defined in the document Rational points on certain hyperelliptic curves over finite fields by Maciej Ulas, dated 11 Jun. 2007 are functions of two parameters u and t. In the context of the present invention, one of the parameters can advantageously be set and consequently the polynomials satisfying Skalba's equation are then functions of a single parameter t.

(13) In order to determine a point on the curve, we try to determine, for given input parameters u and t, those among the values X1=X1(t,u), X2=X2(t,u), X3=X3(t,u) that correspond to a squared term in the finite field Fq. For this purpose, application of two different processings is advantageously envisaged depending on whether or not the term f(X1).Math.f(X2) is a squared term in the finite field Fq.

(14) At an initial step 100, the parameter t is taken into account and we calculate:
Xi=Xi(t) for i between 1 and 3,
and
U=U(t)

(15) At a step 11, we decide whether this product f(X1).Math.f(X2) is a squared term. This decision can be based on previous calculations or can be based on a check during application of the method. If the term f(X1).Math.f(X2) is a squared term then the term f(X3) is also a squared term. In this case it is envisaged to calculate the square root of the term f(X3), at a step 12. At a step 16, the point P thus determined has X3 as abscissa and Y3 as ordinate satisfying the following equation:
Y.sub.3={square root over (f(X3))}

(16) It should be noted that if the product f(X1).Math.f(X2) is a squared term, it follows that the term f(X3) is also a squared term. However, in order to keep determination of a point on the elliptical curve to a constant time, application of a test 10 is envisaged, so as to check that the term f(X3) is actually a squared term. This test 10 makes it possible to guarantee application of the method according to one embodiment of the present invention in a constant time.

(17) In the other case, i.e. when the term f(X1).Math.f(X2) is not a squared term, we can deduce from this that either f(X1), or f(X2) is a squared term. We can therefore envisage checking, firstly, whether the term f(X1) is a squared term at a step 13. If the test is positive, its square root is then calculated at a step 14 in order to obtain the abscissa of the point P:
Y.sub.1={square root over (f(X.sub.1))}

(18) At a step 17, we then obtain the point P which has X1 as ordinate and Y1 as abscissa.

(19) If the test at step 13 is negative, it can then be deduced from this that the term f(X2) is a squared term. Consequently, at a step 15 we obtain the abscissa Y2 of a point P on the elliptical curve according to the equation:
Y.sub.2={square root over (f(X.sub.2))}

(20) A point P(X2, Y2) of the curve can thus be supplied at a step 18.

(21) It should be noted that reaching steps 16, 17 or 18 for obtaining a point on the elliptical curve according to one embodiment of the present invention requires similar operations. Thus, regardless of the input parameters t and u, it is not possible to launch an attack on the basis of the time elapsed.

(22) The point P(Xi,Yi), for an i between 1 and 3, can then be used advantageously in a cryptographic application of encryption or hashing or signature or authentication or identification, since its determination has not supplied any element that can break its secret.

(23) In the field Fq, q corresponding to 3 mod 4, it is possible to check whether a term is a squared term in various ways. The tests for a squared term such as tests 10 and 13 in FIG. 1 can be performed as follows. In one embodiment of the present invention, when trying to determine whether a term A is a squared term in Fq, the following steps can be executed:

(24) $\begin{array}{cc}{W}_{1^{}}=\frac{1}{A_4^{q+1}}=A_4^{q-1-q+1}& \left(i\right)\end{array}$
W.sub.2=W.sub.1.sup.2(ii)
W.sub.3=W.sub.2.Math.A(iii)

(25) Finally, if term A is a squared term then: W1 corresponds to the reciprocal of the square root of A, i.e. ||JA, since an exponentiation at (q1) corresponds to an inversion and an exponentiation at (q+1)/4 corresponds to a square root in the finite field Fq; W2 corresponds to the inverse of A; and W3 corresponds to the value 1.

(26) Thus, when W3 is equal to the value 1, it is concluded from this that the term A is a squared term in the finite field Fq. If A is not a squared term then W3 is not equal to 1.

(27) FIG. 2 illustrates the implementation of a method of execution of a calculation according to one embodiment of the present invention.

(28) In one embodiment of the present invention, at a step 201, the following multiplication is performed:
Ro=f(X1).Math.f(X2) Then it is checked whether this term Ro is a squared term by applying steps (iv) and (v). Thus, at a step 202, we calculate: .sub.RR (q+1)14 Then, at step 203, we determine whether the following equation is satisfied:
R.sub.1.sup.2=R.sub.0(v)

(29) It is decided whether the term Ro, equal to f(X1).Math.f(X2), is a squared term or not. In the case where the term Ro is a squared term, a test is applied with the aim of determining whether the term f(X3) is a squared term. The result of the latter test is known beforehand since if Ro is a squared term, then this test is positive. However, for the purpose of ensuring a constant time, it is advisable to apply it according to steps (i) to (iii).

(30) Thus, at a step 204, the following calculation is performed:
R2=f(X3)(q.sup.1(q.sup.1|.sup.4|

(31) Here, R2 corresponds to calculation of the reciprocal of the square root of f(X3), in the case when f(X3) is a squared term.

(32) Then, at a step 205, the following equation is calculated:
R.sub.3=R.sub.2.sup.2

(33) Here, R3 corresponds to the inverse of f(X3).

(34) Then, at a step 206, R3 is multiplied by the term f(X3), obtaining a term R4. As we know that f(X3) is a squared term, we also know that the term R4 is equal to 1. These steps 205 and 206 are employed in order to guarantee determination of a point P on the elliptical curve in a constant time.

(35) At a step 207, it is therefore tested whether the term R4 corresponds to 1. In the present case, this test is always positive, since it follows from test 203.

(36) Then, at a step 208, the following calculation is performed:
Rs=R2.Math.f(X3)

(37) Here, a point P on the curve is obtained which has X3 as abscissa and, as ordinate, the square root of f(X3), i.e. the value Rs.

(38) In the case when, at step 11, it is decided that the term f(X1).Math.f(X2) is not a squared term, then either the term f(X1) or the term f(X2) is a squared term.

(39) Next it is a matter of determining which of these two terms f(X1) and f(X2) corresponds to a squared term.

(40) For this purpose, operations similar to those described previously are carried out, except that in this case, the term f(X1) need not be a squared term.

(41) At a step 211, the following equation is calculated:
R2=f(X1).sub.q.sup.1(q+.sup.1|.sup.4

(42) In the case when f(X1) is a squared term, R2 corresponds to the value of the reciprocal of the square root of f(X1) as described for step (i). Then this last-mentioned term is squared, at a step 212:
R.sub.3=R.sub.2.sup.2

(43) in order to obtain the inverse of f(X1) in the case when f(X1) would be a squared term.

(44) Thus, on multiplying R3 by the term f(X1), we obtain R4 at a step 213, which has the value 1 if the term f(X1) is actually a squared term. In this case, the test carried out at a step 214, during which the term R4 is compared with the value 1, is positive.

(45) Then, the following calculation is performed at a step 215:
Rs=R2.Math.f(X1)

(46) The term Rs then corresponds to f(X1).

(47) A point P on the curve is obtained with X1 as abscissa and R's as ordinate.

(48) In the case when test 214 is negative, the term f(X1) is not a squared term. Then, it follows from this that the squared term in Skalba's equation (2) is the term f(X2). In this case, at a step 216, the following calculation is performed:
R.sub.5=R.sub.1.Math.R.sub.2

(49) It should be noted that the above equation makes it possible to obtain advantageously the square root of f(X2) but without carrying out an operation of exponentiation such as that carried out at step 204 or also at step 211. In fact, here it is, ingeniously, a matter of performing a multiplication instead of an exponentiation.

(50) We then obtain Rs, which corresponds to the term f(X2), supplied at a step 216. Thus, a point P on the elliptical curve has been determined which has X2 as abscissa and Rs as ordinate.

(51) In the embodiment described previously with reference to FIG. 2, regardless of the determination of point P, i.e. whether this determination is based on the value X1 or X2 or X3, similar calculations are employed, thus ensuring determination of a point on the elliptical curve in a constant time.

(52) More precisely, two operations of exponentiation are employed, one exponentiation at step 202 and another exponentiation at step 204 or 211 depending on the result of test 203. Thus, it is no longer necessary to perform four exponentiations to determine a point on a curve in the context of Skalba polynomials in a constant time.

(53) In one embodiment of the present invention, it is possible to select polynomials that satisfy Skalba's equality in such a way that the polynomial f(X3(t)) can never correspond to a squared term whatever the value of t. In this case, Skalba's equation:
f(X.sub.1(t)).Math.f(X.sub.2(t)).Math.f(X.sub.3(t))=U.sup.2(t)(2)

(54) can be written in the form:
f(X.sub.1(t)).Math.f(X.sub.2(t)).Math.f(X.sub.3(t)).sub.4.sup.q+1=U(t)2).sub.4.sup.q+1=U(t)

(55) then also in the form:

(56) ${\left(f\left(X_1\left(t\right)\right).Math.f\left(X_2\left(t\right)\right)\right)}^{\begin{array}{c}q+1\\ 4\end{array}}\frac{U\left(t\right)}{{f\left(X3\left(t\right)\right)}^{\begin{array}{c}q+1\\ 4\end{array}}}$

(57) and also as:

(58) $\begin{array}{cc}{\left(f\left(X1\left(t\right)\right).Math.f\left(X_2\left(t\right)\right)\right)}^{\begin{array}{c}q+1\\ 4\end{array}}=U\left(t\right).Math.({f\left(X_3\left(t\right)\right)}^{q-1\frac{q+1}{4}}& \left(4\right)\end{array}$

(59) All these equations are only valid if the condition q=3 mod 4 is satisfied. Now, if the term

(60) $({f\left(X_3\left(t\right)\right)}^{q-1\frac{q+1}{4}}$
of this last-mentioned equation corresponds to a set value, we are able to calculate the value of the term

(61) $R_1={\left(f\left(X_1\right).Math.f\left(X_2\right)\right)}^{\begin{array}{c}q+1\\ 4\end{array}}$
efficiently using the multiplication

(62) 0$U.Math.({f\left(X_3\left(t\right)\right)}^{q-1\frac{q+1}{4}}.$
In this case, a point on the elliptical curve can be determined using just one operation of exponentiation, that corresponding to step 204 of test 10, or that corresponding to step 211 of test 13, as appropriate.

(63) These conditions can be fulfilled using for example a set of polynomials satisfying Skalba's equation as described in the document Rational points on certain hyperelliptic curves over finite fields by Macie Ulas, dated 11 Jun. 2007. In this document, the polynomials satisfying Skalba's equation (2) are described:

(64) $X_1\left(t,u\right)=\underset{a}{\_\}\}\_}[1+\frac{1-J}{t^{4}f\left(u\right)+t^{2}f\left(u\right)}{X}_2\left(t,u\right)=t^{2}f\left(u\right)X_1\left(t,u\right)X_3\left(t,u\right)=uU\left(t,u\right)=t^3{f\left(u\right)}^{4}f\left(X_1\left(t,u\right)\right)\mathrm{where}f\left(u\right)=u3+\mathrm{au}+b$ where a and b are elements of Fq such that their product is not zero.

(65) Thus, by determining a value of u that is set and that does not correspond to a squared term in Fq, the value of R1 is then a set value that can be pre-calculated according to equation (4), for any determination of point P according to one embodiment of the present invention.

(66) FIG. 3 illustrates a method of execution of a cryptographic calculation in detail according to one embodiment of the present invention in the particular case of Ulas polynomials, for a set polynomial X3(t,u) according to one embodiment of the present invention. In this case, steps 211 to 216 alone can be employed. If step 216 is executed, then the value R1 can be recovered from a memory area as it was calculated previously.

(67) Accordingly, the number of exponentiations required for determining a point on the curve can be further reduced, to a single exponentiation, that which corresponds to test 10 or to test 13.

(68) In one embodiment of the present invention, the use of Jacobian coordinates is advantageously envisaged. This transformation to Jacobian coordinates makes it possible to transform the operations of inversion into operations of multiplication which are quicker and easier to apply. It should be noted that such an embodiment cannot be applied to all curves of the Skalba type, including to the particular case of Ulas curves.

(69) The equation of an elliptical curve:
X.sup.3+ax+b=Y2

(70) can be written in Jacobian coordinates:
X.sup.3+aXZ.sup.4+bZ.sup.6=Y.sup.2

(71) It should be noted that the coordinates of a point (X,Y) can be written in Jacobian coordinates (X,Y,Z) such that:
X=X.Math.Z2 and
Y=Y.Math.Z.sup.3

(72) We should therefore determine a polynomial Z(t,u) in such a way that the Jacobian coordinates X, Y and Z can be written without inversion.

(73) In the following sections, this transformation into Jacobian coordinates is applied to a particular case, that of Ulas curves as described previously.

(74) In this context, any operation of inversion is eliminated by taking:
Z(t,U)=a(t.sup.4f(u).sup.2+t.sup.2f(u))

(75) in which u is set.

(76) In fact, the Ulas polynomials can then be written in the following form in Jacobian coordinates:
X\(t,u)=b.Math.Z(t,u)(t.sup.4f(u)2+t.sup.2f(u)+l)
X.sub.2(t,u)=t.sup.2.Math.f(u).Math.X.sub.1(t,u)
X.sub.3(t,u)=u

(77) It should therefore be noted that there is no longer any inversion in Jacobian coordinates. As this operation can be as costly as an exponentiation, these coordinates permit a significant improvement in calculation time.

(78) Then, to obtain the Jacobian coordinate Y, it is advisable to calculate U(t,u), the equivalent of U(t,u) in Jacobian coordinates.

(79) In this context, in classical coordinates we have:
U(t,u).sup.2=f(X.sub.1(t,u)).Math.f(X.sub.2(t,u)).Math.f(X.sub.3(t,u))

(80) We can then write in Jacobian coordinates:
U(t,u).sup.2=f(X.sub.1(t,u)|Z(t,u)2).Math.f(X.sub.2(t,u)|Z(t,u)2).Math.f(X.sub.3(t,u)|Z(t,u)2)

(81) By writing:
f=(t)(X)=X.sup.3+a.Math.X.Math.Z(t).sup.4+b.Math.Z(t).sup.6=Z.sup.6.Math.f( ) we obtain the following equation:
Z.sup.18(t,u).Math.U(t,u).sup.2=(Z(t,u).sup.9.Math.U(t,u).sup.2=fz(t,u)(Xi(t,u)).Math.fz(t,u(X.sup.2(t,u)).Math.f z(X.sub.3(t,u))

(82) Then:
U(t,u)=Z(t,u).sup.9.Math.U(t,u) where U(t,u) is the expression of U(t,u) in Jacobian coordinates.

(83) In the case where it is considered that U(t,u) satisfies the equation:
U(t,u)=t.sup.3.Math.f(u).sup.2.Math.|(X.sub.2(t,u)) we can then write:
U(t,u)=t.sup.3.Math.f(u)2.Math.fz(t,u)(X.sub.2(t,u))Z(t,u).sup.3 Skalba's equality becomes, in Jacobian coordinates:
U(t,u).sup.2=Jz(t,u)(X\(t,u)).Math.Jz(t,u)(X.sub.2(t,u)),Jz(t,u)(X.sub.3(t,u))

(84) Nevertheless, as in the case of Ulas polynomials it is possible to require

(85) that x3(t,u) is such that fz(t,u)(X3(t,u) is never a square. In this case, we have:
U(t,u)=t.sup.3.Math.f(u)2.Math.fZ(t,u)(X.sub.2(t,U))

(86) and the corresponding Skalba equality is:
U(t,u).sup.2=fz(t,u)(Xi(t,u)).Math.fz(t,u)(X.sub.2(t,u)).Math.f(X.sub.3(t,u))

(87) The present invention can advantageously be implemented in any type of cryptographic calculation using elliptical curves. It can in particular be advantageous in protocols for authentication by password, such as PACE (Password Authenticated Connection Establishment). In this case, it allows an improvement in calculation performance, while not allowing any attack linked to the execution time of the cryptographic calculation.

(88) The electronic component used to perform a disclosed cryptographic calculation may be any type of general purpose or dedicated computer which has been programed to receive the necessary inputs, perform the desired calculations, and provide the resulting output. By way of example, such a computer could be in the nature of a controller, micro-controller, field programmable gate array (FPGA), or application specific integrated circuit (ASIC).

(89) The processing performed by such electronic computer includes obtention 411 of a password identifier t which is provided as an input to obtain a point P(X,Y) 413 which is then used to perform a cryptographic calculation using one of the above-described cryptographic protocols according to one of the disclosed embodiments of an execution method according to the present invention.

(90) FIG. 5 discloses an electronic component of the type which may be utilized in the present invention. The electronic component includes a memory 513, a calculator 515 and an interface 517. It is much as such memory, calculator and interface are well known components of the type implemented in known channel purpose or dedicated computers, no further details are necessary in order for a person having ordinary skill in the art to implement such electronic component.

(91) The present invention can also be applied advantageously in the context of privacy protocols, such as those used for checking electronic identity documents, such as electronic passports.