Randomizing the montgomery powering ladder
Published in Information Security Theory and Practice: 9th IFIP WG 11.2 International Conference (WISTP), 2015
Recommended citation: Duc-Phong Le, Chik How Tan, Michael Tunstall. (2015). "Randomizing the montgomery powering ladder." WISTP 2015. https://eprint.iacr.org/2015/657.pdf
In this paper, we present novel randomized techniques to enhance Montgomery powering ladder. The proposed techniques increase the resistance against side-channel attacks and especially recently published correlation collision attacks in the horizontal setting. The first of these operates by randomly changing state such that the difference between registers varies, unpredictably, between two states. The second algorithm takes a random walk, albeit tightly bounded, along the possible addition chains required to compute an exponentiation. We also generalize the Montgomery powering ladder and present randomized (both left-to-right and right-to-left) m-ary exponentiation algorithms.
Recommended citation: Duc-Phong Le, Chik How Tan, Michael Tunstall. (2015). Randomizing the montgomery powering ladder. WISTP 2015.