CRYPTOGRAPHY ON A SIMPLIFIED 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 satisfying: f(X.sub.1(t)).Math.f(X.sub.2(t))=U(t).sup.2 in the finite body Fq, irrespective of the parameter t, q=3 mod 4. A value of the parameter t is obtained and the point P is determined by: (i) calculating X.sub.1=X.sub.1(t), X.sub.2=X.sub.2(t) and U=U(t); (ii) testing whether the term f(X1) is a squared term in the finite body Fq and, if so, calculating the square root of the term f(X1), the point P having X.sub.1 as abscissa and Y.sub.1, the square root of the term f(X.sub.1), as ordinate; (iii) otherwise, calculating the square root of the term f(X.sub.2), the point P having X.sub.2, as abscissa and Y.sub.2, the square root of the term f(X.sub.2), as ordinate. The point P is useful in encryption, scrambling, signature, authentication or identification cryptographic applications.

Claims

1. An electronic component configured to execute a cryptographic calculation and obtain a point P(X,Y) from at least one parameter t, on an elliptical curve that satisfies the equation: Y.sub.2=f(X) and from polynomials X.sub.1(t), X.sub.2(t), and U(t) satisfying the following equality: f(X.sub.1(t))f(X.sub.2(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, said electronic component configured to: obtain a value of the parameter t; determine the point P by: (i) calculating X.sub.1=X.sub.1(t), X.sub.2=X.sub.2(t) and U=U(t) (ii) testing whether the term f(X.sub.1) is a squared term in the finite field F.sub.q and in this case calculating the square root of the term f(X.sub.1), point P having X.sub.1 as abscissa and the square root of the term f(X.sub.1) as ordinate Y.sub.1; (iii) otherwise calculating the square root of the term f(X.sub.2), point P having X.sub.2 as abscissa and the square root of the term f(X.sub.2) as ordinate Y.sub.2; and 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 to generate at least one of a secret key, a secret signature and an encrypted message for a user of said device, wherein the cryptographic calculation is an application of authentication or identification by a checking entity, and wherein said electronic component in obtaining the value of the parameter t is further configured to: /a/ generate a random value; /b/ obtain 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/ transmit 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 R1 such that: $R_1=f\left(X_1\right).Math.\frac{q-1}{2}$ If the calculated R.sub.1 is equal to 1, decide that the term f(X.sub.1) is a squared term in the finite field F.sub.q; and otherwise, calculate the ordinate $Y_2={f\left(X_2\right)}^{\frac{q+1}{4}}.$

3. 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^{}={f\left(X_1\right)}^{q-1-\frac{q+1}{4}}$ calculate R.sub.2 such that:
R.sub.2=R.sub.1.sup.2 calculate R.sub.3 such that:
R.sub.3=R.sub.2.Math.f(X.sub.1) if R.sub.3 is not equal to 1, then obtain the square root of the term f(X.sub.2) according to the following equation:
{square root over (f(X.sub.2))}=R.sub.0.Math.R.sub.1 where R.sub.0 satisfies the following equation: $R_0=U\left(t\right).Math.{\left(-1\right)}^{q-1-\frac{q+1}{4.Math.}}.$

4. The electronic component according to claim 3, further configured to determine the point P by obtaining the square root of the term f(X.sub.1) according to the following equation:
{square root over (f(X.sub.1))}=R.sub.3.Math.f(X.sub.1). if R.sub.3 is equal to 1.

5. The electronic component according to claim 1, wherein the polynomials 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 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:
y2=f.sub.Z(X) in which the polynomials expressed in Jacobian coordinates are X1(t), X.sub.2(t), Z(t) and U(t) and satisfy the equality in Jacobian coordinates:
U(t).sup.2=f.sub.Z(t)(X1(t)).Math.f.sub.Z(t)(X2(t))) and in which Z(t) is determined in such a way that the operations of inversion are transformed into operations of multiplication.

6. The electronic component according to claim 1, wherein in obtaining the value of the parameter t said electronic component is further configured to obtain the value of the parameter t as a function of a password or an identifier.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0075] The invention will also be better understood with the aid of the following figures:

[0076] FIG. 1 show the main steps of a method of execution of a cryptographic calculation according to one embodiment of the present invention;

[0077] FIG. 2 shows a method of execution of a cryptographic calculation in detail according to one embodiment of the present invention;

[0078] FIG. 3 shows a method of execution of a cryptographic calculation in detail according to one embodiment of the present invention.

[0079] 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;

[0080] 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

[0081] FIG. 1 shows the main steps of a method of execution of a calculation according to one embodiment of the present invention.

[0082] 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 and therefore on parameter t. 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).

[0083] This calculation comprises, in a finite field F.sub.q, 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)

[0084] A point P(X,Y) has its abscissa X which corresponds to one of X.sub.1(t) and X.sub.2(t), for a value of t obtained, such that:

f(X.sub.1(t)).Math.f(X.sub.2(t))=U.sup.2(t)(4)

[0085] in the finite field F.sub.q.

[0086] Such polynomials can be a function 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 equation (4) are then functions of a single parameter t.

[0087] Generally, in order to determine a point on the curve, we try to determine, given input parameters u and t, those among the values X.sub.1=X.sub.1(t,u) and X.sub.2=X.sub.2(t,u) that correspond to a squared term in the finite field F.sub.q. For this purpose, at a step 11, the parameter t is taken into account and we calculate:

X.sub.i=X.sub.i(t) for i equal to 1 or 2,

and

U=U(t)

[0088] At a step 12, we decide whether the term f(X.sub.1) is a squared term on the basis of certain calculations. If the term f(X.sub.1) is a squared term then its square root is calculated in order to obtain, at step 13, the point P on abscissa X.sub.1 and ordinate Y.sub.1 obtained from the calculation of the previous square root.

[0089] In the opposite case, the point P on the abscissa X.sub.2 and the ordinate Y.sub.2 are obtained at step 14. To this end we envisage calculating the square root of the term f(X.sub.2).

[0090] It should be noted that reaching steps 13 or 14 for obtaining a point on the elliptical curve according to one embodiment of the present invention requires similar operations. Thus, regardless of the input parameter or parameters t and u, it is not possible to launch an attack on the basis of the time elapsed.

[0091] The point P(X.sub.i,Y.sub.i), for an i equal to 1 or 2, 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.

[0092] In the field F.sub.q, q corresponding to 3 mod 4, it is possible to check whether a term is a squared term in various ways.

[0093] FIG. 2 illustrates the application of the method according to an embodiment of the present invention.

[0094] At step 21, we calculate:

[00007]$R_1={f\left(X_1\right)}^{\frac{q-1}{2}}$

[0095] Then, the test for checking whether the term f(X.sub.1) is a squared term in F.sub.q, can be carried out, at a step 22, by comparing R.sub.1 to 1. In fact, in F.sub.q, if R.sub.1 is equal to 1, then f(X.sub.1) is a squared term. In this case, at step 24, the square root of this term is calculated as follows:

[00008]$\sqrt{f\left(X_1\right)}={f\left(X_1\right)}^{\frac{q+1}{4}}$

[0096] Otherwise, the term f(X.sub.2) is a squared term. Then, at a step 23, its square root is calculated as follows:

[00009]$\sqrt{f\left(X_2\right)}={f\left(X_2\right)}^{\frac{q+1}{4}}$

[0097] In this embodiment, it should be noted that the number and the type of operations carried out for the determination of a point P is the same whatever the processing option taken, i.e. whatever the term which corresponds to a squared term in equation (4).

[0098] FIG. 3 illustrates another embodiment of an execution method according to one embodiment of the present invention in which only one exponentiation is applied.

[0099] Here, advantageously, the number of exponentiations can be further reduced, by not using the same test for a squared term 12 of FIG. 1.

[0100] In one embodiment of the present invention, when trying to determine whether a term A is a squared term in F.sub.q, the following steps can be executed:

[00010]$\begin{array}{cc}{W}_1=\frac{1}{A^{\frac{q+1}{4}}}=A^{q-1-\frac{q+1}{4}}& \left(i\right)\\ W_2=W_1^2& \left(\mathrm{ii}\right)\\ W_3=W_2.Math.A& \left(\mathrm{iii}\right)\end{array}$

[0101] Finally, if term A is a squared term then: [0102] W1 corresponds to the reciprocal of the square root of A, i.e. 1/{square root over (A)}, 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 F.sub.q; [0103] W.sub.2 corresponds to the inverse of A; [0104] and W.sub.3 corresponds to the value 1.

[0105] Thus, when W.sub.3 is equal to the value 1, it is concluded from this that the term A is a squared term in the finite field F.sub.q. If A is not a squared term then W.sub.3 is not equal to 1.

[0106] The following sections describe an embodiment based on this type of test. In one embodiment of the present invention, at a step 311, the following multiplication is performed:

[00011]$R_1^{}={f\left(X_1\right)}^{q-1-\frac{q+1}{4}}$

[0107] Then it is checked whether this term Ro is a squared term as stated previously. Thus in a step 312, we calculate

R.sub.2=R.sub.1.sup.2

[0108] Then in a step 313, we calculate

R.sub.3=R.sub.2.Math.f(X.sub.1)

[0109] Then, we decide whether the term R.sub.3 is equal to 1 at step 314. If this is the case, then the following term corresponds to the square root of the term f(X.sub.1):

R.sub.4=R.sub.3.Math.f(X.sub.1)

[0110] If the test 314 is not satisfied, then the term f(X.sub.2) is a square root in F.sub.q. The square root of this term is thus obtained at step 316 according to the following equation:

R.sub.4=R.sub.0.Math.R.sub.1

[0111] where R.sub.0 satisfies the following equation

[00012]$R_0=U\left(t\right).Math.{\left(-1\right)}^{q-1-\frac{q+1}{4}}$

[0112] It should be noted that the above equation makes it possible to obtain advantageously the square root of f(X.sub.2) but without carrying out an operation of exponentiation such as that carried out at step 23 or also at step 311. In fact, here it is, ingeniously, a matter of performing a multiplication instead of an exponentiation.

[0113] We then obtain R4, which corresponds to the term f(X.sub.2). Thus, a point P on the elliptical curve has been determined which has X.sub.2 as abscissa and R4 as ordinate.

[0114] In the embodiment described previously with reference to FIG. 3, like that described with reference to FIG. 2, regardless of the determination of point P, i.e. whether this determination is based on the value X.sub.1 or X.sub.2, similar calculations are employed, thus ensuring determination of a point on the elliptical curve in a constant time.

[0115] In one embodiment of the present invention, it is possible to select polynomials that satisfy equation (4) according to one embodiment of the present invention, by basing it on Ulas polynomials as defined in the document Rational points on certain hyperelliptic curves over finite fields by Macie Ulas, dated 11 Jun. 2007.

[0116] In this document, the polynomials satisfying Skalba's equation (2) are described:

[00013]$X_1\left(t,u\right)=-\frac{b}{a}.Math.\left(1+\frac{1}{t^4.Math.f\left(u\right)+t^2.Math.f\left(u\right)}\right)$$X_2\left(t,u\right)=t^2.Math.f\left(u\right).Math.X_1\left(t,u\right)$$U\left(t,u\right)=t^3.Math.{f\left(u\right)}^4.Math.f\left(X_1\left(t,u\right)\right)$$\mathrm{where}.Math..Math.f\left(u\right)=u.Math..Math.3+a.Math..Math.u+b$ [0117] where a and b are elements of Fq such that their product is not zero.

[0118] Thus, the equations can be rewritten by setting

f(u)=1

[0119] without it being necessary to calculate a value of parameter u for which this last equation is satisfied. We then obtain

[00014]$X_1\left(t\right)=-\frac{b}{a}.Math.\left(1+\frac{1}{t^4-t^2}\right)$$X_2\left(t\right)=-t^2.Math.X_1\left(t\right),\mathrm{and}$$U\left(t\right)=t^3.Math.f\left(X_1\left(t\right)\right)$

[0120] Advantageously, these polynomials satisfy the following equation:

f(X.sub.1(t)).Math.f(X.sub.2(t)=U(t).sup.2

[0121] In one embodiment of the present invention, the use of Jacobian coordinates is advantageously envisaged. This transformation into Jacobian coordinates makes it possible to transform the operations of inversion into operations of multiplication which are quicker and easier to apply.

[0122] The equation of an elliptical curve:

X.sup.3+ax+b=Y2

[0123] can be written in Jacobian coordinates:

X.sup.3+aXZ.sup.4+bZ.sup.6=Y.sup.2

[0124] 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.Z.sup.2 and

Y=Y.Math.Z.sup.3

[0125] 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.

[0126] In the following sections, this transformation into Jacobian coordinates is applied to a particular case of polynomials as stated previously.

[0127] In this context, any operation of inversion is eliminated by taking:

Z(t)=a(t.sup.4t.sup.2)

[0128] In fact, the polynomials can then be written in the following form in Jacobian coordinates:

X.sub.1(t)=b.Math.Z(t)(t.sup.4t.sup.2+1)

X.sub.2(t)=t.sup.2.Math.X.sub.2(t)

[0129] 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.

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

[0131] We can then write in Jacobian coordinates:

U(t)=t.sup.3.Math.fz(X.sub.2(t))

with:

fz(t)(X)=X.sup.3+a.Math.X.Math.Z(t).sup.4+b.Math.Z(t).sup.6

[0132] By way of example only, the equations below make it possible to no longer have to carry out inversion operations. Under these conditions an execution method is then obtained which is more efficient and quick, while ensuring an execution still in a constant time.

[0133] The electronic component used to perform a disclosed cryptographic calculation may be any type of general purpose or dedicated computer which has been programmed 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).

[0134] 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.

[0135] 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.

[0136] 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.

[0137] 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.