TY - GEN
T1 - RSA speedup with residue number system immune against hardware fault cryptanalysis
AU - Yen, Sung Ming
AU - Kim, Seungjoo
AU - Lim, Seongan
AU - Moon, Sangjae
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.
PY - 2002
Y1 - 2002
N2 - 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.
AB - 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.
KW - Chinese remainder theorem (CRT)
KW - Cryptography
KW - Factorization
KW - Fault detection
KW - Fault infective CRT
KW - Fault tolerance
KW - Hardware fault cryptanalysis
KW - Physical cryptanalysis
KW - Residue number system
KW - Side channel attack
UR - http://www.scopus.com/inward/record.url?scp=84949936541&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84949936541
SN - 3540433198
SN - 9783540433194
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 397
EP - 413
BT - Information Security and Cryptology - ICISC 2001 - 4th International Conference, Proceedings
A2 - Kim, Kwangjo
PB - Springer Verlag
T2 - 4th International Conference on Information Security and Cryptology, ICISC 2001
Y2 - 6 December 2001 through 7 December 2001
ER -