An efficient CRT-RSA algorithm secure against power and fault attacks

RSA digital signatures based on the Chinese Remainder Theorem (CRT) are subject to power and fault attacks. In particular, modular exponentiation and CRT recombination are prone to both attacks. However, earlier countermeasures are susceptible to the possibility of advanced and sophisticated attacks. In this paper, we investigate state-of-the-art countermeasures against power and fault attacks from the viewpoint of security and efficiency. Then, we show possible vulnerabilities to fault attacks. Finally, we propose new modular exponentiation and CRT recombination algorithms secure against all known power and fault attacks. Our proposal improves efficiency by replacing arithmetic operations with logical ones to check errors in the CRT recombination step. In addition, since our CRT-RSA algorithm does not require knowledge of the public exponent, it guarantees a more versatile implementation.

► We investigate state-of-the-art countermeasures against power and fault attacks.
► We show potential vulnerabilities to fault attacks against existing countermeasures.
► Our modular exponentiation and CRT recombination algorithms are secure against all known power and fault attacks.
► Our CRT-RSA algorithm has a guarantee that requires no knowledge of the public exponent.