Cryptology ePrint Archive: Report 2015/657

Randomizing the Montgomery Powering Ladder

Duc-Phong Le, Chik How Tan and Michael Tunstall

Abstract: 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.

Category / Keywords: implementation / side channel analysis

Original Publication (with minor differences): WISTP 2015

Date: received 1 Jul 2015, last revised 2 Jul 2015

Contact author: mike tunstall at yahoo co uk

Available format(s): PDF | BibTeX Citation

Version: 20150702:173647 (All versions of this report)

Short URL: ia.cr/2015/657

Discussion forum: Show discussion | Start new discussion