US6064740A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for masking modulo exponentiation calculations in an integrated circuit
Assignee: Maxim Integrated Products Inc
•
Filing: 1997-11-12
•
Granted: 2000-05-16
•
Expires: 2017-11-12
Abstract
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.
Inventors
- 👤 Andreas Curiger
- 👤 Wendell Little
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 18:50
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/723; G06F2207/00; G06F2207/72; G06F2207/7219; G06F2207/7261
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
269 words
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.
Claim 2
Dependent Claim
269 words
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.
Claim 3
Dependent Claim
44 words
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.
Claim 4
Dependent Claim
146 words
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.
Claim 5
Dependent Claim
146 words
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.
Claim 6
Dependent Claim
37 words
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.
Claim 7
Dependent Claim
33 words
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.
Claim 8
Dependent Claim
93 words
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.
Claim 9
Dependent Claim
93 words
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.
Claim 10
Dependent Claim
32 words
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.
Claim 11
Dependent Claim
30 words
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.
Claim 12
Dependent Claim
16 words
The article of manufacture of claim 6, wherein said bit of said exponent is a one.
Claim 13
Dependent Claim
19 words
The article of manufacture of claim 6, wherein said bit of said exponent is a one or a zero.
Claim 14
Dependent Claim
64 words
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.
Claim 15
Dependent Claim
64 words
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.
Claim 16
Dependent Claim
39 words
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.
Claim 17
Dependent Claim
39 words
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.
Claim 18
Dependent Claim
36 words
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.
Claim 19
Dependent Claim
27 words
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.
References Cited (Backward Citations)
US4424414A
Cited
US4532638A
Cited
US4658094A
Cited
US4891781A
Cited
US5261001A
Cited
US5414651A
Cited
US5289397A
Cited
US5274707A
Cited
US5299262A
Cited
US5513133A
Cited
US5870478A
Cited
US5928315A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-05-16 | 2003-11-15 | 2004-05-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-05-16 | 2007-11-15 | 2008-05-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-05-16 | 2011-11-15 | 2012-05-16 | $7700.00 | Window Closed / Lapsed |