Patent Publication Number: US-9841950-B2

Title: Modular multiplier and modular multiplication method thereof

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application is a continuation application of U.S. patent application Ser. No. 13/792,642, filed on Mar. 11, 2013, which claims priority under 35 U.S.C. §119 from Korean Patent Application No. 10-2012-0052609, filed on May 17, 2012 in the Korean Intellectual Property Office, the disclosures of which are incorporated herein in their entirety by reference. 
    
    
     BACKGROUND 
     Apparatuses and methods consistent with exemplary embodiments relate to modular multipliers and a modular multiplication method thereof. 
     An operation performed in a public key crypto algorithm such as a Rivest Shamir Adleman (RSA) and an elliptic curve cryptography (ECC) is based on a modular operation. As a basic operation of the modular operation, there are a modular addition/subtraction and a modular multiplication. A modular division is not used in many algorithms because the quantity of calculations in a modular division is very large. In some cases, a modular division is calculated using a modular multiplication. A modular multiplication can be calculated by sets of modular additions. This case corresponds to a serialized multiplication and thereby its operation speed is very low. Thus, to improve performance, a modular multiplication increases a radix to be realized in a digit-serialized multiplication form. 
     Accordingly, operations basically performed in a public key operational unit are a modular addition/subtraction and a modular multiplication. Since a modular multiplication operation is more complicated than a modular addition/subtraction operation and a critical path of the modular multiplication operation is longer than that of the modular addition/subtraction operation, the maximum frequency of the whole secure operational unit depends on how a modular multiplication is embodied. 
     A modular multiplication algorithm includes two operations. The two operations are a multiplication operation and a reduction operation. A modular multiplication algorithm widely used in a hardware design is a Montgomery multiplication algorithm. The Montgomery multiplication algorithm can effectively perform a reduction operation. 
     The Montgomery multiplication algorithm performs a reduction determination or a quotient generation as one process of execution. If radix is small (e.g.,  2  or  4 ), a reduction determination can be simply calculated. However, to increase a performance speed of a public key operational unit, the size of a digit is inevitably increased. At this time, a reduction determination becomes complicated and, thereby, a part for the reduction determination occupies a large portion of a critical path. This not only reduces a performance speed of the public key operation but also acts as the limit of radix increase. 
     SUMMARY 
     According to an aspect of an exemplary embodiment, there is provided a modular multiplier including: a first register which stores a previous accumulation value calculated at a previous cycle; a second register which stores a previous quotient calculated at the previous cycle; a quotient generator which generates a quotient using the stored previous accumulation value output from the first register; and an accumulator which receives an operand, a bit value of a multiplier, the stored previous accumulation value, and the stored previous quotient to calculate an accumulation value in a current cycle, wherein the calculated accumulation value is updated to the first register, and the generated quotient is updated to the second register. 
     According to an aspect of another exemplary embodiment, there is provided a modular multiplication method of a modular multiplier, the modular multiplication method including: calculating a quotient using a previous accumulation value for a calculation of an accumulation value of next cycle; and calculating an accumulation value using the previous accumulation value, a previous quotient, a bit value of multiplier, an operand and a modulus, wherein the previous quotient is a value calculated in a previous cycle, and, in a current cycle, the calculating the quotient and the calculating the accumulation value are independently performed. 
     According to an aspect of another exemplary embodiment, there is provided a modular multiplication method of a modular multiplier using a pipeline method, the modular multiplication method including: calculating, outside of a critical path of a pipeline of a modular multiplication operation, a quotient that is not used in a current cycle of the modular multiplication operation; and calculating, in the current cycle of the modular multiplication operation, an accumulation value using a previous quotient calculated in a previous cycle of the modular multiplication operation. 
    
    
     
       BRIEF DESCRIPTION OF THE FIGURES 
       Exemplary embodiments will be described below in more detail with reference to the accompanying drawings. Exemplary embodiments may, however, be embodied in different forms and should not be constructed as limited to the exemplary embodiments set forth herein. Rather, these exemplary embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the inventive concept to those skilled in the art. Like numbers refer to like elements throughout. 
         FIG. 1  is a block diagram of Montgomery multiplier in which an algorithm according to an exemplary embodiment is embodied; 
         FIG. 2  is a drawing illustrating a modular multiplication operation of the Montgomery multiplier illustrated in  FIG. 1  according to an exemplary embodiment; 
         FIG. 3  is a block diagram of Montgomery multiplier in which an algorithm in accordance with another exemplary embodiment is embodied; 
         FIG. 4  is a drawing illustrating a modular multiplication operation of the Montgomery multiplier illustrated in  FIG. 3  according to an exemplary embodiment; 
         FIG. 5  is a flow chart illustrating a modular multiplication method of a modular multiplier using a pipeline method according to an exemplary embodiment; and 
         FIG. 6  is a block diagram illustrating a memory system including a crypto processor having a Montgomery multiplier according to an exemplary embodiment. 
     
    
    
     DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS 
     Exemplary embodiments will be described more fully hereinafter with reference to the accompanying drawings. Exemplary embodiments may, however, be embodied in many different forms and should not be construed as limited to the exemplary embodiments set forth herein. Rather, these exemplary embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the inventive concept to those skilled in the art. In the drawings, the size and relative sizes of layers and regions may be exaggerated for clarity. Like numbers refer to like elements throughout. 
     A modular multiplier using a pipeline method in accordance with an exemplary embodiment increases an operation speed by removing a process of calculating a quotient in a critical path. For convenience of description, it is assumed that the modular multiplier is a Montgomery multiplier. 
     A general Montgomery multiplication algorithm adopting a pipeline method will be described below. 
     In the case that radix is large in a Montgomery multiplication, a pipeline method may be used to reduce a critical path. An algorithm 1 below is a Montgomery multiplication algorithm having radix of 2k (where k is natural number) adopting a pipeline method: 
     
       
         
           
               
             
               
                   
               
               
                 Algorithm 1: Montgomery Multiplication with pipelined high-radix 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
            
               
                 Input: 0 ≦ A, B &lt; 2M where B = Σ i=0   n−1  b i 2 ki  and b i  ∈ {0,1,..., 2 k  − 1} 
               
               
                    2 r−1  &lt; M &lt; 2 r  where r = nk 
               
               
                    m′ such that (−m′ × M) mod 2 k  = 1  
               
               
                 Output: S n  ≡ AB2 −r  mod M where 0 ≦ S n  &lt; 2M 
               
               
                 1. S −1  =; b n  = 0; 
               
               
                 2. For i = 0 to n 
               
               
                 3. s i−1  = S i−1  mod 2 k ; 
               
               
                 4. q i−1  = m′ × s i−1  mod 2 k ; 
               
               
                 5. S i  = (S i−1  + q i−1 M) div 2 k  + b i A; 
               
               
                   
               
            
           
         
       
     
     An accumulation value output from the algorithm 1 may be expressed as follows: 
     
       
         
           
             
               S 
               n 
             
             = 
             
               
                 
                   ∑ 
                   
                     i 
                     = 
                     0 
                   
                   
                     n 
                     - 
                     1 
                   
                 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   
                     ( 
                     
                       
                         
                           b 
                           i 
                         
                         ⁢ 
                         A 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           2 
                           ki 
                         
                       
                       + 
                       
                         
                           q 
                           i 
                         
                         ⁢ 
                         M 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           2 
                           ki 
                         
                       
                     
                     ) 
                   
                   ⁢ 
                   
                     2 
                     
                       - 
                       nk 
                     
                   
                 
               
               = 
               
                 
                   ( 
                   
                     AB 
                     + 
                     QM 
                   
                   ) 
                 
                 ⁢ 
                 
                   2 
                   
                     - 
                     r 
                   
                 
               
             
           
         
       
     
     Here, 
     
       
         
           
             B 
             = 
             
               
                 
                   ∑ 
                   
                     i 
                     = 
                     0 
                   
                   
                     n 
                     - 
                     1 
                   
                 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   
                     b 
                     i 
                   
                   ⁢ 
                   
                     2 
                     ki 
                   
                   ⁢ 
                   Q 
                 
               
               = 
               
                 
                   ∑ 
                   
                     i 
                     = 
                     0 
                   
                   
                     n 
                     - 
                     1 
                   
                 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   
                     q 
                     i 
                   
                   ⁢ 
                   
                     2 
                     ki 
                   
                 
               
             
           
         
       
     
     In the algorithm 1, a calculation process corresponding to a critical path proceeds in the order of step 3→step 4→step 5. Steps for generating a quotient (q i−1 ), i.e., steps 3 and 4, are included in the critical path. 
     A modification of the algorithm 1 is disclosed in H. Orup, “Simplifying quotient determination in high-radix modular multiplication,” (Proceedings of the 12th Symposium on Computer Arithmetic, pp. 193-199, 1995), incorporated herein by reference in its entirety. That is, generating the quotient (q i ) is simplified and thereby the quotient generation is excluded from the critical path. An algorithm 2 in accordance with Orup is as follows: 
     
       
         
           
               
             
               
                   
               
               
                 Algorithm 2: MM-PHR by Orup 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
            
               
                 Input: 2 r−1  &lt; M &lt; 2 r  where r = nk 
               
               
                    {tilde over (M)} = m′ × M such that (−m′ × M) mod 2 k  = 1 
               
               
                    0 ≦ A, B &lt; 2{tilde over (M)} where B = Σ i=0   n  b i 2 ki  and b i  ∈ {0,1,..., 2 k  − 1} 
               
               
                 Output: S n+1  ≡ AB2 −r  mod M where 0 ≦ S n+1  &lt; 2{tilde over (M)} 
               
               
                 1. S −1  = 0; b n+1  = 0; 
               
               
                 2. For i = 0 to n + 1 
               
               
                 3. q i−1  = S i−1  mod 2 k ; 
               
               
                 4. S i  = (S i−1  + q i−1 {tilde over (M)}) div 2 k  + b i A; 
               
               
                   
               
            
           
         
       
     
     In the algorithm 2, calculation of the quotient (q i−1 ) involves the least significant digit (LSD) of the accumulation value (S i−1 ). If the accumulation value (S i−1 ) exists in a non-redundant form, the quotient (q i−1 ) can be induced without a separate calculation process. Thus, a process of calculating the quotient (q i−1 ) may be excluded from the critical path. 
     However, in the algorithm 2, a modulus M is converted into {tilde over (M)} to be used and thereby all the operands and a range of {tilde over (M)} become larger by k bits. That is, a range of operated values increases to [0, 2 k+1 M]. Consequently, a size of hardware for processing/storing an intermediate result and a final result increases. However, in this case, an operation process for reducing a range of result values finally calculated causes overhead. Additionally, since a range of operands increases, the number of iterations is greater than the algorithm 1. 
     If the accumulation value (S i ) exists in a redundant form, a process of converting the accumulation value (S i ) into a non-redundant form may be included in the critical path. To exclude that conversion process from the critical path, an extra pipeline step may be introduced. At this time, a cycle in addition increases and a range of input values and result values increases to have [0,2 2k+1 M]. 
     An exemplary embodiment provides a Montgomery multiplication algorithm of which a range of calculation results does not become great while excluding a process of calculating a quotient from a critical path. The Montgomery multiplication algorithm in accordance with exemplary embodiments calculates a quotient one cycle ahead of time and performs a multiplying operation using a previously calculated quotient. 
     An algorithm 3 in accordance with an exemplary embodiment is as follows: 
     
       
         
           
               
             
               
                   
               
               
                 Algorithm 3 MM-RP1 (Montgomery Multiplication with Reduction  
               
               
                 Predetermination 1) 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
            
               
                 Input: 0 ≦ A, B &lt; 2M where B = Σ i=0   n−1  b i 2 ki , and b i  ∈ {0,1,..., 2 k  − 1}, 
               
               
                    2 r−1  &lt; M &lt; 2 r  where r = nk 
               
               
                    m′ such that (−m′ × M) mod 2 2k  ≡ 1  
               
               
                 Output: S n+1  ≡ AB2 −r  mod M where 0 ≦ S n+1  &lt; 2M 
               
               
                 1. S −1  = 0; q −2  = 0; b n  = 0; b n+1  = 0; 
               
               
                 2. For i = 0 to n + 1 
               
               
                 3. s i−1  = S i−1  mod 2 2k ; 
               
               
                 4. q i−1  = (m′ × s i−1  mod 2 2k ) div 2 k ; 
               
               
                 5. S i  = (S i−1  + q i−2 M) div 2 k  + b i A2 k ; 
               
               
                   
               
            
           
         
       
     
     In step 4 of the algorithm 3, after quotient of 2 k bit corresponding to two digits is calculated, only k bit which is the most significant digit (MSD) is stored as quotient (q i−1 ). The stored quotient (q i−1 ) is used in step 5. A condition for calculating the effective quotient (q i−1 ) is that partial product (b l A) with respect to 0≦1≦i−1 is accumulated on accumulation value (S i−1 ) of previous cycle. In the step 5, the accumulation value (S i−1 ) includes an intermediate value (S i−1 +q i−2 M) div 2 k  and a partial product (b i A2 k ). Since in the step 5, the accumulation value (S i−1 ) accumulates the partial product (b l A), the above condition can be satisfied. 
     Whether final accumulation value (S n+1 ) outputs a correct value can be checked as described below. While the steps 3, 4 and 5 are iterated, the following mathematical formula is satisfied: 
     
       
         
           
             
               
                 
                   
                     S 
                     i 
                   
                   = 
                     
                   ⁢ 
                   
                     
                       
                         ( 
                         
                           
                             S 
                             
                               i 
                               - 
                               1 
                             
                           
                           + 
                           
                             
                               q 
                               
                                 i 
                                 - 
                                 2 
                               
                             
                             ⁢ 
                             M 
                           
                         
                         ) 
                       
                       ⁢ 
                       div 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         2 
                         k 
                       
                     
                     + 
                     
                       
                         b 
                         i 
                       
                       ⁢ 
                       A 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         2 
                         k 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       
                         S 
                         
                           i 
                           - 
                           1 
                         
                       
                       ⁢ 
                       
                         2 
                         
                           - 
                           k 
                         
                       
                     
                     + 
                     
                       
                         q 
                         
                           i 
                           - 
                           2 
                         
                       
                       ⁢ 
                       M 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         2 
                         
                           - 
                           k 
                         
                       
                     
                     + 
                     
                       
                         b 
                         i 
                       
                       ⁢ 
                       A 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         2 
                         k 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       ∑ 
                       
                         l 
                         = 
                         0 
                       
                       i 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         ( 
                         
                           
                             
                               q 
                               
                                 i 
                                 - 
                                 2 
                               
                             
                             ⁢ 
                             M 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               2 
                               
                                 - 
                                 k 
                               
                             
                           
                           + 
                           
                             
                               b 
                               i 
                             
                             ⁢ 
                             A 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               2 
                               k 
                             
                           
                         
                         ) 
                       
                       ⁢ 
                       
                         2 
                         
                           
                             ( 
                             
                               l 
                               - 
                               i 
                             
                             ) 
                           
                           ⁢ 
                           k 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       ∑ 
                       
                         l 
                         = 
                         0 
                       
                       i 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         ( 
                         
                           
                             
                               q 
                               
                                 l 
                                 - 
                                 2 
                               
                             
                             ⁢ 
                             M 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               2 
                               
                                 k 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     l 
                                     - 
                                     1 
                                   
                                   ) 
                                 
                               
                             
                           
                           + 
                           
                             
                               b 
                               l 
                             
                             ⁢ 
                             A 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               2 
                               
                                 k 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     l 
                                     + 
                                     1 
                                   
                                   ) 
                                 
                               
                             
                           
                         
                         ) 
                       
                       ⁢ 
                       
                         2 
                         
                           - 
                           ik 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       ∑ 
                       
                         l 
                         = 
                         0 
                       
                       i 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         ( 
                         
                           
                             
                               q 
                               
                                 l 
                                 - 
                                 2 
                               
                             
                             ⁢ 
                             M 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               2 
                               
                                 k 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     l 
                                     - 
                                     2 
                                   
                                   ) 
                                 
                               
                             
                           
                           + 
                           
                             
                               b 
                               l 
                             
                             ⁢ 
                             A 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               2 
                               kl 
                             
                           
                         
                         ) 
                       
                       ⁢ 
                       
                         2 
                         
                           
                             - 
                             
                               ( 
                               
                                 i 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                           ⁢ 
                           k 
                         
                       
                     
                   
                 
               
             
           
         
       
     
     Herein, q −2 =q −1 =b n =b n+1 =0, and 0≦i≦n+1. 
     Thus, when i=n+1, the final result value (S n+1 ) is determined by the following mathematical formula:
 
 S   n+1 =Σ l=0   n+1 ( q   l−2   M 2 k(l−2)   +b   l   A 2 kl )2 −nk  
 
     Herein, since q −2 =q −1 =b n =b n+1 =0, the final result value is expressed by the following mathematical formula:
 
 S   n+1 =Σ l=0   n−1 ( q   l   M 2 kl   +b   l   A 2 kl )2 −nk =( AB+QM )2 −r  
 
     Thus, the final result value (S n+1 ) is the same as that of a general Montgomery multiplication algorithm. Consequently, the suggested algorithm 3 is effective. 
     An index of quotient (q i−1 ) generated in the step 4 of the algorithm 3 is ‘i−1’ and an index of quotient (q i−2 ) used in the step 5 is ‘i−2’. In the algorithm 3, a quotient value is calculated one cycle ahead of time as compared with time actually used. Therefore, a calculation process of the quotient can be excluded from a critical path. 
       FIG. 1  is a block diagram of a modular multiplier (e.g., a Montgomery multiplier  100 ) in which an algorithm according to an exemplary embodiment is embodied. Referring to  FIG. 1 , the Montgomery multiplier  100  includes a register  1  (i.e., first register)  110 , a register  2  (i.e., second register)  120 , a quotient generator  130 , and an accumulator  140 . 
     The register  1   110  stores an accumulation value (S i ) being generated in the current cycle while outputting the accumulation value (i.e., previous accumulation value) (S i−1 ) of the previous cycle. 
     The register  2   120  stores a quotient (q i−1 ) generated in the current cycle while outputting the quotient (i.e., previous quotient) (q i−2 ) generated in the previous cycle. 
     The quotient generator  130  generates a quotient (q i−1 ) which will be used in a next cycle using the accumulation value (S i−1 ) of the previous cycle. Herein, a process of generating a quotient (q i−1 ) corresponds to the steps 3 and 4 of the algorithm 3. 
     The accumulator  140  receives an operand A, a modulus M, a bit string b i  of operand B, an accumulation value (S i−1 ), and a quotient (q i−2 ) to perform a partial multiplying operation. Herein, a part generating and accumulating a partial multiplying operation corresponds to the step 5 of the algorithm 3. 
     In  FIG. 1 , the quotient (q i−1 ) is a value being stored in the register  2   120  and the quotient (q i−2 ) is a value which was stored in the register  2   120  in a previous iteration and a value being input to the accumulator  140 . Thus, the Montgomery multiplier  100  includes the quotient generator  130  generating quotient (q i−1 ) before applying the quotient (q i−2 ). Consequently, the critical path illustrated in  FIG. 1  is determined by the greater delay value between a delay value of the quotient generator  130  and a delay value of the accumulator  140 . For instance, a delay value of the quotient generator  130  may be greater than or smaller than that of the accumulator  140 . If the two delay values are properly distributed, the related art maximum frequency of the Montgomery multiplier  100  can be maximally doubled. 
     A calculation of the quotient generator  130  induces a result of one digit. Because of this, the accumulator  140  performing a long operation may have a longer critical path. At this time, a calculation process of the quotient generator  130  may be excluded from the critical path. 
     An exemplary embodiment can provide a Montgomery multiplication algorithm removing one cycle. An algorithm 4 in accordance with another exemplary embodiment is as follows: 
     
       
         
           
               
             
               
                   
               
               
                 Algorithm 4 MM-RP2 (Montgomery Multiplication with Reduction  
               
               
                 Predetermination 2) 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
            
               
                 Input: 0 ≦ A, B &lt; 2M where B = Σ i=0   n−1  b i 2 ki , and b i  ∈ {0,1,..., 2 k  − 1} 
               
               
                    2 r−1  &lt; M &lt; 2 r  where r = nk 
               
               
                    a 0  = A mod 2 k   
               
               
                    m′ such that (−m′ × M) mod 2 2k  ≡ 1  
               
               
                 Output: S n  ≡ AB2 −r  mod M where 0 ≦ S n  &lt; 2M 
               
               
                 1. S −1  = 0; p 0  = a 0 b 0  mod 2 k ; q −1  = 0; b n  = 0; b n+1  = 0; 
               
               
                 2. For i = 0 to n  
               
               
                 3. p i+1  = a o b i+1  mod 2 k ; 
               
               
                 4. s i  = (S i-1  + p i 2 k ) mod 2 2k ; 
               
               
                 5. qi = (m′ × s i  mod 2 2k ) div 2 k ; 
               
               
                 6. S i  = (S i−1  + q i−1 M) div 2 k  + b i A i ; 
               
               
                   
               
            
           
         
       
     
     Just like the algorithm 3, after a quotient corresponding to two digits is calculated (m′×s i  mod 2 2k ), only the most significant part is stored in the quotient (q i ) through div 2 k  and the stored quotient (q i ) is used in a next iteration. Unlike the algorithm 3, to reduce one cycle, the quotient (q i ) is used instead of the quotient (q i−1 ). Because of this, the quotient (q i ) is calculated using the accumulation value (S i−1 ). Thus, compensation to the partial product (b i A) is to be reflected in a calculation of the quotient (q i ). However, the whole partial product (b i A) value is not needed but only the least significant digit (LSD) may be used. In the step 3, the least significant digit (LSD; p i+1 ) of the partial product (b i+1 A) is calculated. The least significant digit (p i+1 ) calculated in the step 3 is stored in a register and is used to compensate the accumulation value (S i−1 ) in the step 4 of the next cycle. In the step 5, the effective quotient (q i ) is calculated using the compensated accumulation value (s i ). 
     To verify an effectiveness of the final accumulation value (S i ) is similar to the algorithm 3. The following mathematical formula is satisfied while an accumulation operation is iterated: 
     
       
         
           
             
               
                 
                   
                     S 
                     i 
                   
                   = 
                     
                   ⁢ 
                   
                     
                       
                         ( 
                         
                           
                             S 
                             
                               i 
                               - 
                               1 
                             
                           
                           + 
                           
                             
                               q 
                               
                                 i 
                                 - 
                                 2 
                               
                             
                             ⁢ 
                             M 
                           
                         
                         ) 
                       
                       ⁢ 
                       div 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         2 
                         k 
                       
                     
                     + 
                     
                       
                         b 
                         i 
                       
                       ⁢ 
                       A 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         2 
                         k 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       
                         S 
                         
                           i 
                           - 
                           1 
                         
                       
                       ⁢ 
                       
                         2 
                         
                           - 
                           k 
                         
                       
                     
                     + 
                     
                       
                         q 
                         
                           i 
                           - 
                           2 
                         
                       
                       ⁢ 
                       M 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         2 
                         
                           - 
                           k 
                         
                       
                     
                     + 
                     
                       
                         b 
                         i 
                       
                       ⁢ 
                       A 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         2 
                         k 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       ∑ 
                       
                         l 
                         = 
                         0 
                       
                       i 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         ( 
                         
                           
                             
                               q 
                               
                                 l 
                                 - 
                                 2 
                               
                             
                             ⁢ 
                             M 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               2 
                               
                                 - 
                                 k 
                               
                             
                           
                           + 
                           
                             
                               b 
                               l 
                             
                             ⁢ 
                             A 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               2 
                               k 
                             
                           
                         
                         ) 
                       
                       ⁢ 
                       
                         2 
                         
                           
                             ( 
                             
                               l 
                               - 
                               i 
                             
                             ) 
                           
                           ⁢ 
                           k 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       
                         ∑ 
                         
                           l 
                           = 
                           0 
                         
                         i 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           ( 
                           
                             
                               
                                 q 
                                 
                                   l 
                                   - 
                                   2 
                                 
                               
                               ⁢ 
                               M 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 2 
                                 
                                   k 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       l 
                                       - 
                                       1 
                                     
                                     ) 
                                   
                                 
                               
                             
                             + 
                             
                               
                                 b 
                                 l 
                               
                               ⁢ 
                               A 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 2 
                                 
                                   k 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       l 
                                       + 
                                       1 
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                           ) 
                         
                         ⁢ 
                         
                           2 
                           
                             - 
                             ik 
                           
                         
                       
                     
                     - 
                   
                 
               
             
             
               
                 
                     
                   ⁢ 
                   
                     
                       ∑ 
                       
                         l 
                         = 
                         0 
                       
                       i 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         ( 
                         
                           
                             
                               q 
                               
                                 l 
                                 - 
                                 2 
                               
                             
                             ⁢ 
                             M 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               2 
                               
                                 k 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     l 
                                     - 
                                     2 
                                   
                                   ) 
                                 
                               
                             
                           
                           + 
                           
                             
                               b 
                               l 
                             
                             ⁢ 
                             A 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               2 
                               kl 
                             
                           
                         
                         ) 
                       
                       ⁢ 
                       
                         2 
                         
                           
                             - 
                             
                               ( 
                               
                                 i 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                           ⁢ 
                           k 
                         
                       
                     
                   
                 
               
             
           
         
       
     
     Herein, q −1 =b n =0, and 0≦i≦n. 
     Thus, final result value (S n ) is determined by the following mathematical formula:
 
 S   n =Σ l=0   n ( q   l−1   M 2 k(l−1)   +b   l   A 2 kl )2 −nk  
 
     Herein, since q −1 =b n =0, the final result value (S n ) is expressed by the following mathematical formula:
 
 S   n =Σ l=0   n−1 ( q   l   M 2 kl   +b   l   A 2 kl )2 −nk =( AB+QM )2 −r  
 
     Thus, the final result value (S n ) is the same as that of a general related art Montgomery multiplication algorithm. Consequently, the suggested algorithm 4 according to an exemplary embodiment is effective. 
     The total number of iterations (or the number of cycles) in the algorithm 4 is ‘n+1’. The total number of iterations in the algorithm 4 is less than that of the algorithms 2and 3 by 1 and is equal to that of the algorithm 1. A hardware overhead occurring in the algorithm 4 is a process that p i+1  is calculated in the step 3 and the p i+1  is added to reflect the p i+1  in s i  in the step 4. A size of p i+1  is k-bit corresponding to 1 digit. 
     For instance, if radix is 16, the p i+1  is 4 bits and if radix is 256, the p i  is a mere 8 bits. In case of the most widely used RSA, a length of key is minimum 1024-bit and a size of chunk (the number of bits processed at a time) is generally 512-bit or 1024-bit. Thus, hardware overhead of the algorithm 4 is relatively small. 
     Since in the algorithm 4, an operation of p 0 =a 0 b 0  mod 2 k  is not included in an iteration, a pre-computation is to be performed. To calculate p 0 , only the least significant digit (LSD) of operands A and B is needed. To load the operands A and B on a secure operational unit, many cycles may be needed because a size of operand is large. Thus, if loading the least significant digit (LSD) of operands A and B in advance, and then calculating p 0  while loading the rest of digits, further cycles due to a pre-computation are not needed. 
       FIG. 2  is a drawing illustrating a modular multiplication operation of the Montgomery multiplier  100  illustrated in  FIG. 1  according to an exemplary embodiment. Referring to  FIG. 2 , in the modular multiplication operation, an operation ACC of calculating an accumulation value and an operation QG of calculating a quotient are independently performed in each of cycles (i−2, i−1, i). 
     Referring to  FIGS. 1 and 2 , a modular multiplication operation proceeds as follows. 
     A modular multiplication operation of i−1th cycle proceeds as follows. 
     In an operation QG of calculating a quotient of i−1th cycle, the quotient generator  130  receives a previous accumulation value (S i−2 ) to calculate a quotient (q i−2 ). Herein, the previous accumulation value (S i−2 ) is a value calculated in i−2th cycle and a value output from the register  1   110  in i−1th cycle. The calculated quotient (q i−2 ) is newly updated to the register  2   120 . 
     In the operation ACC of calculating an accumulation value of i−1th cycle, the accumulator  140  receives a previous accumulation value (S i−2 ), a previous quotient (q i−3 ), a bit (b i−1 ) of multiplier, an operand A, and a modulus M to calculate an accumulation value (S i−1 ). Herein, the previous accumulation value (S i−2 ) is output from the register  1   110  and the previous quotient (q i−3 ) is output from the register  2   120 . The previous quotient (q i−3 ) is a value calculated in i−2th cycle. The calculated accumulation value (S i−1 ) is newly updated to the register  1   110 . With this, a modular multiplying operation of i−1th cycle is completed. 
     After that, a modular multiplying operation of ith cycle proceeds. The quotient generator  130  receives the previous accumulation value (S i−1 ) to calculate a quotient (q i−1 ) in an operation of calculating a quotient of ith cycle. The previous accumulation value (S i−1 ) is a value calculated in i−1th cycle and is a value output from the register  1   110  in ith cycle. The calculated quotient (q i−1 ) is newly updated to the register  2   120 . 
     In an operation ACC of calculating an accumulation value of ith cycle, the accumulator  140  receives a previous accumulation value (S i−1 ), a previous quotient (q i−2 ), a bit (b i ) of multiplier, an operand A, and a modulus M to calculate an accumulation value (S i ). Herein, the previous accumulation value (S i−1 ) is output from the register  1   110  and the previous quotient (q i−2 ) is output from the register  2   120 . The previous quotient (q i−2 ) is a value calculated in i−1th cycle. The calculated accumulation value (S i ) is newly updated to the register  1   110 . With this, a modular multiplying operation of ith cycle is completed. 
     In the modular multiplying operation in accordance with an exemplary embodiment, an operation QG of calculating a quotient in a current cycle and an operation ACC of calculating an accumulation value can be independently performed. For instance, a previous quotient used in the operation ACC of calculating an accumulation value is a value calculated in the operation QG of calculating a quotient of previous cycle. With this, an operation of calculating a quotient in a critical path can be excluded. 
       FIG. 3  is a block diagram of a modular multiplier (e.g., Montgomery multiplier  200 ) in which an algorithm according to another exemplary embodiment is embodied. Referring to  FIG. 3 , the Montgomery multiplier  200  includes a register  1  (i.e., first register)  210 , a register  2  (i.e., second register)  220 , a quotient generator  230 , and an accumulator  240 . In the Montgomery multiplier  200 , an index of quotient q i  generated from the quotient generator  230  is greater by 1 than that of the Montgomery multiplier  100  according to the exemplary embodiment illustrated in  FIG. 1 . Because of this, a process of generating a quotient in the Montgomery multiplier  200  is faster by one cycle than that in the Montgomery multiplier  100  and a final result in the Montgomery multiplier  200  is also faster by one cycle than that in the Montgomery multiplier  100 . 
     The algorithm 3 can exclude a part (reduction determination) of calculating a quotient from a critical path to reduce a critical path of the Montgomery multiplication algorithm. Thus, as compared with a related art algorithm, the algorithm 3 can exclude a part of calculating a quotient in a critical path without increasing a range of operation result. 
     The algorithm 4 can remove an overhead of one cycle to reduce a critical path. That is, the algorithm 4 removes an overhead of cycle by minimum hardware overhead. The algorithm 4 can reduce a critical path without an increase of one cycle in a reduction determination. 
       FIG. 4  is a drawing illustrating a modular multiplication operation of the Montgomery multiplier illustrated in  FIG. 3  according to an exemplary embodiment. Referring to  FIGS. 3 and 4 , the modular multiplication operation is as follows. 
     A modular multiplication operation of i−1th cycle proceeds as follows. 
     In an operation QG of calculating a quotient of i−1th cycle, the quotient generator  230  receives a previous accumulation value (S i−2 ) to calculate a quotient (q i−1 ). Herein, the previous accumulation value (S i−2 ) is a value calculated in i−2th cycle and a value output from the register  1   210  in i−1th cycle. The calculated quotient (q i−1 ) is newly updated to the register  2   220 . 
     In the operation ACC of calculating an accumulation value of i−1th cycle, the accumulator  240  receives a previous accumulation value (S i−2 ), a previous quotient (q i−2 ), a bit (b i−1 ) of multiplier, an operand A, and a modulus M to calculate an accumulation value (S i−1 ). Herein, the previous accumulation value (S i−2 ) is output from the register  1   210  and the previous quotient (q i−2 ) is output from the register  2   220 . The previous quotient (q i−2 ) is a value calculated in i−2th cycle. The calculated accumulation value (S i−1 ) is newly updated to the register  1   210 . With this, a modular multiplying operation of i−1th cycle is completed. 
     After that, a modular multiplying operation of ith cycle proceeds. The quotient generator  230  receives the previous accumulation value (S i−1 ) to calculate a quotient (q i ) in an operation of calculating a quotient of ith cycle. The previous accumulation value (S i−1 ) is a value calculated in i−1th cycle and is a value output from the register  1   210  in ith cycle. The calculated quotient (q i ) is newly updated to the register  2   220 . 
     In an operation ACC of calculating an accumulation value of ith cycle, the accumulator  240  receives a previous accumulation value (S i−1 ) a previous quotient (q i−1 ), a bit (b i ) of multiplier, an operand A, and a modulus M to calculate an accumulation value (S i ). Herein, the previous accumulation value (S i−1 ) is output from the register  1   210  and the previous quotient (q i−1 ) is output from the register  2   220 . The previous quotient (q i−1 ) is a value calculated in i−1th cycle. The calculated accumulation value (S i ) is newly updated to the register  1   210 . With this, a modular multiplying operation of ith cycle is completed. 
     In the modular multiplication operation in accordance with an exemplary embodiment, an operation of calculating a quotient is faster by one cycle than that of the modular multiplication operation illustrated in  FIG. 1 . 
       FIG. 5  is a flow chart illustrating a modular multiplication method of modular multiplier using a pipeline method according to an exemplary embodiment. Referring to  FIG. 5 , a modular multiplication method is as follows. 
     The modular multiplier  100  or  200  calculates a quotient (q i−1  or q i ) using a previous accumulation value (S i−1 ) (operation S 110 ). The calculated quotient may be used for calculating an accumulation value in a next cycle. The modular multiplier  100  or  200  calculates an accumulation value S i  using a previous accumulation value (S i−1 ), a previous quotient (q i−2  or q i−1 ), a bit (b i ) of multiplier, an operand A, and a modulus M (operation S 120 ). 
     According to an exemplary embodiment, in a current cycle, a step of calculating a quotient and a step of calculating an accumulation value can be independently performed. For example, in case of  FIG. 1 , a calculation operation of the accumulation value S i  and a calculation operation of the quotient q i−1  have a mutual interdependence between them. However, since result values of calculation operations are stored in the registers  110  and  120 , and then are used as input values for each other, a calculation operation of the accumulation value S i  and a calculation operation of the quotient do not affect a critical path of each other. That is, in one cycle, a calculation operation of the accumulation value S i  and a calculation operation of the quotient q i−1  are independently performed. In case of  FIG. 3 , a calculation operation of the accumulation value S i  and a calculation operation of the quotient q i  are independently performed in one cycle. 
     Consequently, the modular multiplication method according to an exemplary embodiment can remove a step of calculating a quotient from a critical path by independently performing a step of calculating a partial product and a step of calculating a quotient. 
       FIG. 6  is a block diagram illustrating a memory system  1000  including a crypto processor having a Montgomery multiplier according to an exemplary embodiment. Referring to  FIG. 6 , the memory system  1000  includes a central processing unit (CPU)  1100 , a crypto processor  1200 , a buffer memory  1300 , a code memory  1400 , a nonvolatile memory interface  1500 , and at least one nonvolatile memory  1600 . 
     The CPU  1100  controls an overall operation of the memory system  1000 . The crypto processor  1200  decodes a command that enables a code (e.g., certification or an electronic signature) and processes data according to a control of the CPU  1100 . The crypto processor  1200  includes at least one of the modular multipliers  100  and  200  illustrated in  FIGS. 1 and 2 . The buffer memory  1300  can store data used for driving the memory system  1000 , for example, input/output data or data used in a code process. The buffer memory  1300  can be embodied by a volatile memory device such as dynamic random access memory (DRAM), static random access memory (SRAM), etc. The code memory  1400  may store code data used for operating the memory system  1000  or may store a secure module and a modulus for data to be protected such as key used for an electronic signature. The code memory  1400  may be embodied by a nonvolatile memory device such as read-only memory (ROM), parameter random access memory (PRAM), etc. The nonvolatile memory interface  1500  performs an interface with at least one nonvolatile memory device  1600 . The nonvolatile memory device  1600  stores user data. 
     The memory system  1000  in accordance with an exemplary embodiment can process data more quickly as compared with a related art memory system by removing a process of calculating a quotient when performing a modular multiplication operation. Details about constitution of the memory system  1000  may be as disclosed in U.S. Pat. Nos. 7,802,054, 8,027,194, 8,122,193, U.S. Patent Application Publication No. 2007/0106836, and U.S. Patent Application Publication No. 2010/0082890, which are incorporated herein by reference in their entireties. 
     In a modular multiplier and a modular multiplying method thereof according to an exemplary embodiment, the maximum operation frequency of a public key can be maximally doubled by removing a calculation process of reduction determination from a critical path of a Montgomery multiplication algorithm. 
     While not restricted thereto, an exemplary embodiment can be embodied as computer-readable code on a computer-readable recording medium. The computer-readable recording medium is any data storage device that can store data that can be thereafter read by a computer system. Examples of the computer-readable recording medium include read-only memory (ROM), random-access memory (RAM), CD-ROMs, magnetic tapes, floppy disks, and optical data storage devices. The computer-readable recording medium can also be distributed over network-coupled computer systems so that the computer-readable code is stored and executed in a distributed fashion. Also, an exemplary embodiment may be written as a computer program transmitted over a computer-readable transmission medium, such as a carrier wave, and received and implemented in general-use or special-purpose digital computers that execute the programs. Moreover, it is understood that in exemplary embodiments, one or more of the above-described elements can include circuitry, a processor, a microprocessor, etc., and may execute a computer program stored in a computer-readable medium. 
     The above-disclosed exemplary embodiments are to be considered illustrative, and not restrictive, and the appended claims are intended to cover all such modifications, enhancements, and other exemplary embodiments, which fall within the true spirit and scope of the inventive concept. Thus, to the maximum extent allowed by law, the scope of the inventive concept is to be determined by the broadest permissible interpretation of the following claims and their equivalents, and shall not be restricted or limited by the foregoing detailed description.