Patent ID: 8577028
Filing Date: 2013-11-05
Classification: G06F,H04L

Abstract:
1. A method of computing an exponentiated message of the form s=m d 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 (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: