An Improved Square-always Exponentiation Resistant to Side-channel Attacks on RSA Implementation

摘要

Many cryptographic algorithms embedded in security devices have been used to strengthen homeland defense capability and protect critical information from cyber attacks. The RSA cryptosystem with the naive implementation of an exponentiation may reveal a secret key by two types of side-channel attacks, namely passive leakage information analysis and active fault injection attacks. Recently, a square-always exponentiation algorithm in which the multiplication is traded for squarings has been proposed. This novel algorithm for RSA implementation is faster than other regularity-based countermeasures and is resistant to SPA (simple power analysis) and fault injection attacks. This paper shows that the right-to-left version of square-always exponentiation algorithm is vulnerable to several side-channel attacks, namely collision distance-based doubling, chosen-message CPA (collision power analysis), and horizontal CPA-based combined attacks. Furthermore, an improved right-to-left square-always algorithm adopting the additive message blinding method and the intermediate message update technique is proposed to defeat previous and proposed side-channel attacks. The proposed exponentiation algorithm can be employed for secure CRT-RSA (RSA based on the Chinese remainder theorem) implementation resistant to the Bellcore attack. The paper presents some experimental results for the proposed power analysis attacks using an evaluation board.