Generic implementations of ellipitic curve cryptography using partial reduction

• US 20030208518A1
• Filed: 03/11/2003
• Published: 11/06/2003
• Est. Priority Date: 05/01/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Gura, Nils, Eberle, Hans, Goupy, Edouard
• Granted Patent: US 7,240,084 B2
• Time in Patent Office: Days
• US Class Current: 708/492
• CPC Class Codes: G06F 7/527 in serial-parallel fashion, i.e. one operand being entered serially and the other in parallel G06F7/533 takes 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

Abstract

A reduction operation is utilized in an arithmetic operation on two binary polynomials X(t) and Y(t) over GF(2), where an irreducible polynomial M_m(t)=t^m+a_m−1t^m−1+a_m−2t^m−2+ . . . +a₁t+a₀, where the coefficients as are equal to either 1 or 0, and m is a field degree. The reduction operation includes partially reducing a result of the arithmetic operation on the two binary polynomials to produce a congruent polynomial of degree less than a chosen integer n, with m≦n. The partial reduction includes using a polynomial M′=(M_m(t)−t^m)*t^n−m, or a polynomial M″=M_m(t)*t^n−m as part of reducing the result to the degree less than n and greater than or equal to m. The integer n can be the data path width of an arithmetic unit performing the arithmetic operation, a multiple of a digit size of a multiplier performing the arithmetic operation, a word size of a storage location, such as a register, or a maximum operand size of a functional unit in which the arithmetic operation is performed.

Claims

1. A method for performing an arithmetic operation on two binary polynomials X(t) and Y(t) over GF(2), where an irreducible polynomial M_m(t)=t^m+a_m−

1t<sup>m−

1</sup>+a<sub>m−

2</sub>t<sup>m−

2</sup>+ . . . +a₁t+a₀, where the coefficients a_i are equal to either 1 or 0, and m is a field degree, comprising;

partially reducing a result of the arithmetic operation on the two binary polynomials to produce a congruent polynomial of degree less than a chosen integer n, with m≦

n.

2. The method as recited in claim 1 further comprising using at least one of a first and second polynomial M′

and M″

, respectively, as part of reducing the result to the degree less than n and greater than or equal to m, M′

=(M_m(t)−

t^m)*t<sup>n−

m</sup> and M″

=(M_m(t)*t<sup>n−

m</sup>).

3. The method as recited in claim 2 wherein n is a data path width of an arithmetic unit performing the arithmetic operation.

4. The method as recited in claim 2 wherein the arithmetic operation is a multiplication and n is a multiple of a digit size of a multiplier performing the multiplication.

5. The method as recited in claim 2 wherein n is a multiple of a word size of a storage location.

6. The method as recited in claim 5 wherein the storage location is a register.

7. The method as recited in claim 2 where n is a maximum operand size of an functional unit in which the arithmetic operation is performed.

8. A method for performing a multiplication on two binary polynomials X(t) and Y(t) over GF(2), where an irreducible polynomial M_m(t)=t^m+a_m−

1t<sup>m−

1</sup>+a<sub>m−

2</sub>t<sup>m−

2</sup>+ . . . +a₁t+a₀, where the coefficients a_i are equal to either 1 or 0, and m is a field degree, comprising;

splitting a result co from the multiplication of X(t) and Y(t) into a low portion c_0,1 and a high portion c_0,h such that c₀=c_0,h* tⁿ+c_0,1, where n is greater than or equal to the field degree m; and

partially reducing the result co of the multiplication by executing a series of polynomial multiplications and additions to produce a polynomial of degree less than n and congruent to co modulo M_m(t).

9. The method as recited in claim 8 wherein partially reducing the result comprises:

iteratively determining successive congruent polynomials c_j+1=c_j,h* t<sup>n−

m</sup>*(M_m(t)−

t^m)+c_j,l,=c_j+1,h*tⁿ+c_j+1,l, until c_j,h=0, where initially j=0.

10. The method as recited in claim 8 wherein partially reducing the result comprises:

iteratively determining successive congruent polynomials c_j+1=c_j,h*t<sup>n−

m</sup>*M_m(t)+c_j=c_j+1,h*tⁿ+c_j+1,l, until c_j,h=0, where initially j=0.

11. The method as recited in claim 8 wherein n is a maximum operand size of a multiplier in which the multiplication is performed.

12. The method as recited in claim 8 wherein n is a data path width of the multiplier.

13. The method as recited in claim 8 wherein n is a multiple of a digit size of the multiplier.

14. The method as recited in claim 8 wherein n is a multiple of a word size of a memory.

15. An elliptic curve processing apparatus for performing a multiplication of two elements X(t) and Y(t), over GF(2), where m is a field degree, and M_m(t) is an irreducible polynomial for GF(2^m), M_m(t)=t^m+a_m−

1t<sup>m−

1</sup>+a<sub>m−

2</sub>t<sup>m−

2</sup>+ . . . +a₁t+a₀, where the coefficients a_i are equal to either 1 or 0, and m is a field degree, comprising;

means for multiplying a first register (X) storing an initial value of X(t) and a second register Y storing an initial value of Y(t) and generating a result c₀=X(t)*Y(t);

means for providing c₀ as a low portion c_0,l and a high portion c_0,h such that c₀=c_0,h*tⁿ+c_0,l, where n is greater than or equal to the field degree m; and

means for partially reducing the result co of the multiplication by executing a series of polynomial multiplications and additions to produce a polynomial of degree less than n and congruent to c₀ modulo M_m(t).

16. The elliptic curve processing apparatus as recited in claim 15 wherein the means for partially reducing comprises:

means for iteratively determining successive congruent polynomials c_j+1=c_j,h*t<sup>n−

m</sup>*(M_m(t)−

t^m)+c_j,l,=c_j+1,h*tⁿ+c_j+1,l, until c_j,h=0, where j initially=0.

17. The elliptic curve processing apparatus as recited in claim 15 wherein the means for partially reducing comprises:

means for iteratively determining successive congruent polynomials c_j+1=c_j,h*t<sup>n−

m</sup>*M_m(t)+c_j=c_j+1,h*tⁿ+c_j+1,l, until c_j,h=0, where j initially=0.

18. The elliptic curve processing apparatus as recited in claim 15 wherein n is at least one of a maximum operand size, a data path width, a multiple of a digit size, a multiple of a word size of memory, and a register size in the elliptic curve processing apparatus.

19. An elliptic curve processing apparatus for performing a squaring operation of an element X(t), over GF(2), where m is a field degree, and M_m(t) is an irreducible polynomial for GF(2^m), comprising:

means for squaring X(t) to generate a result c₀=X(t)*X(t);

means for providing c₀ as a low portion c_0,l and a high portion c_0,h such that c₀=c_0,h*tⁿ+c_0,l, where n is greater than or equal to the field degree m; and

means for partially reducing the result c₀ of the multiplication by executing a series of polynomial multiplications and additions to produce a polynomial of degree less than n and congruent to c₀ modulo M_m(t).

20. A computer program product encoded on computer readable media comprising:

a first instruction sequence for multiplying a first polynomial X(t) and a second polynomial Y(t), both over GF(2), to generate a result c₀;

a second instruction sequence for partially reducing the result c₀ of the multiplication by executing a series of polynomial multiplications and additions to produce a polynomial of degree less than n, the polynomial of degree less than n, being congruent to c₀ modulo M_m(t), M_m(t)=t^m+a<sub>m−

1</sub>t<sup>m−

1</sup>+a<sub>m−

2</sub>t<sup>m−

2</sup>+ . . . +a₁t+a₀, where the coefficients a_i are equal to either 1 or 0, and m is a field degree, and

where n is at least one of a maximum operand size, a data path width, a multiple of a digit size, and a multiple of a word size of memory, and a multiple of a register size available in a processor in which the computer program product is executed.

21. The computer program product as recited in claim 20 wherein the second instruction sequence generates a polynomial c₁, congruent to c₀ modulo M(t), c₁ being equal to c_0,h*tⁿ⁻

m*(M_m(t)−

t^m)+c_0,l, where c_0,l is a low portion and c_0,h is a high portion such that c₀=c_0,h*t^n+c_0,l, where n is greater than or equal to the field degree m and for iteratively determining successive congruent polynomials c_j+1=c_j,h*t<sup>n−

m</sup>*(M_m(t)−

t^m)+c_j,l,=c_j+1,h*tⁿ+c_j+1,l, until c_j,h=0, where initially j=0, the successive congruent polynomials being congruent to co modulo M_m(t).

22. A computer program product encoded on computer readable media comprising:

a first instruction sequence for performing an arithmetic operation on two binary polynomials X(t) and Y(t) over GF(2) to generate a result c₀, where an irreducible polynomial M_m(t)=t^m+a<sub>m−

1</sub>t<sup>m−

1</sup>+a<sub>m−

2</sub>t<sup>m−

2</sup>+ . . . +a₁t+a₀, and where the coefficients as are equal to either 1 or 0, and m is a field degree, the result co being of a degree greater than or equal to n;

a second instruction sequence for partially reducing the result of the arithmetic operation on the two binary polynomials to produce a congruent polynomial of degree less than an integer n, with m being less than or equal to n, the second instruction sequence using one of a first and second polynomial M′ and

M″

, as part of partially reducing the result c₀, M′

=(M_m(t)−

t^m)*t<sup>n−

m</sup> and M″

=(M_m(t)*t<sup>n−

m</sup>).

23. A method for performing an arithmetic operation on a first and second binary polynomial X(t) and Y(t) over GF(2), where an irreducible polynomial M_m(t)=t^m+a_m−

1t<sup>m−

1</sup>+a<sub>m−

2</sub>t<sup>m−

2</sup>+ . . . +a₁t+a₀, and where the coefficients a_i are equal to either 1 or 0, and m is a field degree, the first and second binary polynomials being of degree less than m, the method comprising;

multiplying one of the polynomials and t<sup>n−

m</sup> to left align the first binary polynomial in an n bit register;

multiplying the left-aligned first binary polynomial and the second binary polynomial to generate a result of 2n bits with a high order portion of the result being n most significant bits and a low portion of the result being n least significant bits; and

reducing the result until the high order portion is zero, thereby providing a reduced result in the low order portion.

24. The method as recited in claim 23 further comprising aligning the result in the low order portion.

25. The method as recited in claim 24 wherein aligning the result comprises multiplying the reduced result by t^m to align the reduced result in the high order portion.

26. The method as recited in claim 23 wherein reducing the result comprises multiplying the high order portion and one of a first and second polynomial M′

and M″

, M′

=(M_m(t)−

t^m)*t<sup>n−

m</sup> and M″

=(M_m(t))*t<sup>n−

m</sup>.

27. An apparatus for performing an arithmetic operation on a first and second binary polynomial X(t) and Y(t) over GF(2), where an irreducible polynomial M_m(t)=t^m+a_m−

1t<sup>m−

1</sup>+a<sub>m−

2</sub>t<sup>m−

2</sup>+ . . . +a₁t+a₀, and where the coefficients a_i are equal to either 1 or 0, and m is a field degree, the first and second binary polynomials being of degree less than m, the apparatus comprising;

means for multiplying one of the polynomials and t<sup>n−

m</sup> to left align the first binary polynomial in an n bit register;

means for multiplying the left-aligned first binary polynomial and the second binary polynomial to generate a result of 2n bits with a high order portion of the result being n most significant bits and a low portion of the result being n least significant bits; and

means for reducing the result until the high order portion is zero, thereby providing a reduced result in the low order portion.

28. The apparatus as recited in claim 27 further comprising means for aligning the reduced result.