Modular multiplier

• US 20030212729A1
• Filed: 03/11/2003
• Published: 11/13/2003
• Est. Priority Date: 05/01/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Gura, Nils, Eberle, Hans, Gupta, Vipul, Brown, Russell A., Chang-Shantz, Sheueling
• Granted Patent: US 7,461,115 B2
• Time in Patent Office: Days
• US Class Current: 708/625
• CPC Class Codes: G06F 7/527 in serial-parallel fashion, i.e. one operand being entered serially and the other in parallel G06F7/533 takes precedence
• 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

Modular multiplication of two elements X(t) and Y(t), over GF(2), where m is a field degree, may utilize field degree to determine, at least in part, the number of iterations. An extra shift operation may be employed when the number of iterations is reduced. Modular multiplication of two elements X(t) and Y(t), over GF(2), may include a shared reduction circuit utilized during multiplication and reduction. In addition, a modular multiplication of binary polynomials X(t) and Y(t), over GF(2), may utilize the Karatsuba algorithm, e.g., by recursively splitting up a multiplication into smaller operands determined according to the Karatsuba algorithm.

Claims

1. A method of performing a modular multiplication of two elements X(t) and Y(t), of GF(2^m), where m is a field degree, comprising:

performing a polynomial multiplication in a number of iterations, the number of iterations being determined, at least in part, according to the field degree m and digit size d, the digit size d being at least two bits, and supplying an intermediate result thereof.

2. The method as recited in claim 1 further comprising performing a reduction operation on the intermediate result to provide an output element P(t) of GF(2^m).

3. The method as recited in claim 2 further comprising:

performing an additional shift operation when the field degree is less than a predetermined amount prior to supplying the intermediate result for the reduction operation.

4. The method as recited in claim 3 wherein each iteration comprises:

shifting a current intermediate result in a register (Z) by an amount d to produce a shifted intermediate result, d being less than a size of the register Z;

adding to the shifted intermediate result a product of a portion of a register X initially containing X(t), the portion being d bits in size, and contents of register Y, initially containing Y(t); and

shifting the X register by d bits.

5. The method as recited in claim 4 further comprising performing a number of iterations determined by a rounded up value of m divided by d(m/d).

6. The method as recited in claim 4 wherein the additional shift operation is performed when the rounded up value of m divided by d(m/d) is less than n divided by d(n/d), where n is the number of bits supplied by the Y register to the multiplier.

7. The method as recited in claim 1 wherein performing the modular multiplication comprises:

summing a plurality of partial products, each partial product formed utilizing three partial products in the form of Xh*Yh, Xl*Yl and (Xh−

Xl)*Yh−

Yl), where Xh are high order bits of at least a portion of X(t), Xl are low order bits of the portion of X(t), Yh are high order bits of at least a portion of Y(t), and Yl are low order bits of the portion of Y(t).

8. An apparatus for performing a modular multiplication of two polynomial elements X(t) and Y(t), of GF(2^m), where m is a field degree, and supplying as an output an element P(t) of GF(2^m), comprising:

a first register (X) for storing an initial value of X(t) and coupled to supply a d number of bits, d being an integer;

a shift circuit coupled to shift the first register X by d bits;

a second register (Y) coupled to supply n bits, n being an integer;

a multiplier coupled to multiply d bits of the first register and n bits of the second register and supply a multiplier output;

a third register (Z) at least 2n bits wide providing an intermediate result;

an adder coupled to add the multiplier output and an output of the third register Z;

a reduction circuit coupled to receive an intermediate result from the third register, the intermediate result received by the reduction circuit being one of an output of the third register and a shifted output of the third register resulting from an additional shift operation on contents of the third register Z, the additional shift operation being determined according to the field degree m.

9. The apparatus as recited in claim 8 wherein the additional shift operation is performed when a rounded up value of m divided by d(m/d) is less than n divided by d(n/d), where n is the number of bits supplied by the Y register to the multiplier.

10. An apparatus comprising:

means for supplying two elements X(t) and Y(t), of GF(2^m), where m is a field degree; and

means for providing a modular multiplication of the two elements X(t) and Y(t), of GF(2^m), and supplying as an output an element P(t) of GF(2^m), the modular multiplication being optimized, in terms of number of iterations utilized to perform the modular multiplication, according to the field degree m and a digit size d, d being at least two.

11. The apparatus as recited in claim 10 wherein fewer iterations are utilized when the field degree is less than a predetermined number.

12. The apparatus as recited in claim 11 wherein an extra shift operation is utilized when fewer iterations are utilized.

13. A method of performing modular multiplication of two elements X(t) and Y(t), of GF(2^m), comprising reducing one of the multiplicands in the process of generating an intermediate result in a reduction circuit and reducing the intermediate result in the reduction circuit to generate an element P(t) of GF(2^m).

14. The method as recited in claim 13 wherein the reduction circuit supports multiple elliptic curves.

15. A method of performing a modular multiplication of two elements X(t) and Y(t), of GF(2^m), X(t) and Y(t) being stored initially in a register X and a register Y, respectively, and supplying as an output element P(t) of GF(2^m), comprising:

performing a polynomial multiplication of the contents of register X and Y using a number of iterations, and supplying an intermediate result;

performing a reduction operation on contents of Y, during each of the iterations, in a reduction circuit; and

performing a reduction operation in the reduction circuit on the intermediate result to provide the output element P(t).

16. The method as recited in claim 15 wherein one of the iterations comprises:

adding to a current intermediate result a product of a portion of register X, the portion being d bits in size, and contents of the Y register;

shifting the X register by d bits; and

shifting the Y register by d bits to produce a shifted result, reducing the shifted result and then storing the shifted result into the Y register.

17. The method as recited in claim 15 wherein performing the modular multiplication comprises:

summing a plurality of partial products, each partial product formed utilizing three partial products in the form of Xh*Yh, Xl*Yl and (Xh−

Xl)*(Yh−

Yl), where Xh are high order bits of at least a portion of X(t), Xl are low order bits of the portion of X(t), Yh are high order bits of at least a portion of Y(t), and Yl are low order bits of the portion of Y(t).

18. The method as recited in claim 16 further comprising performing a number of iterations determined by a rounded up value of m divided by d(m/d).

19. An apparatus for performing a modular multiplication of two elements X(t) and Y(t), of GF(2^m), where m is a field degree, and supplying as an output an element P(t) of GF(2m), comprising:

a first register (X) storing an initial value of X(t) and coupled to supply d bits, d being an integer;

a second register (Y) storing an initial value of Y(t) coupled to supply n bits;

a multiplier coupled to multiply d bits of the first register and n bits of the second register and supply a multiplier output;

a third register (Z) coupled to supply an intermediate result;

an adder coupled to add the multiplier output and an output of the third register Z; and

a reduction circuit coupled to selectably receive one of the intermediate result from the third register and to receive a shifted value of the second register (Y).

20. The apparatus as recited in claim 19 further comprising a shift circuit coupled to shift the first register X by d bits.

21. The apparatus as recited in claim 19 wherein the third register Z is less than 2n bits wide.

22. The apparatus as recited in claim 19 wherein the second register (Y) is coupled to receive an output of the reduction circuit.

23. The apparatus as recited in claim 19 wherein the modular multiplication includes summing a plurality of partial products, each partial product formed utilizing three partial products in the form of Xh*Yh, Xl*Yl and (Xh−

Xl)*(Yh−

Y1), where Xh are high order bits of at least a portion of X(t), X1 are low order bits of the portion of X(t), Yh are high order bits of at least a portion of Y(t), and Yl are low order bits of the portion of Y(t).

24. A method of performing a modular multiplication of two elements X(t) and Y(t), of GF(2^m), X(t) and Y(t) being stored initially in a register X and a register Y and supplying as an output an element P(t) of GF(2^m), comprising:

performing a polynomial multiplication of the contents of register X and Y using a number of iterations;

wherein one iteration includes;

adding to a current reduced intermediate result a product of a portion of register X, the portion being d bits in size, and contents of the register Y to produce a sum;

performing a first reduction operation on shifted contents of the Y register in a first reduction circuit;

performing a second reduction operation in a second reduction circuit on the sum to generate a reduced sum.

25. An apparatus for performing a modular multiplication of two elements X(t) and Y(t), of GF(2^m), where m is a field degree, and supplying as an output an element P(t) of GF(2^m), comprising:

a first register (X) storing an initial value of X(t) and coupled to supply d bits, d being an integer;

a second register (Y) storing an initial value of Y(t) coupled to supply n bits;

a multiplier coupled to multiply d bits of the first register and n bits of the second register and supply a multiplier output;

a third register (Z) coupled to supply an intermediate result;

an adder coupled to add the multiplier output and an output of the third register Z;

a first reduction circuit coupled to the adder to supply the third register Z with result of the first reduction circuit; and

a second reduction circuit coupled to receive a shifted value of the second register (Y) and to supply an output of the second reduction circuit to the second register (Y).

26. A method of performing a modular multiplication of binary polynomials X(t) and Y(t), over GF(2), the modular multiplication comprising:

summing a plurality of partial products, each partial product formed utilizing three partial products in the form of Xh*Yh, Xl*Yl and (Xh−

Xl)*(Yh−

Yl), where Xh is a high portion of X(t), Xl is a low portion of X(t), Yh is a high portion of Y(t), and Yl is a low portion of Y(t).

27. A method of performing a modular multiplication of two binary polynomial elements X(t) and Y(t), the modular multiplication comprising recursively splitting up a multiplication into smaller operands determined according to the Karatsuba algorithm.

28. A method of performing a modular multiplication of two elements X(t) and Y(t), over GF(2), the modular multiplication comprising:

applying a multiplication algorithm utilizing three partial products in the form of Xh*Yh, Xl*Yl and(Xh−

Xl)*(Yh−

Yl), where Xh is a high portion of X(t), Xl is a low portion of X(t), Yh is a high portion of Y(t), and Yl is a low portion of Y(t);

recursively applying the multiplication algorithm utilizing three partial products in the form of Xhh*Yhh, Xhl*Yhl and(Xhh−

Xhl)*(Yhh−

Yhl), where Xhh is a high portion of Xh, Xhl is a low portion of Xh, Yhh is a high portion of Yh, and Yhl is a low portion of Yh, to determine the product of Xh*Yh; and

utilizing a serial shift and add multiplication at a low level to the three partial products.

29. A method of performing a hybrid long-word multiplication of two binary polynomials X(t) and Y(t), the multiplication comprising:

utilizing a shift and add algorithm that sums partial products; and

generating the partial products utilizing a multiplication algorithm that utilizes three partial products in the form of Xh*Yh, Xl*Yl and (Xh−

Xl)*(Yh−

Yl), where Xh is a high portion of X, Xl is a low portion of X, Yh is a high portion of Y, and Yl is a low portion of Y, X and Y being a portion of X(t) and Y(t).

30. A method of performing a modular multiplication of binary polynomials X(t) and Y(t), over GF(2), comprising selecting one of a plurality of hardwired reduction circuits to use in a reduction operation associated with the modular multiplication according to an underlying field extension field of GF(2).

31. An apparatus for performing a modular multiplication of binary polynomials X(t) and Y(t), over GF(2), comprising a plurality of hardwired reduction circuits selected for use in a reduction operation associated with the modular multiplication according to an underlying extension field of GF(2).