Patent ID: 8027467

Claim:
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.