Patent Publication Number: US-8527570-B1

Title: Low cost and high speed architecture of montgomery multiplier

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application claims the benefit of U.S. Provisional Application No. 61/233,432, filed on Aug. 12, 2009. 
     This application is related to U.S. patent application Ser. No. 12/713,297, filed on Feb. 26, 2010. The disclosures of the above applications are incorporated herein by reference in their entirety. 
    
    
     FIELD 
     The present disclosure relates to cryptography systems and methods, and more particularly to Montgomery multiplier architectures in cryptographic systems and methods. 
     BACKGROUND 
     The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent the work is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure. 
     Cryptographic systems for data communication and storage may use public key cryptography. In public key cryptography, data may be encrypted and decrypted with a pair of keys. For example, a public key and a private key may be used to encrypt and decrypt the data, respectively. It is extremely difficult to derive the private key from the public key. Cryptography systems that use public key cryptography include, for example, Rivest, Shamir, and Adleman (RSA) cryptography and elliptic curve cryptography (ECC) over prime fields. 
     In public key cryptography, plain text data is encrypted into cipher text using the public key at a first node. The cipher text is transmitted to a second node. At the second node, the cipher text is decrypted into the plain text data using the private key. 
     For example, to generate the public key (n, e) in RSA cryptography, two distinct prime numbers of similar bit length p and q are selected. A modulus n=pq is calculated and used for both the public and private keys. The integer e is selected based on 1≦e≦φ(pq), where e and φ(pq) share no divisors other than 1 (i.e. e and φ(pq) are co-prime), and φ corresponds to Euler&#39;s totient function. The private key (n, d) corresponds to de≡1 (mod φ(pq)). 
     To encrypt a message M into cipher text at the first node, the message M is changed to an integer 0≦m≦n using a padding scheme. The cipher text c is calculated according to c=m e  mod n and transmitted to the second node. At the second node, m is recovered according to m=C d  mod n, and M is recovered from m according to the padding scheme. 
     Accordingly, ECC and RSA cryptography each involve multiplication and division of large operands. For example, for c=m e  mod n, m is multiplied by itself e times, and reduced modulo n after each multiplication. In arithmetic computation, Montgomery multiplication is typically used when the modulus is large (e.g. 128 to 1024 bits). 
     For example, Montgomery multiplication of two integers X and Y with a modulo M (e.g. MM(X, Y, M)) and n bits of precision results in a number Z according to Z=MM(X, Y, M)=XY2 −n  mod M, where M is an integer between 2 n−1  and 2 n  and n is an integer (e.g. typically n=[log 2 M]+1). In RSA cryptographic systems, M is the product of the prime numbers p and q as described above. In elliptic curve cryptographic systems over prime fields, M is a large prime number. Accordingly, M is an odd number. 
     Referring now to  FIG. 1 , Montgomery multiplication may be performed according to an example radix-2 Montgomery multiplication method  10 . In the method  10 , S i  is a partial sum for loop i of n loops, and q (0 or 1) is selected such that S+XY+qM is divisible by 2. In each loop i, if S[i+1]+x i ·Y is odd, then M is added to the result. Further, a shift register storing X (as a plurality of words x i ) is shifted to the right by 1. Accordingly, the partial sum stored as S[n] after n loops is less than or equal to 2M. 
     The calculation in step  4  of the method  10  may be performed using a carry-save adder, which includes double registers to store partial sums and carries. Alternatively, large operands in step  4  may be split into smaller operands that can be processed using a pipelined systolic array. Adjacent processing elements (PE) interchange the least significant bit (LSB) of the partial sum or the carry in two processing cycles. Accordingly, the latency of one Montgomery multiplication is approximately 2n cycles, where n is the bit size of the operands. (See A. Tenca and C. K. Koc, “A scalable architecture for Montgomery multiplication,”  CHES  99 , Lecture Notes in Computer Sciences,  1717, pp. 94-108, 1999; A. Tenca, G. Todorov, and C. K. Koc, “High-radix design of a scalable modular multiplier,”  CHES  2001 , Lecture Notes in Computer Sciences,  2162, pp. 185-201, 2001; and A. Tenca and C. K. Koc, “A scalable architecture for modular multiplication based on Montgomery&#39;s algorithm,”  IEEE Trans. Computers,  52(9), pp. 1215-1221, 2003). 
     The architecture can be optimized via pre-computing the partial sum using two possibilities for the most significant bit (MSB) from the previous PE. Accordingly, the latency can be reduced to n cycles with a marginal increase in area. (See M. Huang, K. Gaj, S. Kwon, and T. El-Ghazawi, “An optimized hardware architecture for the Montgomery multiplication algorithm,”  Proc.  11 th    International Workshop on Practice and Theory in Public Key Cryptography , PKC 2008, Barcelona, Spain, pp. 214-228, March 2008). Regardless of which architecture is used, a large number of flip flops are required to perform the Montgomery multiplication. Consequently, Montgomery multiplier architecture requires a large chip area to accommodate the flip flops. 
     SUMMARY 
     A system to perform Montgomery multiplication includes a first multiplier array configured to multiply w bits of an operand X by W bits of an operand Y, where w and W are integers and w is less than W. A second multiplier array is configured to multiply w bits of an operand Q by W bits of a modulo M. An adder array is configured to add outputs of the first and second multiplier arrays to generate a sum. A partial sum array is configured to store a left portion of the sum. A memory is configured to store a right portion of the sum. Q computation logic includes a lookup table and a half-multiplier that compute W bits of the operand Q sequentially in 
             2   ·     W   w           
cycles or
 
             W   w         
cycles. The W bits of the operand Q are stored in the fourth buffer for use by subsequent W×W operations.
 
     In other features, the systems and methods described above are implemented by a computer program executed by one or more processors. The computer program can reside on a tangible computer readable medium such as but not limited to memory, nonvolatile data storage, and/or other suitable tangible storage mediums. 
     Further areas of applicability of the present disclosure will become apparent from the detailed description, the claims and the drawings. The detailed description and specific examples are intended for purposes of illustration only and are not intended to limit the scope of the disclosure. 
    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
       The present disclosure will become more fully understood from the detailed description and the accompanying drawings, wherein: 
         FIG. 1  is a Montgomery multiplication method according to the prior art; 
         FIG. 2  illustrates a Montgomery multiplier system according to the present disclosure; 
         FIG. 3  is a Montgomery multiplication method according to the present disclosure; 
         FIGS. 4A ,  4 B, and  4 C are a functional block diagram of a Montgomery Multiplier according to the present disclosure; 
         FIG. 5  is a lookup table for calculating −m 0   −1  according to the present disclosure; 
         FIG. 6A  illustrates the lookup table and a half-multiplier according to the present disclosure; 
         FIG. 6B  illustrates modified architecture for calculating Q according to the present disclosure; 
         FIG. 7  is the method for calculating a parameter r=2 2n  mod M according to the prior art; 
         FIG. 8  is the method for calculating a parameter r=2 2n  mod M according to the present disclosure; and 
         FIG. 9  is a table illustrating a speed increase for calculating the parameter r according to the present disclosure. 
     
    
    
     DESCRIPTION 
     The following description is merely exemplary in nature and is in no way intended to limit the disclosure, its application, or uses. For purposes of clarity, the same reference numbers will be used in the drawings to identify similar elements. As used herein, the phrase at least one of A, B, and C should be construed to mean a logical (A or B or C), using a non-exclusive logical OR. It should be understood that steps within a method may be executed in different order without altering the principles of the present disclosure. 
     As used herein, the term module may refer to, be part of, or include an Application Specific Integrated Circuit (ASIC), an electronic circuit, a processor (shared, dedicated, or group) and/or memory (shared, dedicated, or group) that execute one or more software or firmware programs, a combinational logic circuit, and/or other suitable components that provide the described functionality. 
     Referring now to  FIG. 2 , a Montgomery multiplier (MM) system  100  includes an MM module  102  (which includes MM core logic) and memory, such as random access memory (RAM)  104 . Operands X and Y to be multiplied by the MM module  102  are stored in X and Y portions  106  and  108  of the RAM  104 . For example, if the operands X and Y are each 512 bits long, the respective X and Y portions  106  and  108  of the RAM  104  may store the operands as 8 words of 64 bits each (i.e. f words of W bits). Each word of W bits may be further separated into 8 words of 8 bits each (i.e. e words of w bits). Similarly, a modulo operand M is stored in an M portion  110  of the RAM  104  as f words of W bits each, and the segment Z of the result is stored in a Z portion  112 . The width of the RAM  104  is represented by w_RAM (i.e. the RAM  104  is w_RAM bits wide). 
     As such, the MM module  102  does not address the entire operands (e.g. X, Y, and M) during each cycle. Instead, the MM module  102  performs W×W multiplications sequentially (e.g. via a w×w multiplier array). In other words, the MM module  102  multiplies W bits of each of the operands X, Y, and M instead of addressing the entire operands. Consequently, fewer flip flops FF (FFs, e.g. D-FFs) are required, and less chip area is needed to accommodate the flip flops. A portion of the flip flops are replaced with RAM for storing portions of the operands that are not being multiplied in a particular cycle. In some implementations (e.g. when RAM bandwidth is limited), double buffers may be used to reduce data transfer overhead. For example, while the multiplication X i ×Y j  is performed, Y i+1  and M i+1  can be transferred to a D-FF buffer. 
     For example, when a word X i  of size W is multiplied by a word Y j  of size W, the lowest W bits of the product may be stored in RAM, and the highest W bits of the product may be stored in partial sum registers and carry registers within the MM module  102 . 
     Because W is generally large, Q i  of W bits (i.e. Q i  satisfying S i+1 =S i +X i ·Y+Q i ·M=0 mod 2 w ) can not be obtained directly from a lookup table (LUT). Instead, Q i  is computed sequentially (e.g. using Q calculation module  120  to compute w bits of Q sequentially) when performing the multiplication of X i  by Y 0  and stored in Q buffer  122 . Further, Q i  may be retrieved from the Q buffer  122  when scanning subsequent words of the operands Y and M. 
     When using Montgomery multiplication for either RSA or ECC cryptography, operands are converted to and from a Montgomery domain. A parameter r=2 2n  mod M, where n is the size of the operand, is used to perform the conversion. Accordingly, the MM module  102  participates in computing r. 
     Referring again to  FIG. 2 , an X buffer  124  receives the operand X from the RAM  104  and provides the operand X to a first multiplier array  126 . The X buffer  124  includes, for example, w_RAM bit or 2×w_RAM bit D-FFs (depending on the Q i  computation scheme). A double Y buffer  128  includes a Y buffer  130  that receives the operand Y from the RAM  104  and a Y buffer  132  that receives the operand Y from the Y buffer  130  and provides the operand Y to the first multiplier array  126 . The double Y buffer  128  includes 2×W bit D-FFs. A product of the first multiplier array  126  is provided to a first adder array  134 . 
     A double M buffer  140  includes an M buffer  142  that receives the modulo M from the RAM  104  and an M buffer  144  that receives the modulo M from the M buffer  142  and provides the modulo M to a second multiplier array  146 . The Q buffer  122  receives w bits of Q data that correspond to the operand Q from the Q calculation module  120  either each cycle or every other cycle and provides the w bits of Q data to the second multiplier array  146 . For example, the Q buffer  122  receives the w bits of Q data when an initial portion of M 0  of the modulo M is provided to the second multiplier array  146 . The Q buffer  122  retains the same W bits of Q data until calculations for X i ·Y f-1  and Q·M f-1  are complete. The Q buffer  122  includes W bit D-FFs. A product of the second multiplier array  146  is provided to the first adder array  134 . 
     An S L  buffer  150  includes W+1 bit D-FFs and a carry array (CA) buffer  152  includes ((3×W)/w)+1 bit D-FFs. The S L  buffer  150  and the CA buffer  152  update the leftmost W+1 bits of the partial sum and provide data to a second adder array  154 . An output of the second adder array  154  is provided to the first adder array  134 . 
     A Z buffer  160  receives data corresponding to the partial sum from the RAM  104  via a multiplexer  162 . The Z buffer  160  includes W bit D-FFs. If a size of the operand n is small, the Z buffer  160  may receive the data directly from an S R  buffer  164 . The Z buffer  160  provides the data to the first adder array  134  via a multiplexer  166 . The S R  buffer  164  includes w_RAM bit D-FFs to latch the rightmost bits of the partial sum received from the first adder array  134 . The S R  buffer  164  provides the rightmost bits of the partial sum to the RAM  104 . 
     A most significant bit (MSB) buffer  170  and a temporary (TEMP) buffer  172  include W+1 bit D-FFs. The MSB buffer  170  and the TEMP buffer  172  latch a sum of S L  and CA (received from the second adder array  154 ) after Y f-1  and M f-1  are processed. Accordingly, it is not necessary to store the sum of S L  and CA in the RAM  104 . Outputs of the MSB buffer  170  and the TEMP buffer  172  are provided to the first adder array  134  (via the multiplexer  166 ) when a next W bit word of the operand X, Y f-1 , and M f-1  are processed. When performing x 0 ·Y f-1 , the multiplexer  166  provides data from the MSB buffer  170  and the TEMP buffer  172  to the first adder array  134 . When performing x 0 ·Y j , in X i ·Y j  (i≠0, j≠f−1) the multiplexer  166  provides data from the Z buffer  160  to the first adder array  134 . Otherwise, the multiplexer  166  provides 0 to the first adder array  134 . 
     Referring now to  FIG. 3 , the MM module  102  performs Montgomery multiplication according to an example Montgomery multiplication method  200 . In the method  200 , the operand X is stored in RAM as f words of W bits (e.g. X=X 0 , X 1 , . . . , X f-1 ). Each X i  may be stored as e words of w bits (e.g. x 0 , x 1 , . . . , x e-1 ). The operand Y is stored in RAM as f words of W bits (e.g. Y=Y 0 , Y 1 , . . . , Y f-1 ). Each Y j  may be stored as e words of w bits (e.g. y 0 , y 1 , . . . , y e-1 ). The modulo M is stored in RAM as f words of W bits (e.g. M=M 0 , M 1 , . . . , M f-1 ). Each M j  may be stored as e words of w bits (e.g. m 0 , m 1 , . . . , m e-1 ). 
     An intermediate result is represented by (msb, Z), where msb is the most significant bit and is stored in a one bit D-FF. A final product Z is stored in RAM as f words of W bits (e.g. Z=Z 0 , Z 1 , . . . , Z f-1 ). For Z f-1 , the msb and its leftmost w bits form Z e-1 , and the remaining W-w bits of Z f-1  form z 0 , z 1 , . . . , z e-2 . Each of the remaining Z j  is stored as e words of W bits. S R  corresponds to the rightmost W bits of the partial sum after e cycles. When the number of the bits of S R  reaches the word size of the RAM, S R  is shifted into the RAM. S R  may be denoted as e words of w bits (e.g. s R, 0 , S R,1 , . . . , S R,e-1 ). 
     The leftmost W+1 bits of the partial sum corresponds to the sum of S L  and CA, where CA is the carry array Σ i=0   e-1 ca i ·2 w , and ca e-1  has 4 bits and the remaining c ai  each have 3 bits. S L  may be stored as e words (e.g. S L, 0 , S L,1 , . . . , S L,e-1 ), where S L,e-1  has w+1 bits and the remaining S L  words have w bits. Q i  is selected to satisfy S i+1 =S i +X i ·Y+Q i ·M=0 mod 2 w . The rightmost w bits of the product of two w bit numbers are shown as (•) R . Conversely, the leftmost w bits of the product of two w bit numbers are shown as (•) L . 
     The method  200  includes index loops i, j, g, and k. The loop of index i computes S i+1 =S i +X i ·Y+Q·M=mod M. The loop of index j separates Y and M into the W bit words that are scanned in each round (e.g. each iteration of the loop). The loop of index g performs W×W multiplications (e.g. X i ·Y j  and Q i ·M j ) and accumulation. To perform W×W multiplications, each factor of W bits is separated into w bit words, which are scanned in each round. 
     The loop of index k performs w×W multiplications (e.g. x g ·Y j  and q·M j ) and accumulation. Y j  and M j  are separated into w bit words, which may be multiplied by x g  and q simultaneously. The products of these multiplications are accumulated and shifted to partial sum and carry registers in one cycle. Accordingly, the w×W multiplications performed within the loop of index k may be performed in parallel. 
     The method  200  calculates Q i  while performing the X i ·Y 0  calculation. If the rightmost w bits s of S i +X i ·Y 0  are known, then the rightmost w bits of Q i  are calculated according to q 0 =s·(−m 0   −1 )mod 2 w , where m 0  corresponds to the rightmost w bits of M. For q 0 , the rightmost w bits of S i +X i ·Y 0 +q 0 ·M 0  are zeros. The second rightmost w bits of S i +X i ·Y 0 +q·M 0  are calculated according to s=(S i +X i ·Y 0 +q 0 ·M 0 )/2 w  mod 2 w . Then, q i =s·(−m 0   −1 ) mod 2 w  such that s+q 1 ·m 0 =0 mod 2 w . When q g  is determined, s may be updated according to s=(s+q g ·M 0 )/2 w  mod 2 w . Then, can be computed sequentially according to q g+1 =s·(−m 0   −1 )mod 2 w . After e loops of index g, Q i  may be determined and stored in shift registers. Accordingly, Q i  may then be used to perform multiplications such as Q i ·M j , where j≧1. 
     In steps  51 - 53  of the method  200 , the final reduction may be performed via a w_RAM (e.g. 32) bit subtractor and a one bit carry register. For example, intermediate results may be stored in the Y portion  108  of the RAM  104 . If a carry from the reduction is one, the contents of the Y portion  108  are determined to be the final result. Otherwise, the contents of the Z portion  112  are determined to be the final result. If a particular application requires that the contents of the X portion  106 , the Y portion  108 , and the Z portion  112  be retained, the RAM  104  may be extended to store the intermediate results of steps  51 - 53 . 
     In RSA and ECC cryptographic systems, M is always odd. Accordingly, −m 0   −1  mod 2 w  may be predetermined and stored. For example, −m 0   −1  mod 2 w  may be stored in (w−1)×2 w−1  read only memory (ROM). 
     Referring now to  FIGS. 4A ,  4 B, and  4 C, a Montgomery Multiplier (MM)  300  according to the present disclosure includes the multiplier arrays  126  and  146  and an adder array  306  (which includes, for example, the adder arrays  134  and  154  as shown in  FIG. 2 ). Each of the multiplier arrays  126  and  146  includes e (e.g. 8) w×w multipliers  310 . For example, the multiplier array  126  communicates with X and Y buffers  124  and  128  and performs W×W multiplications of X i ·Y j . Conversely, the multiplier array  146  communicates with M and Q buffers  140  and  122  and performs W×W multiplications of Q i ·M j . The adder array  306  performs additions shown in steps  15 ,  17 ,  30 ,  32 , and  37  of the method  200 . 
     The RAM  104  as shown in  FIG. 2  stores one or more of the operands (e.g. X i , Y j , and/or M j ) and results (e.g. sum Z i ). Portions of the operands being addressed in a particular cycle are transferred to corresponding ones of the X buffer  124 , the Y buffer  128 , the M buffer  140 , and the Z buffer  160 . For example, the portions of the operands being addressed are transferred from the RAM  104  to corresponding shift registers  322  in the X buffer  124  and shift registers  324  and  326  in the Y buffer  132  and the M buffer  144  (via shift registers  324 ′ and  326 ′ in the Y buffer  130  and the M buffer  142 , respectively). Similarly, the S R  buffer  164  and the Q buffer  122  may include shift registers  328  and  330 , respectively. 
     Outputs of the multiplier array  126  include, for example, the leftmost w bits  332  of the product of a w×w multiplication and the rightmost w bits  334  of the product of a w×w multiplication. The adder array  306  receives outputs of the multiplier array  126 , partial sums, carry bits, and intermediate results u 0 -u 7 . Outputs of the adder array  306  include, for example, the rightmost w bits  336  and the leftmost 3 bits  338  of the corresponding sum. 
     The MM  300  addresses Y j  and M j  in each cycle. For example, if a word size w RAM  of the RAM is less than W, then Y j  and M j  are transferred from the RAM  104  and stored in the shift registers  324 ′ and  326 ′. The RAM  104  stores Z j  (of the final product Z). Z j  is transferred from the RAM  104  in 
             W     w   RAM           
cycles. Accordingly, the MM  300  may accumulate Z j  while multiplying X i ·Y j . Multiple buffering may be used to eliminate data transfer overhead between the RAM  104  and logic of the MM  300 . When the MM  300  is performing operations on Y j , M j , and Z j , Y j+1 , M j+1 , and Z j+1  can be transferred to alternate shift registers. For example, the Y and M buffers  132  and  144  provide two words of Y j  and M j  for a current W×W multiplication, and the Y and M buffers  130  and  142  receive Y j+1  and M j+1  for a next W×W multiplication. The z buffer  160 , which includes shift registers  340 , receives Z i . The z buffer  160  stores Z j  for a current W×W multiplication, and subsequently stores Z j+1  for a next W×W multiplication.
 
     The values of W and w determine performance and cost of the MM  300 . For example, greater values correspond to an increase in processing speed and chip area, and therefore an increase in cost. Further, the value of w may be selected such that latency of data transfer from the RAM  104  is less than latency of one W×W multiplication. If the RAM  104  includes single-port RAM (i.e., one w bit word addressable per cycle), each word of X i , Y j , M j , or Z j  is transferable in 
             W     w   RAM           
cycles, and a single W×W multiplication is completed in
 
             W   w         
cycles. Accordingly, the value of w may be selected such that
 
                 4   ·     W     w   RAM         ≤     W   w       ⇒     ≤         w   RAM     4     .             
Conversely, if the RAM  104  includes dual-port RAM, w may be selected such that
 
     
       
         
           
             w 
             ≤ 
             
               
                 
                   w 
                   RAM 
                 
                 2 
               
               . 
             
           
         
       
     
     Since only w bits of X i  are used in each cycle, multiple buffering is not required for X i . Q i  may be calculated during multiplication of X i ·Y 0  and stored in the shift registers  330 . 
     The buffers of the MM  300  include arrays of D-FFs to store results of multiplications. For example, the MM  300  includes the S L  buffer  150 , the S R  buffer  164  (both the S L  buffer  150  and the S R  buffer  164  form a partial sum array), and the CA buffer  152  (i.e., a carry array). The S L  buffer  150  includes e segments (e.g., 8). A leftmost segment  354  is instantiated as w+1 bit D-FFs to store (q·m e-1 ) L +(x g ·y e-1 ) L . The remaining e−1 (e.g., 7) segments  356  are instantiated as w bit D-FFs. The S R  buffer  164  includes e segments. Although the rightmost e (e.g., 8) segments  358  of w bits are shown, the segments  358  may not be instantiated as D-FFs and are instead stored in the RAM  104 . For example, a number of segments n s1  storing S R  instantiated as D-FFs is based on w RAM . In other words, n s1  may be the smallest number satisfying n s1 ·w≧w RAM  because the data may be stored in the RAM  104  when the data amounts to, for example, one word of RAM. However, when i=0 and j=0, S R  will be all zeros and therefore is not written to the RAM  104 . The CA buffer  152  includes e segments. A leftmost segment  360  is instantiated as 4-bit D-FFs to store ca e-1 . The remaining e−1 segments  362  are instantiated as 3-bit D-FFs. For example, as shown in steps  30  and  34  of the method  200 , when k=e−1 and g=0: sum e-1 =s L,e-1 +ca e-1 +(x 0 ·y e-1 ) R +(x 0 ·y e-2 ) L +z e-1 +(q·m e-1 ) R +(q·m e-2 ) L    
     Each of S L,e-1  and z e-1  has w+1 bits and each of (x 0 ·Y e-1 ) R , (x 0 ·y e-2 ) L , (q·m e-1 ) R  and (q·m e-2 ) L  has w bits. The rightmost w bits of sum e-1  will be stored in D-FFs for and the leftmost 3 bits of sum e-1  will be stored in D-FFs for a following cycle. Accordingly, ca e-1  has at least 3 bits and sum e-1  has at least w+3 bits. To maintain sum e-1  as w+4 bits, ca e-1  should have 4 bits. Each remaining ca k  may include 3 bits. 
     A sum of the values stored in the S L  and CA buffers  150  and  152  (i.e., S L =(S L,e-1 , s L,e-2 , . . . , S L,2 , S L,1 , s L,0 )) and CA=(ca e-1 , ca e-2 , . . . , ca 1 , ca 0 )) corresponds to the leftmost W+1 bits for Z j +X i ·Y j +Q i ·M j +S L +CA. The leftmost bits of Z j +X i ·Y j +Q i ·M j +S L +CA are accumulated for a following operation Z j+1 +X i ·Y j+1 +Q i ·M j+1 S L +CA. The rightmost bits of Z j +X i ·Y j +Q i ·M j +S L +CA are transferred to the RAM  104  (except when j=0). 
     The MSB and TEMP buffers  170  and  172  are used to eliminate the latency of transferring the sum of S L  and CA (when j=f−1) to the RAM  104 , and the latency of transferring Z f-1  from the RAM  104  to the Z buffer  160 . When S L +CA is performed for j=f−1, the sum is stored in the MSB and TEMP buffers  170  and  172 . For example, the rightmost 64 bits of the sum of the S L  and CA buffers  150  and  152  are stored in shift registers  364  of the TEMP buffer  172 . The last carry of the sum of the S L  and CA buffers  150  and  152  is stored in the MSB buffer  170 . For j=f−1, the sum of S L  and CA is performed sequentially (e.g. because W is large and the operation can not be completed in one cycle) to obtain (msb, Z e-1 ). 
     However, if timing closure can be satisfied, the sum of S L  and CA can be performed in one cycle and stored in parallel-in-parallel-out buffers (e.g. the MSB buffer  170  and the TEMP buffer  172 ). In other words, in this case the TEMP buffer  172  may be implemented without shift registers because the sum can be completed in one cycle. The next time Z f-1  is loaded, the value can be input directly to the adder array  306  from the MSB and TEMP buffers  170  and  172 . 
     Referring now to  FIG. 4C , values of u 0  through u 7  are provided to the adder array  306  via multiplexers  366  and  368  (represented by the multiplexer  166  in  FIG. 2 ). The multiplexers  366  and  368  are responsive to, for example, 2-bit selector signals sel. The multiplexer  366  outputs u 7 . For example, when performing x 0 ·Y f-1 , the multiplexer  366  outputs the contents of the MSB buffer  170  and the contents of temp 7  of the TEMP buffer  172 . When performing x 0 ·Y j  in X i ·Y j (i≠0, j≠f−1), the multiplexer  366  outputs the contents of z 7  of the Z buffer  160  and a 0 bit. Otherwise, the multiplexer  366  outputs all zero bits. 
     The multiplexer  368  outputs u 0 -u 6 . For example, when performing x 0 ·Y f-1  the multiplexer  368  outputs the contents of temp 0  through temp 6  of the TEMP buffer  172 . When performing x 0 ·Y j  in X i ·Y j  (i≠0, j≠f−1), the multiplexer  368  outputs the contents of z 0  through z 6  of the Z buffer  160 . Otherwise, the multiplexer  366  outputs all zero bits. 
     The MM  300  calculates Q i  of W bits while performing the multiplication X i ·Y 0 . The MM  300  obtains w bits of Q i  every two cycles: one cycle to update s according to s=(s+q g ·M 0 )/2 w =2 w , and one cycle to determine q of w bits according to q g+1 =s·(−m 0   −1 )mod  2   w . For example, the MM  300  includes a lookup table (LUT)  370  and a w×w half multiplier  372 . The half multiplier  372  calculates a·b mod 2 w . The LUT  370  stores −m 0   −1 . The LUT  370  may be instantiated in, for example, read only memory. 
     Referring now to  FIG. 5 , the LUT  370  stores values of −m 0   −1  corresponding to input values of m 0  in address locations 0-127, where w=8. For example, to calculate q of w bits corresponding to Qi, −m 0   −1  mod 2 w  (where m 0  is the rightmost w bit word of the modulo M) must first be determined. When w is small (e.g. 8), −m 0   −1  may be stored in a LUT of size (w−1)×2 w−1  (where M and −m −1  mod 2 w  are odd). However, for higher speed operations, the multiplier size w may be larger. For example, if the multiplier is 2w, the size of a LUT will increase by a factor of 2 w+1 . 
     Because M does not change frequently when performing high-level operations in RSA and ECC cryptography systems, −m 0   −1  can be pre-calculated and stored in a 2w bit buffer. For a fixed modulo M, the pre-calculation of −m 0   −1  may be performed only once prior to Montgomery multiplication. When m 0 =m 0L ·2 w +m 0R  (where 0≦m 0L , m 0R ≦2 w −1), −m 0   −1  mod 2 2w =m L ·2 w +M R  (where 0≦m L , m R ≦2 w −1) is calculated to satisfy m 0 ·(−m 0   −1 )=−1 mod 2 2w . As such, can be determined according to m R =−m 0R   −1  mod 2 w . 
     Referring now to  FIGS. 5 and 6 , the LUT  370  stores m R , where the leftmost w−1 bits of m 0R  are the read address of the LUT  370 , and the leftmost w−1 bits of m R  are the output of the LUT  370 . The relationship (m 0L ·2 w +m OR )·(m L ·2 W +m R )+1=0 mod 2 2w  can be reduced to determine m L  according to:
 
( m   0L   ·m   R   +m   0R   ·m   L )·2 w   +m   0R   ·m   R +1=0 mod 2 2w  
 
( m   0L   ·m   R   +m   0R   ·m   L )+( m   0R   ·m   R ) L +1=0 mod 2 w  
 
 m   L   =m   R ·(1+( m   0L   ·m   R ) R +( m   0R   ·m   R ) L )mod 2 w ,
 
     where (•) L  indicates the leftmost w bits of the product and (•) R  indicates the rightmost w bits of the product. 
     As shown in  FIG. 6A , the LUT  370  receives the leftmost w−1 bits of M 0R  and outputs m R  (where m R ≡−m 0R   −1  mod 2 w ). The half multiplier  372  calculates m L =m R ·(1+(m 0L ·m R ) R +(m 0R ·m R ) L )mod 2 w . For example, a multiplier  400  multiplies the w bits of m 0R  by m R . A multiplier  402  multiplies the w bits of m 0L  by m R . An adder  404  outputs a sum of the leftmost w bits of the product of the multiplier  400 , the rightmost w bits of the product of the multiplier  402 , and 1. A multiplier  406  multiplies the sum output by the adder  404  by m R  and outputs m L . An output of the half multiplier  372  combines m R  and m L  to form −m 0   −1 =(m L , m R ) of 2w bits. When the bit width of m 0  is large (e.g. 16), the circuitry shown in  FIG. 6A  is used to calculate −m 0   −1 . Conversely, when the bit width of m 0  is small (e.g. 8), the circuitry shown in  FIG. 6A  is not necessary and the LUT  370  may be sufficient for determining −m 0   −1 . 
     Referring now to  FIG. 6B , a modified architecture  450  for calculating q in one cycle is shown. Before calculating X i ×Y 0 , a cycle is used to obtain q 0 . Accordingly, the rightmost bits  334  of the result from x 0 ×y 0  are added to u 0  (the S L  and CA buffers are zero during the first multiplication of X i ×Y 0 , and the multiplexer  166  selects zero if i is zero) and provided to the half multiplier  372 . A comp_q 0  signal, which indicates that q 0  calculation, is generated as a select signal for the multiplexer  452 . 
     In the subsequent x i ×Y 0  calculations, x i+1  and y 0  are provided to half multiplier  454 . The output of the half multiplier  454  is added to the carry  338  and partial sum  339  (which will be latched into the rightmost 3 bits of the CA buffer  152  and the rightmost w-bits of the S L  buffer  150 ) and provided to the half multiplier  372 . The output of the half multiplier  372  is q i+1 . The comp_q 0  signal is transitioned off to select the desired path at the multiplexer  452 . 
     Referring now to  FIG. 7 , when using Montgomery multiplication for either RSA or ECC cryptography, operands are converted to and from a Montgomery domain. A parameter r=2 2n  mod M, where n is the size of the operand, is used to perform the conversion. Conventionally, r may be determined according to the method  500 . 
     Referring now to  FIG. 8 , the MM  300  of the present disclosure calculates r according to the method  600 , which calculates r by performing Montgomery multiplication recursively. As shown in the method  500 , the operands are multiplied by r=2 2n  mod M. In steps  1 - 15 , the method  600  determines r←2 n+s  mod M via an improved reduction (maximum number of iterations is less than or equal to s). In steps  16 - 18 , the method  600  determines r←MM (r, r) using Montgomery multiplication, where MM indicates the Montgomery multiplication. After t iterations of r←MM(r, r), r← 2   n+2t·s  is obtained. 
     A value of s is selected based on a speed ratio between the MM  300  and a word subtractor associated with the reduction in steps  1 - 7  of the method  600 . For example, if T MM  is the latency in cycles for one Montgomery multiplication, then 
               T   MM     ≤       n     w   RAM       ·     s   .             
An integer t is selected based on t=log 2 n/s. Because t=log 2 n/s is an integer, s may be selected as the smallest number satisfying
 
               T   MM     ≤       n     w   RAM       ·   s           
and
 
             n   s         
is a power of 2. T MM  is determined based on the values of W and w according to
 
     
       
         
           
             
               T 
               MM 
             
             = 
             
               
                 3 
                 · 
                 
                   W 
                   
                     w 
                     RAM 
                   
                 
               
               + 
               
                 
                   n 
                   W 
                 
                 · 
                 
                   ( 
                   
                     
                       n 
                       W 
                     
                     + 
                     1 
                   
                   ) 
                 
               
               + 
               
                 
                   n 
                   
                     w 
                     RAM 
                   
                 
                 . 
               
             
           
         
       
     
     For a first W×W multiplication performed by the method  600 , transferring three W bit words of X 0 , Y 0 , and M 0  takes 
               3   ·     W     w   RAM         ⁢     cycles   .           
A W×n multiplication of X i ·Y takes
 
               n   w     +   1         
cycles. Accordingly, a total number of W×n multiplications to be performed is
 
     
       
         
           
             
               n 
               W 
             
             . 
           
         
       
     
     Referring now to  FIG. 9 , table  602  illustrates the speed increase for calculating r using the method  600  with respect to the method  500  where W=128, w=8, and w RAM =32. For example, for n=128, 256, 512, 1024, 1024, and 2048, the method  600  calculates r 3.4, 4.2, 4.8, 5.1, and 5.2 times faster, respectively, than the method  500 . The method  600  can be stored in, for example, ROM. 
     As described, the Montgomery multiplier of the present disclosure can perform Montgomery multiplications with operand sizes ranging from 2 to n by specifying how many W-bit words the operands include. A size of the operands (i.e. how many W-bit words) may be adjusted dynamically. For example, when the operand size is 128 bits, W=64, and n=1024, it is not necessary to add  896  zeroes to the 128 bit operand to form a 1024 bit operand. Instead, a size mode may be selected according to the size of the operand. For example, a size mode register may be programmed with a 2 to indicate 2 64 bit words. In this manner, the Montgomery multiplier can be shared between ECC cryptography systems (having bit boundaries of 128, 192, 224, 256, 384, 512, etc. bits) and RSA cryptography systems (having bit boundaries of 512, 1024, 2048, etc. bits). 
     The broad teachings of the disclosure can be implemented in a variety of forms. Therefore, while this disclosure includes particular examples, the true scope of the disclosure should not be so limited since other modifications will become apparent upon a study of the drawings, the specification, and the following claims.