Apparatus and methods for prime field modular reduction
Apparatus and methods for prime field modular reduction are described. As an example, a custom modular reduction digital circuit for reducing an n-bit integer based on a modulus, where the modulus comprises a k-bit integer for use with a cryptographic algorithm, is described. The custom modular reduction digital circuit includes a first circuit to generate at least two partial results by processing: (1) k lower order significant bits of the n-bit integer and (2) at least a subset of bits for congruent representations corresponding to any n-k higher order bits of the n-bit integer that are higher in significance than the most significant bit of the k-bit integer. The custom modular reduction digital circuit further includes a second circuit to process the at least two partial results, output by the first circuit, to generate a reduced version of the n-bit integer for use with the cryptographic algorithm.
1 . A custom modular reduction digital circuit for reducing an n-bit integer based on a modulus, wherein the modulus comprises a k-bit integer for use with a cryptographic algorithm, the custom modular reduction digital circuit comprising:
a first circuit to generate at least two partial results by processing: (1) k lower order significant bits of the n-bit integer and (2) at least a subset of bits for congruent representations corresponding to any n-k higher order bits of the n-bit integer that are higher in significance than most significant bit of the k-bit integer, wherein the first circuit is to bypass subtraction operations and multiplication operations with respect to the at least two partial results; and
a second circuit to process the at least two partial results, output by the first circuit, to generate a reduced version of the n-bit integer for use with the cryptographic algorithm, wherein the first circuit and the second circuit are implemented at least partly in a hardware logic component.
2 . The custom modular reduction digital circuit of claim 1 , wherein the generation of the at least two partial results comprises summing the k lower order significant bits of the n-bit integer with the subset of the bits for the congruent representations corresponding to any n-k higher order bits of the n-bit integer that are higher in significance than the most significant bit of the k-bit integer.
3 . The custom modular reduction digital circuit of claim 2 , wherein the summing results in a formation of intermediate partial results with a carryover bit having a higher significance than the most significant bit of the k-bit integer, and wherein the first circuit is to fold back any such formed intermediate partial results by replacing them with respective congruent representations for further processing.
4 . The custom modular reduction digital circuit of claim 1 , wherein the first circuit comprises a structure corresponding to a Wallace tree or a Dadda tree to perform addition operations.
5 . The custom modular reduction digital circuit of claim 4 , wherein the second circuit comprises a carry look-ahead adder.
6 . The custom modular reduction digital circuit of claim 1 , wherein the cryptographic algorithm uses only a specific prime modulus, and wherein the modulus comprises the specific prime modulus.
7 . The custom modular reduction digital circuit of claim 1 , wherein the encryption algorithm is one of a Rivest-Shamir-Adleman (RSA) algorithm, an Elliptic Curve Cryptography (ECC), or a lattice-based cryptography algorithm.
8 . A method for reducing an n-bit integer based on a modulus, wherein the modulus comprises a k-bit integer for use with a cryptographic algorithm, the method comprising:
generating, via a custom modular reduction digital circuit, at least two partial results by processing: (1) k lower order significant bits of the n-bit integer and (2) at least a subset of bits for congruent representations corresponding to any n-k higher order bits of the n-bit integer that are higher in significance than most significant bit of the k-bit integer, wherein subtraction operations and multiplication operations are bypassed with respect to the at least two partial results; and
processing, via the custom modular reduction digital circuit, the at least two partial results to generate a reduced version of the n-bit integer for use with the cryptographic algorithm.
9 . The method of claim 8 , wherein generating the at least two partial results comprises summing the k lower order significant bits of the n-bit integer with the subset of the bits for the congruent representations corresponding to any n-k higher order bits of the n-bit integer that are higher in significance than the most significant bit of the k-bit integer.
10 . The method of claim 9 , wherein the summing results in a formation of intermediate partial results with a carryover bit having a higher significance than the most significant bit of the k-bit integer, and wherein the method further comprises folding back any such formed intermediate partial results by replacing them with respective congruent representations for further processing.
11 . The method of claim 8 , wherein the cryptographic algorithm uses only a specific prime modulus, and wherein the modulus comprises the specific prime modulus.
12 . The method of claim 8 , further comprising pre-computing the congruent representations and storing them in one or more lookup tables.
13 . The method of claim 12 , further comprising prior to generating the at least two partial results, retrieving the congruent representations from the one or more lookup tables.
14 . A custom modular reduction digital circuit for reducing an n-bit integer based on a modulus, wherein the modulus comprises a k-bit integer for use with a cryptographic algorithm, the custom modular reduction digital circuit comprising:
a first circuit to generate at least two partial results by processing: (1) k lower order significant bits of the n-bit integer, (2) at least a subset of bits for congruent representations corresponding to any n-k higher order bits of the n-bit integer that are higher in significance than most significant bit of the k-bit integer, and (3) a constant corresponding to any negative terms associated with the congruent representations, wherein the first circuit is to bypass subtraction operations and multiplication operations with respect to the at least two partial results; and
a second circuit to process the at least two partial results, output by the first circuit, to generate a reduced version of the n-bit integer for use with the cryptographic algorithm, wherein the first circuit and the second circuit are implemented at least partly in a hardware logic component.
15 . The custom modular reduction digital circuit of claim 14 , wherein the generation of the at least two partial results comprises summing the k lower order significant bits of the n-bit integer, the subset of the bits for the congruent representations corresponding to any n-k higher order bits of the n-bit integer that are higher in significance than the most significant bit of the k-bit integer, and the constant corresponding to any negative terms associated with the congruent representations.
16 . The custom modular reduction digital circuit of claim 15 , wherein the summing results in a formation of intermediate partial results with a carryover bit having a higher significance than the most significant bit of the k-bit integer, and wherein the first circuit is to fold back any such formed intermediate partial results by replacing them with respective congruent representations for further processing.
17 . The custom modular reduction digital circuit of claim 15 , wherein the first circuit comprises a structure corresponding to a Wallace tree or a Dadda tree to perform addition operations.
18 . The custom modular reduction digital circuit of claim 17 , wherein the second circuit comprises a carry look-ahead adder.
19 . The custom modular reduction digital circuit of claim 14 , wherein the cryptographic algorithm uses only a specific prime modulus, and wherein the modulus comprises the specific prime modulus.
20 . The custom modular reduction digital circuit of claim 14 , wherein the encryption algorithm is one of a Rivest-Shamir-Adleman (RSA) algorithm, an Elliptic Curve Cryptography (ECC), or a lattice-based cryptography algorithm.