Circuit and method for decompressing compressed elliptic curve points

• US 6,199,086 B1
• Filed: 12/24/1997
• Issued: 03/06/2001
• Est. Priority Date: 12/24/1997
• Status: Expired due to Term

• Current Assignee: Certicom Corporation (Blackberry Limited)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Lambert, Robert John, Glaser, P. Michael, Torla, Michael John, Vanstone, Scott Alexander, Vadekar, Ashok, Dworkin, James Douglas
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US08/997,959
• Time in Patent Office: 1,168 Days
• Field of Search: 708/492, 708/491, 380/28, 380/30
• US Class Current: 708/492
• CPC Class Codes: G06F 7/725 over elliptic curves

Abstract

An elliptic curve (EC) processor circuit (120) comprising a finite field arithmetic logic unit (122), operation registers (124) an EC control unit (123) and a register file (127). A storage element (250) is coupled to the finite field arithmetic logic unit (122). The EC control unit (123) controls the various components of the EC processor circuit (120) to decompress a compressed one-bit representation of a Y coordinate of an elliptic curve point (X, Y). The EC control unit (123) controls the use of the operation register (124), the storage element (250) and the finite field arithmetic logic unit (122) 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 (120).

Claims

1. An elliptic curve processing circuit comprising:

a finite field arithmetic logic unit comprising a finite field square circuit, a finite field inverse circuit, a finite field multiplier circuit, and a finite field adder circuit;

first and second operation registers;

a storage element; and

a control unit coupled to the finite field arithmetic logic unit, to the storage element, and to the first and second operation registers, the control unit being programmed to configure the elliptic curve processing circuit to decompress binary information representing a compressed elliptic curve point by;

(a)loading a plurality of bits representing a corresponding X coordinate into the first operation register;

(b)coupling the contents of the first operation register to the finite field arithmetic logic unit to compute a first plurality of bits according to an elliptic curve equation and loading the first plurality of bits into the second operation register;

(c)loading into the storage element and also into a least significant bit position of the second operation register a single bit which represents the compressed Y coordinate of a compressed elliptic curve point;

(d)coupling the contents of the second operation register and the storage element to the finite field arithmetic logic unit to determine a second plurality of bits which replace the contents of the second operation register, wherein a most significant bit of the second plurality of bits is equal to the single bit representing the compressed Y coordinate; and

(e)coupling the contents of the first operation register and the second operation register to the finite field arithmetic logic unit to multiply the second plurality of bits in the second operation register by the plurality of bits representing the X coordinate to generate a product which is a third plurality of bits representing a decompressed Y coordinate.

2. The elliptic curve processing circuit of claim 1, wherein the storage element is a one-bit storage element.

3. The elliptic curve processing circuit of claim 1, wherein the control unit is programmed to determine the second plurality of bits by:

(d1)coupling to the finite field arithmetic logic unit a current value of the storage element and a current most significant bit of the second operation register which are added together, and a result of which is returned to the storage element as a new current value;

(d2)coupling the contents of the second operation register to the finite field arithmetic unit for squaring the contents of the second operation register in order to rotate the contents thereof;

(d3)loading the result to the least significant bit position of the second operation register; and

(d4)repeating (d1) through (d3) until all the bits of the second plurality of bits are determined.

4. The elliptic curve processing circuit of claim 3, and further comprising first and second operations buses which connect the first and second operation registers and the storage element to the finite field arithmetic logic unit and a result bus which connects results generated by the finite field arithmetic logic unit to the first and second operation registers and to the storage element.

5. The elliptic curve processing circuit of claim 1, wherein the control unit is programmed to compute the first plurality of bits by controlling the finite field multiplier circuit and finite field inverse circuit to operate on the contents of the first operation register.

6. A communication device comprising the elliptic curve processing circuit of claim 1.

7. The communication device of claim 6, and further comprising:

a receiver for receiving RF signals;

a controller coupled to the receiver; and

the controller being coupled to the elliptic curve processing circuit to supply elliptic curve point information embedded in the RF signals for processing by the elliptic curve processing circuit.

8. A selective call receiver comprising the elliptic curve processing circuit of claim 1, and further comprising:

a receiver for receiving RF signals;

a controller coupled to the receiver;

a decoder coupled to the receiver and to the controller, the decoder decoding information in the RF signals; and

the controller being coupled to the elliptic curve processing circuit to supply elliptic curve point information embedded in the RF signals for processing by the elliptic curve processing circuit.

9. In combination, a finite field arithmetic logic unit comprising a finite field square circuit, a finite field inverse circuit, a finite field multiplier circuit, and a finite field adder circuit;

first and second operation registers;

a storage element; and

a control unit coupled to the finite field arithmetic logic unit, to the storage element, and to the first and second operation registers, the control unit being programmed to;

(a)load a plurality of bits representing a corresponding X coordinate into the first operation register;

(b)couple the contents of the first operation register to the finite field arithmetic logic unit to compute a first plurality of bits according to an elliptic curve equation and loading the first plurality of bits into the second operation register;

(c) load a single bit which represents a compressed Y coordinate into the storage element and also into a least significant bit position of the second operation register;

(d) couple the contents of the second operation register and the storage element to the finite field arithmetic logic unit to determine a second plurality of bits which replace the contents of the second operation register, wherein a most significant bit of the second plurality of bits is equal to the one bit which represents the compressed Y coordinate; and

(e) couple the contents of the first operation register and the second operation register to the finite field arithmetic logic unit to multiply the second plurality of bits in the second operation register by the plurality of bits representing the X coordinate to generate a product which is a third plurality of bits representing a decompressed Y coordinate.

10. An elliptic curve processing circuit comprising the combination of claim 9.

11. The combination of claim 9, wherein the control unit is further programmed to determine the second plurality of bits by:

(d1)coupling to the finite field arithmetic logic unit a current value of the storage element and a current most significant bit of the second operation register which are added together, and a result of which is returned to the storage element as a new current value;

(d2)coupling the contents of the second operation register to the finite field arithmetic unit for squaring the contents of the second operation register in order to rotate the contents thereof;

(d3)loading the result to the least significant bit position of the second operation register; and

(d4)repeating (d1) through (d3) until all the bits of the second plurality of bits are determined.

12. The combination of claim 9, wherein the storage element is a one-bit storage element.

13. The combination of claim 9, and further comprising first and second operations buses which connect the first and second operation registers and the storage element to the finite field arithmetic logic unit and a result bus which connects results generated by the finite field arithmetic logic unit to the first and second operation registers and to the storage element.

14. The combination of claim 9, wherein the control unit is programmed to compute the first plurality of bits by controlling the finite field multiplier circuit and finite field inverse circuit to operate on the contents of the first operation register.

15. A method for decompressing a compressed elliptic curve point comprising:

receiving a compressed elliptic curve point comprising a single bit which represents a compressed Y coordinate and a plurality of bits representing a corresponding X coordinate;

computing a first plurality of bits according to an elliptic curve equation using the plurality of bits representing the X coordinate;

determining a second plurality of bits based on the first plurality of bits and the single bit representing the compressed Y coordinate, wherein a most significant bit of the second plurality of bits is equal to the single bit representing the compressed Y coordinate; and

determining a decompressed Y coordinate by multiplying the plurality of bits representing the X coordinate by the second plurality of bits.

16. The method of claim 15, wherein the step of determining the second plurality of bits comprises computing lesser significant bits of the second plurality of bits by adding bits of the first plurality of bits with corresponding determined bits of the second plurality of bits.