Methods and apparatus for efficient finite field basis conversion

• US 5,854,759 A
• Filed: 05/05/1997
• Issued: 12/29/1998
• Est. Priority Date: 05/05/1997
• Status: Expired due to Term

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: RSA Data Security, Inc. (Symphony Technology Group LLC)
• Inventors: Kaliski, Burton S. Jr., Yin, Yiqun Lisa
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US08/851,045
• Time in Patent Office: 603 Days
• Field of Search: 364/746.1, 364/746
• 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

Abstract

Methods and apparatus for converting a value A representing in a first basis an element of a finite field GF(q^m) to a value B representing the element in a second basis, where q is a prime number or power of a prime number and m is an integer greater than or equal to 2, and where the value B includes a vector of m coefficients from a finite field GF(q). An exemplary apparatus, particularly well-suited for exporting the value A in an internal basis representation to the value B in an external basis representation, includes an externally shifted sequence generator for generating from the value A a sequence of intermediate values representing in the first basis elements of the finite field GF(q^m) whose representations in the second basis are related to the value B by a predetermined external shift operation. An extractor coupled to the externally shifted sequence generator receives and processes the sequence of intermediate values to generate each coefficient of the value B.

Claims

1. A method of generating in a digital data processor, from a value A representing in a first basis an element of a finite field GF(q^m), at least part of a value B representing said element in a second basis, wherein q is a prime number or power of a prime number and m is an integer greater than or equal to 2, and wherein said value B includes a vector of m coefficients from a finite field GF(q), the method comprising the steps of:

generating from said value A in an externally shifted sequence generator a sequence of intermediate values representing in said first basis elements of the finite field GF(q^m) whose representations in said second basis are related to said value B by at least one predetermined external shift operation; and

generating from said sequence of intermediate values in an extractor at least a subset of the coefficients of said value B.

2. The method of claim 1 wherein the step of generating from said value A a sequence of intermediate values includes sequentially applying a predetermined logic function to said value A, such that after a number of steps, each of said intermediate values has been generated.

3. The method of claim 2 wherein said number of steps is m-1.

4. The method of claim 2 wherein said number of steps is approximately .left brkt-bot.(m-1)/k.right brkt-bot., where k is an integer greater than or equal to 2.

5. The method of claim 1 wherein said second basis is a normal basis and said predetermined external shift operation is a rotation operation that rotates in the direction of increasing powers of a generator of the normal basis.

6. The method of claim 1 wherein said second basis is a polynomial basis and said predetermined external shift operation is a shift operation that shifts in the direction of decreasing powers of a generator of the polynomial basis.

7. The method of claim 1 wherein the step of generating the sequence of intermediate values further includes feeding back at least one of the intermediate values to a register previously storing the value A.

8. The method of claim 1 further including the step of feeding back at least one of the coefficients of said value B to an input of the externally shifted sequence generator performing the generating step.

9. The method of claim 1 further including the step of premultiplying the value A by a scaling factor, such that the step of generating the sequence of intermediate values and the step of generating the coefficients may be performed in a scaled basis.

10. The method of claim 1 wherein the step of generating the coefficients includes applying the sequence of intermediate values to a coefficient selector which processes the intermediate values to generate the coefficients of said value B.

11. The method of claim 10 wherein the step of generating the coefficients includes multiplying the sequence of intermediate values by at least one extraction factor prior to applying the sequence of intermediate values to the coefficient selector.

12. The method of claim 1 wherein the step of generating the coefficients includes generating a coefficient of said value B as a dot product of coefficients of an intermediate value and a corresponding set of values {s_i }.

13. The method of claim 1 wherein the step of generating the coefficients includes generating a coefficient of said value B as an exclusive-or of selected coefficients of an intermediate value.

14. The method of claim 1 wherein the step of generating the coefficients includes applying an additional predetermined external shift operation to the sequence of intermediate values prior to computing the coefficients of said value B, wherein the additional predetermined external shift operation shifts subcoefficients in one or more coefficients of the intermediate value.

15. The method of claim 1 wherein the step of generating the sequence of intermediate values includes applying the value A to an exponentiator to generate the sequence of intermediate values in the form of a sequence of successive exponentiations of the value A.

16. The method of claim 1 wherein the step of generating the sequence of intermediate values includes applying the value A to a scalar subtractor, and multiplying the result by G^-1, where G^-1 is an internal basis representation of an inverse of a generator for the external basis over GF(q^m), to perform a computation A←

(A-tI)G^-1, where t is one of said coefficients of said value B.

17. The method of claim 1 wherein the step of generating the sequence of intermediate values includes applying the value A to a scalar multiplier/subtractor having an input scaling factor V, and multiplying the result by G^-1, where G^-1 is an internal basis representation of an inverse of a generator for the external basis over GF(q^m), to perform a computation A←

(A-tV)G^-1, where t is one of said coefficients of said value B.

18. An apparatus for generating, from a value A representing in a first basis an element of a finite field GF(q^m), at least part of a value B representing said element in a second basis, wherein q is a prime number or power of a prime number and m is an integer greater than or equal to 2, and wherein said value B includes a vector of m coefficients from a finite field GF(q), the apparatus comprising:

an externally shifted sequence generator for generating from said value A a sequence of intermediate values representing in said first basis elements of the finite field GF(q^m) whose representations in said second basis are related to said value B by at least one predetermined external shift operation; and

an extractor coupled to the externally shifted sequence generator and operative to generate at least a subset of the coefficients of said value B from said sequence of intermediate values.

19. The apparatus of claim 18 wherein the externally shifted sequence generator sequentially applies a predetermined logic function to said value A, such that after a number of steps, each of said intermediate values has been computed.

20. The apparatus of claim 19 wherein said number of steps is m-1.

21. The apparatus of claim 19 wherein said number of steps is approximately .left brkt-bot.(m-1)/k.right brkt-bot., where k is an integer greater than or equal to 2.

22. The apparatus of claim 18 wherein said second basis is a normal basis and said predetermined external shift operation is a rotation operation that rotates in the direction of increasing powers of a generator of the normal basis.

23. The apparatus of claim 18 wherein said second basis is a polynomial basis and said predetermined external shift operation is a shift operation that shifts in the direction of decreasing powers of a generator of the polynomial basis.

24. The apparatus of claim 18 further including a feedback path within the externally shifted sequence generator for feeding back at least one of the intermediate values to a register previously storing the value A.

25. The apparatus of claim 18 further including a feedback path between at least one output of the extractor and an input of the externally shifted sequence generator.

26. The apparatus of claim 18 further including a premultiplier for multiplying the value A by a scaling factor before the sequence of intermediate values are generated therefrom.

27. The apparatus of claim 18 wherein the extractor includes a coefficient selector which receives the sequence of intermediate values and processes the intermediate values to generate the coefficients of said value B.

28. The apparatus of claim 27 wherein the extractor further includes a multiplier for multiplying the sequence of intermediate values by at least one extraction factor before applying the sequence of intermediate values to the coefficient selector.

29. The apparatus of claim 18 wherein the extractor is operative to generate a coefficient of said value B as a dot product of coefficients of an intermediate value and a corresponding set of values {s_i }.

30. The apparatus of claim 18 wherein the extractor is operative to generate a coefficient of said value B as an exclusive-or of selected coefficients of an intermediate value.

31. The apparatus of claim 18 wherein the extractor is operative to apply an additional predetermined external shift operation to the sequence of intermediate values prior to generating the coefficients of said value B, wherein the additional predetermined external shift operation shifts subcoefficients in one or more coefficients of the intermediate value.

32. The apparatus of claim 18 wherein the externally shifted sequence generator includes an exponentiator arranged in a feedback loop with an input register, such that the sequence of intermediate values is generated in the form of a sequence of successive exponentiations of said value A.

33. The apparatus of claim 18 wherein the externally shifted sequence generator is operative to apply the value A to a scalar subtractor, and to multiply the result by G^-1, where G^-1 is an internal basis representation of an inverse of a generator for the external basis over GF(q^m), so as to perform the computation A←

(A-tI)G^-1, where t is one of said coefficients of said value B.

34. The apparatus of claim 18 wherein the externally shifted sequence generator is operative to apply the value A to a scalar multiplier/subtractor having an input scaling factor V, and to multiply the result by G^-1, where G^-1 is an internal basis representation of an inverse of a generator for the external basis over GF(q^m), so as to perform the computation A←

(A-tV)G^-1, where t is one of said coefficients of said value B.