Chinese remainder theorem-based computation method for cryptosystems
View Patent ↗A computer hardware implemented cryptography method computes a modular exponentiation, M :=Cd (mod p·q), upon a message data value C using a Chinese Remainder Theorem (CRT) based technique. To secure against cryptanalysis, the private key moduli p and q are transformed by multiplication with a generated random value s, so that p′: =p·s and q′ :=q·s, as shown in an exemplary embodiment in FIG. 2 . The CRT steps of the modular exponentiation are applied using the transformed moduli p′ and q′ to obtain a random intermediate message data value M′. A final reduction of M′ modulo p·q yields the final message data value M. Values needed for the computation are loaded into data storage and accessed as needed by electronic processing hardware.
1. A cryptographic method implemented in an electronic processing system for performing modular exponentiation computations, comprising:
loading private key values, including at least one private key exponent and two private key moduli p and q, wherein the two private key moduli are p and q, into a data storage accessible to electronic processing hardware;
selecting, by the electronic processing hardware, a non-random pre modular exponentiation transformation factor to secure cryptographic operations utilizing modular exponentiation from cryptanalysis, wherein the transformation factor is co-prime with the private key moduli;
multiplying, by the electronic processing hardware, the private key moduli by the transformation factor to produce transformed moduli p′ :=p·s and q′ :=q·s, wherein the transformed moduli are p′ and q′ and wherein the transformation factor is s;
loading a first data value into the data storage at any time prior to performing modular exponentiation;
computing, by the electronic processing hardware, at least one transformed inverse value, R′ :=(p′) −1 (mod q);
performing, by the electronic processing hardware, a modular exponentiation upon the first data value using the at least one private key exponent and the transformed moduli to obtain an intermediate data value; and
reducing, by the electronic processing hardware, the intermediate data value modulo a product of the two private key moduli to obtain a final data value.
2. The method as in claim 1 wherein the selected transformation factor is a fixed value.
3. The method as in claim 1 , wherein performing modular exponentiation is executed using a Chinese Remainder Theorem (CRT) calculation of the intermediate data value.
4. The method as in claim 3 , wherein a pair of CRT exponents are computed from a single private key exponent as part of the performing the modular exponentiation.
5. The method as in claim 3 , wherein a pair of CRT exponents are pre-computed from a single private key exponent, the pair of CRT exponents being loaded as private key exponents into the data storage.
6. The method as in claim 1 , wherein the product of the two private key moduli is pre-computed as a public key modulus, the public key modulus also being loaded into the data storage for subsequent use in the reducing of the intermediate data value.
7. The method as in claim 1 , wherein the first data value represents a ciphertext message, the modular exponentiation is executed in the electronic processing hardware as part of a cipher program, and the final data value represents a decrypted plaintext message.
8. A cryptographic method implemented in an electronic processing system for performing modular exponentiation computations, comprising:
loading at least one private key exponent d and two private key moduli p and q, wherein the two private key moduli are p and q, into a data storage accessible to electronic processing hardware;
selecting, by the electronic processing hardware, a non-random pre modular exponentiation transformation factor s to secure cryptographic operations utilizing modular exponentiation from cryptanalysis, wherein the transformation factor is co-prime with the private key moduli;
multiplying, by the electronic processing hardware, the private key moduli by the transformation factor to produce transformed moduli p′ :=p·s and q′ :=q·s, wherein the transformed moduli are p′ and q′;
computing, by the electronic processing hardware, at least one transformed inverse value, R′ :=(p′) −1 (mod q);
loading a first data value C into the data storage at any time prior to performing modular exponentiation;
performing a modular exponentiation upon the first data value C using the at least one private key exponent d and the transformed moduli p′ and q′ to obtain an intermediate data value M′, wherein performing modular exponentiation is executed by the electronic processing hardware using a Chinese Remainder Theorem (CRT) calculation of the intermediate data value involving:
(a) computing CRT exponents d 1 :=d (mod (p−1)) and d 2 :=d (mod (q−1)),
(b) computing CRT message components M 1 ′:=C d 1 (mod p′) and M 2 ′:=C d 2 (mod q′), and
(c) computing an intermediate data value M′ from the CRT message components M 1 and M 2 ′; and reducing, by the electronic processing hardware, the intermediate data value M′ modulo a product of the two private key moduli, n =p·q, to obtain a final data value M :=M′ (mod n).
9. The method as in claim 8 , wherein the CRT exponents are pre-computed from the private key exponent d and loaded as a pair of private key exponents d 1 and d 2 into the data storage.
10. The method as in claim 8 , wherein M′:=M 1 ′+p′·{[(M 2 ′−M 1 ′)·R′](mod q′)}.
11. The method as in claim 8 , wherein M′:=(M 1 ′·R 1 ′·q′+M 2 ′·R 2 ′·p′) (mod p′·q′), and R 1 ′:=(q′) −1 (mod p).
12. The method as in claim 8 , wherein M′:={[(M 1 ′·R 1 ′) (mod p′)]·q′+[(M 2 ′·R′) (mod q′)]·p′}(mod p′·q′), and R 1 ′:=(q′) −1 (mod p).
13. The method as in claim 8 , wherein M′:=q′·{[(M 1 ′−M 2 ′)·R′](mod p′)}+M 2 ′.
14. The method as in claim 8 , wherein the product n=p·q is pre-computed and loaded into the data storage for subsequent use during the reducing of the intermediate data value.
15. The method as in claim 8 , wherein the first data value represents a ciphertext message, the modular exponentiation is executed in the electronic processing hardware as part of a cipher program, and the final data value represents a decrypted plaintext message.