标题：Cryptanalysis of a type of CRT-based RSA algorithms
作者：BaoDong Qin;Ming Li;FanYu Kong
作者机构：[Qin, B.-D] College of Computer Science and Technology, Southwest University of Science and Technology, Mianyang 621010, China;[ Li, M] Institute of N 更多
会议名称：1st International Symposium on Data, Privacy and E-Commerce
关键词：Chinese remainder theorem;RSA;BOS scheme;cryptanalysis;fault attack;LLL
摘要：It is well known that the Chinese Remainder Theorem (CRT) can greatly improve the performances of RSA cryptosystem in both running times and memory requirements. However, if the implementation of CRT-based RSA is careless, an attacker can reveal some secret information by exploiting hardware fault cryptanalysis. In this paper, we present some fault attacks on a type of CRT-RSA algorithms namely BOS type schemes including the original BOS scheme proposed by Blomer, Otto, and Seifert at CCS 2003 and its modified scheme proposed by Liu et al. at DASC 2006. We first demonstrate that if some special signed messages such as m = 0, ±1 are dealt carelessly, they can be exploited by an adversary to completely break the security of both the BOS scheme and Liu et al.\'s scheme. Then we present a new permanent fault attack on the BOS scheme with a success probability about 25%. Lastly, we propose a polynomial time attack on Liu et al.\'s CRT-RSA algorithm, which combines physical fault injection and lattice reduction techniques when the public exponent is short.