Method for multiplication in Galois fields using programmable circuits

• US 6,377,969 B1
• Filed: 04/23/1999
• Issued: 04/23/2002
• Est. Priority Date: 04/23/1999
• Status: Expired due to Term

• Current Assignee: General Dynamics C4 Systems Incorporated (General Dynamics Corporation)
• Original Assignee: General Dynamics Government Systems Corporation (General Dynamics Corporation)
• Inventors: Orlando, Gerardo, Paar, Christof
• Primary Examiner(s): NGO, CHUONG D
• Application Number:
  US09/298,651
• Time in Patent Office: 1,096 Days
• Field of Search: 708/491, 708/492, 708/620, 708/625, 708/627, 380/28, 380/30
• 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

Abstract

A scalable multiplier architecture for the Galois field GF(2^k) is implemented in a programmable circuit. This architecture may be used in an implementation of public-key cryptosystems which use programmable multipliers in large Galois fields. This architecture is also fine grain scalable in both the time and the area (or logic) dimensions.

Claims

1. A method for multiplying two binary numbers, U and V, of k bits or less, in a Galois field GF(2^k), using a programmable circuit, comprising:

a. choosing an irreducible polynomial of degree k, having coefficients of 1 or 0;

b. choosing a number m, less than k, which is no greater than the number of processing elements in the programmable circuit;

c. logically mapping functions that would be performed by an x^th processor of a k-bit serial multiplier onto a y^th processor of an m bit super-serial multiplier, where y=x mod m;

d. using the super-serial multiplier to emulate in ┌

k/m┐

cycles one cycle of the serial multiplier, thus multiplying one bit of U by V; and

e. repeating step d k times, each time appropriately combining the prior partial product with the results of the current multiplication, whereby the product of U and V is determined in k*┌

k/m┐

cycles.

2. The method of claim 1, wherein each time step d is performed, processors 0 to m−

1 of the serial multiplier are first emulated, then processors m to 2m−

1, and so on until all k processors are emulated.

3. The method of claim 1, wherein the super-serial multiplier includes 3*┌

k/m┐

bits of storage for the V operand, the multiplication result W and the coefficients of the irreducible polynomial P, such storage being used to restore a state of the processor being emulated.

4. The method of claim 1, wherein the super-serial multiplier includes a mechanism to propagate the results from one cycle of the serial multiplier to another.

5. The method of claim 1, wherein the super-serial multiplier first restores a state of the emulated serial processor, then computes the next partial result, then saves a new state.

6. The method of claim 1, wherein in a first multiplication cycle of the serial multiplication emulation W is initialized with the product u_k−

1V(x).

7. The method of claim 1, wherein the super-serial multiplier includes a data transfer mechanism from processor m−

1 to processor 0, to emulate the connection between processors m−

1 and m, 2m−

1 and 2m, and so forth, in the serial multiplier.

8. The method of claim 1, wherein the irreducible polynomial P(x) is a trinomial of the form x^k+x^r+1.

9. The method of claim 8, wherein the irreducible polynomial P(x) is a trinomial of the form x^k+x^r+1, where r is small compared to k.

10. The method of claim 1, wherein the programmable circuit is a programmable integrated circuit.

11. The method of claim 10, wherein the programmable integrated circuit is a field programmable gate array.

12. A method for programming a programmable circuit to multiply two binary numbers, U and V, of k bits or less, in a Galois field GF(2^k), comprising:

a. choosing an irreducible polynomial of degree k, having coefficients of 1 or 0;

b. choosing a number m, less than k, which is no greater than the number of processing elements in the programmable circuit;

c. programming the programmable circuit wherein functions that would be performed by an x^th processor of a k-bit serial multiplier are logically mapped onto a y^th processor of the m bit super-serial multiplier, where y=x mod m;

d. programming the programmable circuit wherein the super-serial multiplier emulates in ┌

k/m┐

cycles one cycle of the serial multiplier, thus multiplying one bit of U by V; and

e. programming the programmable circuit wherein the process of step d is repeated k times, each time appropriately combining prior partial product with results of the current multiplication, whereby the product of U and V is determined in k*┌

k/m┐

cycles.

13. The method of claim 12, further including programming the programmable circuit wherein each time step d is performed processors 0 to m−

1 of the serial multiplier are first emulated, then processors m to 2m−

1, and so on until all k processors are emulated.

14. The method of claim 12, further including programming the programmable circuit wherein the super-serial multiplier includes 3*┌

k/m┐

bits of storage for the V operand, the multiplication result W and the coefficients of the irreducible polynomial P, such storage being used to restore a state of the processor being emulated.

15. The method of claim 12, further including programming the programmable circuit wherein the super-serial multiplier includes a mechanism to propagate results from one cycle of the serial multiplier to another.

16. The method of claim 12, further including programming the programmable circuit wherein the super-serial multiplier first restores the state of the emulated serial processor, then computes a next partial result, then saves a new state.

17. The method of claim 12, further including programming the programmable circuit wherein in a first multiplication cycle of the serial multiplication emulation W is initialized with a product u_k−

1V(x).

18. The method of claim 12, further including programming the programmable circuit wherein the super-serial multiplier includes a data transfer mechanism from processor m−

1 to processor 0, to emulate the connection between processors m−

1 and m, 2m−

1 and 2m, and so forth, in the serial multiplier.

19. The method of claim 12, further including programming the programmable circuit wherein the irreducible polynomial P(x) is a trinomial of the form x^k+x^r+1.

20. The method of claim 19, further including programming the programmable circuit where the irreducible polynomial P(x) is a trinomial of the form x^k+x^r+1, where r is small compared to k.

21. The method of claim 12, wherein the programmable circuit is a programmable integrated circuit.

22. The method of claim 21, wherein the programmable integrated circuit is a field programmable gate array.

23. A method for emulating the operation of a serial multiplier multiplying two binary numbers U and V, of k bits or less, in the Galois field GF(2^k) in a programmable circuit, comprising:

a. choosing an irreducible polynomial of degree k, having coefficients of 1 or 0;

b. choosing a number m, less than k, which is no greater than the number of processing elements in the programmable circuit;

c. logically mapping functions that would be performed by an x^th processor of the k-bit serial multiplier onto an y^th processor of the m-bit super-serial multiplier, where y=x mod m; and

d. using the super-serial multiplier to emulate in ┌

k/m┐

cycles one cycle of the serial multiplier, thereby multiplying one bit of U by V.

24. The method of claim 23, wherein the process of step d is repeated k times, each time appropriately combining the prior partial product with the results of a current multiplication, whereby the product of U and V is determined in k*┌

k/m┐

cycles.

25. The method of claim 24, wherein each time step d is performed processors 0 to m−

1 of the serial multiplier are first emulated, then processors m to 2m−

1, and so on until all k processors are emulated.

26. The method of claim 25, wherein the super-serial multiplier includes 3*┌

k/m┐

bits of storage for the V operand, the multiplication result Wand the coefficients of the irreducible polynomial P, such storage being used to restore a state of the processor being emulated.

27. The method of claim 26, wherein the super-serial multiplier includes a mechanism to propagate the results from one cycle of the serial multiplier to another.

28. The method of claim 27, wherein the super-serial multiplier first restores the state of the emulated serial processor, then computes a next partial result, then saves a new state.

29. The method of claim 28, wherein in a first multiplication cycle of the serial multiplication emulation W is initialized with a product u_k−

1V(x).

30. The method of claim 29, wherein the super-serial multiplier includes a data transfer mechanism from processor m−

1 to processor 0, to emulate the connection between processors m−

1 and m, 2m−

1 and 2m, and so forth, in the serial multiplier.

31. The method of claim 30, wherein the irreducible polynomial P(x) is a trinomial of the form x^k+x^r+1.

32. The method of claim 31, wherein the irreducible polynomial P(x) is a trinomial of the form x^k+x^r+1, where r is small compared to k.

33. The method of claim 32, wherein the programmable circuit is a programmable integrated circuit.

34. The method of claim 33, wherein the programmable integrated circuit is a field programmable gate array.

35. A programmable circuit program to multiply two binary numbers, U and V, of k bits or less, in a Galois field GF(2^k), comprising:

a. means for choosing an irreducible polynomial of degree k, having coefficients of 1 or 0;

b. means for choosing a number m, less than k, which is no greater than the number of processing elements in the programmable circuit;

c. means for logically mapping of functions that would be performed by an x^th processor of a k-bit serial multiplier onto a y^th processor of the m bit super-serial multiplier, where y=x mod m;

d. means for having a super-serial multiplier emulate in ┌

k/m┐

cycles one cycle of a serial multiplier, thereby multiplying one bit of U by V; and

e. means for repeating step d k times, each time appropriately combining a prior partial product with results of a current multiplication, whereby the product of U and V is determined in k*┌

k/m┐

cycles.

36. The programmable circuit program of claim 35, wherein each time step d is performed, processors 0 to m−

1 of the serial multiplier are first emulated, then processors m to 2m−

1, and so on until all k processors are emulated.

37. The programmable circuit program of claim 36, wherein the super-serial multiplier coefficients of the irreducible polynomial P, such storage being used to restore a state of the processor being emulated.

38. The programmable circuit program of claim 37, wherein the super-serial multiplier includes a mechanism to propagate results from one cycle of the serial multiplier to another.

39. The programmable circuit program of claim 38, wherein the programmable circuit program includes a means to first restore the state of the emulated serial processor, then compute a next partial result, and save a new state.

40. The programmable circuit program of claim 39, wherein the programmable circuit program includes a means in a first multiplication cycle of the serial multiplication emulation to initialize W with a product u_k−

1V(x).

41. The programmable circuit program of claim 40, wherein the programmable circuit program includes a data transfer mechanism from processor m−

1 to processor 0 in the super-serial multiplier, to emulate the connection between processors m−

1 and m, 2m−

1 and 2m, and so forth, in the serial multiplier.

42. The programmable circuit program of claim 41, wherein the irreducible polynomial P(x) is a trinomial of the form x^k+x^r+1.

43. The programmable circuit program of claim 42, wherein the irreducible polynomial P(x) is a trinomial of the form x^k+x^r+1, where r is small compared to k.

44. The programmable circuit program of claim 43, wherein the programmable circuit program is a programmable integrated circuit program.

45. The programmable integrated circuit program of claim 44, wherein the programmable integrated circuit program is a field programmable gate array program.

46. A method for programming a programmable circuit to multiply two binary numbers, U and V, of k bits or less, in a Galois field GF(2^k), comprising:

a. choosing an irreducible polynomial of degree k, having coefficients of 1 or 0;

b. choosing a number m, less than k, which is no greater than the number of processing elements in the programmable circuit;

c. programming the programmable circuit wherein functions that would be performed by the x^th processor of a k-bit serial multiplier are logically mapped onto the y^th processor of the m bit super-serial multiplier, where y=x mod m;

d. programming the programmable circuit wherein the super-serial multiplier emulates in ┌

k/m┐

cycles one cycle of the serial multiplier, thus multiplying one bit of U by V; and

e. programming the programmable circuit wherein the process of step d is repeated k times, each time appropriately combining the prior partial product with the results of the current multiplication, whereby the product of U and V is determined in k*┌

k/m┐

cycles;

f. programming the programmable circuit wherein each time step d is performed, processors 0 to m−

1 of the serial multiplier are first emulated, then processors m to 2m−

1 are emulated, and so on until all k processors are emulated,

g. programming the programmable circuit wherein the super-serial multiplier includes 3*┌

k/m┐

bits of storage for the V operand, the multiplication result W and the coefficients of the irreducible polynomial P, such storage being used to restore the state of the processor being emulated,

h. programming the programmable circuit wherein the super-serial multiplier including a mechanism to propagate results from one cycle of the serial multiplier to another,

i. programming the programmable circuit wherein the super-serial multiplier first restores the state of the emulated serial processor, then computes a next partial result, then saves a new state,

j. programming the programmable circuit wherein in a first multiplication cycle of the serial multiplication emulation W is initialized with a product u<sub>k−

1</sub>V(x),

k. programming the programmable circuit wherein the super-serial multiplier includes a data transfer mechanism from processor m−

1 to processor 0, to emulate the connection between processors m−

1 and m, 2m−

1 and 2m, and so forth, in the serial multiplier, and

l. programming the programmable circuit wherein the irreducible polynomial P(x) is a trinomial of the form x^k+x^r+1, where r is small compared to k.

47. A programmable circuit to multiply two binary numbers, U and V, of k bits or less, in a Galois field GF(2^k), comprising:

a. means for logically mapping functions that would be performed by an x^th processor of a k-bit serial multiplier onto a y^th processor of an m bit super-serial multiplier, where y=x mod m, m being less than k, and being no greater than the number of processing elements in the programmable circuit;

b. means for choosing an irreducible polynomial of degree k, having coefficients of 1 or 0,

c. means for using the super-serial multiplier to emulate in ┌

k/m┐

cycles one cycle of the serial multiplier, thus multiplying one bit of U by V; and

d. means for repeating step d k times, each time appropriately combining the prior partial product with the results of the current multiplication, whereby the product of U and V is determined in k*┌

k/m┐

cycles.

48. The programmable circuit of claim 47, wherein the super-serial multiplier includes 3*┌

k/m┐

bits of storage for the V operand, the multiplication result W and the coefficients of the irreducible polynomial P, such storage being used to restore a state of the processor being emulated.

49. The programmable circuit of claim 48, wherein the programmable circuit is a programmable integrated circuit.

50. The programmable integrated circuit of claim 49, wherein the programmable integrated circuit is a field programmable gate array.