Simple power analysis attack against cryptosystems based on Montgomery algorithm

Abstract

The Montgomery algorithm is widely used to reduce the computational complexity of large integer modular exponentiation. The SPA (simple power analysis) attacks against public-key cryptosystems based on Montgomery algo-rithm implementation were presented by exploitation of the inherent security vulnerability which that sensitive informa-tion leakage could be used by side-channel attack. The chosen-message SPA attacks were focused on, which enhance the differences of operating wave-forms between multiplication and squaring correlated to the secret key by using the input of particular messages. In particular, a SPA attack against RSA cryptosystem was showed based on large integer modular exponentiation. The results show that the attack algorithm is correct and effective.

Keywords

• modular exponentiation
• side-channel attack
• simple power analysis
• Montgomery algorithm