Abstract:
Disclosed are a semi-sequential Galois field GF(2 n ) multiplier and the method thereof. The GF(2 n ) multiplier comprises two ground field multipliers over GF(2 m ), at least a constant multiplier, and multiple GF(2 m ) adders. The high-order and low-order elements from a composite field GF((2 m ) 2 ) for one operand of one GF(2 n ) multiplication are inputted in parallel into the two ground GF(2 m ) multipliers, respectively. The high-order and low-order elements from the composite field of another operand of the GF(2 n ) multiplication are sequentially inputted into the two ground GF(2 m ) multipliers. As such, multiple partial products are generated. The constant multiplication and additions are performed on the multiple partial products through the constant multiplier and the GF(2 m ) adders. This generates a high-order element and a low-order element of the composite field GF((2 m ) 2 ). After mapping these two elements of GF((2 m ) 2 ) back to GF(2 n ), the GF(2 n ) multiplication is done.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention generally relates to a semi-sequential Galois Field multiplier and the method for performing the same. 
       BACKGROUND OF THE INVENTION 
       [0002]    Galois Counter Mode-Advanced Encryption Standard (GCM-AES) is widely applied to the IPsec environment. The second layer security standard MACsec of Ethernet also uses GCM-AES algorithm as the default encryption/decryption. GCM-AES algorithm uses Galois Field GF(2 128 ) multiplication to realize the hash function, resulting in the increase of the hardware cost of GCM-AES in hardware implementation. The hardware cost of a single GF(2 128 ) multiplier is near the cost of a 128-bit AES core engine. When integrating the MACsec controller having GCM-AES to the Ethernet MAC controller, the cost ration affected by GCM-AES will be even higher. 
         [0003]    GF(2 n ) is a finite field, a space defined by an n-order primitive polynomial, with 2 n  elements. Each element is n-bit, and n bits are the coefficients of the polynomial of the corresponding element: 
         [0000]      b 0 +b 1 x+ . . . +b n-1 x n-1    
         [0000]    where b i  is an element in GF(2), either 0 or 1. Assume that the primitive polynomial constructing the GF(2 n ) space is g(x), the multiplication of GF(2 n ) elements may be seen as two steps: first, two elements go through a general polynomial multiplication; then, the obtained polynomial in the first step is divided by g(x) to obtain the remainder. The addition of GF(2 n ) elements is logically the same as the n-bit XOR operation. 
         [0004]    When n is a large positive integer, such as 128, the GF(2 n ) multiplication is an expensive computation. Therefore, a composite field is used to reduce the computation complexity. The mathematic expression for composite field is GF((2 m ) k ), where k*m=n, and both m and k are positive integers. In terms of the number of bits of elements, the composite field is to translate an n-bit element in GF(2 n ) to k m-bit elements in GF(2 m ). Because k*m=n, the entire result is still an n-bit value. In the composite field, GF(2 m ) is called a ground field. To map an element from GF(2 n ) to GF((2 m ) k ), three polynomials are required, including g(x) required to construct GF(2 n ), an m-order primitive polynomial p(x) and a k-order primitive polynomial r(x), where the coefficients of p(x) belong to GF(2), and the coefficients of r(x) belong to GF(2 m ). 
         [0005]    Then, by using the theory proposed by Christof Paar, an n×n matrix M may be found to map elements from GF(2 n ) to GF((2m) k ). The inverse matrix M −1  will map the elements from GF((2 m ) k ) to GF(2 n ). In the polynomial representation, A element in GF(2 n ) is represented as: 
         [0000]        A ( x )= a   0   +a   1   x+ . . . +a   n-1   x   n-1    a   i   ∈GF (2) 
         [0000]    After mapped to composite field GF((2 m ) k ), A may be represented by: 
         [0000]        A ( x )=a 0   +a   1   x a   i   ∈GF (2 m ) 
         [0000]    The composite field multiplication is the same as the aforementioned two steps, first, a general polynomial multiplication followed by obtaining of a remainder. 
         [0006]    There are numerous disclosed techniques for Galois Field multipliers (GF multiplier). For example, U.S. Pat. No. 4,251,875 disclosed a generic GF multiplier architecture. By using a single GF(2 m ) multiplier architecture, the two operands are sequentially inputted to complete the GF(2 n ) multiplication, where m is a multiple of n. U.S. Pat. No. 7,113,968 disclosed a GF multiplier architecture using a polynomial and two operations of polynomial modulo. 
         [0007]    U.S. Pat. No. 7,133,889 disclosed a GF multiplier architecture, as shown in  FIG. 1 , using a single ground field GF(2 m ) multiplier architecture and using Karatsuba-Ofman computation for multiplication. U.S. Pat. No. 6,957,243 disclosed a GF multiplier architecture using polynomial factoring approach, by inputting an operand A(x) sequentially, i.e., A 0 (x), A 1 (x), . . . ,A T−1 (x) sequentially, and inputting another operand b(x) in parallel, to perform multiplication, as shown in  FIG. 2 . 
         [0008]    In recent years, GF(2 n ) is widely applied to error-control code (ECC) and encryption, such as Reed-Solomon, Cyclic Code in ECC, and Ellipse curve encryption system, AES, and GCM in encryption. Hence, it is imperative to devise a GF multiplier hardware architecture to reduce the GCM-AES cost, maintain Gigabit processing power and suit the network communication environment. 
       SUMMARY OF THE INVENTION 
       [0009]    The disclosed exemplary embodiments of the present invention may provide a semi-sequential GF multiplier and the method for performing the same. 
         [0010]    In an exemplary embodiment, the disclosed is directed to a semi-sequential GF multiplier for executing the multiplication of two operands of GF(2 n ), where n is a positive even number. The GF(2 n ) multiplier may comprise two single ground field GF(2 m ) multipliers, at least a constant multiplier, and a plurality of single GF(2 m ) adders, where n=2m, n and m are both positive integers. The high-order and the low-order elements of the composite field of one operand of GF(2 n ) multiplication are inputted in parallel to the two single ground field GF(2 m ) multipliers, while the high-order and the low-order elements of the composite field of the other operand of GF(2 n ) multiplication are inputted sequentially to the two single ground field GF(2 m ) multipliers, and a plurality of partial products of GF(2 m ) are generated. Then, the partial products of GF(2 m ) generate a high-order and a low-order elements of the GF(2 n ) product through the constant multiplier and the plurality of single GF(2 m ) adders. The high-order and the low-order elements of the GF(2 n ) product are mapped back to GF(2 n ) to accomplish the GF(2 n ) multiplication. 
         [0011]    In another exemplary embodiment, the disclosed is directed to a semi-sequential data input method for GF multiplication, comprising: mapping the two operands of GF(2 n ) multiplication from GF(2 n ) to GF((2 m ) 2 ) to obtain composite field elements; and inputting the high-order and the low-order elements of the composite field of one operand of GF(2 n ) multiplication in parallel to two single ground field GF(2 m ) multipliers, while inputting the high-order and the low-order elements of the composite field of the other operand of GF(2 n ) multiplication sequentially to the two single ground field GF(2 m ) multipliers. 
         [0012]    Yet in another exemplary embodiment, the disclosed is directed to a method for executing semi-sequential GF multiplication, comprising: mapping the two operands of GF(2 n ) multiplication from GF(2 n ) to GF((2 m ) 2 ) to obtain composite field elements, where the high-order and the low-order elements of the composite field of one operand of GF(2 n ) multiplication being inputted in parallel to two single ground field GF(2 m ) multipliers, while the high-order and the low-order elements of the composite field of the other operand of GF(2 n ) multiplication being inputted sequentially to the two single ground field GF(2 m ) multipliers; dividing the GF(2 n ) multiplication into a plurality of GF(2 m ) partial products; and using the two ground field GF(2 m ) multipliers, at least a constant multiplier and a plurality of GF(2 m ) adders to execute the plurality of GF(2 m ) partial products and generate a high-order element and a low-order element of the product. 
         [0013]    The foregoing and other features, aspects and advantages of the present invention will become better understood from a careful reading of a detailed description provided herein below with appropriate reference to the accompanying drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0014]      FIG. 1  shows an exemplary schematic view of a conventional GF multiplier. 
           [0015]      FIG. 2  shows an exemplary schematic view of another conventional GF multiplier. 
           [0016]      FIG. 3  shows an exemplary schematic view of a semi-sequential GF multiplier, consistent with certain disclosed embodiments of the present invention. 
           [0017]      FIG. 4  shows an exemplary flowchart illustrating a method for performing a semi-sequential GF multiplication, consistent with certain disclosed embodiments of the present invention. 
           [0018]      FIG. 5  shows an exemplary schematic view of using Mastrivito multiplier hardware to realize an m-bit GF multiplication, consistent with certain disclosed embodiments of the present invention. 
           [0019]      FIG. 6  shows a scenario when one operand of GF multiplication is a low frequency variable, consistent with certain disclosed embodiments of the present invention. 
           [0020]      FIG. 7  shows an exemplary schematic view illustrating an embodiment of realizing the two ground field GF(2 m ) multipliers of  FIG. 3  by using two Mastrivito multipliers, consistent with certain disclosed embodiments of the present invention. 
           [0021]      FIG. 8  shows an exemplary schematic view of a GF multiplier with integrating mapping to composite field computation and product matrix into a single matrix conversion, consistent with certain disclosed embodiments of the present invention. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0022]    The present invention targets the situation where one operand of the GF(2 n ) multiplication is a low frequency variable and the other operand is a high frequency variable. The low frequency variable is inputted in parallel, and the high frequency variable is inputted sequentially. The GF((2 m ) 2 ) composite field form is used to realize a GF(2 n ) multiplier, where the GF(2 n ) primitive polynomial is g(x) and GF(2 m ) primitive polynomial is p(x). The low frequency variable is similar to the GHASH computation in GCM mode, where the H value involved in the GF multiplication depends on the secret key K, and the update frequency of key K is low in actual application environment. The H value is the value obtained through the encryption algorithm using key K to encrypt an all-zero data block, is also one of the three inputs to the GHASH computation, and n is a positive even integer. 
         [0023]    The disclosed exemplary embodiments uses the polynomial r(x)=r 0 +x+x 2  as the example to form the GF((2 m ) 2 ) space, where r 0  is an element in GF(2 m ), and makes r(x) satisfy the primitivity in GF(2 m ). Assume that A and B are both elements of GF(2 n ), after mapped to GF((2 m ) 2 ) space, the polynomial representations are a 0 +a 1 x and b 0 +b 1 x, respectively, where {a 0 , a 1 , b 0 , b 1 } ∈ GF(2 m ) and b 1  is the coefficient of x. In other words, b 1  is the high-order GF(2 m ) element in GF((2 m ) 2 ), and b 0  is the low-order element. The relation between high-order a 1  and low-order a 0  is also similar. The multiplication may be expressed as: 
         [0000]    
       
         
           
             
               
                 
                   
                     A 
                     × 
                     B 
                   
                   = 
                     
                    
                   
                     
                       ( 
                       
                         
                           a 
                           0 
                         
                         + 
                         
                           
                             a 
                             1 
                           
                            
                           x 
                         
                       
                       ) 
                     
                      
                     
                       ( 
                       
                         
                           b 
                           0 
                         
                         + 
                         
                           
                             b 
                             1 
                           
                            
                           x 
                         
                       
                       ) 
                     
                      
                     
                         
                     
                      
                     mod 
                      
                     
                         
                     
                      
                     
                       r 
                        
                       
                         ( 
                         x 
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       
                         a 
                         0 
                       
                        
                       
                         b 
                         0 
                       
                     
                     + 
                     
                       
                         ( 
                         
                           
                             
                               a 
                               1 
                             
                              
                             
                               b 
                               0 
                             
                           
                           + 
                           
                             
                               a 
                               0 
                             
                              
                             
                               b 
                               1 
                             
                           
                         
                         ) 
                       
                        
                       x 
                     
                     + 
                     
                       
                         a 
                         1 
                       
                        
                       
                         b 
                         1 
                       
                        
                       
                         x 
                         2 
                       
                        
                       
                           
                       
                        
                       mod 
                        
                       
                           
                       
                        
                       
                         r 
                          
                         
                           ( 
                           x 
                           ) 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       ( 
                       
                         
                           
                             a 
                             0 
                           
                            
                           
                             b 
                             0 
                           
                         
                         + 
                         
                           
                             a 
                             1 
                           
                            
                           
                             b 
                             1 
                           
                            
                           
                             r 
                             0 
                           
                         
                       
                       ) 
                     
                     + 
                     
                       
                         ( 
                         
                           
                             
                               a 
                               1 
                             
                              
                             
                               b 
                               0 
                             
                           
                           + 
                           
                             
                               a 
                               1 
                             
                              
                             
                               b 
                               1 
                             
                           
                           + 
                           
                             
                               a 
                               0 
                             
                              
                             
                               b 
                               1 
                             
                           
                         
                         ) 
                       
                        
                       x 
                     
                   
                 
               
             
           
         
       
     
         [0000]    where the value of a 1 b 0 +a 1 b 1 +a 0 b 1  is the high-order element in the product, and the value of a 0 b 0 +a 1 b 1 r 0  is the low-order element in the product. 
         [0024]      FIG. 3  shows an exemplary schematic view of a semi-sequential GF multiplier, consistent with certain disclosed embodiments of the present invention. Referring to  FIG. 3 , the hardware implementation of GF multiplier architecture executes the multiplication of the two operands, i.e., A and B, in GF(2 n ) to generate a product  330 . As may be seen from  FIG. 3 , the GF multiplier architecture may use two single ground field GF(2 m ) multipliers  301 ,  302 , at least a constant multiplier  311 , and a plurality of single GF(2 m ) adders  321 - 323 , to realize the GF(2 n ) multiplication, where n=2m. 
         [0025]    The high-order element and low-order element of composite field GF((2 m ) 2 ) of operand B are inputted in parallel to ground field GF(2 m ) multipliers  301 ,  302 , and the high-order element and the low-order element of composite field GF((2 m ) 2 ) of operand A are inputted sequentially to ground field GF(2 m ) multipliers  301 ,  302  to generate a plurality of GF(2 m ) partial products, such as, a 0 b 0 , a 1 b 1 , a 1 b 0 , and a 0 b 1 . The plurality of GF(2 m ) partial generates a high-order element and a low-order element of the GF((2 m ) 2 ) product through constant multiplier  311  and a plurality of GF(2 m ) adders  321 - 323 . The high-order element and the low-order element of the product are then mapped back to GF(2 n ) to accomplish the GF(2 n ) multiplication. 
         [0026]    The GF multiplier architecture may further include an input operand mapper for mapping each operand of GF(2 n ) to the GF((2 m ) 2 ) composite filed to obtain two corresponding GF(2 m ) elements, i.e., the high-order element and the low-order element of the composite field of the operand. 
         [0027]    The following describes the operation of the components of the GF multiplier to execute the GF(2 n ) multiplication. 
         [0028]    The following description of the GF(2 n ) multiplication execution refers to  FIG. 3 . The two input operands, A and B, to perform the GF(2 n ) multiplication will pass a mapping computation  333   a  for mapping operand A and operands B from GF(2 n ) into composite field GF((2 m ) 2 ) to obtain elements of composite field. The high-order element and low-order element of operand B, after mapping, are depicted as InputB_CF_H (i.e., b 1 ) and InputB_CF_L (i.e., b 0 ), respectively. The sequential input sequence of the high-order element and the low-order element of operand A after mapping is depicted as InputA_CF sequence. High-order element InputB_CF_H and low-order element InputB_CF L of operand B after mapping are inputted in parallel to ground field GF(2 m ) multipliers  301 ,  302 ; while two composite field elements of InputA_CF (i.e., a 1  and a 0 ) are inputted sequentially to ground field GF(2 m ) multipliers  301 ,  302 . 
         [0029]    Assume that the initial values in registers  341 ,  342  are zero, and the sequence of InputA_CF through sequencer  333   b  is first a 1  then a 0 , the execution flow of the operation is to input a 1 , through ground field GF(2 m ) multipliers  301 ,  302  to compute a 1 b 1  and a 1 b 0 . Then, output a 1 b 1  of ground field GF(2 m ) multiplier  301  is multiplied by a constant r 0  by constant multiplier  311  to obtain a 1 b 1 r 0 , which is stored to register  341  by control signal control- 2 . In other words, register  341  contains the value a 1 b 1 r 0  at this point. On the other hand, a 1 b 0  and a 1 b 1 , after GF(2 n ) element addition XOR, is stored to register  342  by control signal control- 1 . In other words, register  342  contains the value a 1 b 0 +a 1 b 1  at this point. Then, a 0  is inputted to composite field GF((2 m ) 2 ) multipliers  301 ,  302  to obtain a 0 b 0  and a 0 b 1 , respectively. 
         [0030]    Then, control signal control- 2  is used to make a 0 b 0  and a previous value of register  341  (i.e., a 1 b 1 r 0 ) to pass GF(2 n ) element addition XOR to obtain a 0 b 0 +a 1 b 1 r 0 . Control signal control- 1  selects a 0 b 1  and a previous value of register  342  to pass through GF(2 n ) element addition XOR to obtain a 1 b 0 +a 1 b 1 +a 0 b 1 . Finally, the contents of registers  341 ,  342  are mapped back to GF(2 n ) field, marked as  350 , to complete a GF(2 n ) multiplication. 
         [0031]      FIG. 4  shows an exemplary flowchart illustrating a method for performing a semi-sequential GF multiplication, consistent with certain disclosed embodiments of the present invention. Referring to the exemplary flowchart in  FIG. 4 , at first, two operands A, B of GF(2 n ) is mapped from GF(2 n ) to GF((2 m ) 2 ) to obtain composite field elements, as shown in step  410 . In step  420 , for one operand, such as B, the high-order element and the low-order element of composite field are inputted in parallel to two ground field GF(2 m ) multipliers, and for the other operand, such as A, the high-order element and the low-order element of composite field are inputted sequentially to two ground field GF(2 m ) multipliers. 
         [0032]    In other words, in the GF(2 n ) multiplication execution method of the disclosed, the input of the two operands are semi-sequential  412 , i.e. including steps  410 ,  420 . In step  420 , the sequential input sequence is not limited to either inputting high-order element first or low-order element first. Either way, both are within the scope of the semi-sequential input method of the present invention. 
         [0033]    After two operands are inputted, GF(2 n ) multiplication is divided into a plurality of GF(2 m ) partial products, as shown in step  430 . Step  440  is to use two ground field GF(2 m ) multipliers, at least a constant multiplier and a plurality of GF(2 m ) adders to execute the plurality of GF(2 m ) partial products and generate a high-order element and a low-order element of the product. 
         [0034]    Finally, the high-order element and the low-order element of the product are mapped back to GF(2 n ) field to complete a GF(2 n ) multiplication, as shown in step  450 . 
         [0035]    GF(2 m ) multipliers may be implemented with the Mastrivito multiplier architecture. Assume that the m-tuple of two GF(2m) elements are represented as A[m-1:0]=[a 0  a 1  . . . a m−1 ,], B[m−1:0]=[b 0  b 1  . . . b m−1 ], respectively, then the computation C=A[m−1:0]×B[m−1:0] of Mastrivito multiplier may be represented as: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       [ 
                       
                         
                           
                             
                               c 
                               0 
                             
                           
                         
                         
                           
                             
                               c 
                               1 
                             
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               c 
                               
                                 m 
                                 - 
                                 1 
                               
                             
                           
                         
                       
                       ] 
                     
                     
                        
                       C 
                     
                   
                   = 
                   
                     
                       
                         [ 
                         
                           
                             
                               
                                 z 
                                 
                                   0 
                                   , 
                                   0 
                                 
                               
                             
                             
                               
                                 z 
                                 
                                   0 
                                   , 
                                   1 
                                 
                               
                             
                             
                               … 
                             
                             
                               
                                 z 
                                 
                                   0 
                                   , 
                                   
                                     m 
                                     - 
                                     1 
                                   
                                 
                               
                             
                           
                           
                             
                               
                                 z 
                                 
                                   1 
                                   , 
                                   0 
                                 
                               
                             
                             
                               
                                 z 
                                 
                                   1 
                                   , 
                                   1 
                                 
                               
                             
                             
                               … 
                             
                             
                               
                                 z 
                                 
                                   1 
                                   , 
                                   
                                     m 
                                     - 
                                     1 
                                   
                                 
                               
                             
                           
                           
                             
                               ⋮ 
                             
                             
                               ⋮ 
                             
                             
                               ⋰ 
                             
                             
                               ⋮ 
                             
                           
                           
                             
                               
                                 z 
                                 
                                   
                                     m 
                                     - 
                                     1 
                                   
                                   , 
                                   0 
                                 
                               
                             
                             
                               
                                 z 
                                 
                                   
                                     m 
                                     - 
                                     1 
                                   
                                   , 
                                   1 
                                 
                               
                             
                             
                               … 
                             
                             
                               
                                 z 
                                 
                                   
                                     m 
                                     - 
                                     1 
                                   
                                   , 
                                   
                                     m 
                                     - 
                                     1 
                                   
                                 
                               
                             
                           
                         
                         ] 
                       
                       
                          
                         
                           Z 
                           B 
                         
                       
                     
                      
                     
                       
                         [ 
                         
                           
                             
                               
                                 a 
                                 0 
                               
                             
                           
                           
                             
                               
                                 a 
                                 1 
                               
                             
                           
                           
                             
                               ⋮ 
                             
                           
                           
                             
                               
                                 a 
                                 
                                   m 
                                   - 
                                   1 
                                 
                               
                             
                           
                         
                         ] 
                       
                       
                          
                         A 
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where Z B  is called product matrix, and the value of the matrix is z ij =f i,j (b 0 , b 1 , . . . , b m-1 ). 
         [0000]    
       
         
           
             
               
                 
                   
                     f 
                     
                       i 
                       , 
                       j 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               
                                 b 
                                 i 
                               
                             
                             
                               
                                 j 
                                 = 
                                 0 
                               
                             
                             
                               
                                 
                                   i 
                                   = 
                                   0 
                                 
                                 , 
                                 … 
                                  
                                 
                                     
                                 
                                 , 
                                 
                                   m 
                                   - 
                                   1 
                                 
                               
                             
                           
                           
                             
                               
                                 
                                   
                                     u 
                                      
                                     
                                       ( 
                                       
                                         i 
                                         - 
                                         j 
                                       
                                       ) 
                                     
                                   
                                    
                                   
                                     b 
                                     
                                       i 
                                       - 
                                       j 
                                     
                                   
                                 
                                 + 
                                 
                                   
                                     ∑ 
                                     
                                       t 
                                       = 
                                       0 
                                     
                                     
                                       j 
                                       - 
                                       1 
                                     
                                   
                                    
                                   
                                     
                                       q 
                                       
                                         
                                           j 
                                           - 
                                           1 
                                           - 
                                           t 
                                         
                                         , 
                                         i 
                                       
                                     
                                      
                                     
                                       b 
                                       
                                         n 
                                         - 
                                         l 
                                         - 
                                         t 
                                       
                                     
                                   
                                 
                               
                             
                             
                               
                                 
                                   j 
                                   = 
                                   1 
                                 
                                 , 
                                 … 
                                  
                                 
                                     
                                 
                                 , 
                                 
                                   m 
                                   - 
                                   1 
                                 
                               
                             
                             
                               
                                 
                                   i 
                                   = 
                                   0 
                                 
                                 , 
                                 … 
                                  
                                 
                                     
                                 
                                 , 
                                 
                                   m 
                                   - 
                                   1 
                                 
                               
                             
                           
                         
                          
                         
                           
 
                         
                          
                         and 
                          
                         
                             
                         
                          
                         
                           u 
                            
                           
                             ( 
                             μ 
                             ) 
                           
                         
                       
                       = 
                       
                         { 
                         
                           
                             
                               1 
                             
                             
                               
                                 μ 
                                 ≥ 
                                 0 
                               
                             
                           
                           
                             
                               0 
                             
                             
                               
                                 μ 
                                 &lt; 
                                 0. 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0036]      FIG. 5  shows an exemplary schematic view of using Mastrivito multiplier hardware to realize an m-bit GF multiplication, consistent with certain disclosed embodiments of the present invention. In the exemplary hardware implementation of  FIG. 5 , matrix-vector multiplier  501  is to execute the computation of equation (1) and product matrix  511  is to execute the computation of equation (2). An m×m product matrix Z B  may be obtained after function f mapping m-bit operand B. Then, the value of the matrix is multiplied by a matrix-vector multiplier, i.e., computation of equation (1), to complete an m-bit GF multiplication. 
         [0037]    In other words, one feature of the Mastrivito multiplier architecture is to divide the GF(2 m ) multiplication into two steps to complete an m-bit GF multiplication. The first step is to convert one operand B from m-bit vector into an m×m product matrix, and the second step is to perform matrix-vector multiplication with the matrix and the other operand A to obtain the final product. 
         [0038]    In the two-step architecture, when one operand is a low-frequency variable, as shown in  FIG. 6 , each B i  operand will be multiplied with a plurality of A i  operands. In this manner, a pipeline design may be used to perform matrix conversion on low frequency variable B to obtain an m×m product matrix Z B  and store the product matrix. Because A has a higher frequency of change than B, all the A×B operations before the change of B only require to execute equation (1) without equation (2). 
         [0039]      FIG. 7  shows an exemplary schematic view illustrating an embodiment of realizing the two ground field GF(2 m ) multipliers of  FIG. 3  by using two Mastrivito multipliers, consistent with certain disclosed embodiments of the present invention. Ground field GF(2 m ) multiplier  301  is realized by matrix-vector multiplier  501  and product matrix  511 , and ground field GF(2 m ) multiplier  302  is realized by matrix-vector multiplier  502  and product matrix  512 . As shown in  FIG. 7 , operand B will pass two operations of conversion before entering matrix-vector multiplier. One conversion is mapping to composite filed, and the other conversion is the product matrix conversion required by the Mastrivito architecture. The operation of mapping to composite field and the product matrix may be integrated into a single matrix conversion, shown as matrix conversion  821 ,  822  of  FIG. 8 , for converting the high-order element and low-order element of operand B, respectively. 
         [0040]    The above hardware realization of GF multiplier and related execution method may be applied to encryption/decryption system based on GCM-AES as the default encryption/decryption computation. Because the GF multipliers may be reused with computation units, the GCM-AES hardware cost may be effectively reduced. 
         [0041]    The following exemplar uses a GF((2 4 ) 2 ) composite field realizing a GF(2 8 ) multiplier, i.e., n=8, m=4, to explain the disclosed exemplary semi-sequential GF multiplier and executed method according to the present invention. 
         [0042]    Assume that primitive polynomial g(x) forming GF(2 8 ) is 1+x 2 +x 3 +x 4 +x 8 , primitive polynomial p(x) forming GF(2 4 ) is 1+x+x 4 , and the primitive polynomial for generating GF((2 4 ) 2 ) is x 2 +x+α 14 . According to Christof Paar theory, the matrix mapping from GF(2 8 ) to GF((2 4 ) 2 ) is: 
         [0000]    
       
         
           
               
             
               [ 
               
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     1 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                 
                 
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     1 
                   
                   
                     0 
                   
                 
                 
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                   
                     1 
                   
                   
                     1 
                   
                 
               
               ] 
             
           
         
       
     
         [0000]    Assume that operand B belongs to GF(2 8 ), with coefficients [b 0  b 1  b 2  b 3  b 4  b 5  b 6  b 7  b 8 ] T . After conversion, the following may be obtained, i.e., the operation of mapping into composite field in  FIG. 3 ,  FIG. 7  and  FIG. 8 . 
         [0000]    
       
         
           
             
               
                 [ 
                 
                   
                     
                       0 
                     
                     
                       0 
                     
                     
                       1 
                     
                     
                       0 
                     
                     
                       0 
                     
                     
                       0 
                     
                     
                       0 
                     
                     
                       0 
                     
                   
                   
                     
                       0 
                     
                     
                       1 
                     
                     
                       1 
                     
                     
                       0 
                     
                     
                       0 
                     
                     
                       1 
                     
                     
                       0 
                     
                     
                       0 
                     
                   
                   
                     
                       0 
                     
                     
                       0 
                     
                     
                       0 
                     
                     
                       1 
                     
                     
                       1 
                     
                     
                       0 
                     
                     
                       1 
                     
                     
                       0 
                     
                   
                   
                     
                       1 
                     
                     
                       0 
                     
                     
                       0 
                     
                     
                       1 
                     
                     
                       0 
                     
                     
                       0 
                     
                     
                       0 
                     
                     
                       0 
                     
                   
                   
                     
                       0 
                     
                     
                       0 
                     
                     
                       1 
                     
                     
                       0 
                     
                     
                       0 
                     
                     
                       1 
                     
                     
                       1 
                     
                     
                       0 
                     
                   
                   
                     
                       1 
                     
                     
                       0 
                     
                     
                       0 
                     
                     
                       1 
                     
                     
                       1 
                     
                     
                       0 
                     
                     
                       1 
                     
                     
                       0 
                     
                   
                   
                     
                       0 
                     
                     
                       0 
                     
                     
                       1 
                     
                     
                       0 
                     
                     
                       0 
                     
                     
                       0 
                     
                     
                       1 
                     
                     
                       0 
                     
                   
                   
                     
                       0 
                     
                     
                       0 
                     
                     
                       0 
                     
                     
                       0 
                     
                     
                       1 
                     
                     
                       0 
                     
                     
                       1 
                     
                     
                       1 
                     
                   
                 
                 ] 
               
                
               
                 [ 
                 
                   
                     
                       
                         b 
                         0 
                       
                     
                   
                   
                     
                       
                         b 
                         1 
                       
                     
                   
                   
                     
                       
                         b 
                         2 
                       
                     
                   
                   
                     
                       
                         b 
                         3 
                       
                     
                   
                   
                     
                       
                         b 
                         4 
                       
                     
                   
                   
                     
                       
                         b 
                         5 
                       
                     
                   
                   
                     
                       
                         b 
                         6 
                       
                     
                   
                   
                     
                       
                         b 
                         7 
                       
                     
                   
                 
                 ] 
               
             
             = 
             
               
                 [ 
                 
                   
                     
                       
                         b 
                         2 
                       
                     
                   
                   
                     
                       
                         
                           b 
                           1 
                         
                         + 
                         
                           b 
                           2 
                         
                         + 
                         
                           b 
                           5 
                         
                       
                     
                   
                   
                     
                       
                         
                           b 
                           3 
                         
                         + 
                         
                           b 
                           4 
                         
                         + 
                         
                           b 
                           6 
                         
                       
                     
                   
                   
                     
                       
                         
                           b 
                           0 
                         
                         + 
                         
                           b 
                           3 
                         
                       
                     
                   
                   
                     
                       
                         
                           b 
                           2 
                         
                         + 
                         
                           b 
                           5 
                         
                         + 
                         
                           b 
                           6 
                         
                       
                     
                   
                   
                     
                       
                         
                           b 
                           0 
                         
                         + 
                         
                           b 
                           3 
                         
                         + 
                         
                           b 
                           4 
                         
                         + 
                         
                           b 
                           6 
                         
                       
                     
                   
                   
                     
                       
                         
                           b 
                           2 
                         
                         + 
                         
                           b 
                           6 
                         
                       
                     
                   
                   
                     
                       
                         
                           b 
                           4 
                         
                         + 
                         
                           b 
                           6 
                         
                         + 
                         
                           b 
                           7 
                         
                       
                     
                   
                 
                 ] 
               
               = 
               
                 [ 
                 
                   
                     
                       
                         b 
                         
                           1 
                           , 
                           0 
                         
                         ′ 
                       
                     
                   
                   
                     
                       
                         b 
                         
                           1 
                           , 
                           1 
                         
                         ′ 
                       
                     
                   
                   
                     
                       
                         b 
                         
                           1 
                           , 
                           2 
                         
                         ′ 
                       
                     
                   
                   
                     
                       
                         b 
                         
                           1 
                           , 
                           3 
                         
                         ′ 
                       
                     
                   
                   
                     
                       
                         b 
                         
                           h 
                           , 
                           0 
                         
                         ′ 
                       
                     
                   
                   
                     
                       
                         b 
                         
                           h 
                           , 
                           1 
                         
                         ′ 
                       
                     
                   
                   
                     
                       
                         b 
                         
                           h 
                           , 
                           2 
                         
                         ′ 
                       
                     
                   
                   
                     
                       
                         b 
                         
                           h 
                           , 
                           3 
                         
                         ′ 
                       
                     
                   
                 
                 ] 
               
             
           
         
       
     
         [0000]    Mastrivito multiplier GF(2 4 ) product matrix from equation (2) and 1+x+x 4 , the product matrix of low-order element and high-order element are as follow: 
         [0000]    
       
         
           
             
               [ 
               
                 
                   
                     
                       b 
                       
                         1 
                         , 
                         0 
                       
                       ′ 
                     
                   
                   
                     
                       b 
                       
                         1 
                         , 
                         3 
                       
                       ′ 
                     
                   
                   
                     
                       b 
                       
                         1 
                         , 
                         2 
                       
                       ′ 
                     
                   
                   
                     
                       b 
                       
                         1 
                         , 
                         1 
                       
                       ′ 
                     
                   
                 
                 
                   
                     
                       b 
                       
                         1 
                         , 
                         1 
                       
                       ′ 
                     
                   
                   
                     
                       
                         b 
                         
                           1 
                           , 
                           0 
                         
                         ′ 
                       
                       + 
                       
                         b 
                         
                           1 
                           , 
                           3 
                         
                         ′ 
                       
                     
                   
                   
                     
                       
                         b 
                         
                           1 
                           , 
                           2 
                         
                         ′ 
                       
                       + 
                       
                         b 
                         
                           1 
                           , 
                           3 
                         
                         ′ 
                       
                     
                   
                   
                     
                       
                         b 
                         
                           1 
                           , 
                           1 
                         
                         ′ 
                       
                       + 
                       
                         b 
                         
                           1 
                           , 
                           2 
                         
                         ′ 
                       
                     
                   
                 
                 
                   
                     
                       b 
                       
                         1 
                         , 
                         2 
                       
                       ′ 
                     
                   
                   
                     
                       b 
                       
                         1 
                         , 
                         1 
                       
                       ′ 
                     
                   
                   
                     
                       
                         b 
                         
                           1 
                           , 
                           0 
                         
                         ′ 
                       
                       + 
                       
                         b 
                         
                           1 
                           , 
                           3 
                         
                         ′ 
                       
                     
                   
                   
                     
                       
                         b 
                         
                           1 
                           , 
                           2 
                         
                         ′ 
                       
                       + 
                       
                         b 
                         
                           1 
                           , 
                           3 
                         
                         ′ 
                       
                     
                   
                 
                 
                   
                     
                       b 
                       
                         1 
                         , 
                         3 
                       
                       ′ 
                     
                   
                   
                     
                       b 
                       
                         1 
                         , 
                         2 
                       
                       ′ 
                     
                   
                   
                     
                       b 
                       
                         1 
                         , 
                         1 
                       
                       ′ 
                     
                   
                   
                     
                       
                         b 
                         
                           1 
                           , 
                           0 
                         
                         ′ 
                       
                       + 
                       
                         b 
                         
                           1 
                           , 
                           3 
                         
                         ′ 
                       
                     
                   
                 
               
               ] 
             
              
             
                 
             
              
             
               and 
                
               
                 
 
               
               [ 
               
                 
                   
                     
                       b 
                       
                         h 
                         , 
                         0 
                       
                       ′ 
                     
                   
                   
                     
                       b 
                       
                         h 
                         , 
                         3 
                       
                       ′ 
                     
                   
                   
                     
                       b 
                       
                         h 
                         , 
                         2 
                       
                       ′ 
                     
                   
                   
                     
                       b 
                       
                         h 
                         , 
                         1 
                       
                       ′ 
                     
                   
                 
                 
                   
                     
                       b 
                       
                         h 
                         , 
                         1 
                       
                       ′ 
                     
                   
                   
                     
                       
                         b 
                         
                           h 
                           , 
                           0 
                         
                         ′ 
                       
                       + 
                       
                         b 
                         
                           h 
                           , 
                           3 
                         
                         ′ 
                       
                     
                   
                   
                     
                       
                         b 
                         
                           h 
                           , 
                           2 
                         
                         ′ 
                       
                       + 
                       
                         b 
                         
                           h 
                           , 
                           3 
                         
                         ′ 
                       
                     
                   
                   
                     
                       
                         b 
                         
                           h 
                           , 
                           1 
                         
                         ′ 
                       
                       + 
                       
                         b 
                         
                           h 
                           , 
                           2 
                         
                         ′ 
                       
                     
                   
                 
                 
                   
                     
                       b 
                       
                         h 
                         , 
                         2 
                       
                       ′ 
                     
                   
                   
                     
                       b 
                       
                         h 
                         , 
                         1 
                       
                       ′ 
                     
                   
                   
                     
                       
                         b 
                         
                           h 
                           , 
                           0 
                         
                         ′ 
                       
                       + 
                       
                         b 
                         
                           h 
                           , 
                           3 
                         
                         ′ 
                       
                     
                   
                   
                     
                       
                         b 
                         
                           h 
                           , 
                           2 
                         
                         ′ 
                       
                       + 
                       
                         b 
                         
                           h 
                           , 
                           3 
                         
                         ′ 
                       
                     
                   
                 
                 
                   
                     
                       b 
                       
                         h 
                         , 
                         3 
                       
                       ′ 
                     
                   
                   
                     
                       b 
                       
                         h 
                         , 
                         2 
                       
                       ′ 
                     
                   
                   
                     
                       b 
                       
                         h 
                         , 
                         1 
                       
                       ′ 
                     
                   
                   
                     
                       
                         b 
                         
                           h 
                           , 
                           0 
                         
                         ′ 
                       
                       + 
                       
                         b 
                         
                           h 
                           , 
                           3 
                         
                         ′ 
                       
                     
                   
                 
               
               ] 
             
           
         
       
     
         [0000]    This is the product matrix in  FIG. 5  and  FIG. 7 . 
         [0043]    As shown in  FIG. 8 , the operation of mapping into composite field and the product matrix may be integrated into a single matrix conversion, i.e., substituting b′ 1,i  and b′ h,i  into product matrix. Therefore, for low-order element of operand B, the integrated matrix conversion is: 
         [0000]    
       
         
           
               
             
               [ 
               
                 
                   
                     
                       b 
                       2 
                     
                   
                   
                     
                       
                         b 
                         0 
                       
                       + 
                       
                         b 
                         3 
                       
                     
                   
                   
                     
                       
                         b 
                         3 
                       
                       + 
                       
                         b 
                         4 
                       
                       + 
                       
                         b 
                         6 
                       
                     
                   
                   
                     
                       
                         b 
                         1 
                       
                       + 
                       
                         b 
                         2 
                       
                       + 
                       
                         b 
                         5 
                       
                     
                   
                 
                 
                   
                     
                       
                         b 
                         1 
                       
                       + 
                       
                         b 
                         2 
                       
                       + 
                       
                         b 
                         5 
                       
                     
                   
                   
                     
                       
                         b 
                         0 
                       
                       + 
                       
                         b 
                         2 
                       
                       + 
                       
                         b 
                         3 
                       
                     
                   
                   
                     
                       
                         b 
                         0 
                       
                       + 
                       
                         b 
                         4 
                       
                       + 
                       
                         b 
                         6 
                       
                     
                   
                   
                     
                       
                         b 
                         1 
                       
                       + 
                       
                         b 
                         2 
                       
                       + 
                       
                         b 
                         3 
                       
                       + 
                       
                         b 
                         4 
                       
                       + 
                       
                         b 
                         5 
                       
                       + 
                       
                         b 
                         6 
                       
                     
                   
                 
                 
                   
                     
                       
                         b 
                         3 
                       
                       + 
                       
                         b 
                         4 
                       
                       + 
                       
                         b 
                         6 
                       
                     
                   
                   
                     
                       
                         b 
                         1 
                       
                       + 
                       
                         b 
                         2 
                       
                       + 
                       
                         b 
                         5 
                       
                     
                   
                   
                     
                       
                         b 
                         0 
                       
                       + 
                       
                         b 
                         2 
                       
                       + 
                       
                         b 
                         3 
                       
                     
                   
                   
                     
                       
                         b 
                         0 
                       
                       + 
                       
                         b 
                         4 
                       
                       + 
                       
                         b 
                         6 
                       
                     
                   
                 
                 
                   
                     
                       
                         b 
                         0 
                       
                       + 
                       
                         b 
                         3 
                       
                     
                   
                   
                     
                       
                         b 
                         3 
                       
                       + 
                       
                         b 
                         4 
                       
                       + 
                       
                         b 
                         6 
                       
                     
                   
                   
                     
                       
                         b 
                         1 
                       
                       + 
                       
                         b 
                         2 
                       
                       + 
                       
                         b 
                         5 
                       
                     
                   
                   
                     
                       
                         b 
                         0 
                       
                       + 
                       
                         b 
                         2 
                       
                       + 
                       
                         b 
                         3 
                       
                     
                   
                 
               
               ] 
             
           
         
       
     
         [0000]    and for low-order element of operand B, the integrated matrix conversion is 
         [0000]    
       
         
           
               
             
               [ 
               
                   
               
                
               
                 
                   
                     
                       
                         b 
                         2 
                       
                       + 
                       
                         b 
                         5 
                       
                       + 
                       
                         b 
                         6 
                       
                     
                   
                   
                     
                       
                         b 
                         4 
                       
                       + 
                       
                         b 
                         6 
                       
                       + 
                       
                         b 
                         7 
                       
                     
                   
                   
                     
                       
                         b 
                         2 
                       
                       + 
                       
                         b 
                         6 
                       
                     
                   
                   
                     
                       
                         b 
                         0 
                       
                       + 
                       
                         b 
                         3 
                       
                       + 
                       
                         b 
                         4 
                       
                       + 
                       
                         b 
                         6 
                       
                     
                   
                 
                 
                   
                     
                       
                         b 
                         0 
                       
                       + 
                       
                         b 
                         3 
                       
                       + 
                       
                         b 
                         4 
                       
                       + 
                       
                         b 
                         6 
                       
                     
                   
                   
                     
                       
                         b 
                         2 
                       
                       + 
                       
                         b 
                         4 
                       
                       + 
                       
                         b 
                         5 
                       
                       + 
                       
                         b 
                         7 
                       
                     
                   
                   
                     
                       
                         b 
                         2 
                       
                       + 
                       
                         b 
                         4 
                       
                       + 
                       
                         b 
                         7 
                       
                     
                   
                   
                     
                       
                         b 
                         0 
                       
                       + 
                       
                         b 
                         2 
                       
                       + 
                       
                         b 
                         3 
                       
                       + 
                       
                         b 
                         4 
                       
                     
                   
                 
                 
                   
                     
                       
                         b 
                         2 
                       
                       + 
                       
                         b 
                         6 
                       
                     
                   
                   
                     
                       
                         b 
                         0 
                       
                       + 
                       
                         b 
                         3 
                       
                       + 
                       
                         b 
                         4 
                       
                       + 
                       
                         b 
                         6 
                       
                     
                   
                   
                     
                       
                         b 
                         2 
                       
                       + 
                       
                         b 
                         4 
                       
                       + 
                       
                         b 
                         5 
                       
                       + 
                       
                         b 
                         7 
                       
                     
                   
                   
                     
                       
                         b 
                         2 
                       
                       + 
                       
                         b 
                         4 
                       
                       + 
                       
                         b 
                         7 
                       
                     
                   
                 
                 
                   
                     
                       
                         b 
                         4 
                       
                       + 
                       
                         b 
                         6 
                       
                       + 
                       
                         b 
                         7 
                       
                     
                   
                   
                     
                       
                         b 
                         2 
                       
                       + 
                       
                         b 
                         6 
                       
                     
                   
                   
                     
                       
                         b 
                         0 
                       
                       + 
                       
                         b 
                         3 
                       
                       + 
                       
                         b 
                         4 
                       
                       + 
                       
                         b 
                         6 
                       
                     
                   
                   
                     
                       
                         b 
                         2 
                       
                       + 
                       
                         b 
                         4 
                       
                       + 
                       
                         b 
                         5 
                       
                       + 
                       
                         b 
                         7 
                       
                     
                   
                 
               
               ] 
             
              
             
                 
             
           
         
       
     
         [0000]    The two matrixes are the integrated matrix conversion in  FIG. 8  for converting operand B. 
         [0044]    In summary, the disclosed exemplary embodiments of the present invention uses the GF composite field theory to explore the condition when one operand is a low frequency variable by using GF(2 m ) finite field multipliers to realize GF(2 n ) finite field multiplication, n=2m. As the computation unit may be re-used, the present invention provides a semi-sequential GF multiplier architecture and the method for performing the same. The disclosed exemplary embodiments of the present invention, when applied to encryption/decryption system based on GCM-AES as the default encryption/decryption computation, may effectively reduce the GCM-AES hardware cost. 
         [0045]    Although the present invention has been described with reference to the disclosed exemplary embodiments, it will be understood that the invention is not limited to the details described thereof. Various substitutions and modifications have been suggested in the foregoing description, and others will occur to those of ordinary skill in the art. Therefore, all such substitutions and modifications are intended to be embraced within the scope of the invention as defined in the appended claims.