Method of cryptographic processing of data on elliptic curves, corresponding electronic device and computer program product

Abstract

In one embodiment, it is proposed a method of cryptographic processing of data, the method being executed by an electronic device, and comprising obtaining at least two points belonging to a same elliptic curve defined on an algebraic structure being a finite ring, each point being represented by at least two coordinates. The method is remarkable in that it comprises: obtaining a parameterization of an isomorphism between said elliptic curve and another elliptic curve, said parameterization defining some configuration parameters, each configuration parameter having a range of possible values; determining in function of values of coordinates of said at least two points said configuration parameters, delivering determined configuration parameters; and obtaining coordinates of another point corresponding to an image of an addition of said at least two points through said isomorphism, said another point belonging to said another elliptic curve, and said obtaining being performed without an inversion operation in said algebraic structure, due to said determined configuration parameters.

Claims

1. A method of cryptographic processing of data, the method being executed by an electronic device comprising a memory and at least one hardware processor coupled to said memory, the method comprising obtaining at least two points represented in an affine coordinate system, and denoted respectively P.sub.1=(x.sub.1, y.sub.1) and P.sub.2=(X.sub.2, y.sub.2) belonging to a same elliptic curve defined on an algebraic structure being a finite ring, wherein the method further comprises: obtaining a parameterization of an isomorphism ψ between said elliptic curve, denoted as E.sup.(i-1) and another elliptic curve, denoted as E.sup.(i), said parameterization defining some configuration parameters being either equal to u, when a Weierstrass model is used for representing said elliptic curves, wherein ψ(x, y)=(u.sup.2x,u.sup.3y), or being equal to u, r, s, t when a general Weierstrass model is used for representing said elliptic curve, wherein ψ(x, y)=(u.sup.2x+r, u.sup.3y+u.sup.2sx+t); determining said configuration parameters as a function of values of coordinates of said at least two points, delivering determined configuration parameters, wherein u=x.sub.1−x.sub.2, or u=2y.sub.1; obtaining coordinates of another point denoted Q corresponding to an image of an addition of said at least two points through said isomorphism, said another point belonging to said another elliptic curve, and said obtaining being performed without an inversion operation in said algebraic structure, due to said determined configuration parameters, wherein Q=ψ(P.sub.1+P.sub.2).

2. The method according to claim 1, wherein when said at least two points are identical meaning P.sub.1 is equal to P.sub.2, and said addition is a doubling operation.

3. The method according to claim 1, wherein it is used in a scalar multiplication operation with a first point denoted P belonging to a first elliptic curve denoted E.sup.(0).

4. The method according to claim 3, wherein it comprises converting an output point of said scalar multiplication operation, said output point belonging to a last elliptic curve denoted E.sup.(l(k)), to a converted output point belonging to said first elliptic curve.

5. The method according to claim 3, wherein it further comprises determining configuration parameters r, s, t based on the previously used configuration parameters.

6. The method according to claim 1, wherein said algebraic structure is a finite field having a characteristic equal to 2.

7. The method according to claim 1, wherein said algebraic structure is a finite field having a characteristic equal to 3.

8. The method according to claim 1, wherein said algebraic structure is a finite field having a characteristic equal to a prime number p>3.

9. A non-transitory computer-readable storage medium storing a computer program comprising a set of computer-executable instructions to implement a method for cryptographic computations when the instructions are executed by a hardware processor of a computer, wherein the instructions comprise instructions, which when executed, configure the hardware computer to perform a method of cryptographic processing of data, the method comprising: obtaining at least two points represented in an affine coordinate system, and denoted respectively P.sub.1=(x.sub.1, y.sub.1) and P.sub.2=(x.sub.2,y.sub.2) belonging to a same elliptic curve defined on an algebraic structure being a finite ring; obtaining a parameterization of an isomorphism ψ between said elliptic curve denoted as E.sup.(i-1) and another elliptic curve denoted as E.sup.(i), said parameterization defining some configuration parameters being either equal to u, when a Weierstrass model is used for representing said elliptic curves, wherein ψ(x, y)=(u.sup.2x,u.sup.3y), or being equal to u, r, s, t when a general Weierstrass model is used for representing said elliptic curve, wherein ψ(x, y)=(u.sup.2x+r, u.sup.3y+u.sup.2sx+t); determining said configuration parameters as a function of values of coordinates of said at least two points, delivering determined configuration parameters, wherein u=x.sub.1−x.sub.2, or u=2y.sub.1; obtaining coordinates of another point denoted Q corresponding to an image of an addition of said at least two points through said isomorphism, said another point belonging to said another elliptic curve, and said obtaining being performed without an inversion operation in said algebraic structure, due to said determined configuration parameters, wherein Q=ψ(P.sub.1+P.sub.2).

10. An electronic device configured to perform a cryptographic processing of data, said electronic device comprising a memory and at least one hardware processor coupled to the memory, the at least one hardware processor being configured to obtain at least two points represented in an affine coordinate system, and denoted respectively P.sub.1=(x.sub.1, y.sub.1) and P.sub.2=(x.sub.2, y.sub.2) belonging to a same elliptic curve defined on an algebraic structure being a finite ring, wherein the at least one hardware processor is further configured to: obtain a parameterization of an isomorphism ψ between said elliptic curve denoted as E.sup.(i-1) and another elliptic curve, denoted as E.sup.(i), said parameterization defining some configuration parameters, being either equal to u, when a Weierstrass model is used for representing said elliptic curves, wherein ψ(x, y)=(u.sup.2x, u.sup.3y), or being equal to u, r, s, t when a general Weierstrass model is used for representing said elliptic curve, wherein ψ(x, y)=(u.sup.2x+r, u.sup.3y+u.sup.2sx+t); determine said configuration parameters as a function of values of coordinates of said at least two points, delivering determined configuration parameters, wherein u=x.sub.1−x.sub.2, or u=2y.sub.1; obtain coordinates of another point denoted Q corresponding to an image of an addition of said at least two points through said isomorphism, said another point belonging to said another elliptic curve, without performing an inversion operation in said algebraic structure, due to said determined configuration parameters, wherein Q=ψ(P.sub.1+P.sub.2).

11. The electronic device according to claim 10, wherein when said at least two points are identical meaning P.sub.1 is equal to P.sub.2, and said addition is a doubling operation.

12. The electronic device according to claim 10, wherein said at least one hardware processor is further configured to perform a scalar multiplication operation with a first point denoted P belonging to a first elliptic curve denoted E.sup.(0).

13. The electronic device according to claim 12, wherein said hardware processor is further configured to determine configuration parameters r, s, t based on the previously used configuration parameters.

14. The electronic device according to claim 12, wherein said at least one hardware processor is further configured to convert an output point of said scalar multiplication operation, said output point belonging to a last elliptic curve denoted E.sup.(l(k)), to a converted output point belonging to said first elliptic curve.

15. The electronic device according to claim 10, wherein said algebraic structure is further a finite field having a characteristic equal to a prime number p>3.

Description

BRIEF DESCRIPTION OF THE FIGURES

(1) The above and other aspects of the invention will become more apparent by the following detailed description of exemplary embodiments thereof with reference to the attached drawings in which:

(2) FIG. 1 presents a scalar multiplication on elliptic curves according to one embodiment of the invention;

(3) FIG. 2 presents two classical methods for performing a scalar multiplication on elliptic curves (the double-and-add method, and the add-and-double method);

(4) FIG. 3 presents two methods for performing a scalar multiplication on elliptic curves according to the present technique;

(5) FIG. 4 presents another embodiment of a method for performing a scalar multiplication on elliptic curves according to the present technique;

(6) FIG. 5 presents two classical methods for performing a scalar multiplication on elliptic curves (the Montgomery ladder, and the Joye's double-add ladder);

(7) FIG. 6 presents two modifications of the methods for performing a scalar multiplication on elliptic curves disclosed in FIG. 5, according to one embodiment of the invention;

(8) FIG. 7 presents a modification of Montgomery ladder method for performing a scalar multiplication on elliptic curves disclosed in FIG. 5, according to one embodiment of the invention;

(9) FIG. 8 presents a device that can be used to perform one or several steps of methods disclosed in the present document.

DETAILED DESCRIPTION

(10) Before describing the proposed method in its full generality, we first make a couple of observations on the Weierstraβ model. To simplify the exposition, we focus on elliptic curves defined over a ring of characteristic different of 2, or 3. As is customary, we let * denote the multiplicative group of and Char() the characteristic of .

(11) Consider the elliptic curve E.sub.1 over a ring , Char()≠2,3, given by
E.sub.1:y.sup.2=x.sup.3+a.Math.x+b

(12) For any uε*, elliptic curve E.sub.1 is -isomorphic to elliptic curve.
E.sub.u:y.sup.2=x.sup.3+a.Math.u.sup.4.Math.x+b.Math.u.sup.6
via the inverse mappings

(13) ${\psi }_u\text{:}{E}_1\stackrel{\sim }{.fwdarw.}{E}_u,\{\begin{array}{c}O\mapsto ,O\\ \left(x,y\right)\mapsto \left(u^{2}x,u^{3}y\right)\end{array}\mathrm{and}{\psi }_u^{-1}\text{:}{E}_u\stackrel{\sim }{.fwdarw.}{E}_1,\{\begin{array}{c}O\mapsto ,O\\ \left(\tilde{x},\tilde{y}\right)\mapsto \left(u^{-2}\tilde{x},u^{-3}\tilde{y}\right)\end{array}$
Given two finite point points P.sub.1=(x.sub.1,y.sub.1) and P.sub.2=(x.sub.2,y.sub.2) on E.sub.1 such that P.sub.1≠±P.sub.2 (i.e. such that x.sub.1≠x.sub.2), provided that (x.sub.1−x.sub.2)ε*, their sum is given by P.sub.3=P.sub.1+P.sub.2=(x.sub.3,y.sub.3) where

(14) $\begin{array}{cc}{x}_3={\left(\frac{y_1-y_2}{x_1-x_2}\right)}^2-x_1-x_2\mathrm{and}{y}_3=\left(\frac{y_1-y_2}{x_1-x_2}\right)\left(x_1-x_3\right)-y_1& \left(\mathrm{eq}.1\right)\end{array}$
The double of P.sub.1=(x.sub.1,y.sub.1), provided that y.sub.1ε*, is given by P.sub.4=2P.sub.1=P.sub.1+P.sub.1=(x.sub.4,y.sub.4) where

(15) $\begin{array}{cc}{x}_4={\left(\frac{3x_1^2+a}{2y_1}\right)}^2-2x_1\mathrm{and}{y}_4=\left(\frac{3x_1^2+a}{2y_1}\right)\left(x_1-x_4\right)-y_1& \left(\mathrm{eq}.2\right)\end{array}$

(16) In one embodiment of the invention, the present technique uses the following property: By defining φ:=x.sub.1−x.sub.2, we get from the above addition equation formula (referenced eq. 1)
φ.sup.2x.sub.3=(y.sub.1−y.sub.2).sup.2−φ.sup.2x.sub.1−φ.sup.2x.sub.2 and φ.sup.3y.sub.3=(φ.sup.2x.sub.1−φ.sup.2x.sub.3)(y.sub.1−y.sub.2)−φ.sup.3y.sub.1.

(17) In other words, given points P.sub.1 and P.sub.2 on the elliptic curve E.sub.1, one can easily obtain on the isomorphic elliptic curve E.sub.φ the point {tilde over (P)}.sub.3=ψ.sub.φ(P.sub.1+P.sub.2)=(φ.sup.2x.sub.3,φ.sup.3y.sub.3). It is worth remarking that no inversion is required in the evaluation of {tilde over (P)}.sub.3. We let iADD denote the operation of getting {tilde over (P)}.sub.3εE.sub.φ.

(18) It should be noticed that a similar treatment applies to the point doubling operation (the doubling operation can be viewed as a particular addition between two points which are identical. However, the formulæ used to perform an addition if the points are equal or not are not necessarily the same). Defining now φ:=2y.sub.1, we get from the doubling formula (referenced eq. 2)
φ.sup.2x.sub.4=(3x.sub.1.sup.2+a).sup.2−2φ.sup.2x.sub.1 and φ.sup.3y.sub.4=(φ.sup.2x.sub.1−φ.sup.2x.sub.4)(3x.sub.1.sup.2+a)−φ.sup.3y.sub.1.
Namely, given point P.sub.1 on E.sub.1, one can easily obtain the point {tilde over (P)}.sub.4=ψ.sub.φ(2P.sub.1)=(φ.sup.2x.sub.4,φ.sup.3y.sub.4), which belongs to the elliptic curve E.sub.φ. As for the point addition, it is worth remarking that no inversion is required in the evaluation of {tilde over (P)}.sub.4. We let iDBL denote the operation of getting {tilde over (P)}.sub.4εE.sub.φ.

(19) Let be an elliptic curve over a ring . Consider a family {E.sub.{right arrow over (φ)}} of isomorphic elliptic curves, indexed by some parameter {right arrow over (φ)}, under isomorphism
ψ.sub.{right arrow over (φ)}:{right arrow over (.fwdarw.)}E.sub.{right arrow over (φ)}

(20) Parameter {right arrow over (φ)} is the description of the isomorphism (i.e. it is a parameterization that defines the isomorphism). We use the notation {right arrow over (φ)}=Desc(ψ.sub.{right arrow over (φ)}) (Desc being an acronyme of description). The set of all possible parameters {right arrow over (φ)} is noted .

(21) The following three addition operations, noted iADD, iADDU and iADDC, are defined by the following equations:

(22) $\hspace{1em}\{\begin{array}{c}i\mathrm{ADD}\text{:}\times \left({\psi }_{\stackrel{.fwdarw.}{\varphi }}\left(P_1+P_2\right),\stackrel{.fwdarw.}{\varphi }\right)\\ \begin{array}{c}\mathrm{iADDU}\text{:}\times .Math.E_{\stackrel{.fwdarw.}{\varphi }}\times E_{\stackrel{.fwdarw.}{\varphi }}\times ℱ,\\ \left(P_1,P_2\right)\mapsto \left({\psi }_{\stackrel{.fwdarw.}{\varphi }}\left(P_1+P_2\right),{\psi }_{\stackrel{.fwdarw.}{\varphi }}\left(P_1\right),\stackrel{.fwdarw.}{\varphi }\right)\end{array}\\ \begin{array}{c}\mathrm{iADDC}\text{:}\times .Math.E_{\stackrel{.fwdarw.}{\varphi }}\times E_{\stackrel{.fwdarw.}{\varphi }}\times ℱ,\\ \left(P_1,P_2\right)\mapsto \left({\psi }_{\stackrel{.fwdarw.}{\varphi }}\left(P_1+P_2\right),{\psi }_{\stackrel{.fwdarw.}{\varphi }}\left(P_1-P_2\right),\stackrel{.fwdarw.}{\varphi }\right)\end{array}\end{array}$

(23) For efficiency purposes, parameter {right arrow over (φ)} is chosen so that given two different points P.sub.1 and P.sub.2 on , the output of the addition operation does not require ring inversions.

(24) We also give two doubling operations, iDBL and iDBLU, defined by the following equations:

(25) $\{\begin{array}{c}\mathrm{iDBL}\text{:}.Math.E_{\stackrel{.fwdarw.}{\varphi }}\times ℱ,P_1\mapsto \left({\psi }_{\stackrel{.fwdarw.}{\varphi }}\left(2P_1\right),\stackrel{.fwdarw.}{\varphi }\right)\\ \mathrm{iDBLU}\text{:}.Math.E_{\stackrel{.fwdarw.}{\varphi }}\times E_{\stackrel{.fwdarw.}{\varphi }}\times ℱ,P_1\mapsto \left({\psi }_{\stackrel{.fwdarw.}{\varphi }}\left(2P_1\right),{\psi }_{\stackrel{.fwdarw.}{\varphi }}\left(P_1\right),\stackrel{.fwdarw.}{\varphi }\right)\end{array}\hspace{1em}$

(26) Likewise, the parameter {right arrow over (φ)} is chosen so that, given a point P.sub.1 belonging to , the output of the doubling operation does not require ring inversions.

(27) More generally, given two elliptic curves E.sub.{right arrow over (φ)} and E.sub.{right arrow over (φ)}′, that are isomorphic to , if
ψ.sub.{right arrow over (φ)}:E.sub.{right arrow over (φ)}{tilde over (.fwdarw.)}E.sub.{right arrow over (φ′)},
denotes the isomorphism between the elliptic curves E.sub.{right arrow over (φ)} and E.sub.{right arrow over (φ′)};
we similarly define the operations

(28) $\{\begin{array}{c}{\mathrm{iADD}}_{\stackrel{.fwdarw.}{\varphi }}\text{:}{E}_{\stackrel{.fwdarw.}{\varphi }}\times E_{\stackrel{.fwdarw.}{\varphi }}.Math.E_{\stackrel{.fwdarw.}{{\varphi }^{\prime }}}\times ℱ,\left(P_1,P_2\right)\mapsto \left({\psi }_{\stackrel{.fwdarw.}{\varphi }}\left(P_1+P_2\right),\stackrel{.fwdarw.}{\varphi }\right)\\ \begin{array}{c}{\mathrm{iADDU}}_{\stackrel{.fwdarw.}{\varphi }}\text{:}{E}_{\stackrel{.fwdarw.}{\varphi }}\times E_{\stackrel{.fwdarw.}{\varphi }}.Math.E_{\stackrel{.fwdarw.}{{\varphi }^{\prime }}}\times E_{\stackrel{.fwdarw.}{{\varphi }^{\prime }}}\times ℱ,\\ \left(P_1,P_2\right)\mapsto \left({\psi }_{\stackrel{.fwdarw.}{\varphi }}\left(P_1+P_2\right),{\psi }_{\stackrel{.fwdarw.}{\varphi }}\left(P_1\right),\stackrel{.fwdarw.}{\phi }\right)\end{array}\\ \begin{array}{c}{\mathrm{iADDC}}_{\stackrel{.fwdarw.}{\varphi }}\text{:}{E}_{\stackrel{.fwdarw.}{\varphi }}\times E_{\stackrel{.fwdarw.}{\varphi }}.Math.E_{\stackrel{.fwdarw.}{{\varphi }^{\prime }}}\times E_{\stackrel{.fwdarw.}{{\varphi }^{\prime }}}\times ℱ,\\ \left(P_1,P_2\right)\mapsto \left({\psi }_{\stackrel{.fwdarw.}{\varphi }}\left(P_1+P_2\right),{\psi }_{\stackrel{.fwdarw.}{\varphi }}\left(P_1-P_2\right),\stackrel{.fwdarw.}{\phi }\right)\end{array}\\ {\mathrm{iDBL}}_{\stackrel{.fwdarw.}{\varphi }}\text{:}{E}_{\stackrel{.fwdarw.}{\varphi }}.Math.E_{\stackrel{.fwdarw.}{{\varphi }^{\prime }}}\times ℱ,P_1\mapsto \left({\psi }_{\stackrel{.fwdarw.}{\varphi }}\left(2P_1\right),\stackrel{.fwdarw.}{\phi }\right)\\ {\mathrm{iDBLU}}_{\stackrel{.fwdarw.}{\varphi }}:E_{\stackrel{.fwdarw.}{\varphi }}.Math.E_{\stackrel{.fwdarw.}{{\varphi }^{\prime }}}\times E_{\stackrel{.fwdarw.}{{\varphi }^{\prime }}}\times ℱ,P_1\mapsto \left({\psi }_{\stackrel{.fwdarw.}{\varphi }}\left(2P_1\right),{\psi }_{\stackrel{.fwdarw.}{\varphi }}\left(P_1\right),\stackrel{.fwdarw.}{\phi }\right) \end{array}\hspace{1em}$

(29) Subscript {right arrow over (φ)} in the operator definition indicates that input points belong to the elliptic curve E.sub.{right arrow over (φ)}.

(30) The following example illustrates the principle. For a general Weierstraβ model defined over a ring (whatever is characteristic is), we have

(31) :y.sup.2+a.sub.1xy+a.sub.3y=x.sup.3+a.sub.2x.sup.2+a.sub.4x+a.sub.6, where parameters a.sub.1, a.sub.2, a.sub.3, a.sub.4 and a.sub.6 belong to , and ψ.sub.{right arrow over (φ)}:E.sub.{right arrow over (φ)}{tilde over (.fwdarw.)}E.sub.{right arrow over (φ′)} with (x,y)(u.sup.2x+r,u.sup.3y+u.sup.2sx+t), where the description {right arrow over (φ)} of isomorphism is given by the four parameters u, r, s and t. Hence, {right arrow over (φ)}=(u, r, s, t) and =(1, 0, 0, 0). We also have ={(U, R, S, T)ε.sup.4|Uε*}, where is the definition ring of . Hence, the isomorphism ψ.sub.{right arrow over (φ)} enables the mapping of a point P of :y.sup.2+a.sub.1xy+a.sub.3y=x.sup.3+a.sub.2x.sup.2+a.sub.4x+a.sub.6 to a point belonging to the elliptic curve :y.sup.2+a′.sub.1xy+a′.sub.3y=x.sup.3+a′.sub.2x.sup.2+a′.sub.4x+a′.sub.6, where parameters a′.sub.1, a′.sub.2, a′.sub.3, a′.sub.4 and a′.sub.6 belong to . The corresponding curve parameters are related by the following equations:
ua.sub.1=a′.sub.1+2s
u.sup.2a.sub.2=a′.sub.2−sa′.sub.1+3r−s.sup.2
u.sup.3a.sub.3=a′.sub.3+ra′.sub.1+2t
u.sup.4a.sub.4=a′.sub.4−sa′.sub.3+2ra′.sub.2−(t+rs)a′.sub.1+3r.sup.2−2st
u.sup.6a.sub.6=a′.sub.6+ra′.sub.4+r.sup.2a′.sub.2+r.sup.3−ta′.sub.3−rta′.sub.1

(32) When the characteristic of is not 2 or 3, one can without loss of generality select a.sub.1=a.sub.2=a.sub.3=0. Likewise, when the characteristic of is 2, provided that the elliptic curve is non-supersingular, one can select a.sub.1=1 and a.sub.3=a.sub.4=0.

(33) In the following section, explicit computations to be performed for obtaining the output of the operators iADD, iADDU, iADDC, iDBL and iDBLU are given, with an elliptic curve defined according to the short Weierstraβ model, and over a ring with a characteristic not equal to 2 or 3.

(34) More precisely, the evaluation of {tilde over (P)}.sub.3=(,)=ψ.sub.φ(P.sub.1+P.sub.2)=(φ.sup.2x.sub.3,φ.sup.3y.sub.3) from the points P.sub.1 and P.sub.2 (which belong to an elliptic curve :y.sup.2=x.sup.3+a.Math.x+b (according to the short Weierstraβ model) defined over a ring with a characteristic not equal to 2 or 3 can be done as follows: Obtaining φ=x.sub.1−x.sub.2 in ; Obtaining C=φ.sup.2 in ; Obtaining W.sub.1=x.sub.1C in ; Obtaining W.sub.2=x.sub.2C in ; Obtaining D=(y.sub.1−y.sub.2).sup.2 in ; Obtaining A.sub.1=(W.sub.1−W.sub.2)y.sub.1 in ; Then =D−W.sub.1−W.sub.2 in and =(W.sub.1−)(y.sub.1−y.sub.2)−A.sub.1 in .
This series of operations corresponds to the iADD operation, which has a global cost of 4M+2S, where M and S denote the cost of a multiplication and of a squaring in , respectively. It should be noted that the obtaining of {tilde over (P)}.sub.1=(,)=ψ.sub.φ(P.sub.1)=(φ.sup.2x.sub.1,φ.sup.3y.sub.1) come for free during the evaluation of {tilde over (P)}.sub.3. Indeed, we immediately have {tilde over (P)}.sub.1=(,) with =W.sub.1 and =A.sub.1.

(35) As mentioned previously, the operation of getting {tilde over (P)}.sub.3 together with {tilde over (P)}.sub.1 is noted iADDU.

(36) The evaluation of =(,)=ψ.sub.φ(P.sub.1−P.sub.2)=(φ.sup.2x.sub.3,φ.sup.3y.sub.3) from the points P.sub.1 and P.sub.2 (which belong to an elliptic curve :y.sup.2=x.sup.3+a.Math.x+b defined over a finite ring with a characteristic not equal to 2 or 3) can be done as follows: Obtaining W.sub.1=x.sub.1C in ; Obtaining W.sub.2=x.sub.2C in ; Obtaining A.sub.1=(W.sub.1−W.sub.2)y.sub.1 in ;

(37) Then .sub.3=(y.sub.1+y.sub.2).sup.2−W.sub.1−W.sub.2 in and =(W.sub.1−.sub.3)(y.sub.1+y.sub.2)−A.sub.1 in .

(38) Indeed, since −P.sub.2=(x.sub.2,−y.sub.2), it follows that P.sub.1−P.sub.2=(x′.sub.3,y′.sub.3) satisfies φ.sup.2x′.sub.3=(y.sub.1+y.sub.2).sup.2−φ.sup.2x.sub.1−φ.sup.2x.sub.2 and φ.sup.3y′.sub.3=(φ.sup.2x.sub.1−φ.sup.2x′.sub.3)(y.sub.1+y.sub.2)−φ.sup.3y.sub.1. Hence, the operation of obtaining ψ.sub.φ(P.sub.1−P.sub.2), noted iADDC, only needs 5M+3S.

(39) The evaluation of {tilde over (P)}.sub.4=(,)=ψ.sub.φ(2P.sub.1) from the points P.sub.1 (which belongs to an elliptic curve :y.sup.2=x.sup.3+a.Math.x+b defined over a finite ring with a characteristic not equal to 2 or 3) can be done as follows: Obtaining B=x.sub.1.sup.2 in ; Obtaining E=y.sub.1.sup.2 in ; Obtaining L=E.sup.2 in ; Obtaining M=3B+a in ; Obtaining S=2((x.sub.1+E).sup.2−B−L) in ; Then =M.sup.2−2S in and =M(S−)−8L in .

(40) The evaluation of {tilde over (P)}.sub.4=(,) is noted iDBL, and such operation needs only 1M+5S. Moreover, the obtaining of {tilde over (P)}.sub.1=(,)=ψ.sub.φ(P.sub.1) come for free during the evaluation of {tilde over (P)}.sub.4. Indeed, we have S, and =8L. The operation consisting of obtaining {tilde over (P)}.sub.4 as well as {tilde over (P)}.sub.1 is noted, as previously mentioned, iDBLU.

(41) One of the most used operation in cryptographic scheme using elliptic curves is the scalar multiplication.

(42) FIG. 1 presents a scalar multiplication on elliptic curve according to one embodiment of the invention.

(43) More precisely, the scalar multiplication comprises the use of the doubling and adding operations via the use of a chain or series of isomorphisms that are determined during the scalar multiplication process.

(44) Let E.sup.(0)= denote the original elliptic curve, and E.sup.(i)=E.sub.{right arrow over (φ)}.sub.i the current elliptic curve at step I, and E.sup.(l(k))=E.sub.{right arrow over (φ)}.sub.l(k), the final elliptic, we have PεE.sup.(0) and {tilde over (Q)}:=k((ψ.sub.{right arrow over (φ)}.sub.l(k)◯ . . . ◯ψ.sub.{right arrow over (φ)}.sub.i◯ . . . ◯ψ.sub.{right arrow over (φ)}.sub.1)P)εE.sup.(l(k)).

(45) The isomorphism between the current curve at Step i and the original curve is given by ψ.sub.{right arrow over (φ)}.sub.i=ψ.sub.{right arrow over (φ)}.sub.i◯ . . . ◯ψ.sub.{right arrow over (φ)}.sub.1. Slightly abusing the notation, we also use symbol ◯ denote the operation on the corresponding descriptions, namely Desc (ψ.sub.{right arrow over (φ)}.sub.i)={right arrow over (φ)}.sub.i◯ . . . ◯{right arrow over (φ)}.sub.1. Since {tilde over (Q)}=k(ψ.sub.{right arrow over (φ)}.sub.l(k)(P))=ψ.sub.{right arrow over (φ)}l(k)(k.Math.P), result point Q=k.Math.PεE.sup.(0) is then given by Q=ψ.sub.{right arrow over (φ)}.sub.l(k).sup.−1({tilde over (Q)}). The ‘composed’ isomorphism ψ.sub.{right arrow over (φ)}.sub.l(k) can be obtained iteratively by observing that ψ.sub.{right arrow over (φ)}.sub.i=ψ.sub.{right arrow over (φ)}i◯ψ.sub.{right arrow over (φ)}.sub.i-1 with ψ.sub.{right arrow over (φ)}.sub.0=Id (i.e. the identity map). Since {right arrow over (φ)}.sub.i=Desc(ψ.sub.{right arrow over (φ)}.sub.i), we get {right arrow over (φ)}.sub.i={right arrow over (φ)}.sub.i◯{right arrow over (φ)}.sub.i-1, with {right arrow over (φ)}.sub.0=Desc(Id):=.

(46) The following example illustrates such principle. For a general Weierstraβ model, we have
ψ.sub.{right arrow over (φ)}.sub.i-1:E.sup.(0){tilde over (.fwdarw.)}E.sup.(i-1),(x,y)(U.sub.i-1.sup.2x+R.sub.i-1,U.sub.i-1.sup.3y+U.sub.i-1.sup.2S.sub.i-1x+T.sub.i-1),
and
ψ.sub.{right arrow over (φ)}.sub.i:E.sup.(i-1){tilde over (.fwdarw.)}E.sup.(i),(x,y)(u.sub.i.sup.2x+r.sub.i,u.sub.i.sup.3y+u.sub.i.sup.2s.sub.ix+t.sub.i),
where {right arrow over (φ)}.sub.i-1=(U.sub.i-1, R.sub.i-1, S.sub.i-1, T.sub.i-1), {right arrow over (φ)}.sub.i=(u.sub.i, r.sub.i, s.sub.i, t.sub.i), and =(1, 0, 0, 0). Hence, the equation {right arrow over (φ)}.sub.i={right arrow over (φ)}.sub.i◯{right arrow over (φ)}.sub.i-1 translates into (U.sub.i, R.sub.i, S.sub.i, T.sub.i)=(u.sub.i, r.sub.i, s.sub.i, t.sub.i)◯(U.sub.i-1, R.sub.i-1, S.sub.i-1, T.sub.i-1) with

(47) $\{\begin{array}{c}{U}_i=U_{i-1}{u}_i\\ R_i=u_i^2{R}_{i-1}+r_i\\ S_i=u_i{S}_{i-1}+s_i\\ T_i=u_i^3{T}_{i-1}+u_i^2{s}_i{R}_{i-1}+t_i\end{array}\hspace{1em}$

(48) for i≧1, and (U.sub.0, R.sub.0, S.sub.0, T.sub.0)=(1, 0, 0, 0).

(49) FIG. 2 presents two classical methods for performing a scalar multiplication on elliptic curves (the double-and-add method, and the add-and-double method).

(50) A classical method for evaluating Q=kP (i.e. the scalar multiplication on elliptic curves) considers the binary representation of scalar k, k=(k.sub.n-1, . . . , k.sub.0).sub.2, with k.sub.iε{0, 1}, 0≦i≦n−1. Advantageously it requires a minimal number of registers and is hence well suited to memory-constrained devices like smart cards. The method relies on the obvious relation that kP=2(└k/2┘P), if k is even and kP=2(└k/2┘P)+P if k is odd. Iterating the process yields a left-to-right scalar multiplication algorithm, known as double-and-add method. Such method requires two (point) registers R.sub.0 and R.sub.1. Register R.sub.0 acts as an accumulator and register R.sub.1 is used to store the value of input point P.

(51) There exists a right-to-left variant. The resulting algorithm, known as add-and-double method, is depicted in Algorithm 2 of FIG. 2. It also requires two (point) registers, R.sub.0 and R.sub.1 but in this case both act as accumulators.

(52) FIG. 3 presents two methods for performing a scalar multiplication on elliptic curves according to the present technique.

(53) More precisely, the algorithms or methods presented in FIG. 3 are straightforward implementations of the classical methods with the addition and doubling formulæ according to one embodiment of the invention. We use a variable {right arrow over (φ)} to accumulate [the description of] the current isomorphism with the original curve. This variable is initialized to {right arrow over (φ)}= (corresponding to identity map Id). As previously mentioned, the symbol ◯ denotes the composition of [the description of] elliptic curve isomorphisms.

(54) FIG. 4 presents another embodiment of a method for performing a scalar multiplication on elliptic curves according to the present technique.

(55) Such embodiment is a variant of the left-to-right method that is more efficient than the one depicted in FIG. 3. By remarking that when k.sub.i is equal to 1, register R.sub.1 is added to register R.sub.0, and that the content of register R.sub.1 remains invariant throughout the computation (R.sub.1 always contain input point P), then it is not necessary to constantly update it as a point on the current elliptic curve. Instead, at iteration i, its representative on the current elliptic curve (E.sub.{right arrow over (φ)}) can be computed from input point P as ψ.sub.{right arrow over (φ)}(P).

(56) FIG. 5 presents two classical methods for performing a scalar multiplication on elliptic curves (the Montgomery ladder, and the Joye's double-add ladder).

(57) These classical methods use three registers (register R.sub.0, register R.sub.1 and register T) in order to store some results of operations.

(58) FIG. 6 presents two modifications of the methods for performing a scalar multiplication on elliptic curves disclosed in FIG. 5, according to one embodiment of the invention.

(59) For several elliptic curve models, the point addition formulæ of two distinct points are independent of the curve parameters. In this case, it is interesting to rely on scalar multiplication algorithms that can be written as a series of iADDU and iADDC operations.

(60) The main loop for Algorithm 6 reads as R.sub.1-b←R.sub.b+R.sub.1-b and R.sub.b←2 R.sub.b (where b is equal to 0 or 1), and for Algorithm 7 as R.sub.1-b←R.sub.b+2R.sub.1-b. Therefore, Algorithm 6 and Algorithm 7 can be easily adapted with the new operations proposed in this document. The value k.sub.n-1=1 leads to (R.sub.0, T)=(P,P), and then to R.sub.1=P+P in the first iteration of Algorithm 6. This last operation is a point doubling. In order not to have to handle potential special cases, we assume that k.sub.n-1=1 and hence start the for-loop at i=n−2, and initialize (R.sub.0, R.sub.1) with (P, 2P). For better performance, this is achieved thanks to the iDBLU operation. For the same reason, we assume that k.sub.0=1 in the right-to-left algorithm. We start the for-loop at i=2 and initialize (R.sub.k.sub.1,R.sub.1-k.sub.1) with (P,3P) in Algorithm 9. Again, this can be done with the new operations. When k.sub.0=0, point P needs to be subtracted at the end of the computation to get the correct result.

(61) FIG. 7 presents a modification of Montgomery Ladder method for performing a scalar multiplication on elliptic curves disclosed in FIG. 5, according to one embodiment of the invention.

(62) The original Montgomery ladder keeps invariant the difference R.sub.1−R.sub.0, which is equal to P. Equivalently, variable T (←R.sub.b−R.sub.1-b) in Algorithm 6 is equal to (−1).sup.1-bP. Therefore, at iteration i=0, variable R.sub.b in our version of the Montgomery ladder (Algorithm 8) contains at Line 4 the value of ψ.sub.{right arrow over (φ)}.sub.2n-2((−1).sup.1-k.sup.0P). This may allow one to explicitly recover the description of ψ.sub.{right arrow over (φ)}.sub.2n-2 and consequently that of ψ.sub.{right arrow over (φ)}.sub.2n-2 as {right arrow over (φ)}:=Desc (ψ.sub.{right arrow over (φ)}.sub.2n-1)={right arrow over (φ)}.sub.2n-1◯Desc (ψ.sub.{right arrow over (φ)}.sub.2n-2). As a result, we may obtain a Montgomery-like algorithm where there is no need to keep track of the current isomorphism: the iADDC and iADDU operations only need to return the points and not the description of the isomorphism of the resulting curve (i.e., parameter {right arrow over (φ)}). This is indicated by symbol ′ on the operator. This variant of the Montgomery ladder also requires that the iADDC and iADDU operations are independent of the curve parameters; this is indicated by the absence of subscript {right arrow over (φ)} in the operator.

(63) FIG. 8 presents a device that can be used to perform one or several steps of methods (or algorithms) disclosed in the present document.

(64) Such device referenced 800 comprises a computing unit (for example a CPU, for “Central Processing Unit”), referenced 801, and one or more memory units (for example a RAM (for “Random Access Memory”) block in which intermediate results can be stored temporarily during the execution of instructions a computer program, or a ROM block in which, among other things, computer programs are stored, or an EEPROM (“Electrically-Erasable Programmable Read-Only Memory”) block, or a flash block) referenced 802. Computer programs are made of instructions that can be executed by the computing unit. Such device 800 can also comprise a dedicated unit, referenced 803, constituting an input-output interface to allow the device 800 to communicate with other devices. In particular, this dedicated unit 803 can be connected with an antenna (in order to perform communication without contacts), or with serial ports (to carry communications “contact”). It should be noted that the arrows in FIG. 8 signify that the linked unit can exchange data through buses for example together.

(65) In an alternative embodiment, some or all of the steps of the method previously described, can be implemented in hardware in a programmable FPGA (“Field Programmable Gate Array”) component or ASIC (“Application-Specific Integrated Circuit”) component.

(66) In an alternative embodiment, some or all of the steps of the method previously described, can be executed on an electronic device comprising memory units and processing units as the one disclosed in the FIG. 8.

(67) For certain models (including the popular Weierstraβ model), the neutral element (i.e., point at infinity O) needs a special treatment. This can be circumvented by adequately adapting the initialization step. For the classical left-to-right ladders, assuming that k.sub.n-1=1, we can start the for-loop at i=n−2, and set R.sub.0←P, and R.sub.1←P in Algorithms 3 and 5 at the initialization step.

(68) Similarly, for the right-to-left ladder, assuming that k.sub.0=1, we can start the for-loop at i=1, and set R.sub.0←P, and R.sub.1←2.Math.P in Algorithm 4. When k.sub.0=0, we do the same but substrate P at the end of the computation to get the correct result.

(69) It should be noted that for combined operations, such as the evaluation of R=2.Math.P+Q can be done according to the present technique. This can be done in two steps, by first determining T←P+Q, and then the determination of R←P+T. If the point R is needed together with updated point P, this can be carried out with two consecutive applications of the iADDU operation: (T,P,{right arrow over (φ)}.sub.1)←iADDU.sub.{right arrow over (φ)}(P,Q); (R,P,{right arrow over (φ)}.sub.2)←iADDU.sub.{right arrow over (φ)}.sub.1.sub.◯{right arrow over (φ)}(P,T).

(70) Things are slightly more complex if we want to obtain point R together with updated point Q (rather than point P) at the end of the computation. This can be carried out by an evaluation of iADDU followed by an evaluation of iADDC: (T,P,{right arrow over (φ)}.sub.1)←iADDU.sub.{right arrow over (φ)}(P,Q); (R,Q,{right arrow over (φ)}.sub.2)←iADDC.sub.{right arrow over (φ)}.sub.1.sub.◯{right arrow over (φ)}(P,T).

(71) At last, it should be noted that the proposed technique based on isomorphic elliptic curves is compliant with technique that prevents side channel attacks such as a curve randomization at each execution of the technique.