Method for speeding up the computations for characteristic 2 elliptic curve cryptographic systems

• US 8,144,864 B2
• Filed: 12/28/2007
• Issued: 03/27/2012
• Est. Priority Date: 12/28/2007
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Gueron, Shay, Kounavis, Michael
• Primary Examiner(s): Colin, Carl
• Assistant Examiner(s): THIAW, CATHERINE B
• Application Number:
  US11/966,572
• Publication Number:
  US 20100020965A1
• Time in Patent Office: 1,551 Days
• Field of Search: 380 28- 30, 713/174
• US Class Current: 380/28
• 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: H04L 2209/80 Wireless network architectures or network communication protocols for wireless network security H04W12/00
• CPC Class Codes: H04L 9/3026 details relating to polynomials generation, e.g. generation of irreducible polynomials
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves

Abstract

In some embodiments, an apparatus and method for speeding up the computations for characteristic 2 elliptic curve cryptographic systems are described. In one embodiment, a multiplication routine may be pre-computed using a one iteration graph-based multiplication according to an input operand length. Once pre-computed, the multiplication routine may be followed to compute the products of the coefficients of the polynomials representing a carry-less product of two input operands using a carry-less multiplication instruction. In one embodiment, the pre-computed multiplication routines may be used to extend a carry-less multiplication instruction available from an architecture according to an input operand length of the two input operands. Once computed, the carry-less product polynomial produces a remainder when the product is computed modulo a programmable polynomial that defines the elliptic cryptographic system to form a cryptographic key. Other embodiments are described and claimed.

Claims

1. A method in an elliptic curve cryptographic system comprising:

pre-computing, for encryption, a multiplication routine according to an input operand length using one iteration graph-based multiplication;

computing, by a computing device, a first carry-less product of two input operands according to the pre-computed multiplication routine; and

computing, by the computing device, a second carry-less product between the first carry-less product and a sparse polynomial by performing a number of SHIFT and Exclusive-OR operations,

where the sparse polynomial comprises a plurality of coefficients and the number of coefficients of the plurality equal to one is smaller than the number of coefficients of the plurality equal to 0, and the number of SHIFT and Exclusive-OR operations is in the order of the number of coefficients of the plurality equal to I in a polynomial defining an elliptic curve binary field.

2. The method of claim 1 further comprises:

computing a third carry-less product between the second carry-less product and a second sparse polynomial by performing a number of SHIFT and Exclusive-OR operations, where the second sparse polynomial comprises a plurality of coefficients and the number of coefficients of the plurality equal to one is smaller than the number of coefficients of the plurality equal to 0, and the number of SHIFT and Exclusive-OR operations is in the order of the number of coefficients of the plurality equal to 1 in a polynomial defining an elliptic curve binary field.

3. The method of claim 2, wherein the third carry-less product comprises:

computing a cryptographic key according to a remainder p(x) using the following equation as;

p(x)=c(x)·

x^t mod g(x)

where;

c(x) is a polynomial of degree s−

1 with coefficients in GF(2), representing the s most significant bits of a carry-less product to be reduced;

t is the degree of the polynomial g; and

g(x) is the irreducible polynomial that defines the Elliptic Curve (EC) crypto-system.

4. The method of claim 2, wherein computing the first carry-less product further comprises:

computing a first polynomial g* that includes t least significant terms of the programmable polynomial g(x);

computing a quotient polynomial q⁺, where the quotient polynomial q⁺ is of degree s and is equal to the quotient of the division of x^t+s with the programmable polynomial;

computing a carry-less product of the quotient polynomial and the most significant bits of the carry-less product to provide a result polynomial of the degree 2s−

1 as a first multiplication of two multiplications;

carry-less multiplying the s most significant terms of the resulting polynomial with the first polynomial as a second multiplication of the two multiplications to accomplish the division required to compute a result polynomial of degree t+s−

2; and

returning the t least significant terms of the resulting polynomial as a remainder.

5. The method of claim 4, wherein computing of the carry-less product is performed using a plurality of big number shift operations and exclusive-OR operations if g(x) is one of a trinomial and a pentanomial.

6. The method of claim 4, wherein the carry-less multiplying is performed using two big number shift operations and exclusive-OR operations if g(x) is a trinomial.

7. The method of claim 2, wherein computing the third carry-less product comprises:

computing a remainder p(x) of the first carry-less product modulo a programmable polynomial by performing a division according to two multiplications of the following equation;

p(x)=L^t(g*(x)·

M^s(c(x)·

q⁺(x))),

where;

L^u(v) to denote the coefficients of the u least significant terms of the polynomial v and M^u(v) to denote the coefficients of its u most significant terms;

c(x) is a polynomial of degree s−

1 with coefficients in GF(2), representing the s most significant bits of a carry-less product to be reduced;

t is the degree of the polynomial g;

g(x) is the irreducible polynomial that defines the Elliptic Curve (EC) crypto-system;

g* that includes t least significant terms of g(x); and

q⁺ is a quotient polynomial q⁺ where the quotient polynomial q⁺ is of degree s and is equal to the quotient of the division of x^t+s with the programmable polynomial g(x).

8. The method of claim 1, wherein pre-computing further comprises:

generating a plurality of graphs pertaining to a first operand and a second operand according to an input operand length, the plurality of graphs comprising a plurality of vertices and a plurality of edges;

providing the plurality of vertices and the plurality of edges to perform multiplication of the first operand and the second operand without using recursion, wherein the first operand and the second operand have a size of at least a native operand size of the system;

determining a first plurality of products for the plurality of vertices;

determining a second plurality of products for a plurality of spanning edges and a plurality of spanning planes; and

creating the plurality of coefficients from the first plurality of products and the second plurality of products for performing the multiplication of the first operand and the second operand.

9. An article of manufacture including a non-transitory machine readable storage medium having instructions encoded thereon to program an elliptic curve cryptographic system to perform a method, comprising:

pre-computing, for encryption, a multiplication routine according to an input operand length using a one iteration graph-based multiplication;

computing, by a computing device, a first carry-less product of two input operands according to the pre-computed multiplication routine; and

computing, by the computing device, a second carry-less product between the first carry-less product and a sparse polynomial by performing a number of SHIFT and Exclusive-OR operations,

where the sparse polynomial comprises a plurality of coefficients and the number of coefficients of the plurality equal to one is smaller than the number of coefficients of the plurality equal to 0, and the number of SHIFT and Exclusive-OR operations is in the order of the number of coefficients of the plurality equal to 1 in a polynomial defining an elliptic curve binary field.

10. The article of manufacture of claim 9, wherein pre-computing the multiplication routine comprises:

generating one or more graphs for an input operand length;

selecting a set of complete subgraphs from the one or more graphs;

determining a plurality of generalized edges and a plurality of vertices from the plurality of interconnected graphs, the plurality of generalized edges including a plurality of spanning edges and a plurality of spanning planes;

determining a first plurality of products for the plurality of vertices;

determining a second plurality of products for the plurality of spanning edges and the plurality of spanning planes;

creating a plurality of coefficients for a polynomial representing a product of input operands from the first plurality of products and the second plurality of products; and

providing the plurality of coefficients to a multiplication portion of an encryption process.

11. The article of manufacture of claim 9, wherein the method further comprises:

computing a third carry-less product between the second carry-less product and a second sparse polynomial by performing a number of SHIFT and Exclusive-OR operations, where the second sparse polynomial comprises a plurality of coefficients and the number of coefficients of the plurality equal to one is smaller than the number of coefficients of the plurality equal to 0, and the number of SHIFT and Exclusive-OR operations is in the order of the number of coefficients of the plurality equal to 1 in a polynomial defining an elliptic curve binary field; and

wherein third carry-less product comprises;

computing a cryptographic key according to a remainder p(x) using the following equation as;

p(x)=c(x)·

x^t mod g(x)

where;

c(x) is a polynomial of degree s−

1 with coefficients in GF(2), representing the s most significant bits of a carry-less product to be reduced;

t is the degree of the polynomial g; and

g(x) is the irreducible polynomial that defines the Elliptic Curve (EC) crypto-system.

12. The article of manufacture of claim 9, wherein the first plurality of products are determined for graphs having interconnecting vertices;

and

wherein the second plurality of products is determined using the following equation

13. An elliptic curve cryptograph system comprising:

a first computer device coupled to a first memory, the first computer device to execute an encryption program in the first memory, the encryption program to perform a method comprising;

pre-computing a multiplication routine according to an input operand length using the one iteration graph-based multiplication;

computing a first carry-less product of two input operands according to the pre-computed multiplication routine; and

computing a second carry-less product between the first carry-less product and a sparse polynomial by performing a number of SHIFT and Exclusive-OR operations,

where the sparse polynomial comprises a plurality of coefficients and the number of coefficients of the plurality equal to one is smaller than the number of coefficients of the plurality equal to 0, and the number of SHIFT and Exclusive-OR operations is in the order of the number of coefficients of the plurality equal to 1 in a polynomial defining an elliptic curve binary field; and

a second computer device coupled to a second memory, the second computer device to execute the encryption program in the second memory,

wherein the first computer device and the second computer device transfer encrypted data to one another over a network.

14. The system of claim 13, the method further comprises:

computing a third carry-less product between the second carry-less product and a second sparse polynomial by performing a number of SHIFT and Exclusive-OR operations, where the second sparse polynomial comprises a plurality of coefficients and the number of coefficients of the plurality equal to one is smaller than the number of coefficients of the plurality equal to 0, and the number of SHIFT and Exclusive-OR operations is in the order of the number of coefficients of the plurality equal to 1 in a polynomial defining an elliptic curve binary field.

15. The system of claim 14, wherein the third carry-less product comprises:

computing a remainder p(x) of the first carry-less product modulo a programmable polynomial by performing a division according to two multiplications of the following equation;

p(x)=L^t(g(x)·

M^s(c(x)·

q⁺(x))),

where;

L^u(v) to denote the coefficients of the u least significant terms of the polynomial v and M^u(v) to denote the coefficients of its u most significant terms;

c(x) is a polynomial of degree s−

1 with coefficients in GF(2), representing the s most significant bits of a carry-less product to be reduced;

t is the degree of the polynomial g;

g* that includes t least significant terms of the irreducible polynomial that defines the Elliptic Curve (EC) crypto-system; and

a quotient polynomial q⁺, where the quotient polynomial q⁺ is of degree s and is equal to the quotient of the division of x^t+s with the programmable polynomial.

16. The system of claim 14, wherein the first memory is a double data rate (DDRn) synchronous dynamic random access memory (SDRAM), wherein n is an integer equal to or greater than 2.

17. The system of claim 14, wherein the network is one of a wired and wireless.

18. The system of claim 14, wherein the second computer device is one of a smartcard, a personal digital assistant (PDA), a cellular telephone and a gaming console.