Arithmetic processor for finite field and module integer arithmetic operations

• US 6,349,318 B1
• Filed: 10/14/1999
• Issued: 02/19/2002
• Est. Priority Date: 04/18/1997
• Status: Expired due to Term

• Current Assignee: Certicom Corporation (Blackberry Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Vadekar, Ashok V., Jurisic, Aleksandar, Gallant, Robert, Lambert, Robert J., Vanstone, Scott A.
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US09/418,217
• Time in Patent Office: 859 Days
• Field of Search: 708/491-492, 380/28
• US Class Current: 708/492
• CPC Class Codes: G06F 2207/382 Reconfigurable for different fixed word lengths
• CPC Class Codes: G06F 7/72 using residue arithmetic
• CPC Class Codes: G06F 7/722 Modular multiplication G06F7/724, G06F7/727, G06F7/728 take precedence
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10
• CPC Class Codes: G06F 7/725 over elliptic curves
• CPC Class Codes: G06F 9/30014 with variable precision
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations

Abstract

The present disclosure provides an arithmetic processor having an arithmetic logic unit having a plurality of arithmetic circuits each for performing a group of associated arithmetic operations, such as finite field operations, or modular integer operations. The arithmetic logic unit has an operand input data bus, for receiving operand data thereon and a result data output bus for returning the results of the arithmetic operations thereon. A register file is coupled to the operand data bus and the result data bus. The register file is shared by the plurality of arithmetic circuits. Further a controller is coupled to the ALU and the register file, the controller selecting one of the plurality of arithmetic circuits in response to a mode control signal requesting an arithmetic operation and for controlling data access between the register file and the ALU and whereby the register file is shared by the arithmetic circuits.

Claims

1. An arithmetic processor comprising:

(a) an arithmetic logic unit having a finite field arithmetic circuit for performing finite field arithmetic operations and a modular integer arithmetic circuit for performing modular integer arithmetic operations, the arithmetic logic unit having an operand input data bus for receiving operand data thereon and a result data output bus for returning the results of said arithmetic operations thereon;

(b) a register file coupled to said operand data bus and said result data bus; and

(c) a controller coupled to said ALU and said register file, said controller selecting one of said finite field operations or said integer arithmetic operations in response to a mode control signal and for controlling data access between said register file and said ALU and whereby said register file is shared by both said finite filed and integer arithmetic circuits.

2. An arithmetic processor as defined in claim 1, said register file including general-purpose registers and said ALU having a processing bit width greater than said operand buses data bit width.

3. An arithmetic processor as defined in claim 1, said controller being programmed with instructions for controlling a selected arithmetic operation of said arithmetic logic unit.

4. An arithmetic processor as defined in claim 1, said operand buses having a bit width the same as a processing bit width of said ALU and said result data bus bit width.

5. An arithmetic processor as defined in claim 4, said operand data bus including a first and second operand buses for coupling first and second operands respectively to said ALU.

6. An arithmetic processor as defined in claim 5, said general-purpose registers being individually addressable by said controller wherein data in multiple registers may be combined for computation by said ALU on field sizes greater than said processing bit width of said ALU.

7. An arithmetic processor as defined in claim 1, said controller being responsive to a field size control, whereby said ALU may operate on different field sizes.

8. An arithmetic processor as defined in claim 1, said arithmetic logic unit including a plurality of special purpose registers for receiving operands to be utilized in said arithmetic operations from said register file, a plurality of sub arithmetic logic units having combinatorial and logic circuitry elements coupling one or more bits of said special purpose registers and a sequencing controller responsive to control information received from said controller, said sequencing controller and containing counter and detection circuitry coupled to said special purpose registers and said plurality of sub arithmetic logic units, for controlling operations thereof in order to cause a sequence of steps to be performed in an arithmetic operation.

9. An arithmetic processor as defined in claim 8, said arithmetic logic unit for performing said arithmetic operations of finite field multiplication, squaring, addition, subtraction and inversion.

10. An arithmetic processor as defined in claim 8, said sub arithmetic logic units for performing XOR, shift, shift-XOR, add and subtract logical operations.

11. An arithmetic processor as defined in claim 1, said finite field arithmetic circuit comprising:

a finite field multiplier circuit having a plurality of special purpose registers including an A register and an B register for receiving first and second operand bit vectors respectively, an M register for receiving a modulus bit vector, and an accumulator for containing a finite field product of said operands;

logic circuitry establishing connections from respective cells of said A and B registers to cells of said accumulator; and

a sequencing controller being operatively connected with said registers and said logic circuitry for implementing a sequence of steps to derive said finite field product.

12. An arithmetic processor as defined in claim 11, said sequencing of steps comprising:

computing partial products of the contents of said A register with successive bits of said B register;

storing said partial products in said accumulator;

testing a bit of said partial product;

reducing said partial product by said modulus if said tested bit is set and repeating said steps for successive bits of said B register.

13. An arithmetic processor as defined in claim 12, including storing said operand vectors left justified in said A register and said B register respectively and said test bit being derived from said left most bit of said registers.

14. An arithmetic processor as defined in claim 12, said B register is a shift register.

15. An arithmetic processor as defined in claim 14, said logic circuitry having a plurality of controllable adder units each coupled to respective register cells each comprising a first controllable adder having inputs derived from register cell A_i and accumulator cell C_i and being responsive to a first add control signal derived from cell B_N−

1 of register B for producing a first add output signal;

a second controllable adder having inputs derived from modulus register cell M_i and said add output signal and being responsive to an second add control signal derived from cell C<sub>N−

1</sub> of said accumulator for producing an output which is coupled to accumulator cell C_i.

16. An arithmetic processor as defined in claim 15, including a finite field adder circuit.

17. An arithmetic processor as defined in claim 16, said finite field adder comprising means for coupling an input derived from said cell B_i of register B to each of said first adders;

and means for coupling said output of said second adder to said cell C_i, and said sequencing controller being responsive to a finite field add control signal whereby said finite field addition operation is performed in a single clock cycle.

18. An arithmetic processor as defined in claim 1, said finite field arithmetic circuit including a finite field inversion circuit.

19. An arithmetic processor as defined in claim 18, said finite field inversion circuit comprising:

a plurality of special purpose registers including an A register and a B register for receiving first and second operand bit vectors respectively, an

M register for receiving a modulus bit vector, and an accumulator for containing a finite field product of said operands.

20. An arithmetic processor as defined in claim 1, said arithmetic logic unit comprising:

a finite field multiplier circuit;

a finite field inversion circuit;

a plurality of special purpose registers;

logic circuitry establishing connections between respective cells of said special purpose registers; and

a sequencing controller being operatively connected with said registers and said logic circuitry for implementing a sequence of steps to compute a finite field product or a finite field inversion and whereby said special purpose registers are shared by said finite field multiplier and said finite field inversion circuit.

21. An arithmetic processor as defined in claim 20, said finite field inversion circuit implementing an extended Euclidean algorithm.

22. An arithmetic processor as defined in claim 11, including an integer arithmetic multiplication circuit.

23. An arithmetic processor as defined in claim 12, said integer arithmetic multiplication being implemented by loading said m register with a carry in response to said mode selection signal.

24. An arithmetic processor as defined in claim 1, for use in a cryptographic system.

25. An arithmetic processor comprising:

a) an arithmetic logic unit having a finite field arithmetic circuit and a modular integer arithmetic circuit each for performing a group of associated arithmetic operations, the arithmetic logic unit having an operand input data bus for receiving operand data thereon and a result data output bus for returning the results of said arithmetic operations thereon;

b) a register file coupled to said operand data bus and said result data bus; and

c) a controller coupled to said ALU and said register file, said controller selecting one of said plurality of arithmetic circuits in response to a mode control signal requesting an arithmetic operation and for controlling data access between said register file and said ALU and whereby said register file is shared by said arithmetic circuits.