System and method for big number hardware multiplication for cryptography
A system performs big number multiplication during a cryptographic process. This can occur, for example, when a controller in a storage system encrypts data for storage in its memory or decrypts data read from its memory. To perform the multiplication of these big input numbers quickly, the system uses a modified Toom-Cook algorithm comprising a plurality of levels of coefficient vectors for each of the input numbers. This involves performing a sample extraction process, a point multiplication process, and an interpolation (synthesis) process.
1 . A storage system comprising:
a memory; and
a controller comprising a processor and a plurality of hardware multipliers, wherein the controller is configured to:
receive data from a host to store in the memory;
transform the data received from the host to encrypted data by performing a cryptographic process to encrypt the data by:
using the processor to:
receive input numbers x and y for multiplication; and
generate a plurality of levels of coefficient vectors for x and for y; and
using the plurality of hardware multipliers to:
perform a sample extraction process by multiplying the plurality of levels of coefficient vectors for x by a first decomposition matrix to yield a first result vector and by multiplying the plurality of levels of coefficient vectors for y by a second decomposition matrix to yield a second result vector;
perform a point multiplication process by multiplying the first and second result vectors to yield a third result vector; and
perform an interpolation process by multiplying the third result vector by a synthesis matrix to yield a result and dividing the result by a constant to yield a final result by accessing small, fast memory at algorithm concatenations with iterations done in a single clock cycle; and
store the encrypted data in the memory.
2 . The storage system of claim 1 , wherein the processor is configured to retrieve the constant from a look-up table.
3 . The storage system of claim 1 , wherein the plurality of hardware multipliers is configured to perform the dividing from multiple starting points and make corrections according to remainders of the division.
4 . The storage system of claim 1 , wherein the cryptographic process is based on a Toom-Cook algorithm comprising the plurality of levels of coefficient vectors.
5 . The storage system of claim 1 , wherein the plurality of hardware multipliers is configured to use a modified Montgomery multiplier to perform the multiplying from a most-significant bit to a least-significant bit.
6 . The storage system of claim 1 , wherein the first decomposition matrix comprises a product of decomposition matrices of each of the plurality of levels of coefficient vectors for x, and wherein the second decomposition matrix comprises a product of decomposition matrices of each of the plurality of levels of coefficient vectors for y.
7 . The storage system of claim 6 , wherein the plurality of hardware multipliers is configured to compute the first decomposition matrix offline and then perform the point multiplication process.
8 . The storage system of claim 1 , wherein the plurality of hardware multipliers is configured to perform the point multiplication process before the sample extraction process ends.
9 . The storage system of claim 1 , wherein the memory comprises a three-dimensional memory.
10 . In a data storage device comprising a memory and a controller comprising a processor and a plurality of hardware multipliers, a method comprising:
receiving data from a host to store in the memory;
transforming the data received from the host to encrypted data by performing a cryptographic process to encrypt the data by:
using the processor to:
receive input numbers x and y for multiplication; and
generate a plurality of levels of coefficient vectors for x and for y; and
using the plurality of hardware multipliers to:
perform a sample extraction process by multiplying the plurality of levels of coefficient vectors for x by a first decomposition matrix to yield a first result vector and by multiplying the plurality of levels of coefficient vectors for y by a second decomposition matrix to yield a second result vector;
perform a point multiplication process by multiplying the first and second result vectors to yield a third result vector; and
perform an interpolation process by multiplying the third result vector by a synthesis matrix to yield a result and dividing the result by a constant to yield a final result by accessing small, fast memory at algorithm concatenations with iterations done in a single clock cycle; and
storing the encrypted data in the memory.
11 . The method of claim 10 , further comprising using the processor to retrieve the constant from a look-up table.
12 . The method of claim 10 , further comprising using a Toom-Cook algorithm comprising the plurality of levels of coefficient vectors, wherein the plurality of levels of coefficient vectors comprises two levels, each of the two levels comprising four parts.
13 . The method of claim 10 , further comprising using a modified Montgomery multiplier to perform the multiplying from a most-significant bit to a least-significant bit.
14 . The method of claim 10 , wherein the first decomposition matrix comprises a product of decomposition matrices of each of the plurality of levels of coefficient vectors for the first number, and wherein the second decomposition matrix comprises a product of decomposition matrices of each of the plurality of levels of coefficient vectors for the second number.
15 . The method of claim 10 , further comprising using a plurality of hardware multipliers to perform a point multiplication process before a sample extraction process ends.
16 . The method of claim 10 , wherein the method is performed in a controller of a storage system.
17 . The method of claim 11 , wherein the method is performed in a host in communication with a storage system.
18 . A data storage device comprising:
a memory; and
means for transforming data received from a host to store in the memory to encrypted data by performing a cryptographic process to encrypt the data by:
using a processor to:
receive input numbers x and y for multiplication; and
generate a plurality of levels of coefficient vectors for x and for y; and
using the plurality of hardware multipliers to:
perform a sample extraction process by multiplying the plurality of levels of coefficient vectors for x by a first decomposition matrix to yield a first result vector and by multiplying the plurality of levels of coefficient vectors for y by a second decomposition matrix to yield a second result vector;
perform a point multiplication process by multiplying the first and second result vectors to yield a third result vector; and
perform an interpolation process by multiplying the third result vector by a synthesis matrix to yield a result and dividing the result by a constant to yield a final result by accessing small, fast memory at algorithm concatenations with iterations done in a single clock cycle; and
means for storing the encrypted data in the memory.