Low cost and high speed architecture of montgomery multiplier

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.

The present disclosure relates to cryptography systems and methods, and more particularly to Montgomery multiplier architectures in cryptographic systems and methods.

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'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'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.

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.

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.

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

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

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.