IP Library › Granted Patent US 8,345,864

Granted Patent B1

US 8,345,864 · App. 12/569,284 · Granted Jan 1, 2013

Elliptic curve cryptography scalar multiplication with on demand acceleration table generation

View Patent ↗

Loading inventors, assignments & file history…

Monitor This Case

Get email alerts when status or documents change.

Order Certified Copies

Most orders are placed with the USPTO same day — all within 24 business hours.

Order via The Patent Place →

Pre-filled with this patent's details

Quick Facts

Patent No.: US 8,345,864
App. No.: 12/569,284
Granted: Jan 1, 2013
Kind: B1

External Links

USPTO Patent Center↗ Full Patent PDF↗

Abstract

An improved technique involves dynamic generation of at least a portion of an acceleration table for use in elliptic curve cryptography. Such dynamic generation is capable of providing savings with regard to carrying out elliptic curve cryptography without an acceleration table. Furthermore, once the portion of the acceleration table is dynamically generated and stored (e.g., in a high speed cache), the portion of the acceleration table is capable of being used on subsequent elliptic curve cryptography operations as well thus enabling the cost of dynamically generating the acceleration table to be amortized across multiple elliptic curve cryptography operations.

Claims (201)

1. A method for generating a cryptographically processed value comprising:

receiving, in cryptographic processing circuitry from a user interface, an input value to be cryptographically processed;

applying, in the cryptographic processing circuitry, elliptic curve cryptography (ECC) based cryptographic processing to the input value to generate the cryptographically processed value, wherein applying ECC-based cryptographic processing includes:

generating an enhanced acceleration table (EAT) in response to receiving, in the cryptographic processing circuitry from the user interface, an input value to be cryptographically processed, the EAT including a plurality of ordered sub-tables, each sub-table including exactly one entry,

performing ECC scalar multiplication with the generated EAT, wherein performing ECC scalar multiplication with the EAT includes (i) calculating an ECC scalar multiplication result by generating a plurality of running totals, each running total being associated with a positive integer multiplier and (ii) calculating the sum of each running total multiplied by its associated positive integer multiplier, the sum being the ECC scalar multiplication result,

wherein generating the plurality of running totals includes, for each sub-table of the plurality of ordered sub-tables, (i) adding a value associated with the one entry in that sub-table to a running total associated with a multiplier of the plurality of multipliers, the value being one of the one entry in that sub-table and a negation of the one entry in that sub-table and (ii) carrying a value of 1 to a next sub-table if the value is the negation of the one entry in the current sub-table, and

applying an ECC cryptographic processing algorithm using the calculated ECC scalar multiplication result; and

outputting, from the cryptographic processing circuitry, the generated cryptographically processed value via the user interface;

wherein performing ECC scalar multiplication includes calculating 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 pair of coordinate values being equal to a field size of an elliptic curve group based on the given point and the elliptic curve, the scalar value also having the same bit-length;

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

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

wherein generating the plurality of running totals further includes selecting the positive integer multiplier based on the binary value of the subset associated with that sub-table;

wherein generating the plurality of running totals includes generating an amount of running totals equal to two (2) raised to the power of (^) the window size minus one (w−1), each running total (RT1, . . . , and RTi, wherein i=2^(w−1)), being exclusively associated with one value chosen from the set {1, . . . , i} as its associated positive integer multiplier; and

wherein calculating the sum of each running total multiplied by its associated positive integer multiplier consists of performing a series of nested add, double, and negation operations on the running totals.

2. A method as in claim 1 :

wherein the field size is 256;

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

wherein the window-size is a value chosen from the set {3, 4, 5}.

3. A method as in claim 1 :

wherein the window-size is 3 bits;

wherein generating the amount of running totals equal to two (2) raised to the power of (^) the window size minus one (w−1) includes generating exactly four (4) running totals (RT1, RT2, RT3, and RT4), the exactly four (4) running totals each being exclusively associated with one value chosen from the set {1, 2, 3, 4} as its associated positive integer multiplier;

wherein performing the series of nested add, double, and negation operations on the running totals includes:

doubling RT4 to form a first intermediate value,

calculating a sum of RT2, RT3, and the first intermediate value to form a second intermediate value,

doubling the second intermediate value to form a third intermediate value, and

calculating a sum of RT1, RT3, and the third intermediate value to form the ECC scalar multiplication result.

4. A method as in claim 1 :

wherein the window-size is 4 bits;

wherein generating the amount of running totals equal to two (2) raised to the power of (^) the window size minus one (w−1) includes generating exactly eight (8) running totals (RT1, RT2, RT3, RT4, RT5, RT6, RT7, and RT8), the exactly eight (8) running totals each being exclusively associated with a value chosen from the set {1, 2, 3, 4, 5, 6, 7, 8} as its associated positive integer multiplier;

wherein performing the series of nested add, double, and negation operations on the running totals includes:

calculating a sum of RT8 and RT7 to form a first intermediate value,

doubling the first intermediate value to form a second intermediate value,

calculating a sum of RT4, RT5, RT6, and the second intermediate value to form a third intermediate value,

doubling the third intermediate value to form a fourth intermediate value,

calculating a sum of RT2, RT3, RT6, and the fourth intermediate value to form a fifth intermediate value,

doubling fifth intermediate value to form a sixth intermediate value,

negating RT7 to form a seventh intermediate value, and

calculating a sum of RT1, RT3, RT5, the sixth intermediate value, and the seventh intermediate value to form the ECC scalar multiplication result.

5. A method as in claim 1 :

wherein the window-size is 5 bits;

wherein generating the amount of running totals equal to two (2) raised to the power of (^) the window size minus one (w−1) includes generating exactly sixteen (16) running totals (RT1, RT2, RT3, RT4, RT5, RT6, RT7, RT8, RT9, RT10, RT12, RT13, RT14, RT15, and RT16), the exactly sixteen (16) running totals each being exclusively associated with a value chosen from the set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16} as its associated positive integer multiplier;

wherein performing the series of nested add, double, and negation operations on the running totals includes:

calculating a sum of RT9, RT11 and RT13 to form a first intermediate value,

calculating a sum of RT14, RT15, and RT16 to form a second intermediate value,

doubling the second intermediate value to form a third intermediate value,

calculating a sum of RT7, RT8, the first intermediate value, RT10, RT12, and the third intermediate value to form a fourth intermediate value,

doubling the fourth intermediate value to form a fifth intermediate value,

calculating a sum of RT4, RT5, RT6, RT12, RT13, and the fifth intermediate value to form a sixth intermediate value,

doubling the sixth intermediate value to form a seventh intermediate value,

negating RT14 to form a eighth intermediate value,

calculating a sum of RT2, RT3, RT6, RT10, RT11, the seventh intermediate value, and the eighth intermediate value to form a ninth intermediate value,

doubling the ninth intermediate value to form a tenth intermediate value,

negating RT7 to form a eleventh intermediate value,

negating RT15 to form a twelfth intermediate value, and

calculating a sum of RT1, RT3, RT5, the first intermediate value, the tenth intermediate value, the eleventh intermediate value, and the twelfth intermediate value to form the ECC scalar multiplication result.

6. A method for generating a cryptographically processed value comprising:

receiving, in cryptographic processing circuitry from a user interface, an input value to be cryptographically processed;

applying an ECC cryptographic processing algorithm using the calculated ECC scalar multiplication result; and

outputting, from the cryptographic processing circuitry, the generated cryptographically processed value via the user interface;

wherein the input value to be cryptographically processed is a first input value to be cryptographically processed;

wherein the ECC scalar multiplication result is a first ECC scalar multiplication;

wherein the cryptographically processed value is a first cryptographically processed value; and

wherein the method further comprises:

storing the EAT in a cache,

receiving, in the cryptographic processing circuitry from the user interface, a second input value to be cryptographically processed,

applying, in the cryptographic processing circuitry, ECC based cryptographic processing to the second input value to generate a second cryptographically processed value by: (i) performing ECC scalar multiplication with the stored EAT to calculate a second ECC scalar multiplication result, and (ii) applying the ECC cryptographic processing algorithm using the calculated second ECC scalar multiplication result, and

outputting, from the cryptographic processing circuitry, the generated second cryptographically processed value via the user interface.

7. A computer program product comprising a non-transitory computer-readable medium including computer program logic encoded thereon, which, when performed on a computer directs the computer to perform the following operations:

receiving, from a user interface, an input value to be cryptographically processed;

applying elliptic curve cryptography (ECC) based cryptographic processing to the input value to generate an cryptographically processed value, wherein applying ECC-based cryptographic processing includes:

generating an enhanced acceleration table (EAT) in response to receiving, from the user interface, an input value to be cryptographically processed, the EAT including a plurality of ordered sub-tables, each sub-table including exactly one entry, and

applying an ECC cryptographic processing algorithm using the calculated ECC scalar multiplication result; and

outputting the generated cryptographically processed value via the user interface;

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

wherein generating the plurality of running totals further includes selecting the positive integer multiplier based on the binary value of the subset associated with that sub-table;

8. A computer program product as in claim 7 :

wherein the field size is 256;

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

wherein the window-size is a value chosen from the set {3, 4, 5} as its associated positive integer multiplier.

9. A computer program product as in claim 7 :

wherein the window-size is 3 bits;

wherein performing the series of nested add, double, and negation operations on the running totals includes:

doubling RT4 to form a first intermediate value,

calculating a sum of RT2, RT3, and the first intermediate value to form a second intermediate value,

doubling the second intermediate value to form a third intermediate value, and

calculating a sum of RT1, RT3, and the third intermediate value to form the ECC scalar multiplication result.

10. A computer program product as in claim 7 :

wherein the window-size is 4 bits;

wherein performing the series of nested add, double, and negation operations on the running totals includes:

calculating a sum of RT8 and RT7 to form a first intermediate value,

doubling the first intermediate value to form a second intermediate value,

calculating a sum of RT4, RT5, RT6, and the second intermediate value to form a third intermediate value,

doubling the third intermediate value to form a fourth intermediate value,

calculating a sum of RT2, RT3, RT6, and the fourth intermediate value to form a fifth intermediate value,

doubling fifth intermediate value to form a sixth intermediate value,

negating RT7 to form a seventh intermediate value, and

calculating a sum of RT1, RT3, RT5, the sixth intermediate value, and the seventh intermediate value to form the ECC scalar multiplication result.

11. A computer program product as in claim 7 :