Patent ID: 7991154

Claim:
A method of accelerating scalar multiplication in an elliptic curve-based cryptosystem by representing a scalar value with a multibase representation, the method executed in a processor comprising the steps of: a) selecting a set of bases and corresponding set of window values for performing an ECC scalar multiplication; b) calculating precomputed values according to selected bases and window values wherein the precomputed values are points of a form d i P, where d i εD + \{0} and P is a point on a elliptic curve for which a ECC scalar multiplication kP is computed; c) determining a multibase representation of the scalar value; and d) scanning digits of the multibase representation from left to right until all the digits of the multibase representation are exhausted, performing a point operation of a form a j Q for every scanned digit with associated base a j εA, and performing an additional point addition of a form Q=Q±d i P if a digit has nonzero value d i , where d i P is a point of the precomputed values and Q is a partial result of the scalar multiplication.