RSA speedup with Chinese remainder theorem immune against hardware fault cryptanalysis

Sung Ming Yen, Seungjoo Kim, Seongan Lim, Sang Jae Moon

Research output: Contribution to journalArticlepeer-review

105 Citations (Scopus)


This article considers the problem of how to prevent the fast RSA signature and decryption computation with residue number system (or called the CRT-based approach) speedup from a hardware fault cryptanalysis in a highly reliable and efficient approach. The CRT-based speedup for 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, a hardware fault cryptanalysis can totally break the RSA system by factoring the public modulus. Some countermeasures by using a simple verification function (e.g., raising a signature to the power of public key) or fault detection (e.g., an expanded modulus approach) have been reported in the literature; however, it will be pointed out in this paper 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. Researches show that the expanded modulus approach proposed by Shamir is superior to the approach of using a simple verification function when other 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 rigorous proof of security. Two possible parameter settings are provided for the protocols. One setting is to select a small public key e and the proposed protocols can have comparable performance to Shamir's scheme. The other setting is to have 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 are carefully examined to point out possible weaknesses.

Original languageEnglish
Pages (from-to)461-472
Number of pages12
JournalIEEE Transactions on Computers
Issue number4
Publication statusPublished - 2003 Apr
Externally publishedYes

Bibliographical note

Funding Information:
The authors wish to acknowledge the anonymous reviewers for their valuable suggestions and comments, especially for pointing out an error in the previous version of Lemma 5. This work was supported in part by the Korea Information Security Agency (KISA) under contract R&D project 2001-S-092.


  • Chinese remainder theorem (CRT)
  • Cryptography
  • Denial of service attack
  • Factorization
  • Fault detection
  • Fault infective CRT
  • Fault tolerance
  • Hardware fault cryptanalysis
  • Physical cryptanalysis
  • Residue number system
  • Side channel attack

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'RSA speedup with Chinese remainder theorem immune against hardware fault cryptanalysis'. Together they form a unique fingerprint.

Cite this