How can we overcome both side channel analysis and fault attacks on RSA-CRT?

RSA cryptosystem is one of the most widely used algorithms nowadays. However when it is implemented in embedded devices such as smart cards, it can be vulnerable to power analysis attacks and fault attacks. To defeat all known side channel attacks and fault attacks, several countermeasures should be used together. However due to the low computation capability of the embedded devices, we have to find the best solution or combination among countermeasures. Furthermore, we should be careful since a countermeasure may produce another new vulnerability such as Yen et. al.´s safe-error attack in a simple power analysis (SPA) countermeasure. In 2005, Giraud proposed a scheme secure against simple power analysis as well as fault attack (FA). Afterwards, Fumaroli and Vigilant proposed an exponentiation algorithm secure against differential power analysis (DPA) as well as simple power analysis and fault attack with almost 1.5 times increase in time complexity compared to Giraud´s. To the authors´ best knowledge, it was a first trial to prevent SPA, DPA, and FA simultaneously on exponentiation with one solution. In this paper we show Fumaroli and Vigilant´s scheme can be broken by fault attacks and propose a direction to construct efficient countermeasures secure against all known side channel analyses and fault attacks on RSA-CRT with low time complexity.