Scheme for arithmetic operations in finite field and group operations over elliptic curves realizing improved computational speed

• US 6,038,581 A
• Filed: 01/28/1998
• Issued: 03/14/2000
• Est. Priority Date: 01/29/1997
• Status: Expired due to Term

• Current Assignee: Nippon Telegraph and Telephone Corporation
• Original Assignee: Nippon Telegraph and Telephone Corporation
• Inventors: Aoki, Kazumaro, Ohta, Kazuo
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US09/014,891
• Time in Patent Office: 776 Days
• Field of Search: 708/492, 714/752, 714/758, 380/28, 326/8
• US Class Current: 708/492
• 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: G06F 7/726 Inversion; Reciprocal calculation; Division of elements of a finite field

Abstract

A scheme for arithmetic operations in finite field and group operations over elliptic curves capable of realizing a very fast implementation. According to this scheme, by using a normal basis [α α+1], the multiplicative inverse calculation and the multiplication in the finite field GF(2²ⁿ) can be realized as combinations of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2ⁿ). Also, by using a standard basis [1α], the multiplication, the square calculation, and the multiplicative inverse calculation in the finite field GF(2²ⁿ) can be realized as combinations of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2ⁿ). These arithmetic operations can be utilized for calculating rational expressions expressing group operations over elliptic curves that are used in information security techniques such as elliptic curve cryptosystems.

Claims

1. A method for calculating a multiplicative inverse in finite field GF(2²ⁿ), comprising the steps of:

expressing an element m.di-elect cons.GF(2²ⁿ) as

space="preserve" listing-type="equation">m=xα

+y(α

+1)(x,y.di-elect cons.GF(2.sup.n))

where α

.di-elect cons.GF(2²ⁿ)\GF(2ⁿ), α

² +α

+a=0, and a.di-elect cons.GF(2ⁿ) so that a multiplicative inverse m^-1 of the element m in the finite field GF(2²ⁿ) is expressed as a combination of multiplications, additions and a multiplicative inverse calculation in subfield GF(2ⁿ) given by

space="preserve" listing-type="equation">m.sup.-1 =(a(x+y).sup.2 +xy).sup.-1 yα

+(a(x+y).sup.2 +xy).sup.-1 x(α

+1)

by combining a normal basis [α

α

+1] with extended Euclidean algorithm; and

calculating the multiplicative inverse m^-1 of the element m in the finite field GF(2²ⁿ) by executing said combination of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2ⁿ).

2. The method of claim 1, wherein the calculating step calculates a multiplicative inverse x^-1 of an element X.di-elect cons.GF(2ⁿ) by:

obtaining e=log_g x by looking up a logarithmic conversion table provided in advance, where g is a primitive element in the subfield GF(2ⁿ);

calculating f=-e mod (2ⁿ -1); and

obtaining x^-1 =g^f by looking up an exponential conversion table provided in advance.

3. The method of claim 1, wherein the calculating step converts a multiplication in the subfield GF(2ⁿ) into an addition in additive cyclic group Z/(2ⁿ -1)Z that can be calculated by logarithmic conversion, and re-converts calculation result of the addition in the additive cyclic group Z/(2ⁿ -1l)Z into the subfield GF(2ⁿ) by exponential conversion.

4. The method of claim 1, further comprising the step of:

storing calculation results of multiplications in subfield GF(2ⁿ) into a fast read accessible memory as a multiplication table in advance, so that the calculating step obtains calculation results of multiplications in the subfield GF(2ⁿ) by looking up the multiplication table.

5. The method of claim 1, further comprising the step of:

storing calculation results of multiplications in subfield GF(2ⁿ) for cases where one number to be multiplied is a constant into a memory as a multiplication table in advance, so that the calculating step obtains calculation results of multiplications in the subfield GF(2ⁿ) for said cases by looking up the multiplication table.

6. The method of claim 1, wherein the calculating step reduces multiplications in the subfield GF(2ⁿ) into multiplications, additions and a multiplicative inverse calculation in subfield GF(2^n/2).

7. The method of claim 1, wherein the calculating step calculates a multiplication using one element in the subfield GF(2ⁿ) by looking up a logarithmic conversion table provided in advance, stores a logarithm corresponding to said one element obtained from the logarithmic conversion table, and calculates a subsequent multiplication using said one element by using stored logarithm corresponding to said one element without looking up the logarithmic conversion table.

8. A method for calculating a multiplication in finite field GF(2²ⁿ), comprising the steps of:

reducing a multiplication of two elements m₁ and m₂ in GF(2²ⁿ) into multiplications and additions in subfield GF(2ⁿ) by expressing m₁, m₂ .di-elect cons.GF(2²ⁿ) as

space="preserve" listing-type="equation">m.sub.1 =x.sub.1 α

+y.sub.1 (α

+1), m.sub.2 =x.sub.2 α

+y.sub.2 (α

+1)

where x_i, y_i .di-elect cons.GF(2ⁿ), i=1, 2, α

.di-elect cons.GF(2²ⁿ)\GF(2ⁿ), α

² +α

+a=0, and a.di-elect cons.GF(2ⁿ) so that a multiplication m₀ of m₁, m₂ .di-elect cons.GF(2²ⁿ) is given by

space="preserve" listing-type="equation">m.sub.0 =m.sub.1 m.sub.2 =(x.sub.1 x.sub.2 +a(x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2))α

+(y.sub.1 y.sub.2 +a(x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2))(α

+1); and

calculating the multiplication m₀ by executing said multiplications and additions in the subfield GF(2ⁿ).

9. A device for calculating a multiplicative inverse in finite field GF(2²ⁿ), comprising:

an input unit for expressing an element m.di-elect cons.GF(2²ⁿ) as

space="preserve" listing-type="equation">m=xα

+y(α

+1)(x,y.di-elect cons.GF(2.sup.n))

where α

.di-elect cons.GF(2²ⁿ)\GF(2ⁿ), α

² +α

+a=0, and a.di-elect cons.GF(2ⁿ) so that a multiplicative inverse m^-1 of the element m in the finite field GF(2²ⁿ) is expressed as a combination of multiplications, additions and a multiplicative inverse calculation in subfield GF(2ⁿ) given by

space="preserve" listing-type="equation">m.sup.-1 =(a(x+y).sup.2 +xy).sup.-1 yα

+(a(x+y).sup.2 +xy).sup.-1 x(α

+1)

by combining a normal basis [α

α

+1] with extended Euclidean algorithm; and

a calculation unit for calculating the multiplicative inverse m^-1 of the element m in the finite field GF(2²ⁿ) by executing said combination of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2ⁿ).

10. A device for calculating a multiplication in finite field GF(2²ⁿ), comprising:

an input unit for reducing a multiplication of two elements m₁ and m₂ in GF(2²ⁿ) into multiplications and additions in subfield GF(2ⁿ) by expressing m₁, m₂ .di-elect cons.GF(2²ⁿ) as

space="preserve" listing-type="equation">m.sub.1 =x.sub.1 α

+y.sub.1 (α

+1), m.sub.2 =x.sub.2 α

+y.sub.2 (α

+1)

where x_i, y_i .di-elect cons.GF(2ⁿ), i=1, 2, α

.di-elect cons.GF(2²ⁿ)\GF(2ⁿ), α

² +α

+a=0, and a.di-elect cons.GF(2ⁿ) so that a multiplication m₀ of m₁, m₂ .di-elect cons.GF(2²ⁿ) is given by

space="preserve" listing-type="equation">m.sub.0 =m.sub.1 m.sub.2 =(x.sub.1 x.sub.2 +a(x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2))α

+(y.sub.1 y.sub.2 +a(x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2))(α

+1); and

a calculation unit for calculating the multiplication m₀ by executing said multiplications and additions in the subfield GF(2ⁿ).

11. An article of manufacture, comprising:

a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a system for calculating a multiplicative inverse in finite field GF(2²ⁿ), the computer readable program code means includes;

first computer readable program code means for causing said computer to express an element m.di-elect cons.GF(2²ⁿ) as

space="preserve" listing-type="equation">m=xα

+y(α

+1)(x,y.di-elect cons.GF(2.sup.n))

where α

.di-elect cons.GF(2²ⁿ)\GF(2ⁿ), α

² +α

+a=0, and a.di-elect cons.GF(2ⁿ) so that a multiplicative inverse m^-1 of the element m in the finite field GF(2²ⁿ) is expressed as a combination of multiplications, additions and a multiplicative inverse calculation in subfield GF(2ⁿ) given by

space="preserve" listing-type="equation">m.sup.-1 =(a(x+y).sup.2 +xy).sup.-1 yα

+(a(x+y).sup.2 +xy).sup.-1 x(α

+1)

by combining a normal basis [α

α

+1] with extended Euclidean algorithm; and

second computer readable program code means for causing said computer to calculate the multiplicative inverse m^-1 of the element m in the finite field GF(2²ⁿ) by executing said combination of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2ⁿ).

12. An article of manufacture, comprising:

a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a system for calculating a multiplication in finite field GF(2²ⁿ), the computer readable program code means includes;

first computer readable program code means for causing said computer to reduce a multiplication of two elements m₁ and m₂ in GF(2²ⁿ) into multiplications and additions in subfield GF(2ⁿ) by expressing m₁, m₂ .di-elect cons.GF(2²ⁿ) as

space="preserve" listing-type="equation">m.sub.1 =x.sub.1 α

+y.sub.1 (α

+1), m.sub.2 =x.sub.2 α

+y.sub.2 (α

+1)

where x₁, y₁ .di-elect cons.GF(2ⁿ), i=1, 2, α

.di-elect cons.GF(2²ⁿ)\GF(2ⁿ), α

² +α

+a=0, and a.di-elect cons.GF(2ⁿ) so that a multiplication m₀ of m₁, m₂ .di-elect cons.GF(2²ⁿ) is given by

space="preserve" listing-type="equation">m.sub.0 =m.sub.1 m.sub.2 =(x.sub.1 x.sub.2 +a(x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2))α

+(y.sub.1 y.sub.2 +a(x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2))(α

+1); and

second computer readable program code means for causing said computer to calculate the multiplication m₀ by executing said multiplications and additions in the subfield GF(2ⁿ).

13. A method for calculating a multiplication in finite field GF(2²ⁿ), comprising the steps of:

expressing elements m₁, m₂ .di-elect cons.GF(2²ⁿ)≃

GF(2ⁿ)[x]/(x² +x+a) as

space="preserve" listing-type="equation">m.sub.1 =x.sub.1 +y.sub.1 α

space="preserve" listing-type="equation">m.sub.2 =x.sub.2 +y.sub.2 α

(x.sub.1, x.sub.2, y.sub.1, y.sub.2 .di-elect cons.GF(2.sup.n))

where α

.epsilon slash.GF(2ⁿ), α

² +α

+a=0, and a.di-elect cons.GF(2ⁿ) so that a multiplication m₁ m₂ of the elements m₁ and m₂ in the finite field GF(2²ⁿ) is expressed as a combination of multiplications and additions in subfield GF(2ⁿ) given by

space="preserve" listing-type="equation">m.sub.1 m.sub.2 =(x.sub.1 x.sub.2 +ay.sub.1 y.sub.2)+((x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2)+x.sub.1 x.sub.2)α

by using a standard basis [1α

]; and

calculating the multiplication m₁ m₂ of the elements m₁ and m₂ in the finite field GF(2²ⁿ) by executing said combination of multiplications and additions in the subfield GF(2ⁿ).

14. A method for calculating a multiplicative inverse in finite field GF(2²ⁿ), comprising the steps of:

expressing an element m.di-elect cons.GF(2²ⁿ)≃

GF(2ⁿ) [x]/(x² +x+a) as

space="preserve" listing-type="equation">m=x+yα

(x,y.di-elect cons.GF(2.sup.n))

where α

.epsilon slash.GF(2ⁿ), α

² +α

+a=0, and a .di-elect cons.GF(2ⁿ) so that a multiplicative inverse m^-1 of the element m in the finite field GF(2²ⁿ) is expressed as a combination of multiplications, additions and a multiplicative inverse calculation in subfield GF(2ⁿ) given by

space="preserve" listing-type="equation">m.sup.-1 =(x(x+y)+ay.sup.2).sup.-1 ((x+y)+yα

)

by using a standard basis [1α

]; and

calculating the multiplicative inverse m^-1 of the element m in the finite field GF(2²ⁿ) by executing said combination of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2ⁿ).

15. A device for calculating a multiplication in finite field GF(2²ⁿ), comprising:

an input unit for expressing elements m₁, m₂ .di-elect cons.GF(2²ⁿ) ≃

GF(2ⁿ)[x]/(x² +x+a) as

space="preserve" listing-type="equation">m.sub.1 =x.sub.1 +y.sub.1 α

space="preserve" listing-type="equation">m.sub.2 =x.sub.2 +y.sub.2 α

(x.sub.1, x.sub.2, y.sub.1, y.sub.2 .di-elect cons.GF(2.sup.n))

where α

.epsilon slash.GF(2ⁿ), α

² +α

+a=0, and a.di-elect cons.GF(2ⁿ) so that a multiplication m₁ m₂ of the elements m₁ and m₂ in the finite field GF(2²ⁿ) is expressed as a combination of multiplications and additions in subfield GF(2ⁿ) given by

space="preserve" listing-type="equation">m.sub.1 m.sub.2 =(x.sub.1 x.sub.2 ay.sub.1 y.sub.2)+((x.sub.1 +y.sub.1) (x.sub.2 +y.sub.2)+x.sub.1 x.sub.2)α

by using a standard basis [1α

]; and

a calculation unit for calculating the multiplication m₁ m₂ of the elements m₁ and m₂ in the finite field GF(2²ⁿ) by executing said combination of multiplications and additions in the subfield GF(2ⁿ).

16. A device for calculating a multiplicative inverse in finite field GF(2²ⁿ), comprising:

an input unit for expressing an element m.di-elect cons.GF(2²ⁿ)≃

GF(2ⁿ)[x]/(x² +x+a) as

space="preserve" listing-type="equation">m=x+yα

(x,y.di-elect cons.GF(2.sup.n))

where α

.epsilon slash.GF(2ⁿ), α

² +α

+a=0, and a.di-elect cons.GF(2ⁿ) so that a multiplicative inverse m^-1 of the element m in the finite field GF(2²ⁿ) is expressed as a combination of multiplications, additions and a multiplicative inverse calculation in subfield GF(2ⁿ) given by

space="preserve" listing-type="equation">m.sup.-1 =(x(x+y)+ay.sup.2).sup.-1 ((x+y)+yα

)

by using a standard basis [1α

]; and

a calculation unit for calculating the multiplicative inverse m^-1 of the element m in the finite field GF(2²ⁿ) by executing said combination of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2ⁿ).

17. An article of manufacture, comprising:

a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a system for calculating a multiplication in finite field GF(2²ⁿ), the computer readable program code means includes;

first computer readable program code means for causing said computer to express elements m₁, m₂ .di-elect cons.GF(2²ⁿ)≃

GF(2ⁿ)[x]/(x² +x+a) as

space="preserve" listing-type="equation">m.sub.1 =x.sub.1 +y.sub.1 α

space="preserve" listing-type="equation">m.sub.2 =x.sub.2 +y.sub.2 α

(x.sub.1, x.sub.2, y.sub.1, y.sub.2 .di-elect cons.GF(2.sup.n))

where α

.epsilon slash.GF(2ⁿ), α

² +α

+a=0, and a.di-elect cons.GF(2ⁿ) so that a multiplication m₁ m₂ of the elements m₁ and m₂ in the finite field GF(2²ⁿ) is expressed as a combination of multiplications and additions in subfield GF(2ⁿ) given by

space="preserve" listing-type="equation">m.sub.1 m.sub.2 =(x.sub.1 x.sub.2 +ay.sub.1 y.sub.2)+((x.sub.1 +y.sub.1)(x.sub.2 +y.sub.2)+x.sub.1 x.sub.2)α

by using a standard basis [1α

]; and

second computer readable program code means for causing said computer to calculate the multiplication m₁ m₂ of the elements m₁ and m₂ in the finite field GF(2²ⁿ) by executing said combination of multiplications and additions in the subfield GF(2ⁿ).

18. An article of manufacture, comprising:

a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a system for calculating a multiplicative inverse in finite field GF(2²ⁿ), the computer readable program code means includes;

first computer readable program code means for causing said computer to express an element m.di-elect cons.GF(2²ⁿ)≃

GF(2ⁿ)[x]/(x² +x+a) as

space="preserve" listing-type="equation">m=x+yα

(x,y.di-elect cons.GF(2.sup.n))

where α

.epsilon slash.GF(2ⁿ), α

² +α

+a=0, and a.di-elect cons.GF(2ⁿ) so that a multiplicative inverse m^-1 of the element m in the finite field GF(2²ⁿ) is expressed as a combination of multiplications, additions and a multiplicative inverse calculation in subfield GF(2ⁿ) given by

space="preserve" listing-type="equation">m.sup.-1 =(x(x+y)+ay.sup.2).sup.-1 ((x+y)+yα

)

using a standard basis [1α

]; and

second computer readable program code means for causing said computer to calculate the multiplicative inverse m^-1 of the element m in the finite field GF(2²ⁿ) by executing said combination of multiplications, additions and a multiplicative inverse calculation in the subfield GF(2ⁿ).