Volume 4 - Issue 4
Power Analysis Attacks on the Right-to-Left Square-Always Exponentiation Algorithm
- Jaecheol Ha
Hoseo University, Asan, ChungNam, Korea
jcha@hoseo.edu
- Yongje Choi
ETRI, Daejeon, Korea
choiyj@etri.re.kr
- Dooho Choi
ETRI, Daejeon, Korea
dhchoi@etri.re.kr
- Hoonjae Lee
Dongseo University, Busan, Korea
hjlee@dongseo.ac.kr
Keywords: RSA Cryptosystem, Side-Channel Attack, Simple Power Analysis, Square-Always Exponentiation
Abstract
The naive implementation of an exponentiation used in public key cryptography may reveal a secret
key to the attacker by several side-channel attacks. Recently, a novel square-always exponentiation
algorithm based on trading multiplications for squarings is proposed. This algorithm for RSA implementation
is faster than existing regular countermeasures against side-channel attacks. This paper
suggests that the right-to-left square-always exponentiation algorithm is vulnerable to some sidechannel
attacks: collision distance-based doubling, chosen-message SPA, and CPA-based combined
attacks. The chosen-message SPA attack can be intactly applied to this algorithm. The other two
attacks are variants of the doubling attack and SPA-based combined attack, respectively. In addition,
the paper presents an improved right-to-left square-always algorithm resistant to existing and proposed
power analysis attacks by using the additive message blinding method and the message update
technique before the main iterative operation.