Apparatus and method for consistency checking public key cryptography computations

• US 7,715,551 B2
• Filed: 04/29/2004
• Issued: 05/11/2010
• 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
• Primary Examiner(s): Shiferaw; Eleni A
• Assistant Examiner(s): McNally; Michael S
• Application Number:
  US10/835,102
• Publication Number:
  US 20050243998A1
• Time in Patent Office: 2,203 Days
• Field of Search: 380/2
• US Class Current: 380/2
• 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 receiving a first operand and a second operand and generating therefrom a first result;

a second Montgomery-based cryptographic engine receiving a first reduced operand derived from said first operand, a second reduced operand derived from said second operand, and a reduced intermediate result derived from an intermediate result generated by the first Montgomery-based cryptographic engine, and generating therefrom a second result, wherein said second Montgomery-based cryptographic engine operates in parallel with said first Montgomery-base cryptographic engine; and

a first reduction engine for reducing the first result to a first reduced result,

wherein the first and second reduced operands and the first reduced result are derived using 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, to produce a sum, and then dividing the sum by a second number to obtain a modulo remainder.

2. The cryptographic system as set forth in claim 1, wherein the reduction function produces one of:

a four-bit digest number and an eight-bit digest number.

3. The cryptographic system as set forth in claim 1, 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 1, further comprising a comparator for comparing said second result to said first reduced 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 1, further comprising a second 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 third 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, wherein the first reduction engine reduces 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 the intermediate result generated by said first Montgomery-based cryptographic engine to thereby produce the 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 telecommunication system.

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

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

12. The cryptographic system as set forth in claim 1, wherein said reduction function produces a two-digit hexadecimal number when k=16.

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;

generating a reduced intermediate result from an intermediate result generated by the first Montgomery-based cryptographic engine;

inputting the first and second reduced operands and the reduced intermediate result 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; and

reducing the first result to a first reduced result,

wherein the first and second reduced operands and the first reduced result are derived using 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, to produce a sum, and then dividing the sum by a second number to obtain a modulo remainder.

14. The method as set forth in claim 13, wherein the reduction function produces one of:

a four-bit digit number and an eight-bit digest number.

15. The method as set forth in claim 13, 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 13, further comprising the steps of:

comparing the second result to the first reduced 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 13, 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 13, wherein the reduction function produces a two-digit hexadecimal number when k=16.

20. The method as set forth in claim 19, wherein the first and second Montgomery-based cryptographic engines are disposed in a telecommunication system comprising one of 1) a wireless transceiver, and 2) a wireline transceiver.