System and method for efficient basis conversion

• US 20020041682A1
• Filed: 09/10/2001
• Published: 04/11/2002
• Est. Priority Date: 03/12/1999
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Lambert, Robert J.
• Granted Patent: US 7,299,253 B2
• Time in Patent Office: Days
• US Class Current: 380/28
• 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 used 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, said method comprising the steps of:

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

b) determining a root r of said second irreducible polynomial;

c) evaluating said polynomial a(x) at said root r to obtain a representation a(r) of a(x) in said second basis;

said evaluation being characterised by the steps of;

d) partitioning said polynomial a(x) into a plurality of component polynomials, so that said plurality of component polynomials may be combined to obtain said polynomial a(x) by using the operations of multiplication by x and exponentiation by q;

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

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

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_q²−

1.

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

8. A method according to claim 1, wherein said finite field is F_2^m 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_2¹⁶³.

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;

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_2^m whereby said characteristic q is equal to 2.

16. A method according to claim 15, wherein said finite field is F_2¹⁶³.

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

19. A method according to claim 18, 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;

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.

18. A method for evaluating a polynomial a(x) at a point r, said method comprising the steps of:

a) partitioning said polynomial a(x) into a plurality of component polynomials, so that said plurality of component polynomials may be combined to obtain said polynomial a(x) by using the operations of multiplication by x and exponentiation by q;

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

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

20. In a cryptographic system utilising elements of a finite field of characteristic q represented as a polynomial a(x) in a first basis defined by a first irreducible polynomial, the method of evaluating said polynomial a(x) at an element r of said field comprising the steps of:

a) partitioning said polynomial a(x) into a plurality of component polynomials, so that said plurality of component polynomials may be combined to obtain said polynomial a(x) by using the operations of multiplication by x and exponentiation by q;

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

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

21. A method according to claim 20, 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;

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.

22. A computing device including an accumulator for evaluating a polynomial a(x) of degree d at an element r of a finite field of characteristic 2, said device being programmed to:

a) initialize said accumulator to 0;

b) for each odd number k<

d, compute and store a value r^k;

c) compute a value t=2^l such that 2^l≦

d<

2^l+1;

d) while t≧

1, repeat the steps;

i) for each s from 1 to

$\lfloor <br><br>\frac{d}{t}\rfloor <br><br>$

 

if a_st=1 then add r^s to the accumulator;

ii) square R;

iii) set

$t=\frac{t}{2};<br><br>$

 

whereby the accumulator holds the value of a(r).