A CRT-RSA Algorithm Secure against Hardware Fault Attacks

Chinese remainder theorem based RSA (CRT-RSA) digital signature has important applications in smart cards. Previous CRT-RSA algorithms such as CRT-2 and BOS are susceptible to practical hardware fault attacks. In this paper, a new CRT-RSA algorithm with countermeasures to hardware fault attacks is proposed. To our knowledge, the proposed algorithm is the first that can resist what we call the single-fault adversarial attacks. The proposed algorithm first computes the signature using CRT in a secret algebraic setting, then a set of fault-detection variables are computed to detect possible faults. Lastly, the signature is mapped from the secret algebraic setting to the intended setting. By using a random number and the fault detection variables, every step of the algorithm is protected from hardware faults. The output of the algorithm will be fully randomized in case of faults. The CRT´s speed advantages are also maintained. The proposed algorithm is approximately two times as fast as the direct form RSA for the two-prime case, and about four times as fast for the three-prime case