A new sign-change attack on the Montgomery ladders

In the 1980s, Peter Montgomery developed a powerful, fast algorithm for calculating multiples of field elements. Over subsequent years, the algorithm was adapted to work in arbitrary abelian groups. By the year 2000, it had been developed further to resist standard power and timing attacks and became known as the ‘Montgomery ladder’. In the literature, the focus of this algorithm has been to compute from most to least significant bit, known as the ‘left-to-right’ version. In this paper, we first resurrect the corresponding ‘right-to-left’ version of the Montgomery powering ladder and then demonstrate a new attack on both versions in the context of elliptic curves.