Patent ID: 8160245

Claim:
A method, for being performed by a computer system, of publishing an Elliptic Curve Scalar Multiplication (ECSM) product of a scalar and a base point on an elliptic curve in a manner that counters power analysis attacks, said base point having a prime order, said method comprising: receiving said base point, said scalar, and a previous set of parameters used to split said scalar for a previous ECSM, said previous set of parameters including a previous quotient and a previous remainder determined using said scalar as a dividend and a first random integer as a divisor; selecting, at a processor, a second random integer; determining, at said processor, a new set of parameters for splitting said scalar, said determining based on said previous set of parameters and said random random integer, said new set of parameters including a successive quotient and a successive remainder, said determining said new set of parameters including: determining said successive quotient by: determining a temporary quotient as a sum of said previous quotient and said second random integer; determining a temporary product of said temporary quotient and said first random integer; determining an integer part of a new quotient for which said temporary product is a dividend and said second random integer is a divisor; and determining said successive quotient as a difference between said integer part of said new quotient and said first random integer; and determining said successive remainder based on said previous quotient, said previous remainder and said second random integer; obtaining, at said processor, said ECSM product using said new set of parameters to split said scalar; and publishing said ECSM product.