Abstract:
Disclosed is a low-latency method and apparatus of GHASH operation for authenticated encryption Galois Counter Mode (GCM), which simultaneously computes three interim values respectively yielded from the additional authenticated data A, the ciphertext C, and the hash key H defined in the GCM. Then, the output of the GHASH operation may be derived. Therefore, supposing that A has m blocks and C has n blocks, then this invention performs the GHASH operation with max{m,n}+1 steps. The input order for the additional authenticated data A and the ciphertext C may be independent. A disordered sequence for the additional authenticated data A and the ciphertext C may also be accepted by this invention. This allows the applications in GCM be more flexible.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention generally relates to a low-latency method and apparatus of GHASH operation for authenticated encryption Galois Counter Mode (GCM). 
       BACKGROUND OF THE INVENTION 
       [0002]    Galois Counter Mode (GCM) is an operation mode for the authenticated encryption block cipher system. The main feature of GCM is that GCM is fast, and provides confidentiality and integrity. GCM-Advanced Encryption Standard (GCM-AES) is among the most commonly seen, and is often applied to high speed transmission environment. 
         [0003]    The data encryption of GCM is accomplished by a CTR mode, and the authentication is achieved by a universal hash function based on Galois Field (GF). The authenticated encryption has four inputs, namely, secret key K, initialization vector IV, plaintext P, and additional authenticated data (ADD) A. P is divided into 128-bit blocks, expressed as {P 1 , P 2 , . . . , P n *}, and A is divided into 128-bit blocks, expressed as {A 1 , A 2 , . . . , A m *}, where blocks P n * and A m * are shorter than 128 bits. 
         [0004]    The authentication and encryption has two outputs, namely, ciphertext C and authentication tag T. The ciphertext C has the same length with plaintext P, and the length of authentication tag T is denoted as t. The two outputs C and T are obtained via the following procedures: 
         [0000]    
       
         
           
             
               
                 
                   
                     H 
                     = 
                     
                       E 
                        
                       
                         ( 
                         
                           K 
                           , 
                           
                             0 
                             128 
                           
                         
                         ) 
                       
                     
                   
                    
                   
                     
 
                   
                    
                   
                     
                       Y 
                       0 
                     
                     = 
                     
                       { 
                       
                         
                           
                             
                               
                                 
                                   
                                     IV 
                                      
                                     
                                        
                                       
                                         
                                           
                                             0 
                                             31 
                                           
                                            
                                           1 
                                            
                                           
                                               
                                           
                                            
                                           if 
                                            
                                           
                                               
                                           
                                            
                                           
                                             len 
                                              
                                             
                                               ( 
                                               IV 
                                               ) 
                                             
                                           
                                         
                                         = 
                                         96 
                                       
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       GHASH 
                                        
                                       
                                         ( 
                                         
                                           H 
                                           , 
                                           
                                             { 
                                             } 
                                           
                                           , 
                                           IV 
                                         
                                         ) 
                                       
                                     
                                      
                                     
                                         
                                     
                                      
                                     otherwise 
                                   
                                 
                               
                             
                              
                             
                               
 
                             
                              
                             
                               Y 
                               i 
                             
                           
                           = 
                           
                             
                               
                                 incr 
                                  
                                 
                                   ( 
                                   
                                     Y 
                                     
                                       i 
                                       - 
                                       1 
                                     
                                   
                                   ) 
                                 
                               
                                
                               
                                   
                               
                                
                               for 
                                
                               
                                   
                               
                                
                               i 
                             
                             = 
                             1 
                           
                         
                         , 
                         … 
                          
                         
                             
                         
                         , 
                         
                           
                             n 
                              
                             
                               
 
                             
                              
                             
                               C 
                               i 
                             
                           
                           = 
                           
                             
                               
                                 P 
                                 i 
                               
                               ⊕ 
                               
                                 
                                   E 
                                    
                                   
                                     ( 
                                     
                                       K 
                                       , 
                                       
                                         Y 
                                         i 
                                       
                                     
                                     ) 
                                   
                                 
                                  
                                 
                                     
                                 
                                  
                                 for 
                                  
                                 
                                     
                                 
                                  
                                 i 
                               
                             
                             = 
                             1 
                           
                         
                         , 
                         … 
                          
                         
                             
                         
                         , 
                         
                           
                             n 
                             - 
                             
                               1 
                                
                               
                                 
 
                               
                                
                               
                                 C 
                                 n 
                                 * 
                               
                             
                           
                           = 
                           
                             
                               
                                 P 
                                 n 
                                 * 
                               
                               ⊕ 
                               
                                 
                                   
                                     MSB 
                                     u 
                                   
                                    
                                   
                                     ( 
                                     
                                       E 
                                        
                                       
                                         ( 
                                         
                                           K 
                                           , 
                                           
                                             Y 
                                             n 
                                           
                                         
                                         ) 
                                       
                                     
                                     ) 
                                   
                                 
                                  
                                 
                                   
 
                                 
                                  
                                 T 
                               
                             
                             = 
                             
                               
                                 MSB 
                                 t 
                               
                                
                               
                                 ( 
                                 
                                   
                                     GHASH 
                                      
                                     
                                       ( 
                                       
                                         H 
                                         , 
                                         A 
                                         , 
                                         C 
                                       
                                       ) 
                                     
                                   
                                   ⊕ 
                                   
                                     E 
                                      
                                     
                                       ( 
                                       
                                         K 
                                         , 
                                         
                                           Y 
                                           0 
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where E(K,X) denotes the block cipher encryption of the value X with the key K. MSB t (S) returns the bit string containing only the leftmost t bits of S. { } represents the empty bit string, whose length is zero. 0 n  denotes an n-bit zero sequence. The function incr( ) represents treating the least significant 32 bits on the right as a non-negative integer, adding 1, and then performing the modulo operation mod 2 32 . In other words, incr(F∥I)=F∥(I+1)mod 2 32 . 
         [0005]    GHASH function is an operation of GCM. The function has three inputs, and generates a 128-bit hash value. The three inputs are A, C and H, where H is the value obtained by using the secret key K to encrypt the all-zero blocks. The following equation describes the output X i  in i-th step of GHASH function. 
         [0000]    
       
         
           
             
               
                 
                   
                     X 
                     i 
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               0 
                                
                               
                                   
                               
                                
                               for 
                                
                               
                                   
                               
                                
                               i 
                             
                             = 
                             0 
                           
                         
                       
                       
                         
                           
                             
                               
                                 
                                   
                                     ( 
                                     
                                       
                                         X 
                                         
                                           i 
                                           - 
                                           1 
                                         
                                       
                                       ⊕ 
                                       
                                         A 
                                         i 
                                       
                                     
                                     ) 
                                   
                                   · 
                                   H 
                                 
                                  
                                 
                                     
                                 
                                  
                                 for 
                                  
                                 
                                     
                                 
                                  
                                 i 
                               
                               = 
                               1 
                             
                             , 
                             … 
                              
                             
                                 
                             
                             , 
                             
                               m 
                               - 
                               1 
                             
                           
                         
                       
                       
                         
                           
                             ( 
                             
                               
                                 
                                   X 
                                   
                                     m 
                                     - 
                                     1 
                                   
                                 
                                 ⊕ 
                                 
                                   
                                     
                                       ( 
                                       
                                         
                                           A 
                                           m 
                                           * 
                                         
                                          
                                         
                                            
                                           
                                             0 
                                             
                                               128 
                                               - 
                                               v 
                                             
                                           
                                           ) 
                                         
                                       
                                       ) 
                                     
                                     · 
                                     H 
                                   
                                    
                                   
                                       
                                   
                                    
                                   for 
                                    
                                   
                                       
                                   
                                    
                                   i 
                                 
                               
                               = 
                               m 
                             
                           
                         
                       
                       
                         
                           
                             
                               
                                 
                                   
                                     ( 
                                     
                                       
                                         X 
                                         
                                           i 
                                           - 
                                           1 
                                         
                                       
                                       ⊕ 
                                       
                                         C 
                                         
                                           i 
                                           - 
                                           m 
                                         
                                       
                                     
                                     ) 
                                   
                                   · 
                                   H 
                                 
                                  
                                 
                                     
                                 
                                  
                                 for 
                                  
                                 
                                     
                                 
                                  
                                 i 
                               
                               = 
                               
                                 m 
                                 + 
                                 1 
                               
                             
                             , 
                             … 
                              
                             
                                 
                             
                             , 
                             
                               m 
                               + 
                               n 
                               - 
                               1 
                             
                           
                         
                       
                       
                         
                           
                             ( 
                             
                               
                                 
                                   X 
                                   
                                     m 
                                     + 
                                     n 
                                     - 
                                     1 
                                   
                                 
                                 ⊕ 
                                 
                                   
                                     
                                       ( 
                                       
                                         
                                           C 
                                           n 
                                           * 
                                         
                                          
                                         
                                            
                                           
                                             0 
                                             
                                               128 
                                               - 
                                               u 
                                             
                                           
                                           ) 
                                         
                                       
                                       ) 
                                     
                                     · 
                                     H 
                                   
                                    
                                   
                                       
                                   
                                    
                                   for 
                                    
                                   
                                       
                                   
                                    
                                   i 
                                 
                               
                               = 
                               
                                 m 
                                 + 
                                 n 
                               
                             
                           
                         
                       
                       
                         
                           
                             ( 
                             
                               
                                 
                                   X 
                                   
                                     m 
                                     + 
                                     n 
                                   
                                 
                                 ⊕ 
                                 
                                   
                                     
                                       ( 
                                       
                                         
                                           len 
                                            
                                           
                                             ( 
                                             A 
                                             ) 
                                           
                                         
                                          
                                         
                                            
                                           
                                             len 
                                              
                                             
                                               ( 
                                               C 
                                               ) 
                                             
                                           
                                           ) 
                                         
                                       
                                       ) 
                                     
                                     · 
                                     H 
                                   
                                    
                                   
                                       
                                   
                                    
                                   for 
                                    
                                   
                                       
                                   
                                    
                                   i 
                                 
                               
                               = 
                               
                                 m 
                                 + 
                                 n 
                                 + 
                                 1 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0006]    In equation (2), v is the bit length of block A m *, ⊕ is the addition over GF(2 128 ), and the multiplication is defined in GF(2 128 ). A∥B represents the concatenation of two bit strings A and B. 
         [0007]    In equation (2), GHASH function may be realized with the hardware architecture of  FIG. 1 . In  FIG. 1 , the core of the GHASH hardware architecture is a 128-bit parallel GF(2 128 ) multiplier  101 . The initial value of the hash value in register X is set to 0. In the first m clock cycles, the m blocks A 1 , A 2 , . . . , A m * are substituted into the right part of the equation one by one. Then, in the next n clock cycles, the n 128-bit blocks C 1 , C 2 , . . . , C n−1 , C n  of ciphertext C are substituted into the right part of the equation on the third line of (2). In the last cycle clock, len(A)∥len(C) is substituted into the right part of the equation of the last line of (2). By using the hardware architecture, m+n+1 clock cycles are required to compute the hash value. 
         [0008]    As shown in  FIG. 1 , the temporary result X i  will be XOR-ed with the next input to AC register, and the result is feedback to the AC register to generate the next operand of GF(2 128 ) multiplier  101 . The other operand of GF(2 128 ) multiplier  101  is H, which is stored in the H register. 
         [0009]    In May 2005, D. A. McGrew et. al. disclosed the operation mode of GCM, in which a 64-bit or 128-bit block encryption is used simultaneously to provide authentication and encryption. 
         [0010]    The papers by B. Young et. al. in June 2005 and by A. Satoh in May 2006 also disclosed a high-speed architecture to realize GCM-AES. Both architectures require m+n+1 clock cycles to execute the GHASH operation in GCM. Wherein n is the length of ciphertext and m is the length of authenticated data. The m+n+1 clock cycles may result in the latency of hardware. 
         [0011]    U.S. Patent Publication No. 2006/0126835 disclosed a high-speed GCM-AES block cipher apparatus and method. The GCM-AES block cipher apparatus is realized with four modules, as shown in  FIG. 2 , namely, key expansion module  201 , 8-round CTR-AES block cipher module  203 , 3-round CTR-AES block cipher module  205 , and GF(2 128 ) multiplication module  207 . The data to be encrypted is from 32/128-bit transformer  210 . The encrypted data is inputted to 128/32-bit transformer  220 . 
         [0012]    The block encryption apparatus may be operated in 125 MHz low clock frequency, and provide a 2-Gbps link security function of an optical line termination (OTL) and an optical network unit (ONU) of an Ethernet passive optical network (EPON). 
       SUMMARY OF THE INVENTION 
       [0013]    The exemplary embodiments of the present invention may provide a low-latency method and apparatus of GHASH operation for authenticated encryption GCM. The present invention may compute the authenticated data, ciphertext and H n+1  of GCM, and provide parallel execution of GHASH operation of GCM. The input order of authenticated data and ciphertext may be independent so that the application of GCM is more flexible. The present invention may execute GHASH operation of GCM in parallel, and require only max{m,n}+1 steps. If the ciphertext and H are invariants, only m+1 steps will be required. 
         [0014]    In an exemplary embodiment, the present disclosure is directed to a low-latency method of GHASH operation for authenticated encryption GCM. The first step of the exemplary method may expand, according to the authenticated data, ciphertext and the HASH key H, the final output of the GHASH function as a combination of three interim values, X A , X C , and H n+1 , where X A  is the temporary value related to authenticated data, and X C  is the temporary value related to ciphertext. Then, the computation of X A , X C , and H n+1  may be parallelized. 
         [0015]    In another exemplary embodiment, the present disclosure is directed to a low-latency apparatus of GHASH operation for authenticated encryption GCM. The exemplary apparatus may include three modules to compute X A , X C , and H n+1 . The hardware architecture of the exemplary apparatus may be realized with three GF(2 k ) multipliers, three registers, and a GF(2 k ) addition. The addition may be realized with either XOR gate or software module. 
         [0016]    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 
         [0017]      FIG. 1  shows a schematic view of an exemplary conventional hardware architecture for GHASH operation. 
           [0018]      FIG. 2  shows a schematic view of an exemplary conventional low-latency GCM-AES block encryption apparatus. 
           [0019]      FIG. 3  shows an exemplary flowchart of a low-latency method of GHASG operation for authenticated encryption GCM, consistent with certain disclosed embodiments. 
           [0020]      FIG. 4  shows an exemplary architecture of a low-latency apparatus of GHASH operation for authenticated encryption GCM, consistent with certain disclosed embodiments. 
           [0021]      FIG. 5  shows a working example to use a Mastorvito&#39;s standard multiplier to realize the exemplary embodiment of  FIG. 4 . 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0022]    GHASH function has three inputs, which are the additional authenticated data A, ciphertext C and HASH key H defined in GCM specification. Without the loss of generality, the following exemplary description may use a 128-bit block as a block encryption, the length len(A) of authenticated data A is m, and the length len(C) of ciphertext C is n. In other words, the GCM may use 128-bit block encryption to provide both authentication and encryption, and the authenticated data A and ciphertext C may be divided into m and n 128-bit blocks, respectively. 
         [0023]    When using the conventional equation (2) to execute the GHASH operation of GCM, m+n+1 steps may be required to obtain the result of GHASH function. 
         [0024]      FIG. 3  shows an exemplary flowchart of a low-latency method of GHASH operation for authenticated encryption GCM, consistent with certain disclosed embodiments. Referring to the exemplary flowchart, the final output X m+n+1  of GHASH function may be expanded into a combination of three interim values, X A , X C , and H n+1 , as shown in step  301 . 
         [0025]    In step  301 , X A  is a temporary value related to authenticated data A, and X C  is a temporary value related to ciphertext C. X A  is the temporary value generated by summing the product of each of the m blocks and the decreasing sequence of H, respectively, where the highest order of H is m+1. X C  is the temporary value generated by summing the product of each of the m blocks and the decreasing sequence of H, respectively, where the highest order of H is n+1. 
         [0026]    The flowing expanded equation may describe the (m+n+1) th  output X m+n+1  of GHASH function as a combination of the three interim values, X A , X C , and H n+1 . 
         [0000]    
       
         
           
             
               
                 
                   
                     X 
                     
                       m 
                       + 
                       n 
                       + 
                       1 
                     
                   
                   = 
                     
                    
                   
                     
                       
                         A 
                         1 
                       
                        
                       
                         H 
                         
                           m 
                           + 
                           n 
                           + 
                           2 
                         
                       
                     
                     ⊕ 
                     
                       
                         A 
                         2 
                       
                        
                       
                         H 
                         
                           m 
                           + 
                           n 
                           - 
                           1 
                         
                       
                     
                     ⊕ 
                     … 
                     ⊕ 
                     
                       ( 
                       
                         
                           
                             A 
                             m 
                             * 
                           
                            
                           
                              
                             
                               S 
                               
                                 k 
                                 - 
                                 v 
                               
                             
                             ) 
                           
                            
                           
                             H 
                             
                               n 
                               + 
                               2 
                             
                           
                         
                         ⊕ 
                       
                     
                   
                 
               
             
             
               
                 
                     
                    
                   
                     
                       
                         C 
                         1 
                       
                        
                       
                         H 
                         
                           n 
                           + 
                           1 
                         
                       
                     
                     ⊕ 
                     
                       
                         C 
                         2 
                       
                        
                       
                         H 
                         n 
                       
                     
                     ⊕ 
                     … 
                     ⊕ 
                     
                       ( 
                       
                         
                           
                             C 
                             n 
                             * 
                           
                            
                           
                              
                             
                               S 
                               
                                 k 
                                 - 
                                 u 
                               
                             
                             ) 
                           
                            
                           
                             H 
                             2 
                           
                         
                         ⊕ 
                         
                           ( 
                           
                             
                               
                                 len 
                                  
                                 
                                   ( 
                                   A 
                                   ) 
                                 
                               
                                
                               
                                  
                                 
                                   len 
                                    
                                   
                                     ( 
                                     C 
                                     ) 
                                   
                                 
                                 ) 
                               
                                
                               H 
                             
                             , 
                           
                         
                       
                     
                   
                 
               
             
             
               
                 
                   
                     = 
                       
                      
                     
                       
                         
                           
                             
                               
                                 ( 
                                 
                                   
                                     
                                       A 
                                       1 
                                     
                                      
                                     
                                       H 
                                       
                                         m 
                                         + 
                                         1 
                                       
                                     
                                   
                                   ⊕ 
                                   
                                     
                                       A 
                                       2 
                                     
                                      
                                     
                                       H 
                                       m 
                                     
                                   
                                   ⊕ 
                                   … 
                                   ⊕ 
                                   
                                     ( 
                                     
                                       
                                         A 
                                         m 
                                         * 
                                       
                                        
                                       
                                          
                                         
                                           S 
                                           
                                             k 
                                             - 
                                             v 
                                           
                                         
                                       
                                     
                                   
                                 
                                 ) 
                               
                               ) 
                             
                              
                           
                           
                             X 
                             A 
                           
                         
                          
                         
                           H 
                           
                             n 
                             + 
                             1 
                           
                         
                       
                       ⊕ 
                     
                   
                   , 
                 
               
             
             
               
                 
                     
                    
                   
                     
                       
                         
                           C 
                           1 
                         
                          
                         
                           H 
                           
                             n 
                             + 
                             1 
                           
                         
                       
                       ⊕ 
                       
                         
                           C 
                           2 
                         
                          
                         
                           H 
                           n 
                         
                       
                       ⊕ 
                       … 
                       ⊕ 
                       
                         ( 
                         
                           
                             
                               C 
                               n 
                               * 
                             
                              
                             
                                
                               
                                 S 
                                 
                                   k 
                                   - 
                                   u 
                                 
                               
                               ) 
                             
                              
                             
                               H 
                               2 
                             
                           
                           ⊕ 
                           
                             ( 
                             
                               
                                 len 
                                  
                                 
                                   ( 
                                   A 
                                   ) 
                                 
                               
                                
                               
                                  
                                 
                                   len 
                                    
                                   
                                     ( 
                                     C 
                                     ) 
                                   
                                 
                                 ) 
                               
                                
                               H 
                             
                           
                         
                       
                     
                     
                        
                       
                         X 
                         C 
                       
                     
                   
                 
               
             
           
         
       
     
         [0000]    where S l  is a binary string of l bits, v is the length of block A m *, u is the length of C n *, k is the length of key K, and u and v are both less than or equal to k. 
         [0027]    As shown in step  302 , X A , X C , and H n+1  may be computed in parallel. Step  302  includes max{m,n} sub-steps. Each sub-step has three inputs, a, b, and c. The computation of each sub-step is (a⊕b)·c, which requires one clock cycle. Therefore, it takes m clock cycles to compute X A . On the other hand, it takes n clock cycles to compute X C  and H n+1 . Therefore, it only requires max{m,n} to compute X A , X C , and H n+1  in parallel. 
         [0028]    After X A , X C , and H n+1  are computed, the HASH value of GHASH operation based on X A , X C , and H n+1  may be computed, that is, to compute X A ·H n+1 ⊕X C  as shown in step  303 . This step requires one clock cycle. Therefore, the GHASH operation of GCM of the exemplary embodiment according to the present invention requires max{m,n}+1 clock cycles. 
         [0029]      FIG. 4  shows an exemplary architecture of a low-latency apparatus of GHASH operation for authenticated encryption GCM, consistent with certain disclosed embodiments. The exemplary architecture of the low-latency apparatus may include three modules for computing the temporary value X A  related to authenticated data A, the temporary value X C  related to ciphertext C, and H n+1 . As shown in  FIG. 4 , the exemplary architecture of the apparatus may be realized with three GF(2 k ) multipliers  401 - 403 , three registers  411 - 413 , and a GF(2 k ) addition ⊕. Registers  411 - 413  may be used for storing the temporary values of X A , X C , and H n+1 , respectively. The initial values of register  411 ,  413  are the addition unit element 0 of the GF(2 k ), and the initial value of register  412  is the multiplication unit element 1 of the GF(2 k ). GF(2 k ) addition ⊕ may be realized with XOR gates or software modules. 
         [0030]    In the preparation process, three GF(2 k ) multipliers  401 - 403  may compute the values of X A , X C , and H n+1 , respectively, and then input the values to register  411 - 413  respectively. When computing X C  during the preparation process, the exemplary apparatus may use a control signal  441  to select a certain C i  or len(A)∥len(C) through a multiplexer  431 . The GF(2 k ) addition ⊕ may be performed on the temporary result of X C  stored in register  411  and the output of multiplexer  431 , and the result is feedback to GF(2 k ) multiplier  401  to generate the next operand for GF(2 k ) multiplier  401 . The other operand for GF(2 k ) multiplier  401  is H. Similarly, in computing X A , the GF(2 k ) addition ⊕ may be performed on the temporary result of X A  stored in register  413  and some A i , and the result is feedback to GF(2 k ) multiplier  403  to generate the next operand for GF(2 k ) multiplier  403 . The other operand for GF(2 k ) multiplier  403  is H. In computing H n+1 , the temporary result stored in register  412  is feedback to GF(2 k ) multiplier  402  to generate the next operand for GF(2 k ) multiplier  402 . The other operand for GF(2 k ) multiplier  402  is H. 
         [0031]    In the preparation process, it can be shown that authenticated data A i  and ciphertext C i  may be input separately and independently. Even the disordered sequence, such as C 1 C 2 A 1 C 3 C 4 C 5 A 2 A 3 A 4  . . . is acceptable. 
         [0032]    After X A , X C , and H n+1  are computed, in the output process, the exemplary apparatus may use one of three GF(2 k ) multiplier  401 - 403  and the GF(2 k ) addition ⊕ to execute the computation of X A ·H n+1 ⊕X C . 
         [0033]    Therefore, the computation of X C  may be realized through the use of a multiplexer, a GF(2 k ) multiplier, and a GF(2 k ) addition ⊕. The computation of X A  may be realized through the use of a GF(2 k ) multiplier, and a GF(2 k ) addition ⊕. The preferred computation of H n+1  may be realized through the use of a GF(2 k ) multiplexer. A GF(2 k ) multiplier may be realized by the base multiplier defined in GF(2 k ) Mastorvito&#39;s standard. 
         [0034]      FIG. 5  shows a working example to use a Mastorvito&#39;s standard multiplier to realize the exemplary embodiment of  FIG. 4 . The base multiplier defined in GF(2 k ) Mastorvito&#39;s standard is a matrix-vector (MV) multiplier. Assuming that a(x), b(x), c(x) are defined in GF(2 m ), and are polynomials constructed by generator polynomial g(x). Let r(x) is the product of a(x) and b(x). Then, the polynomial representation is as follows: 
         [0000]        r   0   +r   1   x+ . . . +r   m−1   x   m−1 =( a   0 + . . . +a m−1   x   m−1 )( b   0 + . . . +b m−1   x   m−1 )mod  g ( x )  (3) 
         [0035]    According to the coefficients in equation (3), the Mastorvito&#39;s multiplier generates equation R=Z a B. 
         [0000]    
       
         
           
             
               
                 
                   R 
                   = 
                   
                     
                       ( 
                       
                         
                           
                             
                               r 
                               0 
                             
                           
                         
                         
                           
                             
                               r 
                               1 
                             
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               r 
                               
                                 m 
                                 - 
                                 1 
                               
                             
                           
                         
                       
                       ) 
                     
                     = 
                     
                       
                         
                           Z 
                           a 
                         
                          
                         B 
                       
                       = 
                       
                         
                           ( 
                           
                             
                               
                                 
                                   z 
                                   
                                     0 
                                     , 
                                     0 
                                   
                                 
                               
                               
                                 … 
                               
                               
                                 
                                   z 
                                   
                                     0 
                                     , 
                                     
                                       m 
                                       - 
                                       1 
                                     
                                   
                                 
                               
                             
                             
                               
                                 ⋮ 
                               
                               
                                 ⋱ 
                               
                               
                                 ⋮ 
                               
                             
                             
                               
                                 
                                   z 
                                   
                                     
                                       m 
                                       - 
                                       1 
                                     
                                     , 
                                     0 
                                   
                                 
                               
                               
                                 … 
                               
                               
                                 
                                   z 
                                   
                                     
                                       m 
                                       - 
                                       1 
                                     
                                     , 
                                     
                                       m 
                                       - 
                                       1 
                                     
                                   
                                 
                               
                             
                           
                           ) 
                         
                          
                         
                           ( 
                           
                             
                               
                                 
                                   b 
                                   0 
                                 
                               
                             
                             
                               
                                 
                                   b 
                                   1 
                                 
                               
                             
                             
                               
                                 ⋮ 
                               
                             
                             
                               
                                 
                                   b 
                                   
                                     m 
                                     - 
                                     1 
                                   
                                 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where Z a  is a m×m matrix derived by a(x) and g(x), called Z-matrix, which is expressed as follows: 
         [0000]    
       
         
           
             
               z 
               
                 i 
                 , 
                 j 
               
             
             = 
             
               { 
               
                 
                   
                     
                       a 
                       i 
                     
                   
                   
                     
                       j 
                       = 
                       0 
                     
                   
                   
                     
                       
                         i 
                         = 
                         0 
                       
                       , 
                       … 
                        
                       
                           
                       
                       , 
                       
                         m 
                         - 
                         1 
                       
                     
                   
                 
                 
                   
                     
                       
                         
                           u 
                            
                           
                             ( 
                             
                               i 
                               - 
                               j 
                             
                             ) 
                           
                         
                          
                         
                           a 
                           
                             i 
                             - 
                             j 
                           
                         
                       
                       + 
                       
                         
                           ∑ 
                           
                             k 
                             = 
                             0 
                           
                           
                             j 
                             - 
                             1 
                           
                         
                          
                         
                           
                             q 
                             
                               
                                 j 
                                 - 
                                 1 
                                 - 
                                 k 
                               
                               , 
                               i 
                             
                           
                            
                           
                             a 
                             
                               m 
                               - 
                               1 
                               - 
                               k 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         j 
                         = 
                         1 
                       
                       , 
                       … 
                        
                       
                           
                       
                       , 
                       
                         m 
                         - 
                         1 
                       
                     
                   
                   
                     
                       
                         i 
                         = 
                         0 
                       
                       , 
                       … 
                        
                       
                           
                       
                       , 
                       
                         m 
                         - 
                         1 
                       
                     
                   
                 
               
             
           
         
       
     
         [0000]    in which u(x) is step function, defined as: 
         [0000]    
       
         
           
             
               u 
                
               
                 ( 
                 x 
                 ) 
               
             
             = 
             
               { 
               
                 
                   
                     1 
                   
                   
                     
                       x 
                       ≥ 
                       0 
                     
                   
                 
                 
                   
                     0 
                   
                   
                     
                       x 
                       &lt; 
                       0 
                     
                   
                 
               
             
           
         
       
     
         [0000]    and q i,j  is the elements of the matrix in the following equation: 
         [0000]    
       
         
           
             
               [ 
               
                 
                   
                     
                       x 
                       m 
                     
                   
                 
                 
                   
                     
                       x 
                       
                         m 
                         + 
                         1 
                       
                     
                   
                 
                 
                   
                     ⋮ 
                   
                 
                 
                   
                     
                       x 
                       
                         
                           2 
                            
                           m 
                         
                         - 
                         2 
                       
                     
                   
                 
               
               ] 
             
             ≡ 
             
               
                 
                   [ 
                   
                     
                       
                         
                           q 
                           
                             0 
                             , 
                             0 
                           
                         
                       
                       
                         
                           q 
                           
                             0 
                             , 
                             1 
                           
                         
                       
                       
                         … 
                       
                       
                         
                           q 
                           
                             0 
                             , 
                             
                               m 
                               - 
                               1 
                             
                           
                         
                       
                     
                     
                       
                         
                           q 
                           
                             1 
                             , 
                             0 
                           
                         
                       
                       
                         
                           q 
                           
                             1 
                             , 
                             1 
                           
                         
                       
                       
                         … 
                       
                       
                         
                           q 
                           
                             1 
                             , 
                             
                               m 
                               - 
                               1 
                             
                           
                         
                       
                     
                     
                       
                         ⋮ 
                       
                       
                         ⋮ 
                       
                       
                         ⋱ 
                       
                       
                         ⋮ 
                       
                     
                     
                       
                         
                           q 
                           
                             
                               m 
                               - 
                               1 
                             
                             , 
                             0 
                           
                         
                       
                       
                         
                           q 
                           
                             
                               m 
                               - 
                               1 
                             
                             , 
                             1 
                           
                         
                       
                       
                         … 
                       
                       
                         
                           q 
                           
                             
                               m 
                               - 
                               1 
                             
                             , 
                             
                               m 
                               - 
                               1 
                             
                           
                         
                       
                     
                   
                   ] 
                 
                  
                 
                   [ 
                   
                     
                       
                         1 
                       
                     
                     
                       
                         x 
                       
                     
                     
                       
                         ⋮ 
                       
                     
                     
                       
                         
                           x 
                           
                             m 
                             - 
                             1 
                           
                         
                       
                     
                   
                   ] 
                 
               
                
               
                   
               
                
               mod 
                
               
                   
               
                
               
                 g 
                  
                 
                   ( 
                   x 
                   ) 
                 
               
             
           
         
       
     
         [0036]    According to the base multiplier of Mastorvito&#39;s standard, the working example in  FIG. 5  requires max{m,n}+2 clock cycles to execute the GHASH operation in GCM. As shown in  FIG. 5 , the working example only requires a Z-matrix circuit  510  and three MV multipliers  501 - 503 , and does not require three pairs of hardware circuits, where each pair of hardware circuit includes a Z-matrix circuit and an MV multiplier. In this exemplary hardware, three MV multipliers  501 - 503  may share a Z-matrix circuit  510  hardware resource. Z-matrix circuit  510  may be used to compute the Z-matrix  510   a , described as follows. 
         [0037]    In  FIG. 5 , when HASH key H is loaded into Z-matrix circuit  510 , Z-matrix circuit  510  may compute matrix Z H , and let three MV multipliers  501 - 503  to compute X A , X C , and H n+1  in max{m,n} clock cycles. When computing X A ·H n+1 ⊕X C , control signal  441  may be used to select a certain C i  or len(A)∥len(C). In the next clock cycle, i.e., the (max{m,n}+1)-th clock cycle, when authenticated data A and ciphertext C are both completely input, control signal  542  may be used to load H n+1  into Z-matrix circuit  510 , and then matrix Z H     n+1    is computed. In the last clock cycle, i.e., the (max{m,n}+2)-th cycle, the result of X A ·H n+1 ⊕X C  is computed. 
         [0038]    In the exemplary architecture according to the present invention, it is obvious that the input order of authenticated data and the ciphertext may be independent. This allows more flexibility in the GCM application. For example, in different transmissions or sessions, the change of authenticated data only requires the re-computation of X A . Similarly, if the authenticated data remains the same, and the ciphertext is different, only X C  and H n+1  need to be re-computed. Furthermore, the present invention may accept disordered sequences. 
         [0039]    From the working example realized by base multiplier of Mastorvito&#39;s standard, it is shown that the present invention may allow the three GF(2 k ) multipliers to share hardware resource to reduce the hardware cost. When compared with the conventional technique that uses three GF(2 k ) multipliers and requires the authenticated data A i  and ciphertext C i  to be inputted in order, the exemplary embodiments according to the present invention may save about 20% of resources, and therefore speed up the execution of GHASH operation of GCM. 
         [0040]    In summary, according to the present invention, if additional authenticated data is m blocks and the ciphertext is n block, the exemplary embodiments according to the present invention only requires max{m,n}+1 steps to execute the GHASH operation in GCM. In addition, the input order of additional authenticated data and ciphertext may be independent in the present invention, which may allow more flexibility in GCM application. 
         [0041]    The exemplary embodiments according to the present invention may be applicable to the application areas using GCM encryption mode, such as MACSec, EPON, storage devices, or IPSec. 
         [0042]    Although the present invention has been described with reference to the 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.