Motorola Corporation

Other

Certicom Corporation

P Michael Glaser

Scott Alexander Vanstone

Robert John Lambert

Ashok Vadekar

James Douglas Dworkin

Michael J Torla

A finite field multiplier with intrinsic modular reduction includes an interface unit (,) that translates an n bit wide data path to a m bit wide data path where n is less than m. Also included is a finite field data unit (,) with m bit wide registers that is coupled to a finte field control unit (,). The finite field control unit (,) includes a microsequencer (,) and a finite state machine multiplier (,). The microsequencer (,) controls the finite state machine multiplier (,) which performs a finite field multiply operation with intrinsic modular reduction and presents a finite field multiplication product to the finite field data unit (,).

Finite field multiplier with intrinsic modular reduction

An elliptic curve (EC) processor circuit (,) comprising a finite field arithmetic logic unit (,), operation registers (,) an EC control unit (,) and a register file (,). A storage element (,) is coupled to the finite field arithmetic logic unit (,). The EC control unit (,) controls the various components of the EC processor circuit (,) to decompress a compressed one-bit representation of a Y coordinate of an elliptic curve point (X, Y). The EC control unit (,) controls the use of the operation register (,), the storage element (,) and the finite field arithmetic logic unit (,) to recursively compute the decompressed version of the compressed Y coordinate based upon the X coordinate and the compressed one-bit representation of the Y coordinate. The circuit and method employ minimal additional hardware and processing in an EC processor circuit (,).

Circuit and method for decompressing compressed elliptic curve points

A finite field inverse circuit has a finite field data unit (1112) and an inverse control unit (1110). The inverse control unit includes (1110) a k.sub.l and k.sub.u decrementer pair (1108, 1122), a k.sub.l -k.sub.u difference unit (1106), an inverse control finite state machine (1102), and a one-bit memory (1104) coupled to the inverse control finite state machine (1102). The finite field data unit (1112) includes four m bit wide registers that are shift registers designated as B (1120), A (1118), M (1114), and C (1116), where B- is a first register, A- is a second register, M- is a irreducible polynomial register, and C- is a field element register. An the irreducible polynomial is loaded left justified in the M-register, a field element to be inverted is loaded left justified in the C-register, and a single '1' is loaded in an LSB bit of the B-register. The field element is then inverted in 2n+2 system clock cycles where n is a field size associated with the field element.

Finite field inverse circuit

Growing community of inventors

Tempe, AZ, United States of America

P Michael Glaser