High-speed modulo exponentiator device

Claim 2

A high-speed modulo exponentiator device for performing a modulo experimentation function of the form C=B E (Modulo M), wherein E is a large positive integer and B and M are large integers, as a series of modulo multiplication operations of the form P=(X * Y) (Modulo M), wherein X and Y are operands of the exponentiation function in binary form, comprising: digital integrated circuit ("IC") means having an X register, a Y register, and an A register for computing each modulo multiplication operation, said X, Y, and A registers being interconnected and operative with control means for carrying out a loop computation using said X, Y, and A registers including: (a) first register control means for computing an xf factor based upon three most significant bits of Y, (b) second register control means for computing 4*A+xf*X and transferring the result to the A register, (c) third register control means for determining an mf factor based upon a comparison of A with selected threshold values of M, (d) fourth register control means for computing A+mf*M and transferring the result to the A register, and (e) fifth register control means for shifting the bits of the Y register two bits to the left (two most significant bits of Y) and returning control to said first register control means until said loop computation is completed.

Claim 3

A high-speed modulo exponentiator device according to claim 1, wherein said digital IC means is implemented as a gallium arsenide (GaAs) IC device.

Claim 4

A high-speed modulo exponentiator device according to claim 1, wherein said digital IC means is implemented with a bit slice architecture.

Claim 5

A high-speed modulo exponentiator device according to claim 3, wherein said digital IC means includes a plurality of bit slice units combined in a carry-save element.

Claim 6

A high-speed modulo exponentiator device according to claim 4, wherein said digital IC means includes a plurality of carry-save elements combined in an exponentiator device.

Claim 7

A high-speed modulo exponentiator device according to claim 5, wherein said digital IC means includes a master exponentiator device having input/output and control logic elements combined therewith.

Claim 8

A high-speed modulo exponentiator device according to claim 6, wherein said master exponentiator device includes a most-significant bits carry-save element and a least-significant bits carry-save element.

Claim 9

A high-speed modulo exponentiator device according to claim 6, wherein said master exponentiator device includes a in-boundary carry-save element and an out-boundary carry-save element for transferring data bits across device boundaries.

Claim 10

A high-speed modulo exponentiator device according to claim 6, wherein said digital IC means includes slave exponentiator devices cascaded with said master exponentiator devices.

Claim 11

A high-speed modulo exponentiator device according to claim 1, wherein said digital IC means is incorporated in a public key encryption system for encrypting a base argument B using a public key of an exponent E and a modulus M.

Claim 14

A method for performing a modulo exponentiation function according to claim 11, wherein said step of computing the xf factor includes employing an extended Booth algorithm to obtain xf=-2*y(MSB)+1*y(MSB-1)+1*y(MSB-2), where y(MSB), y(MSB-1), y(MSB-2) are three most-significant bits of Y.

Claim 15

A method for performing a modulo exponentiation function according to claim 11, wherein said step of determining includes determining mf as a multiple of -2, -1, 0, 1, or 2 times 128 based upon comparing eight most-significant bits of A with four selected threshold values of M.

Claim 16

A method for performing a modulo exponentiation function according to claim 11, wherein said X, Y, and A registers have bit lengths of n, and further comprising the step of scaling up the operands X and Y to n bits whenever their bit lengths are less than n.

Claim 17

A method for performing a modulo exponentiation function according to claim 11, further comprising the step of implementing steps (a) through (g) as register operations in an IC circuit.

Claim 18

A method for performing a modulo exponentiation function according to claim 15, wherein said implementing step includes employing a bit slice architecture in carry-save elements of an IC exponentiator device.

Claim 19

A high-speed modulo exponentiator device for performing a modulo exponentiation function of the form C=B E (Modulo M), wherein E is a large positive integer and B and M are large integers, as a series of modulo multiplication operations of the form P=(X * Y) (Modulo M), wherein X and Y are operands of the exponentiation function in binary form, based upon an extended Booth algorithm, comprising: digital integrated circuit ("IC") means including an X register, a Y register, and an A register having bit lengths of n and initialized with operand X, operand Y, and 0, respectively, said X, Y, and A registers being interconnected and operative with control means for carrying out a loop computation using said X, Y, and A registers for k=(n-1)/2, . . . , 0, when n is an odd number, and k=(n-2)/2, . . . , 0, when n is an even number, wherein said control means includes: (a) first register control means for computing xf(k)=-2*y(MSB)+1*y(MSB-1)+1*y(MSB-2), where y(MSB), y(MSB-1), y(MSB-2) are three most significant bits of Y; (b) second register control means for computing 4*A+xf(k)*X and transferring the result to the A register; (c) third register control means for determining mf(k), wherein mf(k) is a multiple of -2, -1, 0, 1, or 2 times 128, depending upon a comparison of eight most-significant bits of A with four selected threshold values of M; (d) fourth register control means for computing A+mf(k)*M and transferring the result to the A register; and (e) fifth register control means for shifting the bits of the Y register two bits to the left (two most significant bits of Y) and returning control to said first register control means until said loop computation is completed.

Claim 20

A high-speed modulo exponentiator device for performing a modulo exponentiation function of the form C=B E (Modulo M), wherein E is a large positive integer and B and M are large integers, as a series of modulo multiplication operations of the form P=(X * Y) (Modulo M), wherein X and Y are operands of the exponentiation function in binary form, based upon an extended Booth algorithm, comprising: digital integrated circuit ("IC") means including an X register, a Y register, and an A register having bit lengths of n and initialized with operand X, operand Y, and 0, respectively, said X, Y, and A registers being interconnected and operative with control means for carrying out a loop computation using said X, Y, and A registers for k=(n-1)/2, . . . , 0, when n is an odd number, and k=(n-2)/2, . . . , 0, when n is an even number, wherein said control means includes: (a) first register control means for computing xf(k)=-2*y(MSB)+1*y(MSB-1)+1*y(MSB-2), where y(MSB), y(MSB-1), y(MSB-2) are three most significant bits of Y; (b) second register control means for computing 4*A+xf(k)*X and transferring the result to the A register; (c) third register control means for determining mf(k), wherein mf(k) is a multiple of -2, -1, 0, 1, or 2 times 128, depending upon a comparison of eight most-significant bits of A with four selected threshold values of M; (d) fourth register control means for computing A+mf(k)*M and transferring the result to the A register; and (e) fifth register control means for shifting the bits of the Y register two bits to the left (two most significant bits of Y) and returning control to said first register control means until said loop computation is completed.

Claim 21

A high-speed modulo exponentiator device according to claim 17, wherein said second and fourth register control means perform multiplication functions by shifting the bits of said X, Y, and M registers.