US 8,411,855 B1Granted

Size optimization for large elliptic curve cryptography scalar multiplication acceleration tables

AssigneeEMC Corporation

InventorsPeter Alan Robinson, David Paul Makepeace, Sean Parkinson, Mark Hibberd

Life of this patent

Estimating the term…

Loading patent…

Abstract

A computer program product and method are provided for optimizing the size of an Elliptic Curve Cryptography (ECC) scalar multiplication table. Steps include (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, and (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. Additional steps are also included depending on the embodiment.

Claims21

Dependent claims

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.

10 more elements

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.

11 more elements

(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 2w−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 2w-bit bit masks with integer indices ranging from 1 to 2w−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 2w-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 2w−1, inclusive, is set to 1.

15 more elements

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 2w−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 2w-bit bit masks with integer indices ranging from 1 to 2w−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 2w-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 2w−1, inclusive, is set to 1.

16 more elements

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 2w−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 2w-bit bit masks with integer indices ranging from 1 to 2w−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 2w-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 2w−1, inclusive, is set to 1.

21 more elements

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.

16 more elements

Dependencies are inferred from the claim text.

Facts

Application: 12/633,400Filed 8 Dec 2009 · us provisional application
Priority: 12 Dec 2008
Granted: 2 Apr 2013
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

H04L 9/3066
Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy: involving…
G06F 7/725
Finite field arithmetic: over elliptic curves
H04L 2209/12
Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication…
H04L
Digital communication

Family

Application61/122,116Us provisional application · filed 12 Dec 2008
Application61/122,120Us provisional application · filed 12 Dec 2008
Application61/122,125Us provisional application · filed 12 Dec 2008
Application61/122,131Us provisional application · filed 12 Dec 2008
US 8,411,855 B1This patent

From the US filing history. Foreign family members aren’t listed.