Method for elliptic curve point multiplication

• US 20040114756A1
• Filed: 12/04/2002
• Published: 06/17/2004
• Est. Priority Date: 12/04/2002
• Status: Active Grant

• Current Assignee: Benhov GmbH, LLC (Intellectual Ventures LLC)
• Original Assignee: Wired Connections LLC (Intellectual Ventures LLC)
• Inventors: Takagi, Tsuyoshi, Moller, Bodo
• Granted Patent: US 7,555,122 B2
• Time in Patent Office: Days
• US Class Current: 380/30
• CPC Class Codes: G06F 2207/7223 Randomisation as countermeasure against side channel attacks
• CPC Class Codes: G06F 2207/7228 Random curve mapping, e.g. mapping to an isomorphous or projective curve
• CPC Class Codes: G06F 7/725 over elliptic curves

Abstract

The method comprises three stages. In the first stage, randomly selected point representations are stored in variables. In the second stage, a right-to-left loop is executed that modifies the variable values in dependency of a multiplier. In the last stage, the result is calculated from the modified variable values.

Claims

2. A mehtod for performing an elliptic curve point multiplication eP where is is an integer and P is a point on an elliptic curve for use in cryptography, comprising the following steps:

representing the multiplier e in the form

$e=\underset{0\le <br><br>i\le <br><br>l}{\sum <br><br>}<br><br>b_i<br><br>2^{\mathrm{wi}}$

by using digits b_i ∈

B where w and l are integers and B is a set of integers,

assigning randomly selected point representations to variables A_b with b ∈

B where the points are chosen such that no A_b is the point at infinity,

computing the sum

$\underset{b\in <br><br>B}{\sum <br><br>}<br><br>{\mathrm{bA}}_b$

and storing it in a variable Q;

performing operations that modify the values of the variables A_b in dependency of the digits b_i such that the sum of the points 2^wi P over those indexes i for which b_i=b holds is added to each variable A_b;

calculating the sum

$\underset{b\in <br><br>B}{\sum <br><br>}<br><br>{\mathrm{bA}}_b$

by using the modified values of A_b, and subtracting from it the point stored in variable Q.

10. A device in particular a smart card, comprising means, in particular a processor and a RAM, providing the method according to the previous independent method claim 2.

14. A computer readable medium comprising a loadable data structure, that provides the method according to the previous independent method claim 2 while being executed on a computer.

3. A method for performing an elliptic curve point multiplication eP where e is an integer and P is a point on an elliptic curve for use in cryptography, comprising the following steps:

representing the multiplier e in the form

$e=\underset{0\le <br><br>i\le <br><br>l}{\sum <br><br>}<br><br>b_i<br><br>2^{\mathrm{wi}}$

using digits b_i ⊂

B where w and l are integers and B is a set of integers,

assigning randomly selected point representations to variables A_b is the point at infinity, but the sum

$\underset{b\in <br><br>B^{\mathrm{\prime <br><br>}}}{\sum <br><br>}<br><br>{\mathrm{bA}}_b$

is the point at infinity, where Bⁱ denoted the set of absolute values of the integers in set B.

perfoming operations that modify the values of the variables A_b in dependency of the digits b_i such that the sum of the points 2^wi P over those indexes i for which b_i=b holds minus the sum of the points 2^wi P over those negative indexes i for which b_i -b holds is added to each variable A_b with b ∈

Bⁱ;

calculating the sum

$\underset{b\in <br><br>B^{\mathrm{\prime <br><br>}}}{\sum <br><br>}<br><br>{\mathrm{bA}}_b$

by using the modified values of the variable A_b.

6. The method according to claim 3, wherein in the third step the values 2^wi P are computed in succession for i=O, . . . ,l and for each i the respective value is added to variable A_bi if b₁>

O and subtracted from variable A_bi if b_i<

O.

11. A device in particular a smart card, comprising means, in particular a processor and a RAM, providing the method according to the previous independent method claim 3.

15. A computer readable medium comprising a loadable data structure, that provides the method according to the previous independent method claim 3 while being executed on a computer.

4-1. The method according to claim 1, wherein in the third step the values 2^wi P are computed in succession for i−

O, . . . ,l and for each i the respective value is added to variable A_bi.