Abstract:
A modular multiplier and an encryption/decryption processor using the modular multiplier, which is mainly applied in a chip to have the needs of small size and faster operation. In the modular multiplier, Montgomery algorithm is realized, the operand is divided into the fixed-length data, and the desired result is provided by the iterative calculation. In the algorithm, two recursive structures include the multiplication operation first and the addition operation later. By the multiplexer to data path&#39;s choice, the desired result of modular multiplication can be calculated by a single data path at different time points.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    This invention relates to a modular multiplier operation structure, particularly to a modular multiplier realized by the high-radix Montgomery operation algorithm.  
           [0003]    2. Description of the Related Art  
           [0004]    Due to the requirements of data transfer in networking and digitization, the cryptography for the data security mechanism has spurred efforts to the design. The basic principle of the cryptography is that a plaintext is converted into a ciphertext through a encryption and a encryption key chosen by a user. When a receiver receives the ciphertext, a decryption with respect to the encryption and a respective decryption key of the encryption key can recover the plaintext. Because the data in transfer or storage is in the ciphertext, the data security is achieved since an adversary has no the decryption key to get the transfer data.  
           [0005]    The security of a cryptosystems is built on the basis of the potential of extracting the keys. The security of the cryptosystem is indicated by the potential of extracting the keys from the existing data. Current cryptosystem is divided into two types, private key cryptosystem and public key cryptosystem. In private key cryptosystem, encryption and decryption keys are the same, for example, the widely used system is the DES system. The same encryption and decryption keys mean that the keys must be stored in an absolutely secure transmission path to ensure the transfer security. This is the main drawback in private key crytosystem. There is no such a problem in public key cryptosystem. In public key cryptosystem, encryption and decryption keys are different. In a pair of encryption and decryption keys, encryption key is a public key. When the plaintext is encrypted by encryption key into the ciphertext, only the respective decryption key of encryption key can recover it. Also, such a system, e.g. Rivest, Shamir, Adleman (RSA), must offer the guaranty that the respective decryption can not or hardly be extracted without telling it. Accordingly, public key cryptosystem becomes increasingly and leads the world trend in the cryptosystem because besides it has not the key transfer and management problem, the descryption key in public key cryptosystem offers the function of certifying a digital signature.  
           [0006]    RSA cryptosystem uses the modular exponentiation operation to generate the encryption/decryption function. The encryption/decryption is expressed as follows: 
             C=M   E (mod  N )  (1) 
             M=C   D (mod  N )  (2) 
           [0007]    where N=PQ and ED 1 mod(P−1) (Q−1), M is plaintext; C is ciphertext; E is encryption key; and D is decryption key.  
           [0008]    N is the product of two prime numbers P and Q. Equation (1) represents the encryption action. The modular multiplication operation (E, N) is used to convert the plaintext M into the ciphertext C. Equation (2) represents the decryption action. The modular multiplication operation (D, N) is used to recover the plaintext M from the ciphertext C. In RSA cryptosystem, the modular exponentiation operation is complex and takes much time in computation. Hence, the modular multiplier is commonly used to realize the modular exponentiation operation, especially to the utilization of Montgomery algorithm. For example, the Montgomery algorithm is used in the basic operation of AB(mod N) as the following algorithm 1: 
           [0009]    &lt;Algorithm 1&gt; 
           [0010]    R 0 =0;  
           [0011]    For i=0 to n−1 do 
             q   i   =R   i   +a   i   B  (mod 2)  (3) 
             R   i+1 =( R   i   +a   i   B+q   i   N )/2  (4) 
           [0012]    end  
           [0013]    where  
         A   =         a     n   -   1            2     n   -   1         +       a     n   -   2            2     n   -   2         +   …   +     a   0         ;     B   =         b     n   -   1            2     n   -   1         +       b     n   -   2            2     n   -   2         +   …   +     b   0         ;                         
 
           [0014]    and a i , b i , q i ε {0, 1}.  
           [0015]    The foregoing algorithm performs a n-time loop with an n-bit adder and a 1×n multiplier. The performed result for every loop is respectively multiplied by 2 0 , 2 1 , 2 2 , . . . , 2 n−1  and then summed total. The final total summed is expressed as follows: 
           2 n   R   n   =AB (mod  N )  (5) 
           [0016]    According to equation (5), R n  is expressed as follows: 
             R   n =2 −n   AB (mod  N )  (6) 
           [0017]    Therefore, the modular exponentiation operation of equation (1) or (2) is performed by Montgomery algorithm according to the following pre-operation, exponentiation operation, and post-operation: 
           MGM( M,  2 2n )=2 n   M (mod  N )  (7) 
           MGM(2 n   M   a ,2 n   M   b )=2 n   M   a+b (mod  N )  (8) 
           MGM(2 n   M   E ,1)= M   E (mod  N )  (9) 
           [0018]    where MGM(,) represents the operand R n  executed by Montgomery algorithm, i.e., the result from equation (6) R n =2 −n AB (mod N).  
           [0019]    Because the need of performing n-time loop in algorithm 1 takes time in the computation, the chip area in the high radix(2 k ) Montgomery algorithm is adopted to efficiently increase the operation speed. The high radix Montgomery algorithm reduces the modular multiplication from one to n/k by dividing the operand A into ┐n/k┌ groups, each group having k bits, when decoding or encoding data, thereby achieving the purpose of increasing the speed. The algorithm is expressed as follows:  
           [0020]    &lt;Algorithm 2&gt; 
           [0021]    R 0 =0;  
           [0022]    For i=0 to ┐n/k┌−1 do 
             q   i =( R   i   +a   i   B )* N   1 (mod 2 k )  (10) 
             R   i+1 =( R   i   +a   i   B+q   i   N )/2 k   (11) 
           [0023]    end  
           [0024]    where N 1  is satisfied with N*N 1 ≡−1 (mod 2 k ), A=a ┐n/k┌−1  (2 k ) ┐n/k┌−  
         A   =           a       ⌈     n   /   k     ⌉     -   1            (     2   k     )           ⌈     n   /   k     ⌉     -   1       +         a       ⌈     n   /   k     ⌉     -   2            (     2   k     )           ⌈     n   /   k     ⌉     -   2       +   …   +     a   0         ;                         
 
           [0025]    and a i , q i ε{0, 1, 2, . . . 2 k−1 }, for k &gt;0.  
           [0026]    Although the loop in algorithm 2 is reduced, a further reduction for the loop is subjected to algorithm 3, which shifts the operand B by k bits and changes the parameter N into N 2  in order to eliminate the multiplication and addition operations in equation (10). The expression is:  
           [0027]    &lt;Algorithm 3&gt; 
           [0028]    R 0 =0;  
           [0029]    For i=0 to ┐n/k┌ do 
             q   i   =R   i (mod 2 k )  (12) 
             R   i+1 =( R   i   +q   i   *N   2 )/2 k   +a   i   B   (13) 
           [0030]    end  
           [0031]    where N 2 =mN≡−1 (mod 2 k ).  
           [0032]    Likewise, the result for every loop is respectively multiplied by 2 0 , 2 1 , 2 2 , . . . , 2 n−1  and then summed total. The final total is expressed as follows: 
           2 n+k   R   ┐n/k┌+1   A* 2 k   *B+Q*N   2   (14) 
           [0033]    Accordingly, the relationship derived from equation (5) is satisfied as a result of R (n/k)+1  and that is: 
           2 n   R   ┐n/k┌+1 AB(mod  N )  (15) 
           [0034]    The best advantage in algorithm 3 is the same operation structure as mentioned above, i.e., only a multiplication and addition is executed for the operand R i+1  in equation (13). 
           Assume that  X=R   i   +q   i   *N   2   (16) 
           [0035]    Then equation (13) is modified as the following equation: 
             R   i+1   =X /2 k   +a   i   *B   (17) 
           [0036]    If Y=X/2 k , equation (17) is changed as the following equation: 
             R   i+1   =Y+a   i   *B   (18) 
           [0037]    Equations (17) and (18) are respectively executed a multiplication and addition operations and the corresponding operands have the same bit number. Therefore, a same data path is used in the computation operation at different time points, thereby saving the area required for a chip.  
           [0038]    However, Montgomery algorithm 3 also has the complex computation problem when the required area for the multiplication is broad. In equations (16) and (18), a k×n multiplier is used. If the values n and k are large, for example, k=32 and n=1024, the chip area therefore becomes very broad. For a chip with the strict request of small size, e.g. a Smart Card, this will influence on its operation and application. As to this point, the invention provides a solution by improving the high radix Montgomery algorithm to reduce the chip area and have the high-speed operation.  
         SUMMARY OF THE INVENTION  
         [0039]    Accordingly, the object of the invention is to provide a modular multiplier and an encryption/decryption processor using the modular multiplier, capable of reducing the chip area and achieving the purpose of high-speed operation.  
           [0040]    To realize the above and other objects, the invention provides a modular multiplier, capable of processing a first operand and a second operand in relation to a modulus for performing the modular multiplication operation. The performed operation includes an instruction, which has an internal multiplication and addition operation with inner recursion and an external multiplication and addition operation. The modular multiplier includes a first buffer device for storing the first operand, the first operand is divided into a first plurality of sub-operands with fixed length; a second buffer device for storing the second operand, the second operand is divided into a second plurality of sub-operands with fixed length; a third buffer device for storing the parameter of the modular multiplication operation; a multiplexer device, coupled to the first, the second, and the third buffer devices, for choosing a first multiplication operand and a second multiplication operand from the first sub-operand, the second sub-operand, and the parameter in order according to the required internal and external multiplication/addition operations; a multiplication device, coupled to the multiplexer device, for multiplying the first multiplication operand by the second multiplication operand to obtain a product; and an addition device, coupled to the multiplication device, for outputting an intermediate result according to the product during the internal multiplication and addition operation and outputting the result of the modular multiplication operation according to the product and the intermediate result during the external multiplication and addition operation.  
           [0041]    The modular multiplier can be an encryption or decryption processor, for example, RSA cryption processor. The encryption or decryption processor performs the modular exponentiation operation in the encryption/decryption function according to the encryption/decryption key, thereby realizing the modular multiplier. The encryption/decryption processor can be applied to, such as, a Smart Card, especially to a modular multiplier having the needs of requiring a small chip area and higher operating speed. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0042]    [0042]FIG. 1 is a block diagram illustrating a modular multiplier of an embodiment of the invention;  
         [0043]    [0043]FIG. 2 is a schematic diagram illustrating an adder to be operated in the first sub-loop according to the embodiment of the invention;  
         [0044]    [0044]FIG. 3 is a schematic diagram illustrating an adder to be operated in the second sub-loop according to the embodiment of the invention;  
         [0045]    [0045]FIG. 4 is a block diagram illustrating an RSA encryption/decryption processor realized by the modular multiplier of FIG. 1;  
         [0046]    [0046]FIG. 5 is a schematic diagram illustrating the application of FIG. 4 in a Smart Card according to the embodiment of the invention. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0047]    This invention provides a solution for reducing the chip area in the prior art. That is, in the prior art, algorithm 3 needs very broad chip area to implement a k×n multiplier. The following embodiment describes the inventive algorithm first and the modular multiplier structure in relation to the algorithm later.  
         [0048]    In order to reduce the required chip area, the n-bit portion (i.e. the operand N 2  in equation (16) and the operand B in equation (18)) in algorithm 3 is grouped to ┐n/k┌ groups, each group having k bits. That is,  
         [0049]    &lt;Algorithm 4&gt; 
         [0050]    R 0 =0;  
         [0051]    For i=0 to ┐n/k┌ do 
           q   i   =R   i (mod 2 k )  (19) 
         [0052]    For j=0 to ┐n/k┌−1 do 
         ( R   i+1 ) j =(( R   i ) j   +q   i * ( N   2 ) j )/2 k   +a   i   B   j   (20) 
         [0053]    end  
         [0054]    end  
         [0055]    where q i *(N 2 ) j  and a i B j  respectively are the k×k multiplication operation.  
         [0056]    In algorithm 4, although the loop j needs extra carry and accumulation operations, the chip area is reduced obviously from k×n to k×k.  
         [0057]    The algorithm 4 is further embodied in following algorithm 5:  
         [0058]    &lt;Algorithm 5&gt; 
         [0059]    R 0 =0;  
         [0060]    For i=0 to ┐n/k┌ do 
         q i =R i mod2 k   (21) 
           W=q   i *( N   2 ) 0   (22) 
           C   −1 =( R   i ) 0   +W[(k− 1):0]  (23) 
         V=0  (24) 
         [0061]    For j=0 to ┐n/k┌−1 do 
         Z=W  (25) 
           W=q   i *( N   2 ) j+1   (26) 
           U=a   i   *B   j   (27) 
         { C   j ,( R   i+1 ) j }=( R   i ) j+1   +W [( k− 1):0]+ Z [(2 k − 1): k]+U [( k− 1):0]+ V[( 2 k− 1): k]+C   j−1   (28) 
         V=U  (29) 
         [0062]    end  
         [0063]    end  
         [0064]    where W, Z, U, V are temporary buffers, C −1 , C j  are carry bits, and {C j , (R i+1 ) j } is the total of k-bit addition. More, (R i ) 0 +W[(k−1):0] can become zero(i.e. C −1 =0) if choosing appropriate q i , N 2 .  
         [0065]    In algorithm 5, two k×k multipliers are used to respectively calculate the operand W in equation (26) and the operand U in equation (27). In fact, algorithm 5 can further uses two sub-loop operations in loop j as following equation 6.  
         [0066]    &lt;Algorithm 6&gt; 
         [0067]    R 0 =0;  
         [0068]    For i=0 to ┐n/k┌ do 
           q   i   =R   i (mod 2 k )  (30) 
         [0069]    For j=0 to ┐n/k┌−1 do 
           Y   j =(( R   i ) j   +q   i *( N   2 ) j )/2 k   (31) 
         [0070]    end  
         [0071]    For j=0 to ┐n/k┌−1 do 
         ( R   i+1 ) j   =Y   j   +a   i   *B   j   (32) 
         [0072]    end  
         [0073]    end  
         [0074]    Likewise, algorithm 6 is further embodied in following algorithm 7:  
         [0075]    &lt;Algorithm 7&gt; 
         [0076]    R 0 =0;  
         [0077]    For i=0 to ┐n/k┌ do 
           q   i   =R   i mod2 k   (33) 
           W=q   i *( N   2 ) 0   (34) 
           C   −1 =( R   i ) 0   +W [( k− 1):0]  (35) 
         [0078]    For j=0 to ┐n/k┌−1 do 
         Z=W  (36) 
           W=q   i *( N   2 ) j+1   (37) 
         { C   j   ,Y   j }=( R   i ) j+1   +W[(k− 1):0 ]+Z[( 2 k− 1): k]+C    j−1   (38) 
         C −1 =0  (39) 
         Z=0  (40) 
         [0079]    end  
         [0080]    For j=0 to ┐n/k┌−1 do 
           W=a   i   *B   j   (41) 
         { C   j ,( R   i+1 ) j   }=Y   j   +W [( k− 1):0 ]+Z [(2 k− 1): k ]+C   j−1   (42) 
         Z=W  (43) 
         [0081]    end  
         [0082]    end  
         [0083]    In algorithm 6 and 7, the loop j in algorithm 5 is divided into two sub-loops. This manner can reduce the requirement of two k×k multipliers to only one k×k multiplier, thereby shrinking the required chip area. Besides, the performance is even faster. For example, when n=1024, k=32, and a clock requirement to a 32×32 multiplication is assumed, executing the first sub-loop j in equation (31) needs ({fraction (1024/32)})=32 clocks and the same clocks as performing the second sub-loop j in equation (32). The entire multiplication operation (i.e. loop i) takes ({fraction (1024/32)}+1)×(32+32)=2112 clocks. If the H-Algorithm is used in the 1024-bit RSA encode or decode modular exponentiation operation, the entire circuit takes about 2×2112×1024 clocks(about 4M clocks), i.e., 4n 2 (n+1)/k 2  in terms of parameters n and k. Thus, the purposes of smaller chip area and faster operation are achieved at the same time.  
         [0084]    [0084]FIG. 1 is a block diagram illustrating a modular multiplier of equation 6 or 7. The modular multiplier structure in FIG. 1 is implemented according to algorithm 7, including buffers  101 ,  102 ,  103 ,  104 ,  105 ; multiplexers  201 ,  202 ; multiplier  203 ; control unit  204 ; flip/flops  301 ,  302 ,  303 ,  305 ,  306 ; and adder  304 . Each element is described as follows.  
         [0085]    Buffer  101  is used to store Montgomery algorithm&#39;s result (R i+1 ) j  or the intermediate operand Y j  in the first sub-loop. Buffers  102 - 105  are used to respectively store the operands A, N 2 , B, q i  of the two multiplication equations (equations (37) and (41)) in algorithm 7, wherein operands A, N 2 , B are a constant, a i  is a portion of bits of the operand A in i th  loop, (N 2 ) j  and B j  are a portion of bits of operands N 2  and B in j th  loop. According to equation (33), q i  stored in buffer  105  is the remainder from R i /2 k , that is, from bit (k−1) to bit 0 in R i . Hence, the lower k bits of R i  stored in buffer  101  are extracted to have the operand q i  in buffer  105 .  
         [0086]    Multiplexers  201  and  202  are used to switch the required operands in the multiplication operation of different loop. For example, a multiplication operation is required for q i  and (N 2 ) j  in equation (37) of the first sub-loop, while a multiplication operation is required for a i  and B j  in equation (41) of the second sub-loop. Multiplexers  201  and  202  are switched by the control signal CTRL of the control unit  204 . A multiplication operation is performed by the k×k multiplier  203  with the outputs of  201  and  202  to create the product stored in buffer W with the length 2k.  
         [0087]    Flip/flops  301 - 303  are used to store the result from the multiplier and output the result to the adder  304  to execute the addition operation in equations (38) and (42). Buffer W with the length 2k is divided into two k-length data, wherein the data in low bits W[(k−1):0] is outputted to flip/flop  302 , the data in high bits W[(2k−1):k] is outputted to flip/flop  301 . Flip/flop  303  stores the high bits Z[(2k−1):k] of the previous multiplication result. Flip/flop  305  stores the carry bit C j−1  of the previous addition result. Adder  304  performs the addition operation in equation (38) of the first sub-loop or in equation (42) of the second sub-loop. The difference between equations (38) and (42) for the addition operation is the operand, using (R i ) j+1  or Y j . When performing the first loop, flip/flop  306  stores the operand Y j  while when performing the second loop, flip/flop  306  stores the operand (R i ) j+1 , and the two operands Y j  and (R i ) j+1  are stored in buffer  101  temporarily.  
         [0088]    The operation of the modular multiplier shown in FIG. 1 is described in detail as follows.  
         [0089]    According to algorithm 7, the first instruction for every i loop begins with the calculation of the remainder of R i /2 k , that is, taking lower k bits of the operand R i  in buffer  101  into buffer  105 .  
         [0090]    The operation starts the first sub-loop, which calculates Y j  with the parameters q i , (N 2 ) j , and (R i ) j . First, in the 1 st  sub-loop, the parameter q i  in the ith loop is unchanged and comes from buffer  105  for the calculation. Buffer  103  outputs the corresponding (N 2 ) j  depending on the value j. The higher k bits W[(2k−1):k] and lower k bits W[(k−1):0] of the product for every multiplication operation in the multiplier  203  are inputted to flip/flops  301  and  302 , respectively. Inputting the higher k bits to flip/flop  301  is performed by a clock delay. Therefore, the performed result is counted into Y j+1  for the addition calculation. The value Y j  is calculated by the adder  304  to add together with the lower k bits W[(k−1):0], the higher k bits Z[(2k−1):k] (stored in flip/flop  303 ) of previous product, (R i ) j+1  (stored in buffer  101 ), and the overflow bit C j−1  of previous addition operation(stored in flip/flop  305 ). The calculated result from the adder  304  is stored in buffer  101  at next clock.  
         [0091]    [0091]FIG. 2 is a schematic diagram illustrating an adder to be operated in the first sub-loop according to the embodiment of the invention. Assume that k=32 and n=1024, the first column representing the calculation of equation (35). When j=0, the adder  304  adds up R i [63:32], (q i (N 2 ) 1 ) [31:0], (q i (N 2 ) 0 ) [63:32], and the carry bit C j−1  and gets Y[31:0]. When j=1, the adder  304  adds up R i [95:64], (q i (N 2 ) 2 ) [31:0], (q i (N 2 ) 1 ) [63:32], and the carry bit C 0  and gets Y[63:32]. The remaining operations for j=2 to 31 are all similar. That is, when j=31, Y[1023:992] is found, and Y[1023:0] is completed.  
         [0092]    Thus, the second sub-loop sequentially starts at the calculation of (R i+1 ) j  with the parameters a i , B j , Y j . Likewise, the parameter a i  in the i th  loop is unchanged and comes from buffer  102  for the calculation. Buffer  104  outputs the corresponding B j  depending on the value j. The higher k bits W[(2k−1):k] and lower k bits W[(k−1):0] of the product for every multiplication operation in the multiplier  203  are inputted to flip/flops  301  and  302 , respectively. Inputting the higher k bits to flip/flop  301  is performed by a clock delay. Therefore, the performed result is counted into (R i+1 ) j+1  for the addition calculation. The value (R i+1 ) j  is calculated by the adder  304  to add up the lower k bits W[(k−1):0], the higher k bits Z[(2k−1):k] (stored in flip/flop  303 ) of previous product, Y j  (stored in buffer  101 ), and the carry bit C j−1  of previous addition operation(stored in flip/flop  305 ). The calculated result from the adder  304  is stored in buffer  101  at next clock.  
         [0093]    [0093]FIG. 3 is a schematic diagram illustrating an adder to be operated in the second sub-loop according to the embodiment of the invention with reference to FIG. 2. When j=0, the adder  304  adds up Y[31:0], (a i B 1 ) [31:0] and (a i B 0 ) [63:32], and gets R i+1  [63:32]. The remaining operations for j=1 to 31 are all similar. That is, when j=31, R i+1  [1023:992] is found, and R i+1  [1023:0] is completed.  
         [0094]    Thus, repeated the calculation of R i  for every i and the final result of the Montgomery algorithm is found, which is the modular multiplication of 2 −n AB (mod N). It is noted that the intermediate content of corresponding flip/flops between the first and second sub-loops is clear in order to use the same data path to calculate different equations. The control unit  204  is used to control the entire operation by a control signal CTRL. The required calculation for the final result of equation 6 or 7 is performed by orderly shifting different multiplication operands into the multiplier.  
         [0095]    The advantage of the invention is that the inventive modular multiplier can save the chip area and quickly perform the operation concurrently. FIG. 4 is a block diagram illustrating an RSA encryption/decryption processor realized by the modular multiplier of FIG. 1. As shown in FIG. 4, the RSA encryption/decryption processor includes an encryption/decryption core  12  and a modular multiplier core  14 . The modular multiplier core  14  can be realized by, for example, the structure of FIG. 1. The modular multiplication result is calculated with the operands A and B. The encryption/decryption core  12  performs the required modular exponentiation operation to encrypt a plaintext to a ciphertext or decrypt the ciphertext to the plaintext using the steps of pre-operation in equation (7), exponentiation operation in equation (8) and post-operation in equation (9).  
         [0096]    [0096]FIG. 5 is a schematic diagram illustrating the encryption/decryption structure applied to a Smart Card according to the embodiment of the invention. Due to the limits to Smart Card&#39;s standard and its facility in carry, the strict chip area is a must. As shown in FIG. 5, the Smart Card  20  exchanges the external data through a communication interface  22 . Before the data transfer, the data is encrypted by the encryption/decryption processor  24  through the internal memory  26  of the Smart Card  20  to ensure the data security. Because the need of finishing the required calculation as soon as possible by using the encryption/decryption processor  24  with a smaller area in a chip, the multiplier structure of the invention is the best choice to reach the goal.  
         [0097]    Although the present invention has been described in its preferred embodiment, it is not intended to limit the invention to the precise embodiment disclosed herein. Those who are skilled in this technology can still make various alterations and modifications without departing from the scope and spirit of this invention. Therefore, the scope of the present invention shall be defined and protected by the following claims and their equivalents.