METHOD FOR SPEEDING UP THE COMPUTATIONS FOR CHARACTERISTIC 2 ELLIPTIC CURVE CRYPTOGRAPHIC SYSTEMS

• US 20100020965A1
• Filed: 12/28/2007
• Published: 01/28/2010
• Est. Priority Date: 12/28/2007
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Kounavis, Michael, Gueron, Shay
• Granted Patent: US 8,144,864 B2
• Time in Patent Office: Days
• US Class Current: 380/44
• 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:

computing a plurality of coefficients of a polynomial representing a carry-less product of two input operands according to a graph-based single iteration multiplication routine that is computed according to an input operand length to reduce an amount of multiplications required to compute the carry-less product of the two input operands;

reducing the carry-less product modulo a programmable polynomial that defines the elliptic curve cryptographic system by performing division using two multiplications.

2. The method of claim 1 wherein, prior to computing, the method further comprises:

pre-computing the multiplication routine according to an input operand length using the one iteration graph-based multiplication to reduce the amount of scalar multiplications required to compute the plurality of coefficients of the polynomial representing the product of the two input operands without recursion.

3. 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.

4. The method of claim 1 further comprising:

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.

5. The method of claim 1, wherein reducing the 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 the 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 the first multiplication of the two multiplications;

carry-less multiplying the s most significant terms of the resulting polynomial with first polynomial as the 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 the desired remainder.

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

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

8. The method of claim 1, wherein reducing the carry-less product comprises:

computing a remainder p(x) of the carry-less product polynomial modulo a programmable polynomial by performing the division according to the 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; and

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

q⁺ is a quotient polynomial, 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).

9. The method of claim 1, wherein computing the plurality of coefficients comprises:

computing, according to the pre-computed multiplication routine, products of the coefficients of the polynomial representing the product of the two input operands using a carry-less multiplication instruction available from the system, wherein the multiplication routine extends the carry-less multiplication instruction according to the input operand length, without recursion.

10. An article of manufacture including a machine readable storage medium having instructions encoded thereon which may be used to program an elliptic curve cryptographic system to perform a method, comprising:

pre-computing a multiplication routine using a one iteration graph-based multiplication according to an input operand length, the multiplication routine to reduce an amount multiplications required to compute a plurality of coefficients for a polynomial representing a product of two input operands;

computing, according to the pre-computed multiplication routine, products of the coefficients of the polynomial representing the product of the two input operands using a carry-less multiplication instruction available from the system to extend the carry-less multiplication instruction according to the input operand length without recursion; and

computing a remainder of the carry-less product polynomial modulo a programmable polynomial that defines the elliptic curve cryptographic system to form a cryptographic key.

11. The article of manufacture of claim 10, 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.

12. The article of manufacture of claim 10, wherein the method further 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.

13. The article of manufacture of claim 10, 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

P^a={P({v<sub>(i0) . . . (iq0) . . . (iq1) . . . (iqm−

1) . . . (iL−

1)</sub><sup>(L−

1)</sup>, v<sub>(i0) . . . (i′

q0) . . . (iq1) . . . (iqm−

1) . . . (iL−

1)</sub><sup>(L−

1)</sup>,

v<sub>(i0) . . . (iq0) . . . (i′

q1) . . . (iqm−

1) . . . (iL−

1)</sub><sup>(L−

1)</sup>, v(i<sub>0) . . . (i′

q0) . . . (i′

q1) . . . (iqm−

1) . . . (iL−

1)</sub><sup>(L−

1)</sup>, . . . , v(i<sub>0) . . . (i′

q0) . . . (i′

q1) . . . (i′

qm−

1) . . . (iL−

1)</sub><sup>(L−

1)</sup>});

i_jε

[o,n_j−

1]∀

jε

[0,L−

1], (i′

_qkε

[0,n_qk−

1]i_qk≠

i′

_qk)∀

kε

[0,m−

1],

0≦

q₀≦

q₁≦

. . . ≦

q<sub>m−

1</sub>, mε

[0,L]},

where P^a represents the second plurality of products, v represents a vertex, L represents a level, q represents position and i represents a local index.

14. The method of claim 10 wherein computing the remainder of the carry-less product polynomial modulo a remainder of the carry-less product polynomial is performed using three 233-bit wide shift operations and an exclusive OR (XOR) operation if a B-233 elliptic curve is the programmable polynomial.

15. The method of claim 10, wherein the input operand length is 233 bits and the native operand size of the system is one of 32 bits and 64 bits;

and wherein the carry-less multiplication instruction available from the system is one of a 32-bit and a 64-bit carry-less multiplication instruction.

16. An elliptic curve cryptograph apparatus comprising:

a computer coupled to a memory, the computer to execute an cryptographic program in the memory, the cryptographic program including a multiplication portion to perform multiplication of input operands, the multiplication portion includes graph based functions to generate a plurality of coefficients of a polynomial representing a carry-less product of two input operands returned from the multiplication portion and a reduction portion to reduce the carry-less product polynomial modulo a programmable polynomial that defines the elliptic curve cryptographic apparatus by performing division using two multiplications.

17. The apparatus of claim 16, wherein the reduction portion is further to compute a remainder of the carry-less product polynomial modulo a programmable polynomial using three 233-bit wide shift operations and an exclusive OR (XOR) operation if a B-233 elliptic curve is the programmable polynomial.

18. The apparatus of claim 16, further comprising:

pre-computation logic to compute a first polynomial g* that includes t least significant terms of the programmable polynomial 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;

carry-less product logic to compute the carry-less product of the quotient polynomial and the most significant bits of the carry-less product as the first multiplication of the two multiplications to provide a result polynomial of the degree 2s−

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

2 and return the t least significant terms of the resulting polynomial as the desired remainder.

19. The apparatus of claim 16, the plurality of graph based functions includes:

a precomputation function to pre-compute the multiplication routine according to an input operand length using the one iteration graph-based multiplication that reduces an amount of multiplications required to compute a plurality of coefficients of the polynomial representing the product of the two input operands without recursion; and

a multiplication function to compute according to the pre-computed multiplication routine, products of the coefficients of the polynomial representing the product of the two input operands using a carry-less multiplication instruction available from a system to extend the carry-less multiplication instruction according to the input operand length without recursion.

20. An elliptic curve cryptograph system comprising:

a first device coupled to a first memory, the first device to execute an encryption program in the first memory, the encryption program including a multiplication portion to perform multiplication of input operands, the multiplication portion includes a plurality of graph based functions to generate a plurality of coefficients of a polynomial representing a carry-less product of two input operands returned from the multiplication portion and a reduction portion to reduce the carry-less product modulo a programmable polynomial that defines the elliptic curve cryptographic system by performing division using two multiplications to generate a first key and a second key;

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

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

21. The system of claim 20, the plurality of graph based functions includes:

a pre-computation function to pre-compute the multiplication routine according to an input operand length using the one iteration graph-based multiplication that reduces an amount of multiplications required to compute a plurality of coefficients of the polynomial representing the product of the two input operands without recursion; and

computing, according to the pre-computed multiplication routine, products of the coefficients of the polynomial representing the product of the two input operands using a carry-less multiplication instruction available from the system to extend the carry-less multiplication instruction according to the input operand length without recursion.

22. The system of claim 21, wherein the reduction portion is further to computing a remainder of the carry-less product polynomial p(x) modulo a programmable polynomial by performing the division according to the 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; and

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.

23. The system of claim 21, 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.

24. The system of claim 21, wherein the network is one of a wired and wireless.

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