Cryptanalysis of a type of CRT-based RSA algorithms

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, +/- 1are 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.