Cryptanalysis of a Type of CRT-Based RSA Algorithms

It is well known that the Chinese Remainder Theorem (CRT) can greatlyimprove the performances of RSA cryptosystem in both running times andmemory requirements. However, if the implementation of CRT-based RSA iscareless, an attacker can reveal some secret information by exploitinghardware fault cryptanalysis. In this paper, we present some faultattacks on a type of CRT-RSA algorithms namely BOS type schemesincluding the original BOS scheme proposed by Bl\"omer, Otto, andSeifert at CCS 2003 and its modified scheme proposed by Liu \it et al.at DASC 2006. We first demonstrate that if some special signed messagessuch as m = 0, \pm1 are dealt carelessly, they can be exploited by anadversary to completely break the security of both the BOS scheme andLiu \it et al.'s scheme. Then we present a new permanent fault attackon the BOS scheme with a success probability about 25\%. Lastly, wepropose a polynomial time attack on Liu \it et al.'s CRT-RSA algorithm,which combines physical fault injection and lattice reduction techniqueswhen the public exponent is short.