Apparatus and method for efficient arithmetic in finite fields through alternative representation

• US 6,199,087 B1
• Filed: 06/25/1998
• Issued: 03/06/2001
• Est. Priority Date: 06/25/1998
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Company (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Roth, Ron M., Seroussi, Gadiel, Blake, Ian F.
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US09/104,894
• Time in Patent Office: 985 Days
• Field of Search: 708/491-492, 380/28
• 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/726 Inversion; Reciprocal calculation; Division of elements of a finite field

Abstract

A method and apparatus are shown for performing efficient arithmetic on binary vectors in a finite field. Typically, there is an efficient algorithm within an execution context, such as hardware or software, for performing a selected arithmetic operation on an operand. When the operand is in a first representative format and the efficient algorithm operates in an alternative representation format, then the operand is permutated from the first representative format to the alternative representation format. The efficient algorithm is then performed on the operand in the alternative representation format in order to obtain a result in the alternative representation format. The result is then permutated from the alternative representation format to the first representation format. Thus, efficient arithmetic is obtained by using the most efficient algorithm available in either the first representation format or the alternative representation format and permuting operands and results to the representation format corresponding to the most efficient algorithm available.

Claims

1. A method for performing efficient arithmetic in a finite field in an elliptic curve cryptography application, the method comprising the steps:

receiving a first operand of the elliptic curve cryptography application having a first representation format;

permuting the first operand from the first representation format to an alternative representation format;

receiving a second operand of the elliptic curve cryptography application having the first representation format;

permuting the second operand from the first representation format to the alternative representation format;

generating a result for use in the elliptic curve cryptography application having the alternative representation format by performing a selected arithmetic operation on the first and second operands; and

permuting the result from the alternative representation format to the first representation format wherein the alternative representation format is preselected to enable the steps of permuting to be performed by a bit wise transposition between the first representation format and the alternative representation format.

2. The method of claim 1, wherein:

the finite field is defined as GF(2ⁿ); and

the first operand is defined as a vector of n binary elements of the finite field GF(2), such that the first operand has an ONB format (a<sub>n−

1</sub>, a<sub>n−

2</sub>, . . . , a₁, a₀); and

there is a prime p=2n+1, where p satisfies one of the following conditions;

(i) the multiplicative order of 2 modulo p is 2n, or

(ii) p≡

(3 modulo

     4) and the multiplicative order of 2 modulo p is n;

there is a one-to-one function π

;

{0, 1, 2, . . . , n−

1}→

{1, 2, 3, . . . , n} defined over 0≦

i≦

n−

1, where j=2ⁱ mod p, and if 0≦

j<

n, then π

(i)=j, else π

(i)=p−

j; and

there is an inverse function σ

;

{1, 2, 3, . . . , n}→

{0, 1, 2, . . . , n−

1} defined such that σ

(j)=i whenever π

(i)=j; and

wherein the step of permuting the format of the first operand from ONB to an alternative representation format includes permuting the first operand to an alternative format (b₁, b₂, . . . , b_n) by setting (b₁, b₂, . . . , b_n)=(a<sub>σ

(1)</sub>, a<sub>σ

(2)</sub>, . . . , a<sub>σ

(n)</sub>).

3. The method of claim 2, wherein the step permuting the format of the result from the alternative representation format to ONB format includes:

permuting the result from an alternative format (c₁, c₂, . . . , c_n) to an ONB format (d<sub>n−

1</sub>, d<sub>n−

2</sub>, . . . , d₁, d₀) by setting (d<sub>n−

1</sub>, d<sub>n−

2</sub>, . . . , d₁, d₀)=(c<sub>π

(n−

1)</sub>, C<sub>π

(n−

2)</sub>, . . . , c<sub>π

(1)</sub>, c<sub>π

(0)</sub>), respectively.

4. A method for performing an arithmetic operation on first and second n-length vectors having a first representation format in a finite field GF(2ⁿ) in a predetermined execution context of an elliptic curve cryptography application, the method comprising the steps:

selecting an efficient algorithm for the arithmetic operation based upon the predetermined execution context of the elliptic curve cryptography application;

selecting an execution representation format based upon the selected efficient algorithm, where the execution representation format is one of the first representation format and a second representation format;

permuting the first and second vectors from the first representation format to the second representation format when the selected execution representation format is the second representation format wherein the second representation format is preselected to enable the step of permuting to be performed by a bit wise transposition between the first representation format and the second representation format; and

performing the arithmetic operation on the first and second vectors to obtain a result for the elliptic curve cryptography application having the selected execution representation format.

5. The method of claim 4, further including:

permuting the result from the second representation format to the first representation format when the selected execution format is the second representation format.

6. The method of claim 5, wherein:

there exists a prime p=2n+1, where p satisfies one of the following conditions;

(i) the multiplicative order of 2 modulo p is 2n, or

(ii) p≡

(3 modulo

     4) and the multiplicative order of 2 modulo p is n;

there is a one-to-one function π

;

{0, 1, 2, . . . , n−

1}→

{1,2,3, . . . , n} defined over 0≦

i≦

n−

1, where j=2ⁱ mod p, and if 0<

j≦

n, then π

(i)=j, else π

(i)=p−

j; and

there is an inverse function σ

;

{1, 2, 3, . . . , n}→

{0, 1, 2, . . . , n−

1} defined such that π

(j)=i whenever π

(i)=j; and

the first representation format is optimal normal basis (ONB), where the first vector is represented by (a<sub>n−

1</sub>, a<sub>n−

2</sub>, . . . , a₁, a₀) and the second vector is represented by (e<sub>n−

1</sub>, e<sub>n−

2</sub>, . . . , e₁, e₀); and

the second representation format is palindromic where the first vector is represented by (b₁, b₂, . . . , b_n, b_n, . . . , b₂, b₁), and the second vector is represented by (f₁,f₂, . . . , f_n,f_n, . . . ,f₂,f_l); and

wherein the step of permuting the first and second vectors from the first representation format to the second representation format further comprises;

setting (b₁,b₂, . . . , b_n)=(a<sub>σ

(1)</sub>, a<sub>σ

(2)</sub>, . . . , a<sub>σ

(n)</sub>), respectively; and

setting (f₁,f₂, . . . , f_n)=(e<sub>σ

(l)</sub>, e<sub>σ

(2)</sub>, . . . , e<sub>σ

(n)</sub>), respectively.

7. The method of claim 6, wherein:

the result is represented by (d<sub>n−

1</sub>, d<sub>n−

2</sub>, . . . , d₁, d₀) in the ONB representation format; and

the result is represented by (c₁, c₂, . . . , c_n, c_n, . . . , c₂, c₁) in the palindromic format; and

the step of permuting the result from the second representation format to the first representation format when the selected execution format is the second representation format further comprises;

setting (d<sub>n−

1</sub>, d<sub>n−

2</sub>, . . . , d₁, d₀)=(c<sub>π

(n−

1)</sub>, c<sub>π

(n−

2)</sub>, . . . , c<sub>π

(1)</sub>, c<sub>π

(0)</sub>), respectively.

8. The method of claim 7, wherein the execution context is computer software, the arithmetic operation is multiplication, and the efficient algorithm is a polynomial multiplier algorithm and where the step of selecting an execution representation format based upon the selected efficient algorithm execution representation format includes:

selecting the palindromic format to be the execution representation format when the arithmetic operation is multiplication.

9. The method of claim 4, wherein the first representation format is palindromic, the second representation format is ONB, the execution context is hardware logic circuitry and where the efficient algorithm for multiplication is implemented in a ONB multiplier circuit and the efficient algorithm for inversion is implemented in a polynomial inverter circuit, and further wherein the step of selecting an execution format representation format based upon the selected efficient algorithm execution representation format includes:

selecting the ONB format to be the execution representation format when the arithmetic operation is multiplication; and

selecting the palindromic format to be the execution representation format when the arithmetic operation is inversion.

10. The method of claim 4, wherein the first representation format is ONB, the second representation format is palindromic, the execution context is hardware logic circuitry, and where the step of selecting an execution representation format based upon the selected efficient algorithm execution representation format includes:

selecting the ONB format to be the execution representation format when the arithmetic operation is multiplication; and

selecting the palindromic format to be the execution representation format when the arithmetic operation is inversion.

11. A method for performing an arithmetic operation on an n-length vector having a first and representation format in a finite field GF(2ⁿ) in a predetermined execution context of an elliptic curve cryptography application, the method comprising the steps:

selecting an efficient algorithm for the arithmetic operation based upon the predetermined execution context of the elliptic curve cryptography application;

selecting an execution representation format based upon the selected efficient algorithm, where the execution representation format is one of the first representation format and a second representation format;

permuting the vector from the first representation format to the second representation format when the selected execution representation format is the second representation format wherein the second representation format is preselected to enable the step of permuting to be performed by a bit wise transposition between the first representation format and the second representation format; and

performing the arithmetic operation on the vector to obtain a result for the elliptic curve cryptography application having the selected execution representation format.

12. The method of claim 11, further including:

permuting the result from the second representation format to the first representation format when the selected execution format is the second representation format.

13. The method of claim 12, wherein:

there exists a prime p=2n+1, where p satisfies one of the following conditions;

(i) the multiplicative order of 2 modulo p is 2n, or

(ii) p≡

(3 modulo

     4) and the multiplicative order of 2 modulo p is n;

there is a one-to-one functions π

;

{0, 1, 2, . . . , n−

1}→

{1, 2, 3, . . . , n} defined over 0≦

i≦

n−

1, where j=2ⁱ mod p, and if 0<

j≦

n, then π

(i)=j, else π

(i)=p−

j; and

there is an inverse function σ

;

{1, 2, 3, . . . , n}→

{0, 1, 2, . . . , n−

1} defined such that σ

(j)=i whenever π

(i)=j; and

the first representation format is optimal normal basis (ONB), where the vector is represented by (a<sub>n−

1</sub>, a<sub>n−

2</sub>, . . . , a₁, a₀); and

the second representation format is palindromic where the vector is represented by (b₁, b₂, . . . , b_n, b_n, . . . , b₂, b₁); and

wherein the step of permuting the vector from the first representation format to the second representation format further comprises;

setting (b₁, b₂, . . . , b_n, b_n, . . . , b₂, b₁)=(a<sub>σ

(1)</sub>, a<sub>σ

(2)</sub>, . . . , a<sub>σ

(n)</sub>, a<sub>σ

(n)</sub>, . . . , a<sub>σ

(2)</sub>, a<sub>σ

(1)</sub>), respectively.

14. The method of claim 13, wherein:

the result is represented by (d<sub>n−

1</sub>, d<sub>n−

2</sub>, . . . , d₁, d₀) in the ONB representation format; and

the result is represented by (c₁, c₂, . . . , c_n, c_n, . . . , c₂, c₁) in the palindromic format; and

the step of permuting the result from the second representation format to the first representation format when the selected execution format is the second representation format further comprises;

setting (d<sub>n−

1</sub>, d<sub>n−

2</sub>, . . . , d₁, d₀)=(c<sub>π

(n−

1)</sub>, c<sub>π

(n−

2)</sub>, . . . , c<sub>π

(1)</sub>, c<sub>π

(0)</sub>), respectively.

15. The method of claim 11, wherein the first representation format is ONB, the second representation format is palindromic, the execution context is hardware logic circuitry, and where the step of selecting an execution representation format based upon the selected efficient algorithm execution representation format includes:

selecting the palindromic format to be the execution representation format when the arithmetic operation is inversion.

16. A computer readable medium having stored therein a plurality of routines of an elliptic curve cryptography application comprising:

a first routine configured to convert a first operand having a first representation format to a second operand having a second representation formation;

a second routine configured to perform a first arithmetic operation on the second operand in order to obtain a first result having the second representation format; and

a third routine configured to convert the first result to a second result for the elliptic curve cryptography application having the first representation format;

wherein the second representation format is preselected to enable the first and third routines to convert by performing by a bit wise transposition between the first representation format and the second representation format.

17. The computer readable medium of claim 16, wherein:

the first representation format is ONB;

the second representation format is palindromic; and

the second routine is configured to perform an inversion operation on the second operand.

18. The computer readable medium of claim 16, wherein:

the first routine is further configured to convert a third operand having the first representation format to a fourth operand having the second representation format; and

the second routine is further configured to perform the first arithmetic operation on both the second and fourth operands in order to obtain the first result.

19. The computer readable medium of claim 18, wherein:

the first representation format is ONB;

the second representation format is palindromic; and

the second routine is configured to perform a multiplication operation on the second operand.

20. The computer readable medium of claim 16, wherein the first routine is further configured to convert the first operand to the second operand by a first algorithm wherein:

the first operand further comprises n binary elements of a finite field GF(2), such that the first operand has the format (a<sub>n−

1</sub>, a<sub>n−

2</sub>, . . . , a₁, a₀);

there is a prime p=2n+1, where p satisfies one of the following conditions;

(i) the multiplicative order of 2 modulo p is 2n, or

(ii) p≡

(3 modulo

     4) and the multiplicative order of 2 modulo p is n;

there is a one-to-one function π

;

{0, 1, 2, . . . , n−

1}→

{1, 2, 3, . . . , n} defined over 0≦

i≦

n−

1, where j=2ⁱ mod p, and if 0<

j≦

n, then π

(i)=j, else π

(i)=p−

j;

there is an inverse function σ

;

{1, 2, 3, . . . , n}→

{0, 1, 2, . . . , n−

1} defined such that σ

(j)=i whenever π

(i)=j; and

wherein the second operand has the format (b₁, b₂, . . . , b_n), where (b₁, b₂, . . . b_n)=(a<sub>σ

(l)</sub>, a<sub>σ

(2)</sub>, . . . , a<sub>σ

(n)</sub>).

21. The computer readable medium of claim 20, wherein the third routine is further configured to convert the first result to the second result by a second algorithm wherein:

the first result has the format (c₁, c₂, . . . , c_n); and

the second result has the format (d<sub>n−

1</sub>, d<sub>n−

2</sub>, . . . , d₁, d₀), where (d<sub>n−

1</sub>, d<sub>n−

2</sub>, . . . , d₁, d₀)=(c<sub>π

(n−

1)</sub>, c<sub>π

(n−

2)</sub>, . . . , c<sub>π

(1)</sub>, c<sub>π

(0)</sub>).

22. The computer readable medium of claim 16, further including:

a fourth routine configured to perform a second arithmetic operation upon the first operand and produce a third result having the first representation format; and

a fifth routine configured to select one of the first arithmetic operation and a second arithmetic operation, and wherein the fifth routine is further configured to invoke the first, second and third routines when the first arithmetic operation is invoked, and further wherein the fifth routine is configured to invoke the fourth routine when the second arithmetic operation is selected.