RSA speedup with residue number system immune against hardware fault cryptanalysis

Sung Ming Yen, Seungjoo Kim, Seongan Lim, Sangjae Moon

Research output: Chapter in Book/Report/Conference proceedingConference contribution

49 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 concept of fault infective CRT computation and fault infective CRT recombination are proposed. Based on the new concept, 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.

Original languageEnglish
Title of host publicationInformation Security and Cryptology - ICISC 2001 - 4th International Conference, Proceedings
EditorsKwangjo Kim
PublisherSpringer Verlag
Number of pages17
ISBN (Print)3540433198, 9783540433194
Publication statusPublished - 2002
Externally publishedYes
Event4th International Conference on Information Security and Cryptology, ICISC 2001 - Seoul, Korea, Republic of
Duration: 2001 Dec 62001 Dec 7

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other4th International Conference on Information Security and Cryptology, ICISC 2001
Country/TerritoryKorea, Republic of


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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'RSA speedup with residue number system immune against hardware fault cryptanalysis'. Together they form a unique fingerprint.

Cite this