Using multiples above two with running totals in elliptic curve cryptography scalar multiplication acceleration tables

1. A method of providing security using elliptic curve cryptography (ECC), the method comprising:

(A) receiving, from interface circuitry, an input signal which represents an input value;

(B) performing, in a microprocessor coupled to the interface circuitry, a set of cryptographic operations to provide a cryptographically processed value (CPV) based on the input value, the set of cryptographic operations including:

(i) calculating an intermediate ECC scalar multiplication result based on the input value using an enhanced acceleration table (EAT), the EAT including a plurality of sub-tables, the plurality of sub-tables being arranged in an order, each sub-table including a plurality of entries, wherein calculating the intermediate ECC scalar multiplication result includes:

(a) generating a plurality of running totals including at least four running totals RT1, RT2, RT3, and RT4, each running total being associated with a respective positive integer multiplier, RT1 being associated with 1 as its associated positive integer multiplier, RT2 being associated with 2 as its associated positive integer multiplier, RT3 being associated with 3 as its associated positive integer multiplier, and RT4 being associated with 4 as its associated positive integer multiplier, wherein generating the plurality of running totals includes, for at least one sub-table of the plurality of sub-tables, (1) choosing an entry of the at least one sub-table based on the input value, and (2) adding a value associated with the chosen entry to one running total, the associated positive integer multiplier of that running total being greater than 2; and

(b) calculating a sum of each running total multiplied by its respective associated positive integer multiplier, including:

doubling RT4, thereby generating a first intermediate value;

calculating a sum of RT2, RT3, and the first intermediate value, thereby generating a second intermediate value;

doubling the second intermediate value, thereby generating a third intermediate value; and

calculating a sum of RT1, RT3, and the third intermediate value, thereby generating the intermediate ECC scalar multiplication result; and

(ii) applying an ECC based cryptographic processing algorithm to the input value to generate the CPV, the algorithm including a computation involving the intermediate ECC scalar multiplication result; and

(C) outputting, from the interface circuitry, an output signal which represents the CPV, the input value and the CPV being related in a secure manner through use of the ECC based cryptographic processing algorithm.

2. The method of claim 1 wherein:

the intermediate ECC scalar multiplication result is a product of a scalar value and a given point on an elliptic curve, the given point being represented by an ordered pair of coordinate values, a bit-length of each coordinate value of the ordered pair being equal to a field size of an elliptic curve group based on the given point and the elliptic curve, wherein the scalar value also has the same bit-length;

the number of sub-tables in the EAT is defined by the bit-length divided by a window-size;

a binary representation of the scalar value is divided into an ordered set of subsets, each subset being a binary value having a length equal to the window-size, each subset corresponding to a particular sub-table in order; and

choosing, for the at least one sub-table, the entry of that sub-table based on the input value includes, selecting an entry in that sub-table associated with the binary value of the subset corresponding to that sub-table.

3. The method of claim 2 wherein:

the field size is 256;

the elliptic curve group is the NIST standard P256 elliptic curve group; and

the window-size is a value chosen from the set {3, 4, 5, 6, 7, 8, 9, 10, 11, 12}.

4. The method of claim 2 wherein:

the input value includes a private key;

the scalar value is equal to the private key;

applying the ECC based cryptographic processing algorithm includes setting the CPV to be equal to the intermediate ECC scalar multiplication result.

5. The method of claim 2 wherein:

for the at least one sub-table, the value associated with the chosen entry is a negation of a value stored in that entry; and

generating the plurality of running totals further includes, for the at least one sub-table, adding a positive integer to a next subset of the ordered set of subsets, the next subset immediately following the subset associated with that sub-table.

6. The method of claim 1 wherein, for the at least one sub-table, the value associated with the chosen entry is a value stored in that entry.

7. The method of claim 1 wherein:

the intermediate ECC scalar multiplication result is a product of a scalar value and a given point on an elliptic curve, the given point being represented by an ordered pair of coordinate values, a bit-length of each coordinate value of the ordered pair being equal to a field size of an elliptic curve group based on the given point and the elliptic curve, wherein the scalar value also has the same bit-length;

the number of sub-tables in the EAT is defined by the bit-length divided by a window-size;

the window-size is 6 bits; and

each sub-table includes exactly 11 entries.

8. The method of claim 1 wherein:

the intermediate ECC scalar multiplication result is a product of a scalar value and a given point on an elliptic curve, the given point being represented by an ordered pair of coordinate values, a bit-length of each coordinate value of the ordered pair being equal to a field size of an elliptic curve group based on the given point and the elliptic curve, wherein the scalar value also has the same bit-length;

the number of sub-tables in the EAT is defined by the bit-length divided by a window-size;

the window-size is 6 bits; and

each sub-table includes exactly 10 entries.

9. An integrated circuit chip comprising:

an interface portion for communicating with an external user interface;

a high speed on-chip cache, the cache being constructed and arranged to store:

the entire contents of an enhanced acceleration table (EAT), the EAT including a plurality of sub-tables, the plurality of sub-tables being arranged in an order, each sub-table including a plurality of entries, each entry including a pair of coordinate values representing a point along an elliptic curve; and

instructions to be performed; and

a controller, the controller being constructed and arranged to perform instructions stored in the cache, wherein performing instructions stored in the cache includes:

(A) receiving, from the interface portion, an input value to be cryptographically processed;

(B) performing a set of cryptographic operations to provide a cryptographically processed value (CPV) based on the input value, the set of cryptographic operations including:

(i) calculating an intermediate ECC scalar multiplication result based on the input value using the EAT, wherein calculating the intermediate ECC scalar multiplication result includes:

(a) generating a plurality of running totals including at least four running totals RT1, RT2, RT3, and RT4, each running total being associated with a respective positive integer multiplier, RT1 being associated with 1 as its associated positive integer multiplier, RT2 being associated with 2 as its associated positive integer multiplier, RT3 being associated with 3 as its associated positive integer multiplier, and RT4 being associated with 4 as its associated positive integer multiplier, wherein generating the plurality of running totals includes, for at least one sub-table of the plurality of sub-tables, (1) choosing an entry of that the at least one sub-table based on the input value, and (2) adding a value associated with the chosen entry to one running total, the associated positive integer multiplier of that running total being greater than 2; and

(b) calculating a sum of each running total multiplied by its respective associated positive integer multiplier, including:

doubling RT4, thereby generating a first intermediate value;

calculating a sum of RT2, RT3, and the first intermediate value, thereby generating a second intermediate value;

doubling the second intermediate value, thereby generating a third intermediate value; and

calculating a sum of RT1, RT3, and the third intermediate value, thereby generating the intermediate ECC scalar multiplication result; and

(ii) applying an ECC based cryptographic processing algorithm to the input value to generate the CPV, the algorithm including a computation involving the intermediate ECC scalar multiplication result; and

(C) outputting, to the interface portion, an output signal which represents the CPV, the input value and the CPV being related in a secure manner through use of the ECC based cryptographic processing algorithm.

10. The integrated circuit chip of claim 9 wherein:

the intermediate ECC scalar multiplication result is a product of a scalar value and a given point on an elliptic curve, the given point being represented by an ordered pair of coordinate values, a bit-length of each coordinate value of the ordered pair being equal to a field size of an elliptic curve group based on the given point and the elliptic curve, wherein the scalar value also has the same bit-length;

the number of sub-tables in the EAT is defined by the bit-length divided by a window-size;

a binary representation of the scalar value is divided into an ordered set of subsets, each subset being a binary value having a length equal to the window-size, each subset corresponding to a particular sub-table in order;

choosing, for the at least one sub-table, the entry of that sub-table based on the input value includes, selecting an entry in that sub-table associated with the binary value of the subset corresponding to that sub-table;

the field size is 256;

the elliptic curve group is the NIST standard P256 elliptic curve group; and

the window-size is a value chosen from the set {3, 4, 5, 6, 7, 8, 9, 10, 11, 12}.

11. The integrated circuit chip of claim 10 wherein:

the window-size is 6 bits; and

each sub-table includes exactly 11 entries.

12. The integrated circuit chip of claim 10 wherein:

the window-size is 6 bits; and

each sub-table includes exactly 10 entries.

13. A computer program product comprising a non-transitory computer readable medium, the computer readable medium storing instructions thereon which, when performed by a computer, cause the computer to:

(A) receive, from interface circuitry, an input signal which represents an input value;

(B) perform, in a microprocessor coupled to the interface circuitry, a set of cryptographic operations to provide a cryptographically processed value (CPV) based on the input value, the set of cryptographic operations including:

(i) calculating an intermediate ECC scalar multiplication result based on the input value using an enhanced acceleration table (EAT), the EAT including a plurality of sub-tables, the plurality of sub-tables being arranged in an order, each sub-table including a plurality of entries, wherein calculating the intermediate ECC scalar multiplication result includes:

(a) generating a plurality of running totals including at least four running totals RT1, RT2, RT3, and RT4, each running total being associated with a respective positive integer multiplier, RT1 being associated with 1 as its associated positive integer multiplier, RT2 being associated with 2 as its associated positive integer multiplier, RT3 being associated with 3 as its associated positive integer multiplier, and RT4 being associated with 4 as its associated positive integer multiplier, wherein generating the plurality of running totals includes, for at least one sub-table of the plurality of sub-tables, (1) choosing an entry of the at least one sub-table based on the input value, and (2) adding a value associated with the chosen entry to one running total, the associated positive integer multiplier of that running total being greater than 2; and

(b) calculating a sum of each running total multiplied by its respective associated positive integer multiplier, including:

doubling RT4, thereby generating a first intermediate value;

calculating a sum of RT2, RT3, and the first intermediate value, thereby generating a second intermediate value;

doubling the second intermediate value, thereby generating a third intermediate value; and

calculating a sum of RT1, RT3, and the third intermediate value, thereby generating the intermediate ECC scalar multiplication result; and

(ii) applying an ECC based cryptographic processing algorithm to the input value to generate the CPV, the algorithm including a computation involving the intermediate ECC scalar multiplication result; and

(C) output, from the interface circuitry, an output signal which represents the CPV, the input value and the CPV being related in a secure manner through use of the ECC based cryptographic processing algorithm.

14. The computer program product of claim 13 wherein:

the intermediate ECC scalar multiplication result is a product of a scalar value and a given point on an elliptic curve, the given point being represented by an ordered pair of coordinate values, a bit-length of each coordinate value of the ordered pair being equal to a field size of an elliptic curve group based on the given point and the elliptic curve, wherein the scalar value also has the same bit-length;

the number of sub-tables in the EAT is defined by the bit-length divided by a window-size;

a binary representation of the scalar value is divided into an ordered set of subsets, each subset being a binary value having a length equal to the window-size, each subset corresponding to a particular sub-table in order; and

choosing, for the at least one sub-table, the entry of that sub-table based on the input value includes, selecting an entry in that sub-table associated with the binary value of the subset corresponding to that sub-table.

15. The computer program product of claim 14 wherein:

the input value includes a private key;

the scalar value is equal to the private key;

applying the ECC based cryptographic processing algorithm includes setting the CPV to be equal to the intermediate ECC scalar multiplication result.