Scalable and unified multiplication methods and apparatus

Abstract

Scalable and unified multipliers for multiplication of cryptographic parameters represented as elements of either of the prime field (GF(p)) and the binary extension field (GF(2 m )) include processing elements arranged to execute in pipeline stages. The processing elements are configurable to perform operations corresponding to either the prime field or the binary extension field. In an example, the processing elements include a dual-field adder having a field-select input that permits selection of a field arithmetic. In a representative example, multipliers are implemented as integrated circuits having processing units that each receive a single bit of one operand and partial words of the remaining operand.

1. A cryptographic processor, comprising:
 inputs for receiving a first and a second cryptographic parameter represented as elements of a finite field; 
 a multiplication module configured to receive the cryptographic parameters from the inputs, the multiplication module including a first processing unit and a second processing unit configured to determine a Montgomery product of the cryptographic parameters, the first processing unit and the second processing unit configured to receive a first bit and a second bit corresponding to the first parameter, respectively, and partial words of the second parameter; and 
 a field-type input in communication with the multiplication module for selection of an arithmetic operation in the multiplication module to be performed in accordance with GF(p) or GF(2 m ) arithmetic, wherein GF(p) is a prime field, GF(2 m ) is a binary extension field, p is a positive prime number, and m is a positive integer. 
 
   
   
     2. The processor of  claim 1 , wherein the first processing unit is configured to communicate intermediate values of partial words of the Montgomery product to the second processing unit. 
   
   
     3. The processor of  claim 2 , wherein the first and second cryptographic parameters are represented as m bits and e words of word length w, wherein e=┌(m+1)/w┐, and m, e, and w are positive integers. 
   
   
     4. The processor of  claim 1 , wherein the arithmetic operation selectable with the field-type input is field addition. 
   
   
     5. The processor of  claim 4 , further comprising a dual-field adder in communication with the field-type input. 
   
   
     6. The processor of  claim 5 , wherein the first and second cryptographic parameters are represented as m bits and e words of word length w, wherein e=┌(m+1)/w┐, and m, e, and w are positive integers. 
   
   
     7. The processor of  claim 4 , wherein the first and second cryptographic parameters are represented as m bits and e words of word length w, wherein e=┌(m+1)/w┐, and m, e, and w are positive integers. 
   
   
     8. The cryptographic processor of  claim 1 , wherein the multiplication module further comprises a third processing unit and a fourth processing unit configured to receive a third bit and a fourth bit, respectively, corresponding to the first parameter and partial words of the second parameter. 
   
   
     9. The processor of  claim 1 , further comprising a dual-field adder in communication with the field-type input. 
   
   
     10. The processor of  claim 9 , wherein the dual-field adder is configured to selectively execute addition corresponding to addition with carry or without carry based on the field-type input. 
   
   
     11. The processor of  claim 1 , wherein the first and second cryptographic parameters are represented as m bits and e words of word length w, wherein e=┌(m+1)/w┐, and m, e, and w are positive integers. 
   
   
     12. A method of determining a Montgomery product of a first cryptographic parameter and a second cryptographic parameter, the method comprising:
 representing the first cryptographic parameter as a series of bits; 
 representing the second cryptographic parameter and a modulus as a series of words; 
 processing a first bit of the first parameter with each word of the modulus and each word of the second parameter to produce a first series of intermediate values and a contribution to the Montgomery product based on the first bit; 
 processing a second bit of the first parameter with each word of the modulus and each word of the second parameter, and a corresponding intermediate value from the first series of intermediate values to produce a second series of intermediate values and a contribution to the Montgomery product based on the second bit, wherein the first series of intermediate values and the second series of intermediate values are determined based on a field-type input that selects an arithmetic operation to be performed in accordance with GF(p) or GF(2 m ) arithmetic, wherein GF(p) is a prime field, GF(2 m ) is a binary extension field, p is a positive prime number, and m is a positive integer, 
 combining the first contribution and the second contribution; and 
 using the combination of the first and second contributions in a cryptographic process. 
 
   
   
     13. A computer-readable medium containing instructions for executing the method of  claim 12 . 
   
   
     14. The method of  claim 12 , further comprising selecting an addition operation based on the field-type input. 
   
   
     15. The method of  claim 14 , wherein the selected addition operation corresponds to addition with carry or without carry.