Cryptographic processing method comprising multiplication of a point of an elliptic curve by a scalar

Patent metadata

Field	Value
Publication number	US-10664240-B2
Application number	US-201715727058-A
Country	US
Kind code	B2
Filing date	Oct 6, 2017
Priority date	Oct 7, 2016
Publication date	May 26, 2020
Grant date	May 26, 2020

Abstract

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 ±2iP, 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.

First claim

The invention claimed is:

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 .

Assignees

• Idemia Identity & Security France
• Idemia Identify & Security France

Inventors

• Servant Victor
• Dabosville Guillaume

Classifications

• G06K19/07

  with integrated circuit chips · CPC title

• G06F2207/7261

  Uniform execution, e.g. avoiding jumps, or using formulae with the same power profile · CPC title

• G06F9/30098

  Register arrangements · CPC title

• G06F7/725 Primary

  over elliptic curves · CPC title

• H04L9/003

  for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA] · CPC title