TY - CHAP

T1 - Security analysis of CRT-based cryptosystems

AU - Okeya, Katsuyuki

AU - Takagi, Tsuyoshi

PY - 2004

Y1 - 2004

N2 - We investigate the security of several cryptosystems based on the Chinese remainder theorem (CRT) against side channel attack (SCA). Novak first proposed a simple power analysis against the CRT part using the difference of message modulo p and modulo q. In this paper we apply Novak's attack to the other CRT-based cryptosystems, namely Multi-Prime RSA, Multi-Exponent RSA, Rabin cryptosystem, and HIME(R) cryptosystem. Novak-type attack is strictly depending how to implement the CRT. We examine the operations related to CRT of these cryptosystems, and show that an extended Novak-type attack is effective on them. Moreover, we present a novel attack called zero-multiplication attack. The attacker tries to guess the secret prime by producing ciphertexts that cause a multiplication with zero during the decryption, which is easily able to be detected by power analysis. We examine the zero-multiplication attack on the above cryptosystems. Finally, we propose countermeasures against these attacks. The proposed countermeasures are based on the ciphertext blinding, but they require no inversion operation. The overhead of the proposed scheme is only about 1% to 5% of the whole decryption.

AB - We investigate the security of several cryptosystems based on the Chinese remainder theorem (CRT) against side channel attack (SCA). Novak first proposed a simple power analysis against the CRT part using the difference of message modulo p and modulo q. In this paper we apply Novak's attack to the other CRT-based cryptosystems, namely Multi-Prime RSA, Multi-Exponent RSA, Rabin cryptosystem, and HIME(R) cryptosystem. Novak-type attack is strictly depending how to implement the CRT. We examine the operations related to CRT of these cryptosystems, and show that an extended Novak-type attack is effective on them. Moreover, we present a novel attack called zero-multiplication attack. The attacker tries to guess the secret prime by producing ciphertexts that cause a multiplication with zero during the decryption, which is easily able to be detected by power analysis. We examine the zero-multiplication attack on the above cryptosystems. Finally, we propose countermeasures against these attacks. The proposed countermeasures are based on the ciphertext blinding, but they require no inversion operation. The overhead of the proposed scheme is only about 1% to 5% of the whole decryption.

UR - http://www.scopus.com/inward/record.url?scp=33646405336&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33646405336&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-24852-1_28

DO - 10.1007/978-3-540-24852-1_28

M3 - Chapter

AN - SCOPUS:33646405336

SN - 3540222170

SN - 9783540222170

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 383

EP - 397

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Jakobsson, Markus

A2 - Yung, Moti

A2 - Zhou, Jianying

PB - Springer Verlag

ER -