Montgomery modular multiplier and method thereof

A method for power reduction and increasing computation speed for a Montgomery modulus multiplication module for performing modulus multiplication. A coding scheme reduces the hamming distance for partial product and multiple modulus selection, reducing MUX operations and power consumption. Synchronization registers synchronize partial product and multiple modulus values input to an accumulator reducing glitch and/or increase computation speed. Registers provide storage of previous values and reduce the need to obtain the values from a MUX, reducing MUX operations and/or reducing power consumption.

CROSS-REFERENCE TO RELATED APPLICATIONS

The present application claims priority from a Korean application having Application No. P2003-29445, filed 9 May 2003 in Korea, the disclosure of which is incorporated herein in its entirety by reference.

FIELD OF THE INVENTION

The present invention relates to the field of cryptosystems and, more particularly, to a Montgomery modular multiplier.

BACKGROUND OF THE INVENTION

As the use of network systems grows, protection of network communications becomes more important. Protection of the integrity and secrecy of data becomes an issue.

The basic process of code transporting, and decoding a message includes taking the message (plaintext), modifying (encrypting) the plaintext into ciphertext, transmitting the ciphertext to a receiver, and de-modifying (decrypting) the ciphertext, to recover the original message.

In cryptosystems, an encryption key is used to encrypt the plaintext. The ciphertext is transmitted to a receiver, and the receiver decrypts the ciphertext, using a decryption key, back to the original plaintext. The encryption key and the decryption key are often referred to as key-pairs.

For example, public and private key-pairs can be functions of two or more large prime numbers. Each function, encryption and decryption, relies on the large prime numbers and each set is referred to as a key-pair. There are two keypairs (P, Q) for a complete system (encrypt then decrypt). To increase the security, the word-length of P and Q may be chosen to be equal, so that they can not be distinguished based on bit length, and then the product M is computed:
M=P*Q.(1)

An encryption key KEis randomly chosen such that KEand (P−1)(Q−1) are relatively prime. Accordingly, the decryption key KDcan be computed using an extended Euclidean algorithm that satisfies:
KD=KE−1mod((P−1)(Q−1)).  (2)

The numbers KDand Mmay also be relatively prime. The numbers (KE, M) may be the encryption key (or public key) used for data encryption, and the numbers (KD, M) are the decryption key used for decryption. After the keys are generated, the original message is encrypted by performing the computation of:
C=TKEmodM,(3)

where T is the original message (plaintext) and C is the encrypted message (ciphertext). To decrypt the encrypted data, the following computation is performed:
T′=CKDmodM,(4)

where T′ is the decrypted message. T′ should be the same as the original message T. As can be seen, several modular multiplications are performed.

In some encryptsystems, a long word-length, generally more than 512 bits, is usually employed to meet security requirements. However, speed performance is limited by the long word-length, requiring increasing computational speeds. For speed of computation, fast exponential computation becomes increasingly important. There are several methods, such as H-algorithm, L-algorithm, etc., which can be used to accelerate the exponential computation. One such method is the Montgomery modular multiplication algorithm, which can be used as a kernel operation in high-performance exponent-computation algorithms. The Montgomery modular multiplication algorithm also improves the efficiency of encryption and decryption operations.

The Montgomery modular multiplication algorithm is provided to compute the resulting n-bit number:
SN=A*B*R−1modM, (where the radixR=2n)  (5)

required in the modular exponential algorithm, where A, B and M are the multiplicand, multiplicator, and modular number, respectively, and each has n bits. An exemplary radix 2 Montgomery iterative modular multiplication algorithm is:

where bIA(=PPI) is a partial product; qIM=(MMI) is a multiple of modulus M which makes one least significant bit (LSB) of SPPI(=I=PPI) into a zero(0) value; n is the bit length of modulus M; N=n/2; SIis the partial accumulated result of a previous cycle; SI+1is the partial accumulated result of the current cycle with n bits; and SNis the final computation result. An exemplary radix-4 Montgomery iterative modular multiplication algorithm is:

where N=n/2; (−M*M′)mod 4=1; and −M is the 2's-complement of M. Both the radix-2 and the radix-4 process are iterative processes producing iterative data; data whose value changes with iterations within the loop of I=0; I<N; I++. The modular operation speed affects the system performance. Therefore, if the bit length is very long, the system performance is degraded. To compute MMI(=qIM), first the PPI(=bIA) is computed and then the computed PPIand SIare added. Therefore, power consumption is increased because the accumulator executes the logical computation twice.

A hardware implementation of a conventional Montgomery modular multiplication algorithm is shown inFIG. 1, which utilizes two carry propagate adders91and92(hereinafter abbreviated as CPAs). The first CPA91is provided for a multiplication operation, and receives a previous computation result and a result of aiANDed with B outputted from an AND logic93that receives the ajand B. The second CPA92is provided for a modular operation, and receives the output of the result of the first CPA91and a result of qiANDed with N from an AND logic94. The output of the CPA92is shifted to right by one bit with a shifter95, so as to divide the output result by 2, thereby generating the computation result for one iteration.

To complete a 512-bit Montgomery modular multiplication, there are 512 iterations, which can be temporally expensive. As a result, the speed of a 512-bit RSA en/decryption is still slower than the current network transmission bandwidth speed.

The Montgomery modular multiplication may be time-consuming and affects the operation in digital appliances including cryptographic computation devices. To manufacture high performance digital appliances, it is often necessary to improve the speed of the modular operation.

In addition to speed, an additional concern is power consumption. A low power consumption is desirable, for example in smart card and mobile products, low power consumption becomes more important. Smart card and mobile products use cryptographic computation devices to secure data (contents) and improving the efficiencies of the devices can improve the power consumption characteristics of these devices. Additionally computational devices consume a lot of power, and the majority of the power is consumed by modular multiplication. In particular, as the bit length increases, the more power is required in the modular operation.

SUMMARY OF THE INVENTION

Exemplary embodiments of the present invention provide for methods of accelerating the speed of Montgomery modular multiplication and/or reducing power consumption by using register pipelines and/or manipulating the arrival time of data to the accumulator.

In exemplary embodiments of the present invention, a pipeline method can be used in a Booth recoder of the Montgomery multiplier to accelerate the speed of the Montgomery modular multiplication.

In exemplary embodiments of the present invention the arrival of a partial product of the I-th iteration (PPI) and a multiple of modulus of the I-th iteration (MMI) at the accumulator at nearly the same time, aids to reduce the power consumption in the Montgomery modular multiplication. Thus, the computational operation of the accumulator is decreased.

In exemplary embodiments of the present invention, the use of a feedback register reduces the number of multiplex operations. If the partial product PPIor multiple modulus MMIvalue of a current iteration is selected “0”, where “0” means it does not have to be added, the value of previous iteration is used without a multiplex operation. Thus, multiplex operations (where the number of multiplex operations is more than “n”) are unnecessary.

In exemplary embodiments of the present invention, an average Hamming distance is reduced, where the Hamming distance is the number of different values of the same bit position. Thus, fewer bit changes can result in the reduction of the variation of fan-out (multiplexer) loading.

The following description of exemplary embodiment(s) is merely illustrative in nature and is in no way intended to limit the invention, its application, or uses.

FIG. 2illustrates a modular multiplier1000of an exemplary embodiment of the present invention. The multiplier1000can include a modulus (M) stored in a register1, a multiplicand (A) stored in a register3, a multiplicator (B) stored in a register7, a Booth processor301, a Modulus processor300, a multiplexer (MUX)10aiding in the computation of the multiple modulus MMI, a MUX20aiding in the computation of the partial product PPI, and an accumulator100for aiding in the computation of the modular multiplication. The accumulator100inputs a partial product value PPIand the multiple modulus value MMIand produces a result for the Montgomery multiplier. In exemplary embodiments of the present invention, the positive value M can have n bits (M[n−1:0]). The positive or negative value A can have n+1 bits (A[n:0]), one bit for a sign bit. Finally, B can be positive or negative. Thus, if n is even B has n+2 bits, two bits being sign bits or if n is odd B has n+1 bits, one bit being a sign bit.

In exemplary embodiments of the present invention, register1provides the modulus M andM, whereMis the one's complement of M. Similarly register3provides the multiplicand A andA, whereAis the one's complement of A.

The multiplier1000solves the modular multiplication, as shown according to Equation (5), in an iterative process. The Modulus processor300and a multiplexer10are used to select multiple modulus (MMI) values. To select MMIvalues, the Modulus processor300receives iterative data from the accumulator100. The iterative data, SPPI[1:0], is the combination of the two LSBs of the value in a sum registry of the accumulator (SI[1:0]), and the two LSBs of the partial product value (PPI[1:0]). SI[1:0] and PPI[1:0] are combined in a 2-bit adder40to form SPPI[1:0]. In addition to SPPI[1:0] the Modulus processor300inputs the second significant bit of the Modulus, M[1]. The Modulus processor300uses SPPI[1:0] and M[1] to generate output signals, which determine the selection of a multiple modulus MMIvalue. In further exemplary embodiments of the present invention, the SPPIvalue can be the combination of more than two values and/or multiple number of bits, the example given herein should not be interpreted as limitative of the scope of the present invention.

The Modulus processor300can output multiple signals (e.g., a multiple modulus selection signal SEL_MM[1:0], a multiple modulus enabling signal EN_MM, a multiple modulus negation signal NEG_MM, . . . ). These signals may be stored in register230. For example, multiple modulus selection signal SEL_MM[1:01] may be stored in sub-register62, while multiple modulus enabling signal EN_MM may be stored in sub-register63. In an exemplary embodiment of the present invention, the Modulus processor300and multiplexer10are used to select multiple modulus values (MMI) values (e.g., 2M, M, 0. −M, . . . ) to supply to the accumulator100. To select MMIvalues, the Modulus processor300outputs multiple modulus selection signal SEL_MM[1:0] to the multiplexer10. The multiplexer10receives the value of the Modulus M and SEL_MM[1:0] and outputs a value to AND gate31. The AND gate31receives the input from the multiplexer10and a multiple modulus enabling signal EN_MM from the Modulus processor300. The AND gate31then outputs the value of MMI. The multiple modulus negation signal NEG_MM and MMIare combined at the accumulator100, where NEG_MM is used to indicate bit-inversion, obtaining a MMIvalue of −M.

Each MUX operation consumes power and energy, hence when a new SEL_MM[1:0] value is used, a MUX operation is performed to change the settings and select a MMIvalue. Using the previous value of SEL_MM[1:0] results in no change in settings and thus no MUX operation. Reducing the necessary number of MUX operations in MMI's selection decreases the overall power consumption of the multiplier1000.

In exemplary embodiments of the present invention, the Modulus processor300further includes a multiple modulus feedback register61and a Modulus recoder70. The feedback register61stores the value of SEL_MM[1:0] of the previous iteration as the value SEL_MM_D[1:0]. When the value of MMI=0 is desired, the modulus processor300outputs a multiple modulus enabling signal, EN_MM, with a value of 0. The signal EN_MM is input to an AND gate31. The AND gate31inputs the output of the multiplexer10, which uses the previous value of the multiple modulus selection signal SEL_MM_D[1:0], hence using no MUX operations, and the AND gate31outputs a value of MMI=0. The assignment of MMI=0 without a MUX operation decreases the power consumption of the multiplier1000. A coding scheme similar to that described above is shown inFIG. 3.

FIG. 3illustrates a coding scheme in accordance with exemplary embodiments of the present invention. AlthoughFIG. 3shows three inputs to the Modulus recoder70, the present invention can have a variety of inputs and outputs depending upon the design criteria, for exampleFIG. 2shows an additional input SEL_MM_D[1:0]. The coding scheme inFIG. 3illustrates that for values of EN_MM=0 the selected MMIvalue is 0, and the value of SEL_MM[1:0]=SEL_MM_D[1:0].

In another exemplary embodiment of the present invention, a similar method of power reduction can be used with the Booth processor301. As mentioned above, the multiplier1000solves for modular multiplication in an iterative process, which includes the supply of MMIand partial product values (PPI) to the accumulator100. The Booth processor301and multiplexer20are used to select partial product (PPI) values (e.g. 0, A, 2A, −2A, −A, . . . ) to supply to the accumulator100. The Booth processor301inputs the two LSBs of the multiplicand (A[1:0]), the two LSBs of the multiplicator (B[1] and B[0]) and B[r], a previous iteration's value of B[1].

To select PPIvalues, the Booth processor301outputs a partial product selection signal SEL_PP[1:0] to the multiplexer20. The multiplexer20receives the value of the multiplicand A and partial product selection signal SEL_PP[1:0] and outputs a value to an AND gate32. The AND gate32receives the input from the multiplexer20and a partial product enabling signal EN_PP from the Booth processor301. The AND gate32then outputs the selected value of the partial product (PPI), which is supplied to the accumulator100. Analogous to the procedure as discussed above, the Booth processor301may include a Booth recoder80and a partial product feedback register64. A zero value of PPIcan be selected by storing SEL_PP_D[1:0], a previous value of SEL_PP[1:0], in the partial product feedback register64. When the value of PPI=0 is desired, the Booth processor301outputs a partial product enabling signal EN_PP with a value of 0. The signal EN_PP is input to an AND gate32. The AND gate32inputs the output of the multiplexer20, which uses the previous value of the multiple modulus selection signal SEL_PP_DE[1:0], hence using no MUX operations, and the AND gate32outputs a value of PPI=0. The assignment of PPI=0 without a MUX operation decreases the power consumption of the multiplier1000. A coding scheme similar to that described above is shown inFIG. 4.

FIG. 4illustrates a coding scheme in accordance with exemplary embodiments of the present invention. AlthoughFIG. 4shows three inputs to the Booth feeedef Recoder70, the present invention can have a variety of inputs and outputs depending upon the design criteria. For example,FIG. 2shows additional inputs SEL_PP_D[1:0] and A[1:0]. The coding scheme inFIG. 4illustrates that for values of EN_PP=0, the selected PPIvalue is 0, and the value of SEL_PP[1:0]=SEL_PP D[1:0]. Output values of PPI[0] shown include 0 and A[0], while output values of PPI[1] shown include 0, A[0], and A[1]{circle around ( )}A[0] (A[1] exclusive-OR A[0]).

Additionally, in exemplary embodiments of the present invention, a coding scheme, an example of which is illustrated inFIG. 4, reduces an average Hamming distance. The Hamming distance is the number of different values of the same bit position. For examples, if SEL_PP[1:0] has the value “00”, corresponding to a PPIvalue of “A”, in the ( I−1)-th iteration then a value of SEL_PP[1:0] in the I-th iteration of “11” corresponding to a PPIvalue of “2A”, results in a Hamming distance of two (2). It is desirable to reduce the Hamming distance between two values and thus the number of bit inversions and computation power usage. By selecting a coding scheme where if a previous iteration PPIvalue is A or 2A, then the subsequent iteration PPIvalue is restricted and can not be 2A and if a previous iteration PPIvalue is −A or −2A, then the subsequent iteration PPIvalue is restricted and can not be −2A.FIG. 4illustrates various bit values for the coding scheme, however the coding scheme of exemplary embodiments of the present invention should not be interpreted to be limited to the bit pattern shown inFIG. 4. For example, a value of PPIfor “A” can correspond to a SEL_PP[1:0] value of 10 instead of the shown 00.

A similar Hamming distance coding scheme, as used for the selection of PPIvalues discussed above, can be applied for the selection of values of MMI.

AlthoughFIG. 2illustrates the use of 4:1 multiplexers, exemplary embodiments of the present invention are not limited to a particular ratio value of the multiplexer.

In conventional iterations, the Modulus processor300and the Booth processor301are run sequentially. However, the Booth processor301is isolated from the iterative nature of the solution of the multiplier1000. In an exemplary embodiment of the present invention the Booth processor301supplies the two LSBs of the partial product (PPI[1:0]), which is added to an accumulated result of previous iterations (SI[1:0]), supplied by the accumulator100, producing SPPI[1:0]. In other exemplary embodiments, various bits and number of bits can be used to produce SPPI. The value SPPI[1:0] is used by the Modulus processor, while register7(storing the value of B) is shifted to the right by two bits. After register7has been shifted, independent of the activity of the Modulus processor300, the new values of B[1], B[0], and B[r] are input to the Booth processor301. Thus, the Booth processor301can be operated while the Modulus processor300is operated. A pipeline register210stores the Booth processor(301)'s output SEL_PP[1:0], EN_PP, NEG_PP, and PPI[1:0] in sub-registers64-67, respectively. Pipeline registers improve the hardware performance of the multiplier by reducing the length of critical path. The above steps may be repeated until B[1] is the highest bit of multiplicator B. The simultaneous operation of the Booth processor301and the Modulus processor300increases the overall computational speed of the multiplier1000.

As discussed above, the multiplier1000inputs the multiple modulus MMIand the partial product PPI. Typically first PPIand then MMIare input to the accumulator100. To compute MMI, first the PPIis computed, a first logical operation, and then the PPIand SIare combined, a second logical operation, and then SEL_MM[1:0] and EN_MM are computed by the modulus processor, a third logical operation as discussed above. The two values PPIand MMIare not input at the same time because each travels a different circuit path. Therefore, power consumption is increased because the accumulator executes the logical operation twice. The power consumption can be reduced if the two values PPIand MMIarrive at the same or substantially the same time to the accumulator100.

In exemplary embodiments of the present invention, synchronization registers may be provided to synchronize the arrival time of PPIand MMIto the accumulator. The Booth processor301contributes SEL_PP[1:0] and EN_PP to multiplexer20and AND gate32respectively to select the partial product PPI, as discussed above. Likewise the Modulus processor300contributes SEL_MM[1:0] and EN_MM to multiplexer10and AND gate31respectively to select a multiple modulus value MMI. Saving values SEL_PP[1:0], EN_PP and/or SEL_MM[1:0], EN_MM, in synchronization register(s) allows the synchronization of MMIand PPI.

In an exemplary embodiment of the present invention, a multiple modulus synchronization register240and/or a partial product synchronization register220are provided. Syncronization registers220and240use reverse clock phase with respect to clock phase of other registers in multiplier1000. The multiple modulus synchronization register240may store values of SEL_MM[1:0] and EN_MM in sub-registers62and63respectively. If a partial product synchronization register220is used, it may store values of SEL_PP[1:0] and EN_PP in sub-registers68and69respectively. One or both synchronization registers can be used and the discussion herein should not be interpreted to limit the exemplary embodiments of the present invention to one synchronization register. In exemplary embodiments where both synchronization registers are used, SEL_PP[1:0] and SEL_MM[1:0] are stored in sub-registers68and62, respectively, while EN_PP and EN_MM are stored in sub-registers69and63, respectively. In response to a clock signal CK SEL_PP[1:0] is input to multiplexer20substantially at the same time as SEL_MM[1:0] is input to multiplexer10. Similarly, in response to the clock signal CK, EN_PP is input to AND nate32substantially at the same time as EN_MM is input to AND gate31. The outputs of the multiplexers20and10are generated substantially at the same time. Similarly, the outputs of AND gates32and31are generated substantially at the same time. Thus, MMIand PPIare synchronized and supplied to the accumulator100. Thus one logical operation can be performed per data set MMiand PPI, as opposed to the conventional two logical operations, significantly decreasing the power consumption of multiplier1000.

Variations and combinations of the exemplary embodiments of the present invention thus discussed are intended to be within the scope of the present invention.

Exemplary embodiments of the present invention are not limited by the Radix of the Montgomery multiplication; they can be used in a variety of Radix based multipliers. For example,FIG. 5illustrates a Radix-2 system having a multiple modulus synchronization (synch) register36and/or another synch register37, for storage of the multiplier value (B). As discussed above, synch registers36and37can be used to provide the accumulator200with substantially simultaneous values of PPIand MMIreducing the power consumption and increasing the speed of the multiplier2000. Additional exemplary embodiments of the present invention can use one or both synchronization registers.

The description of the invention is merely exemplary in nature and, thus, variations that do not depart from the gist of the invention are intended to be within the scope of the embodiments of the present invention. Such variations are not to be regarded as a departure from the spirit and scope of the present invention. For example multiplexers10and20can have a variety of ratio values. The multiple modulus synchronization sub-register62can function a dual purpose as a multiple modulus feedback register without having an additional separate multiple modulus feedback register61. Likewise, partial product feedback register64can serve a dual purpose as a sub-register of the partial product synchronization register220, thus removing the need for both a sub-register68and a feedback register64. In other variations the synchronization registers220and240can be used without other registers such as a pipeline register and/or feedback registers.