Cryptographic processing method comprising multiplication of a point of an elliptic curve by a scalar
The invention relates to a cryptographic processing method comprising multiplication of a point P of an elliptic curve on a Galois field by a scalar k, the multiplication comprising steps of: storing, in a first register, a zero point of the Galois field, executing a loop comprising at least one iteration comprising steps of: selecting a window of w bits in the non-signed binary representation of the scalar k, w being a predetermined integer independent of the scalar k and strictly greater than 1, calculating multiple points of P being each associated with a bit of the window and of the form ±2 i P, adding or not in the first register of multiple points stored, depending of the value of the bit of the window with which the multiple points are associated, wherein the loop ends once each bit of the non-signed binary representation of the scalar k has been selected, returning a value stored in the first register. If all the bits of the window selected during an iteration of the loop are zero, the iteration comprises at least one dummy execution of the addition function, and/or if all the bits of the window during an iteration of the loop are non-zero, the multiple points to be added in the first register during the step are determined from a non-adjacent form associated with the window.
1. A cryptographic processing method executed by at least one processor, the method comprising multiplication of a point P of an elliptic curve on a Galois field by a scalar k, multiplication comprising:
storing a zero point of the Galois field in a first register,
executing a loop comprising at least one iteration, wherein one iteration of the loop comprises:
selecting a window of w bits in a non-signed binary representation of the scalar k, wherein w is a predetermined integer independent of the scalar k and is strictly greater than 1,
calculating, by means of a doubling function, and storing, in at most w second registers, multiple points of P, wherein each multiple point is associated with a bit of the window and is of form ±2 i P where i is a integer,
adding or not, in the first register, multiple points stored in the second register by means of an addition function, wherein each multiple point is added or not in the first register depending of the value of the bit of the window with which the multiple point is associated,
wherein the loop ends once each bit of the non-signed binary representation of the scalar k has been selected in an iteration,
after the end of the loop, returning a value stored in the first register, and wherein:
if all the bits of the window selected during an iteration of the loop are zero, the iteration comprises at least one dummy execution of the addition function, and/or if all the bits of the window selected during an iteration of the loop are non-zero, the multiple points to be added in the first register during the step are determined from a non-adjacent form associated with the window.
2. The method according to claim 1 , wherein for each iteration of the loop, there is n+m≥1, where n is the number of any dummy executions of the addition function during the iteration, and m is the number of any executions of the addition function during the addition step of the iteration.
3. The method according to claim 2 , wherein n+m is identical for several iterations of the loop, or even for all the iterations of the loop.
4. The method according to claim 1 , wherein the windows are selected according to order of reading of the binary representation of the scalar k going from right to left.
5. The method according to claim 1 , wherein, if several bits of the window selected during an iteration of the loop are non-zero, then multiples are added in the first register during the iteration in random order.
6. The method according to claim 1 wherein, if all the bits of the window selected during an iteration of the loop are non-zero, a multiple point of negative value associated with a least significant bit of said non-adjacent form is added in the first register during the iteration.
7. The method according to claim 1 , wherein, if all the bits of the window selected during an iteration of the loop are non-zero, a multiple point associated with a most significant bit of said non-adjacent form is added in the first register in a later iteration or after the end of the loop.
8. The method according to claim 1 , wherein, if all the bits of the window selected during the q-th iteration of the loop are non-zero, a multiple point of value 2 qw P is added in the first register during the q-th iteration.
9. A non-transitory computer-readable medium comprising code instructions for causing at least one processor to perform the method in claim 1 .
10. A cryptographic processing device comprising
at least one processor configured to multiply a point P of an elliptic curve on a Galois field by a scalar k,
at least one memory comprising a first register and w second registers,
wherein the multiplication comprises steps of:
storing a zero point of the Galois field in the first register,
executing a loop comprising at least one iteration, wherein one iteration of the loop comprises steps of:
selecting a window of w bits in a non-signed binary representation of the scalar k, wherein w is a predetermined integer independent of the scalar k and strictly greater than 1,
calculation, by means of a doubling function, and storage, in at most w of the second registers, of multiple points of P, each multiple point being associated with a bit of the window and being of the form ±2 i P where is a integer,
addition or not in the first register of multiple points stored in the second register by means of an addition function, each multiple point being added or not in the first register or not as a function of the value of the bit of the window with which the multiple point is associated,
wherein the loop ends once each bit of the non-signed binary representation of the scalar k has been selected in an iteration,
after the end of the loop, returning a value stored in the first register,
wherein the processors is configured such that:
if all the bits of the window selected during an iteration of the loop are zero, the iteration comprises at least one dummy execution of the addition function, and/or if all the bits of the window selected during an iteration of the loop are non-zero, the multiple points to be added in the first register during the step are determined from a non-adjacent form associated with the window.
11. A smart card comprising a cryptographic processing device according to claim 10 .