Method and apparatus for masking modulo exponentiation calculations in an integrated circuit

• US 6,064,740 A
• Filed: 11/12/1997
• Issued: 05/16/2000
• Est. Priority Date: 11/12/1997
• Status: Expired due to Term

• Current Assignee: Maxim Integrated Products, Inc. (Analog Devices, Inc.)
• Original Assignee: Dallas Semiconductor Corporation (Analog Devices, Inc.)
• Inventors: Little, Wendell, Curiger, Andreas
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Callahan, Paul E.
• Application Number:
  US08/969,144
• Time in Patent Office: 916 Days
• Field of Search: 380/30, 380/264, 380/265, 708/3, 708/7, 708/8, 708/103, 708/105, 708/277, 708/490, 708/491, 708/501, 708/503, 708/504, 708/533, 708/606
• US Class Current: 380/265
• CPC Class Codes: G06F 2207/7261 Uniform execution, e.g. avoiding jumps, or using formulae with the same power profile
• CPC Class Codes: G06F 7/723 Modular exponentiation G06F7/724, G06F7/727, G06F7/728 take precedence

Abstract

Circuitry which performs modular mathematics to solve the equation C=M^k mod n and n is performed in a manner to mask the exponent k'"'"'s signature from timing or power monitoring attacks. The modular exponentation function is performed in a normalized manner such that binary ones and zeros in the exponent are calculated by being modulo-squared and modulo-multiplied.

Claims

1. An integrated circuit containing circuitry for performing modulo exponentiation, said integrated circuit comprising:

a modulo exponentiation calculation circuit;

a mode data, said mode data indicating whether said modulo exponentiation calculation circuit should operate in at least a one of a standard mode and a normalized mode;

when said mode signal indicates that said modulo exponentiation calculation circuit should operate in said standard mode, said modulo exponentiation calculation circuit performs the steps of;

a first step of determining whether a first bit of an exponent is a one or a zero, if said first bit is a zero then said first step is repeated with the next bit until a first one is found;

a second step of performing a modulo square calculation with said first one;

a third step of performing a modulo multiply calculation;

a fourth step of determining whether the next bit of the exponent is a one or a zero, if the next bit is a one then a modulo square calculation is performed and then a modulo multiply calculation is performed, if the next bit is a zero than a modulo square calculation is performed;

a fifth step of repeating the fourth step with each remaining bit in the exponent;

when said mode signal indicates that said modulo exponentiation calculation circuit should operate in said normalized mode, said modulo exponent calculation circuit performs the steps of;

(a) calculating a modulo square calculation on a first bit of said exponent;

(b) calculating a modulo multiply calculation on said first bit of said exponent;

(c) repeating steps (a) and (b) for each remaining bit in said exponent.

2. The integrated circuit of claim 1, wherein after step (b) the result of said step of calculating said modulo multiply is discarded by said modulo exponentiation calculation circuit if first bit or said each of said remaining bits in said exponent is a zero.

3. An integrated circuit for performing modulo exponentiation, said integrated circuit comprising:

a storage location for storing a mode signal, said mode signal indicating whether said integrated circuit should operate in at least one of a standard mode and normalized mode;

a modulo exponentiation calculation circuit responsive to said mode signal, if said mode signal indicates that said integrated circuit should operate in said standard mode then said modulo exponentiation calculation circuit performs the steps of;

(a1) performing a modulo-square operation and then a modulo-multiply operation on an exponent bit that is a one; and

(b1) performing a modulo-square operation on an exponent bit that is a zero;

if said mode signal indicates that said integrated circuit should operate in said normalized mode then said modulo exponentiation calculation circuit performs the steps of;

(a2) performing a modulo-square operation and then a modulo-multiply operation on each exponent bit.

4. The integrated circuit for performing modulo exponentiation of claim 3, wherein said modulo exponentiation calculation circuit performs said modulo-square operation in the same number of clock cycles as said modulo exponentiation calculation circuit performs a modulo-multiply operation.

5. The integrated circuit for performing modulo exponentiation of claim 3, wherein said modulo exponentiation calculation circuit uses substantially the same amount of power to perform either a modulo-square operation and a modulo-multiply operation.

6. An article of manufacture for performing a modular exponentiation calculation in a normalized fashion on a binary exponent, the article of manufacture comprising:

at least one electronically readable medium;

processor instructions contained on the at least one electronically readable medium, the processor instructions configured to be readable from the at least one electronically readable medium by at least one processor and thereby cause the at least one processor to operate as to;

perform a modulo-square calculation on a bit of an exponent; and

perform a modulo-multiply calculation on said bit of said exponent.

7. The article of manufacture of claim 6, wherein after said operation of performing said modulo-multiply calculation a result is saved in an intermediate storage location only if said bit is a one.

8. The article of manufacture of claim 6, wherein said operation of performing said modulo-square calculation requires substantially the same amount of time as said operation of performing said modulo-multiply calculation.

9. The article of manufacture of claim 6, wherein said bit of said exponent is a one.

10. The article of manufacture of claim 6, wherein said bit of said exponent is a one or a zero.

11. An integrated circuit comprising:

a first location for storing a binary number;

an electronic circuit connected to said first location for performing both a modulo square calculation and a modulo multiply calculation on each bit of said binary number, whereby a result of the modulo multiply calculation is not saved as an intermediate result if a bit in said binary number is a zero.

12. The integrated circuit of claim 11, wherein said modulo exponentiation calculation circuit performs said modulo square calculation and said modulo multiply calculation on each bit of said binary number from a most significant bit to a least significant bit.

13. The integrated circuit of claim 11, wherein said modulo exponentiation calculation circuit performs said modulo square calculation and said modulo multiply calculation on each bit of said binary number from a least significant bit to a most significant bit.

14. The integrated circuit of claim 11, wherein said modulo exponentiation calculation circuit receives a plurality clock pulses, and wherein said modulo multiply calculation and said modulo square calculation require the same number of said clock pulses.

15. The integrated circuit of claim 11, wherein the electronic circuit consumes the same amount of power to perform the modulo square calculation and the modulo multiply calculation.