Method for elliptic curve point multiplication
An elliptic curve multiplication 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 method of performing an elliptic curve point multiplication eP using a cryptographic processing device, wherein e is an integer and P is a point on an elliptic curve, and wherein values of variables A b and b are stored on the cryptographic processing device, the method comprising:
modifying the values of the variables A b stored on the cryptographic processing device in dependency of 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 and A b; and
calculating the sum
∑
b
∈
B
bA
b
by using the modified values of the variables A b , wherein B is a set of integers, and wherein the values of variables A b and b were previously determined during an initialization of the cryptographic processing device by:
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;
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 a point at infinity; and
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
bA
b
is the point at infinity.
2. The method or claim 1 , wherein the cryptographic processing device further comprises a smart card.
3. The method of claim 1 , wherein the modifying comprises computing the values 2 wi P in succession for i=0, . . . ,l and for each i the respective value is added to variable A bi .
4. The method of claim 1 , wherein l εB, and wherein the assigning randomly selected point representations comprises assigning random points to the variable A b with b εB−{1} and the negative of the value of the sum
∑
b
∈
B
-
{
1
}
bA
b
is assigned to A 1 .
5. The method of claim 4 , wherein the points in A b are described in projective coordinates, and wherein the assigning randomly selected point representations comprises randomizing the projective representation of the variables A b with b εB−{1}.
6. A cryptographic processing device for performing an elliptic curve point multiplication eP, wherein e is an integer and P is a point on an elliptic curve, the device comprising:
a reader configured to read values of variables A b and b stored on the cryptographic processing device, and
a processor configured to complete the elliptic curve point multiplication by:
modifying the values of the variables A b stored on the cryptographic processing device in dependency of 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
bA
b
by using the modified values of the variables A b , wherein B is a set or integers, and wherein the values of variables A b and b were previously determined during the initialization of the cryptographic processing device by:
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;
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 a point at infinity; and
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
bA
b
is the point at infinity.
7. A non-transitory computer-readable medium having instructions stored thereon that, if executed by a cryptographic processing device, cause the cryptographic processing device to perform operations comprising:
modifying values of variables A b in dependency of 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 , wherein the variables A b and b are associated with an elliptic curve point multiplication eP, where e is an integer and P is a point on an elliptic curve; and
calculating the sum
∑
b
∈
B
bA
b
by using the modified values of the variables A b, wherein B is a set of integers, wherein the values of variables A b and b were previously determined during an initialization of the cryptographic processing device by:
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;
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 a point at infinity; and
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
bA
b
is the point at infinity.
8. A method of performing an elliptic curve point multiplication eP using a cryptographic processing device, wherein e is an integer and P is a point on an elliptic curve, and wherein values of variables A b , b and Q are stored on the cryptographic processing device, the method comprising:
modifying the values of the variables A b stored on the cryptographic processing device in dependency of 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
bA
b
by using the modified values of A b , and subtracting from it the variable Q stored on the cryptographic processing device, wherein B is a set of integers, and wherein the values of variables A b , b and Q were previously determined during the initialization of the cryptographic processing device by:
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;
assigning randomly selected point representations to variables A b , for each b=B, such that none of the selected point representations is a point at infinity; and
computing the sum
∑
b
∈
B
bA
b
and storing it in the variable Q.
9. The method of claim 8 , wherein the cryptographic processing device further comprises a smart card.
10. The method of claim 8 , wherein modifying the values of the variables A b comprises computing the values 2 wi P 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.
11. A cryptographic processing device for performing an elliptic curve point multiplication eP, wherein e is an integer and P is a point on an elliptic curve, the device comprising:
a reader configured to read values of variables A b , b and Q stored on the cryptographic processing device; and
a processor configured to complete the elliptic curve point multiplication by:
modifying the values of the variables A b stored on the cryptographic processing device in dependency of 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
bA
b
by using the modified values of A b and subtracting from it the variable Q stored on the cryptographic processing device, wherein B is a set of integers, and wherein the values of variables A b b and Q were previously determined during the initialization of the cryptographic processing device by:
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;
assigning randomly selected point representations to variables A b for each b i εB, such that none of the selected point representations is a point at infinity; and
computing the
∑
b
∈
B
bA
b
and storing it in the variable Q.
12. A non-transitory computer-readable medium having instructions stored thereon that, if executed by a cryptographic processing device, cause the cryptographic processing device to perform operations comprising:
modifying válues of variables A b in dependency of 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
bA
b
by using the modified values of A b , and subtracting from it a variable Q stored on the cryptographic processing device, wherein B is a set of integers, wherein the variables A b , b and Q are associated with an elliptic curve point multiplication eP, where e is an integer and P is a point on an elliptic curve, and wherein the values of variables A b , b and Q were previously determined during the initialization of the cryptographic processing device by:
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;
assigning randomly selected point representations to variables A b for each b εB, such that none of the selected point representations is a point at infinity; and
comprising the sum
∑
b
∈
B
bA
b
and storing it in the variable Q.
13. A method of performing an elliptic curve point multiplication eP using a cryptographic processing device, wherein e is an integer and P is a point on an elliptic curve, and wherein values of variables A b and b are stored on the cryptographic processing device, the method comprising:
modifying the values of the variables A b , stored on the cryptographic processing device in dependency of 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′, wherein B is a set of integers and B′ denotes, the set of absolute values of the integers in set B; and
calculating the sum
∑
b
∈
B
′
bA
b
by using the modified values of the variables A b, wherein the values of variables A b and b were previously determined during an initialization of the cryptographic processing device by:
representing the multiplier e in the form
∑
0
≤
i
≤
l
b
i
2
wi
using digits b εB where w and l are 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 a point at infinity; and
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
′
bA
b
is the point at infinity.
14. The method of claim 13 , wherein the cryptographic processing device further comprises a smart card.
15. A cryptographic processing device for performing an elliptic curve point multiplication eP, wherein e is an integer and P is a point on an elliptic curve, the device comprising:
a reader configured to read values of variables A b and b stored on the cryptographic processing device; and
a processor configured to complete the elliptic curve point multiplication by:
modifying the values of the variables A b stored on the cryptographic processing device in dependency of 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′; wherein B is a set of integers and B′ denotes the set of absolute values of the integers in set B, and
calculating the sum
∑
b
∈
B
′
bA
b
by using the modified values of the variables A b , wherein the values of variables A b and b were previously determined during the initialization of the cryptographic processing device by:
representing the multiplier e in the form
∑
0
≤
i
≤
l
b
i
2
wi
using digits b εB where w and l are 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 a point at infinity; and
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
′
bA
b
is the point at infinity,
16. A non-transitory computer-readable medium having instructions stored thereon that, if executed by a cryptographic processing device, cause the cryptographic processing device to perform operations comprising:
modifying values of variables A b in dependency of digits b i such that the sure 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′, wherein B is a set of integers and B′ denotes the set of absolute values of the integers inset B, wherein variables A b and b are associated with an elliptic curve point multiplication eP, where e is an integer and P is a point on an elliptic curve; and
calculating the sum
∑
b
∈
B
′
bA
b
by using the modified values of the variables A b , wherein the values of variables A b and b were previously determined during an initialization of the cryptographic processing device by:
representing the multiplier e in the form
∑
0
≤
i
≤
l
b
i
2
wi
using digits b εB where w and l are 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 a point at infinity; and
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
′
bA
b
is the point at infinity.
17. A method of performing an elliptic curve point multiplication eP using a cryptographic processing device, wherein e is an integer and P is a point on an elliptic curve, and wherein values of variables A b , b and Q are stored on the cryptographic processing device, the method comprising:
modifying the values of the variables A b stored on the cryptographic processing device in dependency of 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′, wherein B is a set of integers and B′ denotes the set of absolute values of the integers in set B; and
calculating the sum
∑
b
∈
B
′
bA
b
by using the modified values of A b , and subtracting from it the variable Q stored on the cryptographic processing device, wherein the values of variables A b , b and Q were previously determined during the initialization of the cryptographic processing device by:
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;
assigning randomly selected point representations to variables A b for each b εB′, such that none of the selected point representations is a point at infinity; and
computing the sum
∑
b
∈
B
bA
b
and storing it in a variable Q.
18. The method of claim 17 , wherein the cryptographic processing device further comprises a smart card.
19. A cryptographic processing device for performing an elliptic curve point multiplication eP, wherein e is an integer and P is a point on an elliptic curve, the device comprising:
a reader configured to read values of variables A b , b and Q stored on the cryptographic processing device; and
a processor configured to complete the elliptic curve point multiplication by:
modifying the values of the variables A b in dependency of 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′, wherein B is a set of integers and B′ denotes the set of absolute values of the integers in set B, and
calculating the sum
∑
b
∈
B
′
bA
b
by using the moainea values of A b and subtracting from it the variable Q stored on the cryptographic processing device, wherein the values of variables A b , b and Q were previously determined during the initialization of the cryptographic processing device by:
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;
assigning randomly selected point representations to variables A b for each b εB′, such that none of the selected point representations is a point at infinity; and
computing the sum
∑
b
∈
B
bA
b
and storing it in a variable Q.
20. A non-transitory computer-readable medium having instructions stored thereon that, if executed by a cryptographic processing device, cause the cryptographic processing device to perform operations comprising:
modifying values of variables A b in dependency of 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 ′, wherein B is a set of integers and B ′ denotes the set of absolute values of the integers in set B; and
calculating the sum
∑
b
∈
B
′
bA
b
by using the modified values of A b , and subtracting from it a variable Q stored on the cryptographic processing device, wherein the variables A b , b, and Q are associated with an elliptic curve point multiplication eP, where e is an integer and P is a point on an elliptic curve, and wherein the values of variables A b , b and Q were previously determined during the initialization of the cryptographic processing device by:
representing the multiplier e in the form
∑
0
≤
i
≤
l
b
i
2
w
i
by using digits b i , εB where w and l are integers;
assigning randomly selected point representations to variables A b for each b εB′, such that none of the selected point representations is a point at infinity; and
computing the sum
∑
b
∈
B
bA
b
and storing it in a variable Q.