RSA speedup with chinese remainder theorem immune against hardware fault cryptanalysis
- 2 April 2003
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 52 (4), 461-472
- https://doi.org/10.1109/tc.2003.1190587
Abstract
This article considers the problem of how to prevent RSA signature and decryption computation with a residue number system (CRT-based approach) speedup from a hardware fault cryptanalysis in a highly reliable and efficient approach. CRT-based speedup for an RSA signature has been widely adopted as an implementation standard ranging from large servers to very tiny smart IC cards. However, given a single erroneous computation result, hardware fault cryptanalysis can totally break the RSA system by factoring the public modulus. Countermeasures using a simple verification function (e.g., raising a signature to the power of a public key) or fault detection (e.g., an expanded modulus approach) have been reported in the literature; however, it is pointed out that very few of these existing solutions are both sound and efficient. Unreasonably, in these methods, they assume that a comparison instruction will always be fault-free when developing countermeasures against hardware fault cryptanalysis. Research shows that the expanded modulus approach proposed by Shamir (1997, 1999) is superior to the approach using a simple verification function when another physical cryptanalysis (e.g., timing cryptanalysis) is considered. So, we intend to improve Shamir's method. In this paper, the new concepts of fault infective CRT computation and fault infective CRT recombination are proposed. Based on the new concepts, two novel protocols are developed with a rigorous proof of security. Two possible parameter settings are provided for the protocols. One setting selects a small public key and the proposed protocols can have comparable performance to Shamir's scheme. The other setting has better performance than Shamir's scheme (i.e., having comparable performance to conventional CRT speedup), but with a large public key. Most importantly, we wish to emphasize the importance of developing and proving the security of physically secure protocols without relying on unreliable or unreasonable assumptions, e.g., always fault-free instructions. In this paper, related protocols are also considered and carefully examined to point out possible weaknesses.This publication has 14 references indexed in Scilit:
- Observability Analysis - Detecting When Improved Cryptosystems Fail -Lecture Notes in Computer Science, 2002
- Checking before output may not be enough against fault-based cryptanalysisIEEE Transactions on Computers, 2000
- A Timing Attack against RSA with the Chinese Remainder TheoremLecture Notes in Computer Science, 2000
- Montgomery Exponentiation with no Final Subtractions: Improved ResultsLecture Notes in Computer Science, 2000
- Montgomery exponentiation needs no final subtractionsElectronics Letters, 1999
- Chinks in digital armor: Exploiting faults to break smart‐card cryptosystemsScience News, 1997
- Differential fault analysis of secret key cryptosystemsLecture Notes in Computer Science, 1997
- A public key cryptosystem and a signature scheme based on discrete logarithmsIEEE Transactions on Information Theory, 1985
- Fast decipherment algorithm for RSA public-key cryptosystemElectronics Letters, 1982
- A method for obtaining digital signatures and public-key cryptosystemsCommunications of the ACM, 1978