Patent ID: 7664258

Claim:
A computerized method comprising: operating a processor, within a computing environment, to execute instructions stored on a memory within the computing environment, to multiply a point P on an elliptic curve by a scalar value k, to thereby obtain a scalar-point product Q for use in crytographic systems, wherein the operating performs the steps comprising: selecting a set of random integers, wherein the set comprises at least one integer selected randomly; configuring a string str based in part on the set of random integers, wherein configuring the string str, generates a random sparse format of the scalar k, indicated by k′, which differs from k due to the randomness introduced wherein generating the random sparse format of the scalar comprises: setting the string variable str to a null string, setting a variable S to be the empty set, and initializing a temporary variable T to the scalar k; within a first loop, repeating until T=0; within a second loop nested in the first loop, repeating while T is in set S; choosing R randomly from a set of integers; setting T equal to T+R; setting S equal to S union {T}; setting str equal to a function of T concatenated to str; and setting T equal to a function of T; and returning str; and calculating the scalar-point product Q of the scalar k and the point P based on the string str, wherein the calculating removes effects of the randomness introduced to the string str from the result of Q=k′P in part by establishing a variable β=k−k′ and calculating a point R as R=βP, wherein R is added to Q to remove effects of the randomness to derive Q=kP.