System and method for efficient basis conversion

• US 8,145,697 B2
• Filed: 10/31/2007
• Issued: 03/27/2012
• Est. Priority Date: 03/12/1999
• Status: Expired due to Term

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Lambert, Robert J.
• Primary Examiner(s): Ngo, Chuong D
• Application Number:
  US11/931,236
• Publication Number:
  US 20080177814A1
• Time in Patent Office: 1,609 Days
• Field of Search: 708/492, 380 28- 30
• US Class Current: 708/492
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06F 2207/7209 Calculation via subfield, i.e. the subfield being GF(q) with q a prime power, e.g. GF ((2**m)**n) via GF(2**m)
• 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: H04L 9/08 Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords network architectures or network communication protocols for supporting key management in a packet data network H04L63/06
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes

Abstract

This invention describes a method for evaluating a polynomial in an extension field F_q^m, wherein the method comprises the steps of partitioning the polynomial into a plurality of parts, each part is comprised of smaller polynomials using a q^-th power operation in a field of characteristic q; and computing for each part components of q^th powers from components of smaller powers. A further embodiment of the invention provides for a method of converting a field element represented in terms of a first basis to its representation in a second basis, comprising the steps of partitioning a polynomial, being a polynomial in the second basis, into a plurality of parts, wherein each part is comprised of smaller polynomials using a q^th power operation in a field of characteristic q; evaluating the polynomial at a root thereof by computing for each part components of q^th powers from components of smaller powers; and evaluating the field element at the root of the polynomial.

Claims

1. A non-transitory computer readable medium comprising computer executable instructions for a processor in a device converting an element of a finite field of characteristic q in a cryptographic system from a representation in a first basis defined by a first irreducible polynomial to a representation in a second basis defined by a second irreducible polynomial, wherein said representation in said second basis is to be used in a cryptographic scheme, said computer readable medium comprising instructions for:

a) obtaining said element from said cryptographic system;

b) representing said element of said finite field in said first basis as a polynomial a(x);

c) determining a root r of said second irreducible polynomial; and

d) evaluating said polynomial a(x) at said root r to obtain a representation a(r) of a(x) in said second basis for use in said cryptographic scheme;

said evaluation being characterised by the steps of;

i) partitioning said polynomial a(x) into a plurality of component polynomials, such that said polynomial a(x) is recoverable by combining said plurality of component polynomials using operations of multiplication by x and exponentiation by q;

ii) obtaining values of each of said component polynomials by evaluating each of said component polynomials at said root r; and

iii) computing the value of a(r) from said values of said component polynomials at said root r, using operations of multiplication by r and exponentiation by q.

2. The non-transitory computer readable medium according to claim 1, wherein the evaluation of said component polynomials comprises evaluating said component polynomials directly.

3. The non-transitory computer readable medium according to claim 1, wherein the evaluation of said component polynomials comprises using Horner'"'"'s rule.

4. The non-transitory computer readable medium according to claim 1, wherein said polynomial a(x) is partitioned into q component polynomials C₀, C₁, . . . , C_q−

1.

5. The non-transitory computer readable medium according to claim 4, wherein said component polynomials are combined using the formula

a(r)=(C₀(r))^q+r(C₁(r))^q+r²(C₁(r))^q+ . . . +r ^q−

1(C<sub>q−

1</sub>))^q.

6. The non-transitory computer readable medium according to claim 1, wherein said polynomial a(x) is partitioned into q² component polynomials C₀, C₁, . . . , C_q2−

1.

7. The non-transitory computer readable medium according to claim 6, wherein said component polynomials are combined using the formula

8. The non-transitory computer readable medium according to claim 7, wherein said finite field is F_2m and said characteristic q is equal to 2.

9. The non-transitory computer readable medium according to claim 8, wherein said polynomial a(x) is partitioned into 2 component polynomials b(x) and c(x).

10. The non-transitory computer readable medium according to claim 9, wherein said component polynomials are combined using the formula:

a(r)=(b(r))²+r(c(r))².

11. The non-transitory computer readable medium according to claim 8, wherein said polynomial a(x) is partitioned into 4 component polynomials C₀, C₁, C₂, C₃.

12. The non-transitory computer readable medium according to claim 11, wherein said component polynomials are combined using the formula:

a(r)=(C₀(r))²+r(C₁(r))²+r((C₂(r))²+r(C₃(r))²)².

13. The non-transitory computer readable medium according to claim 8, wherein said finite field is F₂₁₆₃.

14. The non-transitory computer readable medium according to claim 1, in which the evaluation of the component polynomials further comprises the steps of:

determining a set of exponents of x appearing in the component polynomial, such that all exponents appearing in said component polynomial are q-multiples of the exponents in said set of exponents;

computing the exponentiation of r to the exponents in the set of exponents to obtain a first set of exponentiations;

computing the exponentiation of r to q-multiples of the exponents in said set of exponents using the first set of exponentiations and the operation of exponentiation by q to obtain a second set of exponentiations; and

combining said first and second sets of exponentiations in accordance with said component polynomial to obtain the value of said component polynomial.

15. The non-transitory computer readable medium according to claim 14, wherein said finite field is F_2m whereby said characteristic q is equal to 2.

16. The non-transitory computer readable medium according to claim 15, wherein said finite field is F₂₁₆₃.

17. The non-transitory computer readable medium according to claim 15, wherein a set of exponentiations by odd ones of said set of exponents is precomputed and used for multiple basis conversions.

18. The non-transitory computer readable medium according to claim 1 wherein said cryptographic scheme is any one of a key exchange scheme, a signature scheme, and an encryption scheme.

19. A cryptographic system for converting an element of a finite field of characteristic q from a representation in a first basis defined by a first irreducible polynomial to a representation in a second basis defined by a second irreducible polynomial, wherein said representation in said second basis is to be used in a cryptographic scheme, said cryptographic system comprising:

a device comprising an accumulator, and a processor for converting said element from said first basis to said second basis using said accumulator; and

computer executable instructions that when executed by said processor, configure said processor for;

a) obtaining said element from said cryptographic system;

b) representing said element of said finite field in said first basis as a polynomial a(x);

c) determining a root r of said second irreducible polynomial; and

d) evaluating said polynomial a(x) at said root r to obtain a representation a(r) of a(x) in said second basis for use in said cryptographic scheme;

said evaluation being characterised by the steps of;

i)a partitioning said polynomial a(x) into a plurality of component polynomials, such that said polynomial a(x) is recoverable by combining said plurality of component polynomials using operations of multiplication by x and exponentiation by q;

ii) obtaining values of each of said component polynomials by evaluating each of said component polynomials at said root r; and

iii) computing the value of a(r) from said values of said component polynomials at said root r, using operations of multiplication by r and exponentiation by q.

20. The system according to claim 19, wherein the evaluation of said component polynomials comprises evaluating said component polynomials directly.

21. The system according to claim 19, wherein the evaluation of said component polynomials comprises using Horner'"'"'s rule.

22. The system according to claim 19, wherein said polynomial a(x) is partitioned into q component polynomials C₀, C₁, . . . , C_q−

1.

23. The system according to claim 22, wherein said component polynomials are combined using the formula

a(r)=(C₀(r))^q+r(C₁(r))^q+r²(C₁(r))^q+ . . . +r^q−

1(C<sub>q−

1</sub>(r))^q.

24. The system according to claim 19, wherein said polynomial a(x) is partitioned into q² component polynomials C₀, C₁, . . . , C_q2−

1.

25. The system according to claim 24, wherein said component polynomials are combined using the formula

26. The system according to claim 25, wherein said finite field is F_2m and said characteristic q is equal to 2.

27. The system according to claim 26, wherein said polynomial a(x) is partitioned into 2 component polynomials b(x) and c(x).

28. The system according to claim 27, wherein said component polynomials are combined using the formula:

a(r)=(b(r))²+r(c(r))².

29. The system according to claim 26, wherein said polynomial a(x) is partitioned into 4 component polynomials C₀, C₁, C₂, C₃.

30. The system according to claim 29, wherein said component polynomials are combined using the formula:

a(r)=(C₀(r))²+r(C₁(r))²+r((C₂(r))²+r(C ₃(r))²)².

31. The system according to claim 26, wherein said finite field is F₂₁₆₃.

32. The system according to claim 19, in which the evaluation of the component polynomials further comprises the steps of:

determining a set of exponents of x appearing in the component polynomial, such that all exponents appearing in said component polynomial are q-multiples of the exponents in said set of exponents;

computing the exponentiation of r to the exponents in the set of exponents to obtain a first set of exponentiations;

computing the exponentiation of r to q-multiples of the exponents in the said set of exponents using the first set of exponentiations and the operation of exponentiation by q to obtain a second set of exponentiations; and

combining said first and second sets of exponentiations in accordance with said component polynomial to obtain the value of said component polynomial.

33. The system according to claim 32, wherein said finite field is F_2m whereby said characteristic q is equal to 2.

34. The system according to claim 33, wherein said finite field is F₂₁₆₃.

35. The system according to claim 33, wherein a set of exponentiations by odd ones of said set of exponents is precomputed and used for multiple basis conversions.

36. The system according to claim 19, wherein said cryptographic scheme is any one of a key exchange scheme, a signature scheme, and an encryption scheme.

37. A non-transitory computer readable medium for evaluating a first irreducible polynomial a(x) at a root r to obtain a representation a(r) in a second basis, said computer readable medium to be used in a cryptographic scheme by a device having a processor and an accumulator for converting an element of a finite field of characteristic q stored in a cryptographic system from a representation in a first basis defined by said first irreducible polynomial to a representation in said second basis defined by a second irreducible polynomial, said computer readable medium comprising instructions for:

a) obtaining said first irreducible polynomial a(x) and said root r of said second irreducible polynomial from said cryptographic system, said first irreducible polynomial representing said element of said finite field in said first basis;

b) partitioning said first irreducible polynomial a(x) into a plurality of component polynomials, such that said first irreducible polynomial a(x) is recoverable by combining said plurality of component polynomials using operations of multiplication by x and exponentiation by q, said first irreducible polynomial a(x) representing an element of a finite field of characteristic g in a first basis;

c) obtaining values of each of said component polynomials by evaluating each of said component polynomials at said root r;

d) computing the value of a second irreducible polynomial a(r) in a second basis from the values of said component polynomials at said root r using operations of multiplication by r and exponentiation by q and;

e) providing said second irreducible polynomial a(r) to said cryptographic scheme.

38. The non-transitory computer readable medium according to claim 37, wherein the computation of said component polynomials further comprises the steps of:

determining a set of exponents of x appearing in the component polynomial, such that all exponents appearing in said component polynomial are q-multiples of the exponents in said set of exponents;

computing the exponentiation of r to the exponents in the set of exponents to obtain a first set of exponentiations;

computing the exponentiation of r to q-multiples of the exponents in said set of exponents using the first set of exponentiations and the operation of exponentiation by q to obtain a second set of exponentiations; and

combining said first and second sets of exponentiations in accordance with said component polynomial to obtain the value of said component polynomial.

39. The non-transitory computer readable medium according to claim 37 wherein said cryptographic scheme is any one of a key exchange scheme, a signature scheme, and an encryption scheme.

40. A cryptographic system for evaluating a first irreducible polynomial a(x) at a root r to obtain a representation a(r) in a second basis, said cryptographic system configured for participating in a cryptographic scheme for converting an element of a finite field of characteristic q from a representation in a first basis defined by said first irreducible polynomial to a representation in said second basis defined by a second irreducible polynomial, said cryptographic system comprising:

a device comprising an accumulator for operating on said finite field of characteristic q;

said first irreducible polynomial a(x), and said root r of said second irreducible polynomial, and a processor for obtaining said first irreducible polynomial a(x) and said root r of said second irreducible polynomial and for evaluating said first irreducible polynomial a(x) at said root r using said accumulator; and

computer executable instructions that when executed by said processor, configure said processor for;

a) obtaining said first irreducible polynomial a(x) and said root r of said second irreducible polynomial, said first irreducible polynomial representing said element of said finite field in said first basis;

b) partitioning said first irreducible polynomial a(x) into a plurality of component polynomials, such that said first irreducible polynomial a(x) is recoverable by combining said plurality of component polynomials using operations of multiplication by x and exponentiation by q, said first irreducible polynomial a(x) representing an element of a finite field of characteristic q in a first basis;

c) obtaining values of each of said component polynomials by evaluating each of said component polynomials at said root r;

d) computing the value of a second irreducible polynomial a(r) in a second basis from the values of said component polynomials at said root r using operations of multiplication by r and exponentiation by q and;

e) providing said second irreducible polynomial a(r) to said cryptographic scheme.

41. The system according to claim 40, wherein the computation of said component polynomials further comprises the steps of:

determining a set of exponents of x appearing in the component polynomial, such that all exponents appearing in said component polynomial are q-multiples of the exponents in said set of exponents;

computing the exponentiation of r to the exponents in the set of exponents to obtain a first set of exponentiations;

computing the exponentiation of r to q-multiples of the exponents in said set of exponents using the first set of exponentiations and the operation of exponentiation by q to obtain a second set of exponentiations; and

combining said first and second sets of exponentiations in accordance with said component polynomial to obtain the value of said component polynomial.

42. The system according to claim 40 wherein said cryptographic scheme is any one of a key exchange scheme, a signature scheme, and an encryption scheme.