Circuit and method of modulo multiplication

• US 6,182,104 B1
• Filed: 07/22/1998
• Issued: 01/30/2001
• Est. Priority Date: 07/22/1998
• Status: Expired due to Term

• Current Assignee: North Star Innovations Inc. (Wi-LAN Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Tesch, Rodney C., Dworkin, James Douglas, Torla, Michael J., Foster, Robert I., Buss, John Michael
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Callahan, Paul E.
• Application Number:
  US09/120,835
• Time in Patent Office: 923 Days
• Field of Search: 380/28, 380/287, 713/200, 713/154, 708/200, 708/277, 708/490, 708/501, 708/505, 708/523, 708/524, 708/606, 708/627, 708/802, 708/808
• US Class Current: 708/501
• CPC Class Codes: G06F 7/728 using Montgomery reduction

Abstract

A co-processor (44) executes a mathematical algorithm that computes modular exponentiation equations for encrypting or decrypting data. A pipelined multiplier (56) receives sixteen bit data values stored in an A/B RAM (72) and generates a partial product. The generated partial product is summed in a summer (58) with a previous partial product stored in a product RAM (64). A modulo reducer (60) causes a binary data value N to be aligned and added to the summed value when a particular data bit location of the summed value has a logic one value. An N RAM (70) stores the data value N that is added in a modulo reducer (60) to the summed value. The co-processor (44) computes the Foster-Montgomery Reduction Algorithm and reduces the value of (A*B mod N) without having to first compute the value of μ as is required in the Montgomery Reduction Algorithm.

Claims

1. A data processing system for performing modulo multiplication, comprising:

a multiplier having inputs for receiving binary data values A and B;

an adder having a first input coupled to an output of the multiplier, a second input coupled for receiving a partial product, and an output for supplying a summed value; and

a modulo reducer having a first input coupled to the output of the adder, a second input coupled for receiving a binary data value N, and an output for supplying a data value having a form of (A*B/R mod N), wherein a least significant data bit of a reduction value μ

is generated by aligning the binary data value N and adding the binary data value N to the summed value when a predetermined bit location of the summed value has a first logic state.

2. The data processing system of claim 1, wherein the partial product is initially zero and the predetermined bit location of the summed value is a least significant bit of the summed value.

3. The data processing system of claim 1, wherein the data value is reduced to a zero value all bits of the reduction value μ

are determined.

4. A smartcard, comprising:

a data bus for transferring data to an output of the smartcard; and

a co-processor coupled to the data bus for multiplying a first digit (A*R mod N) and a second digit (B*R mod N) and generating a product of (A*B*R mod N) which is reduced modulo N by dividing by a value of R during multiplication, where A and B are integer values, N is a modulo count and an odd integer value, R is an integer value, and the modulo multiplication is based on a value (μ

*N), where μ

is determined when multiplying the first and second digits.

5. The smartcard of claim 4, wherein the co-processor comprises:

a multiplier coupled to the data bus for receiving the data, wherein the data includes a first operand received at a first input of the multiplier and a second operand received at a second input of the multiplier, and wherein the multiplier generates a product from the first and second operands;

a summer circuit having a first input coupled to the multiplier for receiving the product, a second input coupled for receiving a previous partial product, and an output for providing a sum of the product and the previous partial product; and

a modulo reducer having a first input coupled to the output of the summer circuit, a second input coupled for receiving the binary value N, and an output that supplies a reduced product, wherein the reduced product has an even value.

6. The smartcard of claim 5, further including a digit negation unit having an input coupled to the data bus for receiving the first operand and an output coupled to the first input of the multiplier for supplying a two'"'"'s complement negative number of the first operand.

7. The smartcard of claim 5, further including a memory having an input coupled to the output of the modulo reducer for receiving the reduced product and an output coupled to the second input of the summer circuit.

8. The smartcard of claim 4, wherein the binary value N has an odd value.

9. A cryptographic system, comprising:

a central processing unit having a data bus for transferring data; and

a cryptographic accelerator block coupled to the data bus for multiplying a first digit (A*R mod N) and a second digit (B*R mod N) and generating a product (A*B*R mod N) which is reduced modulo N by dividing by a value of R during multiplication of the first and second digits, where A and B are integer values, N is a modulo count and an odd integer value, R is an integer value, and the modulo multiplication is based on a value (μ

*N), where μ

is determined when multiplying the first and second digits.

10. The cryptographic system of claim 9, wherein the cryptographic accelerator block comprises:

a multiplier coupled to the data bus for receiving the data, wherein the data includes a first value received at a first input of the multiplier and a second value received at a second input of the multiplier, and wherein the multiplier generates a product from the first and second values;

a summer circuit having a first input coupled to an output of the multiplier and a second input coupled for receiving a previous partial product, and an output for providing a sum of the product and the previous partial product; and

a modulo reducer having a first input coupled to the output of the summer circuit, a second input coupled for receiving the integer N, and an output that supplies a reduced product.

11. The cryptographic system of claim 10, further including a memory having an input coupled to the output of the modulo reducer and an output coupled to the second input of the summer circuit.

12. The cryptographic system of claim 10, further including a digit negation unit having an input coupled to the data bus for receiving the first value and an output coupled to the first input of the multiplier for supplying a two'"'"'s complement negative number of the first value.

13. A cryptographic circuit, comprising:

a multiplier having first and second inputs coupled for receiving operands A and B, respectively, and an output for supplying a partial product;

an adder having a first input coupled to the output of the multiplier, a second input coupled for receiving a previous reduced partial product, and an output for supplying a summed value; and

a modulo reducer having a first input coupled to the output of the adder, a second input coupled for receiving a modulus, and an output for supplying a reduced partial product.

14. The cryptographic circuit of claim 13, further comprising:

a data bus for transferring data;

a first memory coupled to the data bus, wherein the first memory stores the operands A and B;

a second memory having a first input coupled to the data bus and a second input coupled for receiving the reduced partial product, wherein the second memory stores the reduced partial product and provides the previous reduced partial product; and

a third memory having a first input coupled to the data bus and a second input coupled to the second input of the modulo reducer, wherein the third memory stores the modulus.

15. The cryptographic circuit of claim 14, further comprising:

a Digit Negation Unit (DNU) having an input coupled to the data bus for receiving operand A from the first memory and an output coupled to the first input of the multiplier;

a Data Switch Unit (DSU) having a first input coupled to an output of the second memory, a second input coupled to the data bus, and an output coupled to the second input of the adder for supplying the previous reduced partial product; and

a Digit Compare Unit (DCU) having a first input coupled to an output of the third memory, a second input coupled to the data bus, and an output coupled to the second input of the modulo reducer for supplying the modulus.

16. A method of multiplying two operands, comprising the steps of:

multiplying a first operand A and a second operand B to provide a product;

adding a partial product to the product to provide a summed value; and

adding an integer binary value N to the summed value when a particular data bit location of the summed value has a first logic value.

17. The method of claim 16, wherein the step of multiplying a first operand A and a second operand B include multiplying the first operand A having a form (A*R mod N) and the second operand B having a form (B*R mod N), where R is an integer binary value.

18. The method of claim 16, wherein the particular data bit location of the summed value is a least significant data bit when the partial product has a value of zero.