Microprocessor apparatus and method for modular exponentiation

• US 20050256920A1
• Filed: 05/16/2005
• Published: 11/17/2005
• Est. Priority Date: 05/14/2004
• Status: Active Grant

• Current Assignee: VIA Technologies Incorporated (VIA Technologies)
• Original Assignee: VIA Technologies Incorporated (VIA Technologies)
• Inventors: Parks, Terry, Henry, G. Glenn, Crispin, Thomas A.
• Granted Patent: US 7,664,810 B2
• Time in Patent Office: Days
• US Class Current: 708/491
• CPC Class Codes: G06F 7/728 using Montgomery reduction
• CPC Class Codes: G06F 9/3001 Arithmetic instructions
• CPC Class Codes: G06F 9/3017 Runtime instruction translation, e.g. macros
• CPC Class Codes: G06F 9/30174 for non-native instruction set, e.g. Javabyte, legacy code

Abstract

A technique is provided for performing modular multiplication. In one embodiment, an apparatus in a microprocessor is provided for accomplishing modular multiplication operations. The apparatus includes translation logic and execution logic. The translation logic receives a Montgomery multiplication instruction from a source therefrom, where the Montgomery multiplication instruction prescribes generation of a Montgomery product. The translation logic translates the Montgomery multiplication instruction into a sequence of micro instructions specifying sub-operations required to accomplish generation of the Montgomery product. The execution logic is operatively coupled to the translation logic. The execution logic receives the sequence of micro instructions, and performs the sub-operations to generate the Montgomery product.

Claims

1. An apparatus in a microprocessor, for accomplishing modular multiplication operations, comprising:

translation logic, configured to receive a Montgomery multiplication instruction from a source therefrom, wherein said Montgomery multiplication instruction prescribes generation of a Montgomery product, and configured to translate said Montgomery multiplication instruction into a sequence of micro instructions specifying sub-operations required to accomplish generation of said Montgomery product; and

execution logic, operatively coupled to said translation logic, configured to receive said sequence of micro instructions, and configured to perform said sub-operations to generate said Montgomery product.

2. The apparatus as recited in claim 1, wherein said Montgomery multiplication instruction implicitly references a plurality of registers within the microprocessor.

3. The apparatus as recited in claim 2, wherein said plurality of registers comprises:

a first register, wherein contents of said first register comprise a first pointer to a first memory address, said first memory address specifying a first location in memory.

4. The apparatus as recited in claim 3, wherein said first location comprises:

a first operand pointer, said first operand pointer pointing to a second memory address, said second memory address specifying a second location in said memory comprising a first operand for generation of said Montgomery product.

5. The apparatus as recited in claim 4, wherein said first location further comprises:

a second operand pointer, said second operand pointer pointing to a third memory address, said third memory address specifying a third location in said memory comprising a second operand for generation of said Montgomery product.

6. The apparatus as recited in claim 3, wherein said first location comprises:

a result pointer, said result pointer pointing to a second memory address, said second memory address specifying a second location in said memory, wherein, upon generation of said Montgomery product, said Montgomery product is stored to said second location.

7. The apparatus as recited in claim 3, wherein said first location comprises:

a modulus pointer, said modulus pointer pointing to a second memory address, said second memory address specifying a second location in said memory comprising a modulus for generation of said Montgomery product.

8. The apparatus as recited in claim 3, wherein said first location comprises:

an integer, wherein said integer is related to both a modulus and a radix chosen for generation of said Montgomery product, and wherein said integer is employed to generate said Montgomery product.

9. The apparatus as recited in claim 8, wherein said radix is chosen to be an integer multiple of 32.

10. The apparatus as recited in claim 2, wherein said plurality of registers comprises:

a first register, wherein contents of said first register comprise a value indicating a number of bits in a first operand, a second operand, and a modulus for generation of said Montgomery product.

11. The apparatus as recited in claim 1, wherein said Montgomery multiplication instruction is prescribed according to the x86 instruction format.

12. An apparatus for performing modular multiplication operations, comprising:

a Montgomery multiplication instruction, received by logic within a processor, wherein said Montgomery multiplication instruction prescribes generation of a Montgomery product; and

execution logic, coupled to said logic, configured to generate said Montgomery product.

13. The apparatus as recited in claim 12, wherein said Montgomery multiplication instruction implicitly references a plurality of registers within said processor.

14. The apparatus as recited in claim 13, wherein said plurality of registers comprises:

a first register, wherein contents of said first register comprise a pointer to a memory address, said memory address specifying a location in memory.

15. The apparatus as recited in claim 14, wherein said location comprises:

a plurality of parameters, wherein said plurality of parameters indicate operands and a modulus to be employed during generation of said Montgomery product.

16. The apparatus as recited in claim 15, wherein said plurality of parameters are indicated according to a radix, and wherein said radix is chosen to be an integer multiple of 32.

17. The apparatus as recited in claim 12, wherein said plurality of registers comprises:

a first register, wherein contents of said first register comprise a value indicating a number of bits in a first operand, a second operand, and a modulus for generation of said Montgomery product.

18. The apparatus as recited in claim 12, wherein said Montgomery multiplication instruction is prescribed according to the x86 instruction format.

19. The apparatus as recited in claim 12, wherein said logic comprises:

translation logic, configured to translate said Montgomery multiplication instruction into a sequence of micro instructions specifying sub-operations required to accomplish generation of said Montgomery product.

20. A method for performing modular multiplication operations in a processor, the method comprising:

fetching a Montgomery multiplication instruction from memory, wherein the Montgomery multiplication instruction prescribes generation of a Montgomery product; and

executing the Montgomery multiplication instruction to generate the Montgomery product.

21. The method as recited in claim 20, wherein said fetching comprises:

implicitly referencing a plurality of registers within the processor.

22. The method as recited in claim 21, wherein said implicitly referencing comprises:

specifying a first register, wherein contents of the first register comprise a first pointer to a first memory address, the first memory address indicating a first location in the memory.

23. The method as recited in claim 22, wherein the first location comprises:

a first operand pointer, the first operand pointer pointing to a second memory address, the second memory address indicating a second location in the memory comprising a first operand for generation of the Montgomery product.

24. The method as recited in claim 23 wherein the first location further comprises:

a second operand pointer, the second operand pointer pointing to a third memory address, the third memory address indicating a third location in the memory comprising a second operand for generation of the Montgomery product.

25. The method as recited in claim 22, wherein the first location comprises:

a result pointer, the result pointer pointing to a second memory address, the second memory address specifying a second location in said memory, wherein, upon generation of the Montgomery product, the Montgomery product is stored to the second location.

26. The method as recited in claim 22, wherein the first location comprises:

a modulus pointer, the modulus pointer pointing to a second memory address, the second memory address specifying a second location in said memory comprising a modulus for generation of the Montgomery product.

27. The method as recited in claim 22, wherein said first location comprises:

an integer, wherein the integer is related to both a modulus and a radix chosen for generation of the Montgomery product, and wherein the integer is employed to generate the Montgomery product.

28. The method as recited in claim 27, wherein the radix is chosen to be an integer multiple of 32.

29. The method as recited in claim 21, wherein said implicitly referencing comprises:

specifying a first register, wherein contents of the first register comprise a value indicating a number of bits in a first operand, a second operand, and a modulus for generation of the Montgomery product.

30. The method as recited in claim 20, wherein said fetching comprises:

prescribing the Montgomery multiplication instruction according to the x86 instruction format.

31. The method as recited in claim 20, further comprising:

translating the Montgomery multiplication instruction into a sequence of micro instructions, wherein the micro instructions prescribe sub-operations required to accomplish generation of the Montgomery product.