Methods and apparatus for performing an elliptic curve scalar multiplication operation using splitting

1. A method, for being performed by a computer system, of obtaining 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 a second random integer;

determining a new set of parameters for splitting said scalar, said determining based on said previous set of parameters and said second 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 based on said previous quotient, said previous remainder and said second random integer; and

determining said successive remainder based on said previous quotient, said previous remainder and said second random integer, said determining said successive remainder including:

determining a temporary sum of said previous quotient and said second random integer;

determining a temporary product of said temporary sum and said first random integer;

determining a representation of said temporary product modulo said second random integer; and

determining said successive remainder as a sum of said previous remainder and said representation; and

obtaining said ECSM product using said new set of parameters to split said scalar.

2. The method of claim 1 wherein said scalar is a private cryptographic key.

3. The method of claim 1 further comprising publishing said ECSM product.

4. The method of claim 1 wherein said determining said successive quotient includes:

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.

5. A mobile communication device for obtaining an Elliptic Curve Scalar Multiplication (ECSM) product of a scalar k and a base point P on an elliptic curve in a manner that counters power analysis attacks, said device comprising:

a memory storing said scalar k, said base point P 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; and

a processor configured to:

select a second random integer;

determine a new set of key-splitting parameters for splitting said scalar, said determining based on said previous set of parameters and said second random integer, said new set of parameters including a successive quotient and a successive remainder, by:

determining said successive quotient based on said previous quotient, said previous remainder and said second random integer; and

determining said successive remainder by:

determining a temporary sum of said previous quotient and said second random integer;

determining a temporary product of said temporary sum and said first random integer;

determining a representation of said temporary product modulo said second random integer; and

determining said successive remainder as a sum of said previous remainder and said representation; and

obtain said ECSM product using said new set of parameters to split said scalar.

6. The mobile communication device of claim 5 wherein said scalar is a private cryptographic key.

7. The mobile communication device of claim 5 wherein said processor is further configured to publish said ECSM product.

8. The mobile communication device of claim 5 wherein said processor is further configured to determine 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.

9. A computer-readable medium containing computer-executable instructions that, when executed on a processor, cause said processor to obtain 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 instructions, in particular, causing said processor to:

receive 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;

select a second random integer;

determine a new set of key-splitting parameters for splitting said scalar, said determining based on said previous set of parameters and said second 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 based on said previous quotient, said previous remainder and said second random integer; and

determining said successive remainder based on said previous quotient, said previous remainder and said second random integer, said determining said successive remainder including:

determining a temporary sum of said previous quotient and said second random integer;

determining a temporary product of said temporary sum and said first random integer;

determining a representation of said temporary product modulo said second random integer; and

determining said successive remainder as a sum of said previous remainder and said representation; and

obtain said ECSM product using said new set of parameters to split said scalar.

10. The computer-readable medium of claim 9 wherein said scalar is a private cryptographic key.

11. The computer-readable medium of claim 9 wherein said instructions further cause said processor to publish said ECSM product.

12. The computer-readable medium of claim 9 wherein said instructions further cause said processor to determine 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