System and method for performing exponentiation in a cryptographic system
AssigneeCerticom Corp.
InventorsNevine Maurice Nassif Ebeid, Robert John Lambert
Life of this patent
Estimating the term…
Abstract
There are disclosed systems and methods for computing an exponentiatied message. In one embodiment blinding is maintained during the application of a Chinese Remainder Theorem (CRT) algorithm and then removed subsequent to the completion of the CRT algorithm. In another embodiment, fault injection attacks, such as the gcd attack, can be inhibited by applying and retaining blinding during the application of the CRT algorithm to yield a blinded exponentiation value, and then subsequently removing the blinding in a manner that causes an error injected into the CRT computation to cascade into the exponent of the value used to unblind the blinded exponentiated value.
Claims18
A method of computing an exponentiated message of the form s=md mod n, the method being performed by a correspondent in a cryptographic system, wherein the cryptographic system is an RSA system having a private key d and a corresponding public key (n, e) wherein n=pq, gcd(e, φ)=1, and φ=(p−1)(q−1), the correspondent including a processing unit and a memory, the memory having stored thereon a secret value p, a secret value q, and private key information;
- the method comprising the steps of:
- (a) the correspondent performing modular arithmetic operations in said processing unit to generate a first message component and a second message component, the first message component computed by operating on a message m using a mod p operation, and the second message component computed by operating on said message m using a mod q operation;
- (b) the processing unit computing a first blinded exponentiated message component using said first message component, a value derived from a blinding parameter r, and said private key information, and the processing unit computing a second blinded exponentiated message component using said second message component, another value derived from said blinding parameter r, and said private key information;
- (c) the processing unit combining said first blinded exponentiated message component and said second blinded exponentiated message component using a Chinese Remainder Theorem (CRT) algorithm to obtain a blinded exponentiated message of the form {tilde over (s)}=r(1−e) md mod n;
- (d) the processing unit validating the blinded exponentiated message by applying the blinded exponentiated message as an input to a function ƒ({tilde over (s)}) to obtain an output value of the function ƒ({tilde over (s)}), the output value equalling a predetermined value if the blinded exponentiated message is equal to an expected value of the blinded exponentiated message;
- and,
- (e) the processing unit evaluating the output value and when the output value does not equal the predetermined value, the processing unit notifies the correspondent that the validation has failed, and when the output value does equal the predetermined value, the processing unit:
- (i) combining the output value with the blinding parameter r to obtain the unblinding value rƒ({tilde over (s)});
- and,
- (ii) unblinding the blinded exponentiated message by multiplying the blinded exponentiated message with the unblinding value to obtain the exponentiated message;
- whereby when the output value does not equal the predetermined value, the unblinding value differs from an expected value resulting in a failed unblinding of the blinded exponentiated message, thereby countering a fault injection attack.
A non-transitory computer-readable medium having stored thereon computer readable instructions for performing a method of computing an exponentiated message of the form s=md mod n, the method to be performed by a correspondent in a cryptographic system, wherein the cryptographic system is an RSA system having a private key d and a corresponding public key (n, e) wherein n=pq, gcd(e, φ)=1, and φ=(p−1)(q−1), the correspondent including a processing unit and a memory, the memory having stored thereon a secret value p, a secret value q, and private key information;
- said computer readable instructions comprising instructions for:
- (a) the correspondent performing modular arithmetic operations in said processing unit to generate a first message component and a second message component, the first message component computed by operating on a message m using a mod p operation, and the second message component computed by operating on said message m using a mod q operation;
- (b) the processing unit computing a first blinded exponentiated message component using said first message component, a value derived from a blinding parameter r, and said private key information, and the processing unit computing a second blinded exponentiated message component using said second message component, another value derived from said blinding value r, and said private key information;
- (c) the processing unit combining said first blinded exponentiated message component and said second blinded exponentiated message component using a Chinese Remainder Theorem (CRT) algorithm to obtain a blinded exponentiated message of the form {tilde over (s)}+r(1−e)md mod n;
- (d) the processing unit validating the blinded exponentiated message by applying the blinded exponentiated message as an input to a function ƒ({tilde over (s)}) to obtain an output value of the function ƒ({tilde over (s)}), the output value equalling a predetermined value if the blinded exponentiated message is equal to an expected value of the blinded exponentiated message;
- and,
- (e) the processing unit evaluating the output value and when the output value does not equal the predetermined value, the processing unit notifies the correspondent that the validation has failed, and when the output value does equal the predetermined value, the processing unit:
- (i) combining the output value with the blinding parameter r to obtain the unblinding value rƒ({tilde over (s)});
- and,
- (ii) unblinding the blinded exponentiated message by multiplying the blinded exponentiated message with the unblinding value to obtain the exponentiated message;
- whereby when the output value does not equal the predetermined value, the unblinding value differs from an expected value resulting in a failed unblinding of the blinded exponentiated message, thereby countering a fault injection attack.
A device in a cryptographic system, wherein the cryptographic system is an RSA system having a private key d and a corresponding public key (n, e) wherein n=pq, gcd(e, φ)=1, and φ=(p−1)(q−1), the device being configured to perform a method of computing an exponentiated message the form s=md mod n;
- the device including a processing unit and a memory, the memory having stored thereon a secret value p, a secret value q, and private key information;
- the device being configured for performing the steps of:
- (a) performing modular arithmetic operations in said processing unit to generate a first message component and a second message component, the first message component computed by operating on a message m using a mod p operation, and the second message component computed by operating on said message m using a mod q operation;
- (b) the processing unit computing a first blinded exponentiated message component using said first message component, a value derived from a blinding parameter r, and said private key information, and the processing unit computing a second blinded exponentiated message component using said second message component, another value derived from said blinding parameter r, and said private key information;
- (c) the processing unit combining said first blinded exponentiated message component and said second blinded exponentiated message component using a Chinese Remainder Theorem (CRT) algorithm to obtain a blinded exponentiated message of the form {tilde over (s)}=r(1−e) md mod n;
- and
- (d) the processing unit validating the blinded exponentiated message by applying the blinded exponentiated message as an input to a function ƒ({tilde over (s)}) to obtain an output value of the function ƒ({tilde over (s)}), the output value equalling a predetermined value if the blinded exponentiated message is equal to an expected value of the blinded exponentiated message;
- and,
- (e) the processing unit evaluating the output value and when the output value does not equal the predetermined value, the processing unit notifies the correspondent that the validation has failed, and when the output value does equal the predetermined value, the processing unit:
- (i) combining the output value with the blinding parameter r to obtain the unblinding value rƒ({tilde over (s)});
- and,
- (ii) unblinding the blinded exponentiated message by multiplying the blinded exponentiated message with the unblinding value to obtain the exponentiated message;
- whereby when the output value does not equal the predetermined value, the unblinding value differs from an expected value resulting in a failed unblinding of the blinded exponentiated message, thereby countering a fault injection attack.
Dependencies are inferred from the claim text.