Apparatus and method for consistency checking public key cryptography computations

• US 20050243998A1
• Filed: 04/29/2004
• Published: 11/03/2005
• Est. Priority Date: 04/29/2004
• Status: Active Grant

• Current Assignee: STMicroelectronics Asia Pacific Pte Limited (STMicroelectronics NV)
• Original Assignee: STMicroelectronics Asia Pacific Pte Limited (STMicroelectronics NV)
• Inventors: Plessier, Bernard
• Granted Patent: US 7,715,551 B2
• Time in Patent Office: Days
• US Class Current: 380/28
• CPC Class Codes: G06F 7/728 using Montgomery reduction
• CPC Class Codes: H04L 2209/122 Hardware reduction or efficient architectures
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves

Abstract

A cryptographic system comprising: 1) a first Montgomery-based cryptographic engine that receives a first operand and a second operand and generates a first result and 2) a second Montgomery-based cryptographic engine that receives a first reduced operand derived from the first operand and a second reduced operand derived from the second operand and generates a second result. The second Montgomery-based cryptographic engine operates in parallel with the first Montgomery-base cryptographic engine. The cryptographic system further comprises a comparator for comparing the second result to a first reduced result derived from the first result and generating an error flag if the second result and the first reduced result are different.

Claims

1. A cryptographic system comprising:

a first Montgomery-based cryptographic engine capable of receiving a first operand and a second operand and generating therefrom a first result; and

a second Montgomery-based cryptographic engine capable of receiving a first reduced operand derived from said first operand and a second reduced operand derived from said second operand and generating therefrom a second result, wherein said second Montgomery-based cryptographic engine operates in parallel with said first Montgomery-base cryptographic engine.

2. The cryptographic system as set forth in claim 1, wherein the first and second operands are reduced by a reduction function that reduces an operand X with respect to a number k by summing all the digits of operand X when represented in base k and then taking the rest of the division modulo k−

1.

3. The cryptographic system as set forth in claim 2, wherein the operand X is represented as an n-bit binary number and k is a power of 2 (k=2^p), such that each digit of operand X in base k is a p-bit number.

4. The cryptographic system as set forth in claim 3, further comprising a comparator for comparing said second result to a first reduced result derived from said first result and generating an error flag if said second result and said first reduced result are different.

5. The cryptographic system as set forth in claim 4, further comprising a first reduction engine for reducing said first operand from an N-bit value to a P-bit value, thereby producing said first reduced operand.

6. The cryptographic system as set forth in claim 5, further comprising a second reduction engine for reducing said second operand from an M-bit value to a P-bit value, thereby producing said second reduced operand.

7. The cryptographic system as set forth in claim 6, further comprising a third reduction engine for reducing said first result from an R-bit value to a P-bit value, thereby producing said first reduced result.

8. The cryptographic system as set forth in claim 7, further comprising a fourth reduction engine for reducing an intermediate result received from said first Montgomery-based cryptographic engine to thereby produce a reduced intermediate result that is used by said second Montgomery-based cryptographic engine.

9. The cryptographic system as set forth in claim 8, wherein said cryptographic system is disposed in a data processor.

10. The cryptographic system as set forth in claim 8, wherein said cryptographic system is disposed in a telecommunication system.

11. The cryptographic system as set forth in claim 10, wherein said telecommunication system comprises a wireless transceiver.

12. The cryptographic system as set forth in claim 10, wherein said telecommunication system comprises a wireline transceiver.

13. A method of verifying the operation of a first Montgomery-based cryptographic engine capable of receiving a first operand and a second operand and generating therefrom a first result, the method comprising the steps of:

generating a first reduced operand from the first operand;

generating a second reduced operand from the second operand; and

inputting the first and second reduced operands to a second Montgomery-based cryptographic engine and generating therefrom a second result, wherein the second Montgomery-based cryptographic engine operates in parallel with the first Montgomery-base cryptographic engine.

14. The method as set forth in claim 13, wherein the first and second operands are reduced by a reduction function that reduces an operand X with respect to a number k by summing all the digits of operand X when represented in base k and then taking the rest of the division modulo k−

1.

15. The method as set forth in claim 14, wherein the operand X is represented as an n-bit binary number and k is a power of 2 (k=2^p), such that each digit of operand X in base k is a p-bit number.

16. The method as set forth in claim 15, further comprising the steps of:

comparing the second result to a first reduced result derived from the first result; and

generating an error flag if the second result and the first reduced result are different.

17. The method as set forth in claim 16, wherein the step of generating a first reduced operand comprises the step of reducing the first operand from an N-bit value to a P-bit value in a first reduction engine, thereby producing the first reduced operand.

18. The method as set forth in claim 17, wherein the step of generating a second reduced operand comprises the step of reducing the second operand from an M-bit value to a P-bit value in a second reduction engine, thereby producing the second reduced operand.

19. The method as set forth in claim 18, wherein the cryptographic system is disposed in a data processor.

20. The cryptographic system as set forth in claim 19, wherein the cryptographic system is disposed in a telecommunication system comprising one of 1) a wireless transceiver, and 2) a wireline transceiver.