Cryptography method comprising an operation of multiplication by a scalar or an exponentiation

Abstract

A cryptographic data processing method, implemented in an electronic device including a processor, the method including steps of providing a point of an elliptic curve in a Galois field, and a whole number, and of calculating a scalar product of the point by the number, the coordinates of the point and the number having a size greater than the size of words that may be processed directly by the processor, the scalar multiplication of the point by the number including steps of: storing scalar multiples of the point multiplied-by the number 2 raised to a power belonging to a series of whole numbers, setting a resulting point for each non-zero bit of the first number, adding the resulting point and one of the stored multiple points, and providing at the output of the processor the resulting point as result of the scalar product.

Claims

1. A cryptographic data processing method comprising: receiving, by a processor in an electronic device, a point of an elliptic curve in a Galois field and a first integer number, the first integer number being a private encryption key; and performing, by the processor, a cryptographic operation including a scalar multiplication calculation of the point by the first integer number, the point being defined by coordinates, the coordinates of the point and the first integer number having a size greater than a size of words that can be processed, by the processor, without being divided into smaller words, the scalar multiplication calculation of the point by the first integer number including: storing a set of multiple points each resulting from a scalar product of the point by 2 raised to a power belonging to a set of integer numbers, initializing a resulting point belonging to the elliptic curve, performing several iterations to take into account each of the bits of the first integer number only once, each iteration including: a calculation of a bit combination of several bits of the first integer number, and when the bit combination is non-zero, modifying the resulting point by performing an addition between a prior value of the resulting point and one of the stored multiple points corresponding to ranks of bits in the bit combination, and providing, by the processor, the resulting point as result of the scalar multiplication calculation of the point by the integer first number, the resulting point including a public encryption key corresponding with the private encryption key.

2. The method according to claim 1, wherein the bits of the first integer number are taken into account in a random or pseudo-random order when calculating the resulting point.

3. The method according to claim 1, wherein additions between prior values of the resulting point and the stored multiple points are performed in affine coordinates.

4. The method according to claim 1, wherein the additions between prior values of the resulting point and the stored multiple points are performed in projective coordinates.

5. The method according to claim 4, wherein the scalar products of the point are stored in affine coordinates, which are transformed into projective coordinates by adding, to the affine coordinates, a third coordinate having a value set to 1.

6. The method according to claim 1, wherein the first integer number and the coordinates of the point are non-adjacent-form (NAF) coded, the method further comprising, for each of the bit combinations of the first integer number less than or equal to −1, performing an adding calculation between the resulting point and an opposite of one of the stored multiples corresponding to a rank in the first number of the bit combination.

7. The method according to claim 1, further comprising: randomly choosing the first integer number as the private encryption key; and choosing the resulting point of the scalar multiplication of the point by the first integer number or one of the coordinates of the resulting point as the public encryption key corresponding to the private encryption key.

8. The method according to claim 1, further comprising signing a message, the signing including: randomly choosing a second integer number; applying a hashing function to the message to be signed; and calculating a signature of the message from the following equations:
x=i mod n
y=k.sup.−1(H(m)+s.Math.x)mod n, in which x and y represent the signature of the message m, i being the public encryption key, k being the second integer number, H(m) being the hashing function applied to the message m, s being the private encryption key, and n being a smallest positive integer number such that the scalar product of n by the point is equal to a point at infinity of the elliptic curve.

9. An electronic device comprising a processor configured to: receive a point of an elliptic curve in a Galois field and a first integer number, the first integer number being a private encryption key; and perform a cryptographic operation including a scalar multiplication calculation of the point by the first integer number, the point being defined by coordinates, the coordinates of the point and the first integer number having a size greater than a size of words that can be processed, by the processor, without being divided into smaller words, the scalar multiplication calculation of the point by the first integer number including: storing a set of multiple points each resulting from a scalar product of the point by 2 raised to a power belonging to a set of integer numbers; initializing a resulting point belonging to the elliptic curve; performing several iterations to take into account each of the bits of the first integer number only once, each iteration including: a calculation of a bit combination of several bits of the first integer number; and when the bit combination is non-zero, modifying the resulting point by performing an addition between a prior value of the resulting point and one of the stored multiple points corresponding to ranks of bits in the bit combination; and providing, by the processor, the resulting point as result of the scalar multiplication calculation of the point by the first integer number, the resulting point including a public encryption key corresponding with the private encryption key.

10. The device according to claim 9, wherein the device is portable and autonomous, or is of a smart card type.

11. The device according to claim 9, wherein the bits of the first integer number are taken into account in a random or pseudo-random order when calculating the resulting point.

12. The device according to claim 9, wherein additions between prior values of the resulting point and the stored multiple points are performed in affine coordinates.

13. The device according to claim 9, wherein the additions between prior values of the resulting point and the stored multiple points are performed in projective coordinates.

14. The device according to claim 13, wherein the scalar products of the point are stored in affine coordinates, which are transformed into projective coordinates by adding, to the affine coordinates, a third coordinate having a value set to 1.

15. The device according to claim 9, wherein the first integer number and the coordinates of the point are non-adjacent-form (NAF) coded, the processor being further configured to, for each of the bit combinations of the first integer number, less than or equal to −1, performing an adding calculation between the resulting point and an opposite of one of the stored multiples corresponding to a rank in the first integer number of the bit combination.

16. The device according to claim 9, wherein the processor is further configured to: randomly choose the first integer number as the private encryption key, and choose the resulting point of the scalar multiplication of the point by the first integer number or one of the coordinates of the resulting point as a public encryption key corresponding to the private encryption key.

17. The device according to claim 9, wherein the processor is configured to sign a message, by: randomly choosing a second integer number, applying a hashing function to the message to be signed, and calculating a signature of the message from the following equations:
x=i mod n
y=k.sup.−1(H(m)+s.Math.x)mod n, in which x and y represent the signature of the message m, i being the public encryption key, k being the second integer number, H(m) being the hashing function applied to the message m, s being the private encryption key, and n being a smallest positive integer number such that the scalar product of n by the point is equal to a point at infinity of the elliptic curve.

Description

(1) FIG. 1 represents in block diagram form an electronic device DV1 configured to execute a cryptographic calculation including one or more of the algorithms A3, A4, A4′, A5, A5′, A6, A6′ applied to big numbers. The device DV1 can be an integrated circuit on a semiconductor chip arranged on a portable medium like a plastic card, the assembly forming a smart card. The device DV1 can also be any device equipped with a multi-task processor, such as a smartphone, a multimedia player, a tactile tablet or a personal computer. The device DV1 can also be a component of such a device, for example coupled to a main processor of the device.

(2) The device DV1 comprises a processor PROC, a calculation block AB1 configured to execute an addition of points P and Q belonging to an elliptic curve, a calculation block DB1 configured to execute a doubling of a point P belonging to an elliptic curve, a memory MEM and a communication interface circuit IC. The interface circuit IC can be of the contact or contactless type, for example an RF or UHF interface circuit operating by inductive coupling or by electrical coupling. The calculation blocks AB1, DB1 can each comprise a coprocessor equipped with a programmable central unit, an entirely hardware coprocessor of state machine type. The calculation blocks AB1, DB1 may merely correspond to a function called by a main program executed in particular by the processor PROC. The two calculation blocks AB1, DB1 can also be integrated into a same component (coprocessor or state machine).

(3) In a conventional manner per se, a variable is said to be “big” when its size (in number of bits) is greater than that of the calculation registers of the processor PROC. The latter itself performs, without using the calculation blocks AB1, DB1, operations of numbers that are smaller than or equal to the size of its calculation registers, and uses the calculation blocks AB1, DB1 to perform adding and doubling operations concerning elliptic curve points having big coordinates. For example, if the size of the calculation registers of the processor PROC is 32 bits, a big variable is a variable greater than 32 bits. In cryptography based on elliptic curves, the variables handled (coordinates of the points of elliptic curves, parameters p—modulus, b, n—number of points belonging to the elliptic curve, Gx, Gy—coordinates of the base point G) can reach several hundreds of bits (typically 160, 192, 224, 256, 320, 384, 521 bits).

(4) The memory MEM is coupled to the processor PROC and enables the device DV1 to store a secret key k. The processor PROC receives, through the interface circuit IC, a message m to be ciphered, deciphered, or signed, or a signature to be checked, and sends back a ciphered or deciphered message, or a signature, of the F.sub.k(m) type, F.sub.k being a cryptography function based on the key k comprising a scalar multiplication calculation executed by means of one of the algorithms presented in Appendix II. During the scalar multiplication calculation, the processor PROC uses the calculation blocks AB1, DB1, by providing points P, Q to the calculation block AB1 which sends back the sum P [+] Q, and by providing a point P to the calculation block DB1 which sends back the double [2].Math.P. A part of the memory MEM can also be used as buffer memory to store the content of the registers R and DP mentioned in the algorithms presented in Appendix II.

(5) The device DV1 may also comprise calculation blocks configured to execute a modular multiplication of big numbers and a modular squaring of a big number, these calculation blocks being used by the calculation blocks AB1, DB1 to implement the equations (1) to (6).

(6) The execution times per bit of the scalar number k and the number of large registers used (i.e. of points to be stored) for each of the algorithms previously presented are grouped together in the following table 1:

(7) TABLE-US-00001 TABLE 1 Execution time per bit of the scalar Execution time per k in homogeneous bit of the scalar projective coordi- Number k in homogeneous nates using of Algorithm projective coordinates combined additions registers ADD ≈13.6 .Math. M ≈10.6 .Math. M DOUBLE ≈11 .Math. M ≈11 .Math. M A1 ≈17.8 .Math. M ≈16.3 .Math. M 1 A1′ ≈17.8 .Math. M 2 A2 ≈24.6 .Math. M ≈21.6 .Math. M 2 A3 ≈17.8 .Math. M v + 1 A4 ≈6.8 .Math. M ≈5.3 .Math. M v + 1 A5 ≈(5.1 + 51.8/v) .Math. M ≈(3.98 + 51.8/v) .Math. M v/2 + 3 A6/m = 3 ≈(3.97 + 172/v) .Math. M ≈(3.09 + 172/v) .Math. M v/3 + 7 A6/m = 4 ≈(3.19 + 455/v) .Math. M ≈(2.48 + 455/v) .Math. M v/4 + 15 A6/m = 8 ≈(1.69 + 14,000/v) .Math. M ≈(1.32 + v/8 + 255 14,000/v) .Math. M

(8) In Table 1, v represents the number of bits of the scalar number k, and M represents the computing time of a multiplication of big numbers, M also varying according to the number v. The numerical values relating to the execution time contained in Table 1 have been obtained by considering that the cost in computing time of a squaring of a big number is equal to 0.8 times that of a multiplication of big numbers, and by disregarding the execution time of the additions and subtractions of big numbers. Table 1 also mentions the execution time of the adding and doubling operations of a point. In the algorithms A5, A6, the additional term contained in the columns relating to the execution time, represents the computing time taken to execute step 3 in relation to the number of bits v. The number of adding and doubling operations performed in step 3 rapidly increases with the value of m.

(9) It emerges from Table 1 that the algorithms A4 to A6 reach a computing time per bit of the scalar number substantially equal to or lower than half the computing time of an addition of points of an elliptic curve.

(10) According to one embodiment, the algorithms presented in Appendix II are suited to processing scalar numbers coded not in binary but in another form, for example in NAF coding (Non-Adjacent Form). In NAF coding, each bit of a number can have three states (−1,0,1) and each bit different from 0 of the number is preceded and followed by a bit on 0; the first and last bits of the number can have any value. The result is that the average number of bits on 0 of a number (Hamming weight) goes from half in binary to one third in NAF coding, whereas the number of bits of a number in NAF coding is identical or increased by 1 compared to that of the same number coded in binary. Thus, the algorithms A4″, A5″, A6″, presented in Appendix III are adaptations of the algorithms A4, A5, A6 to a representation of the numbers in NAF coding. In comparison with the algorithms A4, A5, A6, the algorithms A4″, A5″, A6″comprise an additional step 2.3 to deal with the case in which the bit k.sub.i is equal to −1. In this case, the multiple DP[i] or DP[u] is subtracted from the point R. Conventionally, the operation of subtracting points involves an addition, the sign of the second operand being changed. In the group of points of an elliptic curve on a Galois field of F.sub.p type, p being a prime number greater than 3, the change of sign of a point P(x,y) in affine coordinates involves changing the sign of its second coordinate y. In the group of points of an elliptic curve on a Galois field of F.sub.2.sub.m type, the change of sign of a point P(x,y) in affine coordinates involves replacing the second coordinate with the sum x+y of the coordinates of the point.

(11) It will be understood that the algorithms A4′, A5′, A6′ can be adapted in a similar way to process numbers in NAF coding, to counter attacks of SPA and/or DPA type.

(12) Given the average ratio of bits different from 0 equal to 1/3, in a number in NAF coding, the execution times per bit of the scalar number k for each of the algorithms A4″, A5″, A6″ are contained in Table 2 below:

(13) TABLE-US-00002 TABLE 2 Execution time per Execution time per bit of the scalar k in bit of the scalar homogeneous projective k in homogeneous coordinates using Algorithm projective coordinates combined additions A4″ ≈4.53 .Math. M ≈3.53 .Math. M A5″ ≈3.478 + 51.8/v) .Math. M ≈(2.94 + 51.8/v) .Math. M A6″/m = 3 ≈3.19 + 172/v) .Math. M ≈(2.49 + 172/v) .Math. M A6″/m = 4 ≈(2.73 + 455/v) .Math. M ≈(2.13 + 455/v) .Math. M A6″/m = 8 ≈(1.63 + 14,000/v) .Math. M ≈(1.27 + 14,000/v) .Math. M
The number of large registers used by the algorithms A4″, A5″, A6″remains unchanged compared to those used by the algorithms A4, A5, A6.

(14) The algorithms presented in Appendices II and III can be implemented in a public key digital signature algorithm of ECDSA type. The ECDSA algorithm involves choosing an elliptic curve E(a,b) on a Galois field F.sub.q, and a base point G(Gx,Gy) of the elliptic curve chosen E(a,b). The number n is the smallest positive whole number such that [n].Math.G=Ø (point at infinity). The aim is then to generate a pair of public and private keys. The private key s can be chosen randomly between 1 and n−1. The public key Q is chosen equal to [s].Math.G. As the point G is fixed, the doubles of the point G can be calculated only once and stored in a table. The public key Q can be obtained by the algorithm A3 or by the other algorithms presented in Appendix II and III, if the table DP containing the multiples in 2.sup.i of the point G has been completed.

(15) To sign a message m, a number k between 1 and n−1 is randomly chosen. The coordinates of the point P(i,j)=[k].Math.G are calculated. If x=i mod n is equal to 0, it is necessary to choose another number k. The number y=k.sup.−1(H(m)+sx)mod n is then calculated, where H(m) is the result of a hashing function such as SHA-1, applied to the message m. If the number y obtained is zero, it is necessary to start the calculation again by choosing another value for the number k. The signature is made up of the pair (x, y).

(16) To check the signature (x,y), it is first necessary to check that the point Q constituting the public key is different from Ø, that it belongs to the elliptic curve E(a,b), that [n].Math.Q=Ø and that x and y are indeed between 1 and n−1. Then, the coordinates of the point P(i,j) must be calculated in the following manner:
P(i,j)=[H(m).Math.y.sup.−1 mod n].Math.G+[x.Math.y.sup.−1 mod n].Math.Q
and it is necessary to check that x=i mod n. The multiples in 2.sup.i of the point Q can also be stored in a table if the pair of keys (s,Q) can be used several times to sign and check the signature of a message.

(17) The algorithms presented in Appendix II and III can also be implemented in the ECIES ciphering/deciphering algorithm. A pair of private and public keys (s, Q) can be generated as in the ECDSA algorithm. To cipher a message m, a number r between 1 and n−1 is randomly chosen, and the points R=[r].Math.G and P(x,y)=[r].Math.Q are calculated, Q being the public key of the recipient of the ciphered message. The condition P≠Ø must be checked. Here again, the multiples in 2.sup.i of the points G and Q can be calculated once and for all and stored in tables. A key derivation function KDF is then used to generate symmetric keys Ke, Km, such that (Ke, Km)=KDF(x,S1), S1 being a datum shared with the recipient of the ciphered message. The message m is then ciphered by a symmetric ciphering algorithm E using the key Ke. A datum d is then calculated by applying a hashing function to the key Km and to another datum S2 shared with the recipient of the message. The result c of the ciphering of the message is sent to the recipient of the ciphered message with the datum d and the public key R.

(18) To decipher the ciphered message (c,d) the recipient of the message calculates the point P(x,y)=[s].Math.R (=[r].Math.Q). The point P obtained must be different from Ø. The same key derivation function KDF and the shared datum S1 are then used to generate the symmetric keys Ke, Km. The number d is then calculated by using the same formula applied to the key Km and to the shared datum S2. If the number d obtained is identical to the number d received, the message can be deciphered by applying to the ciphered datum c received, the symmetric deciphering function corresponding to the ciphering function used, using the key Ke.

(19) It will be understood by those skilled in the art that the present invention is susceptible of various alternative embodiments and various applications. In particular, the invention is not limited to the applications presented, but applies to any other elliptic curve cryptography application in which the doubles of a point are reused several times.

(20) The present invention is not limited either to the projective coordinates presented, but applies to any other type of coordinates, the adaptation of the algorithms presented to these other types of coordinates being within the understanding of those skilled in the art.

(21) The present invention is not limited either to storing all the multiples in 2.sup.i or 2.sup.m.Math.i of the point P being the subject of a scalar multiplication, up to v or

(22) $.Math.\frac{v}{m}.Math.,$
i.e. the smallest whole number greater than v/m. Indeed, it can be desirable to limit the memory space occupied by the registers DP. For this purpose, the missing multiples can be calculated upon the iterative calculation of the result of the multiplication, only if necessary. Thus, in the algorithms A4, A4′ and A4″, only the multiples in 2.sup.2i or 2.sup.2i+1 may be stored, it being possible to calculate the missing multiples according to the needs of the scalar multiplication calculation, merely by performing a doubling operation to multiply the immediately lower multiple DP[i] by 2. This arrangement can easily be extrapolated to the algorithms A5 and A6 and their derived algorithms. It may also be considered to store only the first multiples in 2.sup.i or 2.sup.m.Math.i of the point P, the other multiples being calculated upon each iteration as in the algorithm A3.

APPENDIX I

Being an Integral Part of the Description

(23) TABLE-US-00003 Algorithm A1 - Multiplication by a Double & Add scalar, from left to right Input: a point P belonging to the elliptic curve E on the Galois field F.sub.q a whole scalar k of v bits such that k = (k.sub.v−1 k.sub.v−2.... k.sub.0).sub.2 Requires: a register R of the size of the point P Output: [k].Math.P Step 1: R = Ø Step 2: for s ranging from v−1 to 0, do: Step 2.1: R = [2].Math.R (DOUBLE) Step 2.2: if k.sub.s = 1 then R = R [+] P (ADD) Step 3: Send back R

(24) TABLE-US-00004 Algorithm A1′ - Multiplication by a Double & Add scalar, from right to left Input: a point P belonging to the elliptic curve E on the Galois field F.sub.q a whole scalar k of v bits such that k = (k.sub.v−1 k.sub.v−2.... k.sub.0).sub.2 Requires: two registers R.sub.0, R.sub.1 of the size of the point P Output: [k].Math.P Step 1: R.sub.0 = Ø; R.sub.1 = P Step 2: for s ranging from 0 to v−1, do: Step 2.1: if k.sub.s = 1 then R.sub.0 = R.sub.0 [+] R.sub.1 (ADD) Step 2.2: R.sub.1 = [2].Math.R.sub.1 (DOUBLE) Step 3: Send back R.sub.0 “P[+]Q” represents the addition of two points P and Q of an elliptic curve “Ø” represents the neutral element of the F.sub.q field (such that P[+]Ø = Ø[+]P = P)

(25) TABLE-US-00005 Algorithm A2 - “Montgomery Ladder” (from left to right) Input: a point P belonging to the elliptic curve E on the Galois field F.sub.q a whole scalar k of v bits such that k = (k.sub.v−1 k.sub.v−2.... k.sub.0).sub.2 Requires: two registers R.sub.0, R.sub.1 of the size of the point P Output: [k].Math.P Step 1: R.sub.0 = Ø; R.sub.1 = P Step 2: for s ranging from v−1 to 0, do: Step 2.1: b = k.sub.s Step 2.2: R.sub.1−b = R.sub.1−b [+] R.sub.b (ADD) Step 2.3: R.sub.b = [2].Math.R.sub.b (DOUBLE) Step 3: Send back R.sub.0

APPENDIX II

Being an Integral Part of the Description

(26) TABLE-US-00006 Algorithm A3 - Multiplication by a “Double & Add” scalar Input: a point P belonging to the elliptic curve E on the Galois field F.sub.q a whole scalar k of v bits such that k = (k.sub.v−1 k.sub.v−2.... k.sub.0).sub.2 Requires: a register R of the size of the point P  a set of v+1 registers DP of the size of the point P Output: [k].Math.P Step 1: R = Ø; DP[0] = P Step 2: for i ranging from 0 to v−1, do: Step 2.1: DP[i+1] = [2].Math.DP[i] (DOUBLE) Step 2.2: if k.sub.i = 1 then R = R [+] DP[i] (ADD) Step 3: Send back R

(27) TABLE-US-00007 Algorithm A4 - Multiplication by a Doubles Stored & Add Only scalar Input: a point P belonging to the elliptic curve E on the Galois field F.sub.q a whole scalar k of v bits such that k = (k.sub.v−1 k.sub.v−2.... k.sub.0).sub.2 Requires: a register R of the size of the point P  a set of v registers DP of the size of the point P such that DP[i]=[2.sup.i].Math.P, with 0 ≦ i < v Output: [k].Math.P Step 1: R = Ø Step 2: for i ranging from 0 to v−1, do: Step 2.2: if k.sub.i = 1 then R = R [+] DP[i] (ADD) Step 3: Send back R

(28) TABLE-US-00008 Algorithm A5-Multiplication by a Doubles Stored & Add Only scalar Input: a point P belonging to the elliptic curve E on the Galois field F.sub.q  a whole scalar k of v bits such that k = (k.sub.v−1 k.sub.v−2 . . . k.sub.0).sub.2 Requires: a set R of three registers of the size of the point P  $a\mathrm{set}\mathrm{of}.Math.\frac{v}{2}.Math.\mathrm{registers}\mathrm{DP}\mathrm{of}\mathrm{the}\mathrm{size}\mathrm{of}\mathrm{the}\mathrm{point}P$   $\mathrm{such}\mathrm{that}\mathrm{DP}\left[i\right]=\left[2^{2i}\right].Math.P,\mathrm{with}0\le i<.Math.\frac{v}{2}.Math.$ Output: [k] .Math. P Step 1: R[1] = ∅; R[2] = ∅; R[3] = ∅ $\mathrm{Step}2\text{:}\mathrm{for}i\mathrm{ranging}\mathrm{from}0\mathrm{to}.Math.\frac{v}{2}.Math.-1,\mathrm{do}\text{:}$  Step 2.1: u = k.sub.2i + 2k.sub.2i+1  Step 2.2: if u ≧ 1 then R[u] = R[u][+] DP[i] (ADD) Step 3: R[1] = R[1][+] R[3] [+] [2] .Math. (R[2] [+] R[3]) (ADD) Step 4: Send back R[1] |X| representing the smallest whole number greater than or equal to x

(29) TABLE-US-00009 Algorithm A6-Multiplication by a Doubles stored & Add Only scalar Input: a point P belonging to the elliptic curve E on the Galois field F.sub.q  a whole scalar k of v bits such that k = (k.sub.v−1 k.sub.v−2 . . . k.sub.0).sub.2 Requires: a set R of 2.sup.m − 1 registers of the size of the point P (m > 2)  $a\mathrm{set}\mathrm{of}.Math.\frac{v}{m}.Math.\mathrm{registers}\mathrm{DP}\mathrm{of}\mathrm{the}\mathrm{size}\mathrm{of}\mathrm{the}\mathrm{point}P$   $\mathrm{such}\mathrm{that}\mathrm{DP}\left[i\right]=\left[2^{m.Math.i}\right].Math.P,\mathrm{with}0\le i<.Math.\frac{v}{m}.Math.$ Output: [k] .Math. P Step 1: for j ranging from 1 to 2.sup.m − 1, do R[j] = ∅ 0$\mathrm{Step}2\text{:}\mathrm{for}i\mathrm{ranging}\mathrm{from}0\mathrm{to}.Math.\frac{v}{m}.Math.-1,\mathrm{do}\text{:}$  $\mathrm{Step}2.1\text{:}u=\underset{j=0}{\overset{m-1}{.Math.}}{2}^j.Math.k_{m.Math.i+j}\left(\mathrm{with}{k}_i=0\mathrm{if}i>v-1\right)$  Step 2.2: if u ≧ 1 then R[u] = R[u] [+] DP[i] (ADD) $\mathrm{Step}3\text{:}R\left[1\right]=\left[\underset{j=1}{\overset{2^m-1}{.Math.}}\right]\left[j\right].Math.R\left[j\right]\left(\mathrm{ADD}\right)$ Step 4: Send back R[1] └Σ┘ represents the adding operator for adding points in the group of points of the elliptic curve, with coordinates in the field F.sub.q.

(30) TABLE-US-00010 Algorithm A4′ - Secured multiplication by a Doubles Stored & Add Only scalar Input: a point P belonging to the elliptic curve E on the Galois field F.sub.q a whole scalar k of v bits such that k = (k.sub.v−1 k.sub.v−2.... k.sub.0).sub.2 Requires: a register R of the size of the point P  a set of v registers DP of the size of the point P such that DP[i]=[2.sup.i].Math.P, with 0 ≦ i < v Output: [k].Math.P Step 1: R = Ø Step 2′: Generate a random permutation σ in {0,...,v−1} Step 2: for i ranging from 0 to v−1, do: Step 2.2: if kσ.sub.(i) = 1 then R = R [+] DP[σ(i)] (ADD) Step 3: Send back R

(31) TABLE-US-00011 Algorithm A5′-Secured multiplication by a Doubles Stored & Add Only scalar Input: a point P belonging to the elliptic curve E on the Galois field F.sub.q  a whole scalar k of v bits such that k = (k.sub.v−1 k.sub.v−2 . . . k.sub.0).sub.2 Requires: a set R of three registers of the size of the point P  $a\mathrm{set}\mathrm{of}.Math.\frac{v}{2}.Math.\mathrm{registers}\mathrm{DP}\mathrm{of}\mathrm{the}\mathrm{size}\mathrm{of}\mathrm{the}\mathrm{point}P$   $\mathrm{such}\mathrm{that}\mathrm{DP}\left[i\right]=\left[2^{2i}\right].Math.P,\mathrm{with}0\le i<.Math.\frac{v}{2}.Math.$ Output: [k] .Math. P Step 1: R[1] = ∅; R[2] = ∅; R[3] = ∅ $\mathrm{Step}{2}^{\prime }\text{:}\mathrm{Generate}a\mathrm{random}\mathrm{permutation}\sigma \mathrm{with}.Math.\frac{v}{2}.Math.$ $\mathrm{elements}\mathrm{in}\left\{0,\mathrm{.Math.},.Math.\frac{v}{2}.Math.-1\right\}$ $\mathrm{Step}2\text{:}\mathrm{for}i\mathrm{ranging}\mathrm{from}0\mathrm{to}.Math.\frac{v}{2}.Math.-1,\mathrm{do}\text{:}$  Step 2.1: u = k.sub.2σ(i) + 2k.sub.2σ(i)+1  Step 2.2: if ≧ = 1 then R[u] = R[u] [+] DP[σ(i)] (ADD) Step 3: R[1] = R[1] [+] R[3] [+] [2] .Math. (R[2] [+] R[3]) (ADD) Step 4: Send back R[1]

(32) TABLE-US-00012 Algorithm A6′-Multiplication by a Doubles stored & Add Only scalar Input: a point P belonging to the elliptic curve E on the Galois field F.sub.q  a whole scalar k of v bits such that k = (k.sub.v−1 k.sub.v−2 . . . k.sub.0).sub.2 Requires: a set R of 2.sup.m − 1 registers of the size of the point P (m > 2)  $a\mathrm{set}\mathrm{of}.Math.\frac{v}{m}.Math.\mathrm{registers}\mathrm{DP}\mathrm{of}\mathrm{the}\mathrm{size}\mathrm{of}\mathrm{the}\mathrm{point}P$   $\mathrm{such}\mathrm{that}\mathrm{DP}\left[i\right]=\left[2^{m.Math.i}\right].Math.P,\mathrm{with}0\le i<.Math.\frac{v}{m}.Math.$ Output: [k] .Math. P Step 1: for j ranging from 1 to 2.sup.m − 1, do R[j] = ∅ 0$\mathrm{Step}{2}^{\prime }\text{:}\mathrm{Generate}a\mathrm{random}\mathrm{permutation}\sigma \mathrm{with}.Math.\frac{v}{2}.Math.$ $\mathrm{elements}\mathrm{in}\left\{0,\mathrm{.Math.},.Math.\frac{v}{m}.Math.-1\right\}$ $\mathrm{Step}2\text{:}\mathrm{for}i\mathrm{ranging}\mathrm{from}0\mathrm{to}.Math.\frac{v}{m}.Math.-1,\mathrm{do}\text{:}$  $\mathrm{Step}2.1\text{:}u=\underset{j=0}{\overset{m-1}{.Math.}}{2}^j{k}_{m\sigma \left(i\right)+j}\left(\mathrm{with}{k}_i=0\mathrm{if}i>v-1\right)$  Step 2.2: if u ≧ 1 then R[u] = R[u] [+] DP[σ(i)] (ADD) $\mathrm{Step}3\text{:}R\left[1\right]=\left[\underset{j=1}{\overset{2^m-1}{.Math.}}\right]\left[j\right].Math.R\left[j\right]\left(\mathrm{ADD}\right)$ Step 4: Send back R[1]

APPENDIX III

Being an Integral Part of the Description

(33) TABLE-US-00013 Algorithm A4″ - Multiplication by a Doubles Stored & Add Only scalar Input: a point P belonging to the elliptic curve E on the Galois field F.sub.q a whole scalar k of v bits such that k = (k.sub.v−1 k.sub.v−2.... k.sub.0).sub.2, NAF coded Requires: a register R of the size of the point P  a set of v registers DP of the size of the point P such that DP[i]=[2.sup.i].Math.P, with 0 ≦ i < v Output: [k].Math.P Step 1: R = Ø Step 2: for i ranging from 0 to v−1, do: Step 2.2: if k.sub.i = 1 then R = R [+] DP[i] (ADD) Step 2.3: if k.sub.i = −1 then R = R [−] DP[i] (ADD) Step 3: Send back R

(34) TABLE-US-00014 Algorithm A5″-Multiplication by a Doubles Stored & Add Only scalar Input: a point P belonging to the elliptic curve E on the Galois field F.sub.q  a whole scalar k of v bits such that k = (k.sub.v−1 k.sub.v−2 . . . k.sub.0).sub.2, NAF coded Requires: a set R of three registers of the size of the point P  $a\mathrm{set}\mathrm{of}.Math.\frac{v}{2}.Math.\mathrm{registers}\mathrm{DP}\mathrm{of}\mathrm{the}\mathrm{size}\mathrm{of}\mathrm{the}\mathrm{point}P$   $\mathrm{such}\mathrm{that}\mathrm{DP}\left[i\right]=\left[2^{2i}\right].Math.P,\mathrm{with}0\le i<.Math.\frac{v}{2}.Math.$ Output: [k] .Math. P Step 1: R[1] = ∅; R[2] = ∅; R[3] = ∅ $\mathrm{Step}2\text{:}\mathrm{for}i\mathrm{ranging}\mathrm{from}0\mathrm{to}.Math.\frac{v}{2}.Math.-1,\mathrm{do}\text{:}$  Step 2.1: u = k.sub.2i + 2k.sub.2i+1  Step 2.2: if u ≧ 1 then R[u] = R[u] [+] DP[i] (ADD)  Step 2.3: if u ≦ −1then R[u] = R[−u] [−] DP[i] (ADD) Step 3: R[1] = R[1] [+] R[3] [+] [2] .Math. (R[2] [+] R[3]) (ADD) Step 4: Send back R[1]

(35) TABLE-US-00015 Algorithm A6″-Multiplication by a Doubles stored & Add Only scalar Input: a point P belonging to the elliptic curve E on the Galois field F.sub.q  a whole scalar k of v bits such that k = (k.sub.v−1 k.sub.v−2, . . . k.sub.0).sub.2, NAF coded Requires: a set R of 2.sup.m − 1 registers of the size of the point P (m > 2)  $a\mathrm{set}\mathrm{of}.Math.\frac{v}{m}.Math.\mathrm{registers}\mathrm{DP}\mathrm{of}\mathrm{the}\mathrm{size}\mathrm{of}\mathrm{the}\mathrm{point}P$   $\mathrm{such}\mathrm{that}\mathrm{DP}\left[i\right]=\left[2^{m.Math.i}\right].Math.P,\mathrm{with}0\le i<.Math.\frac{v}{2}.Math.$ Output: [k] .Math. P Step 1: for j ranging from 1 to 2.sup.m − 1, do R[j] = ∅ 0$\mathrm{Step}2\text{:}\mathrm{for}i\mathrm{ranging}\mathrm{from}0\mathrm{to}.Math.\frac{v}{m}.Math.-1,\mathrm{do}\text{:}$  $\mathrm{Step}2.1\text{:}u=\underset{j=0}{\overset{m-1}{.Math.}}{2}^j.Math.k_{m.Math.i+j}\left(\mathrm{with}{k}_i=0\mathrm{if}i>v-1\right)$  Step 2.2: if u ≧ 1 then R[u] = R[u] [+] DP[i] (ADD)  Step 2.3: if u ≦ −1 then R[u] = R[−u] [−] DP[i] (ADD) $\mathrm{Step}3\text{:}R\left[1\right]=\left[\underset{j=1}{\overset{2^m-1}{.Math.}}\right]\left[j\right].Math.R\left[j\right]\left(\mathrm{ADD}\right)$ Step 4: Send back R[1]