System and method for securing scalar multiplication against differential power attacks

摘要

The system and method for securing scalar multiplication against differential power attacks (DPAs) delays required point additions in elliptic curve cryptosystem scalar multiplication. A buffer is used to store the points that will be added later in a random manner. Then, a randomly selected one of the stored points in the buffer is added to the accumulation point, or several randomly selected points are added consecutively. This makes the power trace appear as a repeated sequence of consecutive point doubling followed by consecutive point additions, which makes it very difficult for an attacker to know the exact value of the inspected bit during the scalar multiplication process.

主权项

1. A method for securing elliptic curve scalar multiplication of a private key k with a point P against differential power attacks using a cryptographic device, comprising the steps of:
establishing buffer memory; precomputing a plurality of points Q[i] on an elliptic curve, wherein i is an integer; partitioning the private key k into m bits, wherein m is an integer, such that k=(km-1, . . . , k0); for each of the partitions, for i=0 to m−1, and if ki=1, performing scalar multiplication as:
defining a random number r, wherein r is less than or equal to a number of points stored in the buffer memory;saving Q[1] in the buffer memory;if r is greater than zero, then:
(a) updating Q[0] by adding a randomly selected point from the buffer memory to Q[0];(b) updating the buffer memory by removing the point added to Q[0] in (a) from the buffer memory;(c) updating r as r=r−1; and(d) repeating (a) through (c) while r is greater than zero;if the buffer memory is full, then:
updating Q[0] by adding a randomly selected point from the buffer memory to Q[0];updating the buffer memory by removing the point added to Q[0] in the immediately preceding step from the buffer memory;if i=m−1, then:
(e) if the buffer memory is not empty, updating Q[0] by adding a point randomly selected from the buffer memory to Q[0];(f) updating the buffer memory by removing the point added to Q[0] in (e) from the buffer memory;(g) repeating (e) and (f) until the buffer memory is empty; updating Q[1] by point doubling of Q[1]; setting a scalar product kP equal to Q[0]; and displaying the scalar product kP.