Method for elliptic curve point multiplication
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.
1. A cryptographic 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 cryptographic processing device, comprising the following steps:
representing the multiplier e in the form
e
=
∑
0
≤
i
≤
l
b
i
2
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 for at least one but not all bεB, such that none of the selected point representations is the point at infinity;
assigning point representations to variables A b for all values of b for which randomly selected point representations were not assigned so that the sum
∑
b
∈
B
b
A
b
is the point at infinity;
modifying 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 ; and
calculating the sum
∑
b
∈
B
b
A
b
by using the modified values of the variables A b .
2. A cryptographic 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 cryptographic processing device, comprising the following steps:
representing the multiplier e in the form
∑
0
≤
i
≤
l
b
i
2
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 for each bεB, such that none of the selected point representations is the point at infinity;
computing the sum
∑
b
∈
B
b
A
b
and storing it in a variable Q;
modifying 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 ; and
calculating the sum
∑
b
∈
B
b
A
b
by using the modified values of A b , and subtracting from it the point stored in variable Q.
3. A cryptographic 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 cryptographic processing device, comprising the following steps:
representing the multiplier e in the form
∑
0
≤
i
≤
l
b
i
2
wi
using digits bεB where w and l are integers and B is a set of integers;
assigning randomly selected point representations to variables A b for at least one but not all bεB′, such that none of the selected point representations is the point at infinity;
assigning point representations to variables A b for all values of b for which randomly selected point representations were not assigned so that the sum
∑
b
∈
B
′
b
A
b
is the point at infinity, where B′ denotes the set of absolute values of the integers in set B.
modifying 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′; and
calculating the sum
∑
b
∈
B
′
b
A
b
by using the modified values of the variables A b .
4. A cryptographic 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 cryptographic processing device, comprising the following steps:
representing the multiplier e in the form
∑
0
≤
i
≤
l
b
i
2
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 for each bεB′, such that none of the selected point representations is the point at infinity, where B′ the set of absolute values or the integers in set B;
computing the sum
∑
b
∈
B
b
A
b
and storing it in a variable Q;
modifying 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′; and
calculating the sum
∑
b
∈
B
′
b
A
b
by using the modified values of A b , and subtracting from it the point stored in variable Q.
5. The method according to claim 1 , wherein in the modifying step the values 2 wi P are computed in succession for i=0, . . . ,l and for each i the respective value is added to variable A bi .
6. The method according to claim 3 , wherein in the modifying step the values 2 wi P are computed in succession for i=0, . . . ,l and for each i the respective value is added to variable A bi if b i ≧0 and subtracted from variable A −bi if b i <0.
7. The method according to claim 1 , wherein 1εB, and wherein in the assigning randomly selected point representations step random points are assigned to the variable A b with bεB−{1} and the negative of the value of the sum
∑
b
∈
B
-
{
1
}
b
A
b
is assigned to A 1 .
8. The method according to claim 7 , wherein the points in A b are described in projective coordinates and wherein at the end of the assigning randomly selected point representations step a projective randomization takes place of the variables A b with bεB−{1}.
9. A device comprising means, configured to provide the method according to the previous independent method claim 1 .
10. A device comprising means, configured to provide the method according to the previous independent method claim 2 .
11. A device comprising means, configured to provide the method according to the previous independent method claim 3 .
12. A device comprising means, configured to provide the method according to the previous independent method claim 4 .
13. A computer readable medium comprising computer executable instructions that when executed provide the method according to the previous independent method claim 1 while being executed on a computer.
14. A computer readable medium comprising computer executable instructions that when executed provide the method according to the previous independent method claim 2 while being executed on a computer.
15. A computer readable medium comprising computer executable instructions that when executed provide the method according to the previous independent method claim 3 while being executed on a computer.
16. A computer readable medium comprising computer executable instructions that when executed provide the method according to the previous independent method claim 4 while being executed on a computer.