System and method for efficient basis conversion

• US 7,299,253 B2
• Filed: 09/10/2001
• Issued: 11/20/2007
• 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): Do; Chat C.
• Application Number:
  US09/948,793
• Publication Number:
  US 20020041682A1
• Time in Patent Office: 2,262 Days
• Field of Search: 708491-492, 380/44
• 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 method 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 a first irreducible polynomial to a representation in a second basis defined by a second irreducible polynomial, wherein said representation in said second basic is to be used in a cryptographic scheme, said method comprising the steps of:

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;

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 system;

said evaluation being characterised by the steps of;

e) 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 the operations of multiplication by x and exponentiation by q;

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

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

h) providing said representation a(r) in said second basis to said cryptographic scheme.

2. A method according to claim 1, wherein the evaluation of said component polynomials comprises evaluating said component polynomials directly.

3. A method according to claim 1, wherein the evaluation of said component polynomials comprises using Horner'"'"'s rule to evaluate said component polynomials.

4. A method according to claim 1, wherein said polynomial a(x) is partitioned into q component polynomials C₀, C₁, . . . , C_q−

1.

5. A method 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>(r))^q.

6. A method according to claim 1, wherein said polynomial a(x) is partitioned into q² component polynomials C₀, C₁, . . . , C_q2−

1.

7. A method according to claim 6, wherein said component polynomials are combined using the formula

$a$

( r ) = ∑

i = 0 q - 1 ⁢

⁢

r i ⁡

( ∑

j = 0 q - 1 ⁢

⁢

r i ⁡

( C j + qi ⁡

( r ) ) q ) q .

8. A method according to claim 1, wherein said finite field is F_2m and said characteristic q is equal to 2.

9. A method according to claim 8, wherein said polynomial a(x) is partitioned into 2 component polynomials b(x) and c(x).

10. A method according to claim 9, wherein said component polynomials are combined using the formula a(r)=(b(r))²+r(c(r))².

11. A method according to claim 8, wherein said polynomial a(x) is partitioned into 4 component polynomials C₀, C₁, C₂, C₃.

12. A method 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. A method according to claim 8, wherein said finite field is F₂₁₆₃.

14. The method of claim 1, in which the evaluation of the component polynomials is further characterised by the steps of:

a) 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;

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

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

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

15. A method according to claim 14, wherein said finite field is F_2m whereby said characteristic q is equal to 2.

16. A method according to claim 15, wherein said finite field is F₂₁₆₃.

17. A method according to claim 15, wherein a set of exponentiations by odd exponents is precomputed and used for multiple basis conversions.

18. A method 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 method for evaluating a first irreducible polynomial a(x) at a root r to obtain a representation a(r) of a second irreducible in a second basis, said method to be used in a cryptographic scheme 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 said second irreducible polynomial, said method for evaluating comprising the steps of:

a) obtaining said first irreducible polynomial a(x) and determining 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 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.

20. A method according to claim 19, wherein the computation of said component polynomials further comprises the steps of:

a) 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;

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

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

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

21. A method according to claim 19 wherein said cryptographic scheme is any one of a key exchange scheme, a signature scheme, and an encryption scheme.

22. In a cryptographic system utilizing a first irreducible polynomial a(x) for converting an element of a finite field of characteristic q stored in said cryptographic system from a representation in a first basis defined by said first irreducible polynomial to a representation in a second basis defined by a second irreducible polynomial, the method of evaluating said first irreducible polynomial a(x) at a root r of said field to obtain a representation a(r) of said second irreducible polynomial in said second basis to be used in a cryptographic scheme comprising the steps of:

a) obtaining said first irreducible polynomial a(x) and determining 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 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.

23. A method according to claim 22, wherein the computation of said component polynomials further comprises the steps of:

a) 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;

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

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

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

24. A method according to claim 22 wherein said cryptographic scheme is any one of a key exchange scheme, a signature scheme, and an encryption scheme.