Size optimization for large elliptic curve cryptography scalar multiplication acceleration tables

1. A computer program product comprising a non-transitory computer-readable storage medium, the computer readable storage medium storing a set of instructions, which, when performed by a computer, cause the computer to perform the following steps:

(a) receiving, from a user interface, a set of integer multipliers and an integer degree greater than 1, d;

(b) choosing a subset of a given set of target integers, the chosen subset defining an index set, such that elements of the index set generate all elements of the given set of target integers using a target generation function;

(c) modifying the index set by removing an element from the index set which is not necessary to generate an element of the given set of target integers using the target generation function;

(d) after modifying the index set, outputting, to the user interface, the index set;

(e) before outputting the index set, for some integer n, modifying the index set by replacing n elements with n−1 elements such that, after the modification, elements of the index set still generate all elements of the given set of target integers using the target generation function; and

(f) before outputting the index set, repeating steps c and e in succession until no further elements can be removed or replaced from the index set; and

wherein step f includes the following ordered sub-steps:

(1) performing step c repeatedly until no further elements can be removed from the index set;

(2) attempting to perform step e for n=2 until n=d or until step e is performed successfully, whichever occurs first; and

(3) looping back to sub-step 1 if step e was successfully performed in sub-step 2, but terminating step f if step e was not successfully performed in sub-step 2.

2. A computer program product as in claim 1 wherein:

the set of instructions, when performed by the computer, cause the computer to further perform the step of receiving, from the user interface, an integer window size, w; and

the given set of target integers consists of all integers between 1 and 2 w −1, inclusive.

3. A computer program product as in claim 2 wherein the set of instructions, when performed by the computer, cause the computer to, when performing step (b), perform the following sub-steps:

(1) creating an index mask array, A, A being an array of 2 w -bit bit masks with integer indices ranging from 1 to 2 w−1 such that for each index, i, the corresponding bit mask is set to represent a set of integers which can be generated from that index using the target generation function;

(2) sequentially, for each index j of A:

logically bitwise OR-ing a best mask, B, B being a 2 w -bit bit mask, with A[j] to form a temporary mask T; and

if a number of set bits in T exceeds a number of set bits in B, then setting B=T and storing j as a best index, b;

(3) after completing sub-step 2, adding b to the index set; and

(4) repeating sub-steps 2 and 3 sequentially until every element of B having an index from 1 to 2 w−1 , inclusive, is set to 1.

4. A computer program product as in claim 2 wherein the set of instructions, when performed by the computer, cause the computer to, when performing step (b), select a set containing the integer 1 and the odd prime integers less than 2 w−1 .

5. A computer program product as in claim 2 wherein the target generation function is configured to generate an element of the given set of target integers if that element can be calculated from an input element by:

(i) multiplying the input element by one multiplier of the set of integer multipliers;

(ii) multiplying the product of step i by a value chosen from the set {−1, 1}; and

(iii) if the chosen value is −1, then adding the product of step ii to 2 w .

6. A computer program product as in claim 2 wherein the target generation function is configured to generate an element of the given set of target integers if that element can be calculated from an input element by:

(i) multiplying the input element by one multiplier of the set of integer multipliers;

(ii) multiplying the product of step i by a value chosen from the set {−1, 1};

(iii) if the chosen value from step ii is −1, then adding the product of step ii to 2 w multiplied by a value chosen from the set {1, 2}; and

(iv) if the chosen value from step ii is 1, then adding the product of step ii to 2 w multiplied by a value chosen from the set {−1, 0}.

7. A computer program product as in claim 1 wherein the set of instructions, when performed by the computer, cause the computer to further perform the steps of:

(g) after modifying the index set, generating an ECC scalar multiplication table having a plurality of sub-tables, each sub-table having one entry for each element of the index set; and

(h) storing the ECC scalar multiplication table on a non-transitory computer-readable storage medium to be used in accelerating ECC scalar multiplication for cryptographic processing.

8. A method for creating an acceleration table for an Elliptic Curve Cryptography (ECC) scalar multiplication table, the method comprising:

(a) receiving, from user interface circuitry, a set of integer multipliers and an integer degree greater than 1, d;

(b) in a microprocessor, choosing a subset of a given set of target integers, the chosen subset defining an index set, such that elements of the index set generate all elements of the given set of target integers using a target generation function;

(c) in the microprocessor, modifying the index set by removing an element from the index set which is not necessary to generate an element of the given set of target integers using the target generation function;

(d) in the microprocessor, after modifying the index set, generating an ECC scalar multiplication table having a plurality of sub-tables, each sub-table having one entry for each element of the index set; and

(e) storing the ECC scalar multiplication table on a non-transitory computer-readable storage medium;

(f) before generating the ECC scalar multiplication table, for some integer n, modifying the index set by replacing n elements with n−1 elements such that, after the modification, elements of the index set still generate all elements of the given set of target integers using the target generation function; and

(g) before generating the ECC scalar multiplication table, repeating steps c and f in succession until no further elements can be removed or replaced from the index set;

wherein step g includes the following ordered sub-steps:

(1) performing step c repeatedly until no further elements can be removed from the index set;

(2) attempting to perform step f for n=2 until n=d or until step f is performed successfully, whichever occurs first; and

(3) looping back to sub-step 1 if step f was successfully performed in sub-step 2, but terminating step g if step f was not successfully performed in sub-step 2.

9. A method as in claim 8 wherein:

receiving includes further receiving, from the user interface, an integer window size, w; and

the given set of target integers consists of all integers between 1 and 2 w −1, inclusive.

10. A method as in claim 9 wherein choosing the subset of the given set of target integers includes performing the following sub-steps:

(1) creating, in memory, an index mask array, A, A being an array of 2 w -bit bit masks with integer indices ranging from 1 to 2 w−1 such that for each index, i, the corresponding bit mask is set to represent a set of integers which can be generated from that index using the target generation function;

(2) sequentially, for each index j of A:

logically bitwise OR-ing a best mask, B, B being a 2 w -bit bit mask, with A[j] to form a temporary mask T; and

if a number of set bits in T exceeds a number of set bits in B, then setting B=T and storing j as a best index, b;

(3) after completing sub-step 2, adding b to the index set; and

(4) repeating sub-steps 2 and 3 sequentially until every element of B having an index from 1 to 2 w−1 , inclusive, is set to 1.

11. A method as in claim 9 wherein choosing the subset of the given set of target integers includes selecting a set containing the integer 1 and the odd prime integers less than 2 w−1 .

12. A method as in claim 9 wherein the target generation function is configured to generate an element of the given set of target integers if that element can be calculated from an input element by:

(i) multiplying the input element by one multiplier of the set of integer multipliers;

(ii) multiplying the product of step i by a value chosen from the set {−1, 1}; and

(iii) if the chosen value is −1, then adding the product of step ii to 2 w .

13. A method as in claim 9 wherein the target generation function is configured to generate an element of the given set of target integers if that element can be calculated from an input element by:

(i) multiplying the input element by one multiplier of the set of integer multipliers;

(ii) multiplying the product of step i by a value chosen from the set {−1, 1};

(iii) if the chosen value from step ii is −1, then adding the product of step ii to 2 w multiplied by a value chosen from the set {1, 2}; and

(iv) if the chosen value from step ii is 1, then adding the product of step ii to 2 w multiplied by a value chosen from the set {−1, 0}.

14. A computer program product comprising a non-transitory computer-readable storage medium, the computer readable storage medium storing a set of instructions, which, when performed by a computer, cause the computer to perform the following steps:

(a) receiving, from a user interface, a set of integer multipliers;

(b) choosing a subset of a given set of target integers, the chosen subset defining an index set, such that elements of the index set generate all elements of the given set of target integers using a target generation function;

(c) modifying the index set by removing an element from the index set which is not necessary to generate an element of the given set of target integers using the target generation function; and

(d) after modifying the index set, outputting, to the user interface, the index set;

wherein:

the set of instructions, when performed by the computer, cause the computer to further perform the step of receiving, from the user interface, an integer window size, w;

the given set of target integers consists of all integers between 1 and 2 w −1, inclusive; and

the set of instructions, when performed by the computer, cause the computer to, when performing step (b), perform the following sub-steps:

(1) creating an index mask array, A, A being an array of 2 w -bit bit masks with integer indices ranging from 1 to 2 w−1 such that for each index, i, the corresponding bit mask is set to represent a set of integers which can be generated from that index using the target generation function;

(2) sequentially, for each index j of A:

logically bitwise OR-ing a best mask, B, B being a 2 w -bit bit mask, with A[j] to form a temporary mask T; and

if a number of set bits in T exceeds a number of set bits in B, then setting B=T and storing j as a best index, b;

(3) after completing sub-step 2, adding b to the index set; and

(4) repeating sub-steps 2 and 3 sequentially until every element of B having an index from 1 to 2 w−1 , inclusive, is set to 1.

15. A computer program product as in claim 14 wherein the target generation function is configured to generate an element of the given set of target integers if that element can be calculated from an input element by:

(i) multiplying the input element by one multiplier of the set of integer multipliers;

(ii) multiplying the product of step i by a value chosen from the set {−1, 1}; and

(iii) if the chosen value is −1, then adding the product of step ii to 2 w .

16. A computer program product as in claim 14 wherein the target generation function is configured to generate an element of the given set of target integers if that element can be calculated from an input element by:

(i) multiplying the input element by one multiplier of the set of integer multipliers;

(ii) multiplying the product of step i by a value chosen from the set {−1, 1};

(iii) if the chosen value from step ii is −1, then adding the product of step ii to 2 w multiplied by a value chosen from the set {1, 2}; and

(iv) if the chosen value from step ii is 1, then adding the product of step ii to 2 w multiplied by a value chosen from the set {−1, 0}.

17. A method for creating an acceleration table for an Elliptic Curve Cryptography (ECC) scalar multiplication table, the method comprising:

(a) receiving, from user interface circuitry, a set of integer multipliers;

(b) in a microprocessor, choosing a subset of a given set of target integers, the chosen subset defining an index set, such that elements of the index set generate all elements of the given set of target integers using a target generation function;

(c) in the microprocessor, modifying the index set by removing an element from the index set which is not necessary to generate an element of the given set of target integers using the target generation function;

(d) in the microprocessor, after modifying the index set, generating an ECC scalar multiplication table having a plurality of sub-tables, each sub-table having one entry for each element of the index set; and

(e) storing the ECC scalar multiplication table on a non-transitory computer-readable storage medium;

wherein:

receiving includes further receiving, from the user interface circuitry, an integer window size, w;

the given set of target integers consists of all integers between 1 and 2 w −1, inclusive; and

choosing the subset of the given set of target integers includes performing the following sub-steps:

(1) creating, in memory, an index mask array, A, A being an array of 2 w -bit bit masks with integer indices ranging from 1 to 2 w−1 such that for each index, i, the corresponding bit mask is set to represent a set of integers which can be generated from that index using the target generation function;

(2) sequentially, for each index j of A:

logically bitwise OR-ing a best mask, B, B being a 2 w -bit bit mask, with A[j] to form a temporary mask T; and

if a number of set bits in T exceeds a number of set bits in B, then setting B=T and storing j as a best index, b;

(3) after completing sub-step 2, adding b to the index set; and

(4) repeating sub-steps 2 and 3 sequentially until every element of B having an index from 1 to 2 w−1 , inclusive, is set to 1.

18. A method as in claim 17 wherein the target generation function is configured to generate an element of the given set of target integers if that element can be calculated from an input element by:

(i) multiplying the input element by one multiplier of the set of integer multipliers;

(ii) multiplying the product of step i by a value chosen from the set {−1, 1}; and

(iii) if the chosen value is −1, then adding the product of step ii to 2 w .

19. A method as in claim 17 wherein the target generation function is configured to generate an element of the given set of target integers if that element can be calculated from an input element by:

(i) multiplying the input element by one multiplier of the set of integer multipliers;

(ii) multiplying the product of step i by a value chosen from the set {−1, 1};

(iii) if the chosen value from step ii is −1, then adding the product of step ii to 2 w multiplied by a value chosen from the set {1, 2}; and

(iv) if the chosen value from step ii is 1, then adding the product of step ii to 2 w multiplied by a value chosen from the set {−1, 0}.

20. An apparatus comprising:

user interface circuitry;

a non-transitory computer-readable storage medium;

a microprocessor; and

memory, the memory storing instructions, which, when performed by the microprocessor, cause the microprocessor to perform the following steps:

(a) receiving, from the user interface circuitry, a set of integer multipliers;

(b) choosing a subset of a given set of target integers, the chosen subset defining an index set, such that elements of the index set generate all elements of the given set of target integers using a target generation function;

(c) modifying the index set by removing an element from the index set which is not necessary to generate an element of the given set of target integers using the target generation function;

(d) after modifying the index set, generating an ECC scalar multiplication table having a plurality of sub-tables, each sub-table having one entry for each element of the index set; and

(e) storing the ECC scalar multiplication table on the non-transitory computer-readable storage medium;

wherein:

receiving includes further receiving, from the user interface circuitry, an integer window size, w;

the given set of target integers consists of all integers between 1 and 2 w −1, inclusive; and

choosing the subset of the given set of target integers includes performing the following sub-steps:

(1) creating, in memory, an index mask array, A, A being an array of 2 w -bit bit masks with integer indices ranging from 1 to 2 w−1 such that for each index, i, the corresponding bit mask is set to represent a set of integers which can be generated from that index using the target generation function;

(2) sequentially, for each index j of A:

 logically bitwise OR-ing a best mask, B, B being a 2 w -bit bit mask, with A[j] to form a temporary mask T; and

 if a number of set bits in T exceeds a number of set bits in B, then setting B=T and storing j as a best index, b;

(3) after completing sub-step 2, adding b to the index set; and

(4) repeating sub-steps 2 and 3 sequentially until every element of B having an index from 1 to 2 w−1 , inclusive, is set to 1.

21. An apparatus comprising:

user interface circuitry;

a non-transitory computer-readable storage medium;

a microprocessor; and

memory, the memory storing instructions, which, when performed by the microprocessor, cause the microprocessor to perform the following steps:

(a) receiving, from the user interface circuitry, a set of integer multipliers and an integer degree greater than 1, d;

(b) choosing a subset of a given set of target integers, the chosen subset defining an index set, such that elements of the index set generate all elements of the given set of target integers using a target generation function;

(c) modifying the index set by removing an element from the index set which is not necessary to generate an element of the given set of target integers using the target generation function;

(d) after modifying the index set, generating an Elliptic Curve Cryptography (ECC) scalar multiplication table having a plurality of sub-tables, each sub-table having one entry for each element of the index set; and

(e) storing the ECC scalar multiplication table on the non-transitory computer-readable storage medium;

(f) before generating the ECC scalar multiplication table, for some integer n, modifying the index set by replacing n elements with n−1 elements such that, after the modification, elements of the index set still generate all elements of the given set of target integers using the target generation function; and

(g) before generating the ECC scalar multiplication table, repeating steps c and f in succession until no further elements can be removed or replaced from the index set;

wherein step g includes the following ordered sub-steps:

(1) performing step c repeatedly until no further elements can be removed from the index set;

(2) attempting to perform step f for n=2 until n=d or until step f is performed successfully, whichever occurs first; and

(3) looping back to sub-step 1 if step f was successfully performed in sub-step 2, but terminating step g if step f was not successfully performed in sub-step 2.