**Faster Montgomery and double-add ladders for short Weierstrass curves**

*Mike Hamburg*

**Abstract: **The Montgomery ladder and Joye ladder are well-known algorithms for elliptic curve scalar multiplication with a regular structure. The Montgomery ladder is best known for its implementation on Montgomery curves, which requires $5\mathbf{M} + 4\mathbf{S} + 1\mathbf{m} + 8\mathbf{A}$ per scalar bit, and 6 field registers. Here $(\mathbf{M},\mathbf{S},\mathbf{m},\mathbf{A})$ represent respectively field $\mathbf{M}$ultiplications, $\mathbf{S}$quarings, $\mathbf{m}$ultiplications by a curve constant, and $\mathbf{A}$dditions or subtractions. This ladder is also complete, meaning that it works on all input points and all scalars.

Many protocols do not use Montgomery curves, but instead use prime-order curves in short Weierstrass form. These have historically been much slower, with ladders costing at least 14 multiplications or squarings per bit: $8\mathbf{M}+6\mathbf{S}+27\mathbf{A}$ for the Montgomery ladder and $8\mathbf{M}+6\mathbf{S}+30\mathbf{A}$ for the Joye ladder. In 2017, Kim et al. improved the Montgomery ladder to $8\mathbf{M}+4\mathbf{S}+12\mathbf{A}+1\mathbf{H}$ per bit using 9 registers, where the $\mathbf{H}$ represents a halving. Hamburg simplified Kim et al.'s formulas to $8\mathbf{M}+4\mathbf{S}+8\mathbf{A}+1\mathbf{H}$ per bit using 6 registers.

Here we present improved formulas which compute the Montgomery ladder on short Weierstrass curves using $8\mathbf{M}+3\mathbf{S}+7\mathbf{A}$ per bit, and requiring 6 registers. We also give formulas for the Joye ladder that use $9\mathbf{M}+3\mathbf{S}+7\mathbf{A}$ per bit, requiring 5 registers. One of our new formulas supports very efficient 4-way vectorization.

We also discuss curve invariants, exceptional points, side-channel protection and how to set up and finish these ladder operations. Finally, we show a novel technique to make these ladders complete when the curve order is not divisible by 2 or 3, at a modest increase in cost.

A sample implementation of these techniques is given in the supplementary material, also posted at https://github.com/bitwiseshiftleft/ladder_formulas.

**Category / Keywords: **public-key cryptography / Elliptic Curve Cryptography, Montgomery Ladder, Joye Ladder, Short Weierstrass Curve, Scalar Multiplication

**Original Publication**** (with minor differences): **IACR-CHES-2020

**Date: **received 15 Apr 2020, last revised 20 Jul 2020

**Contact author: **mhamburg at rambus com

**Available format(s): **PDF | BibTeX Citation

**Note: **CHES 2020 camera-ready version, plus one typo fixed (thanks Shiping Cai). Supplementary material is available at https://github.com/bitwiseshiftleft/ladder_formulas.

**Version: **20200720:155909 (All versions of this report)

**Short URL: **ia.cr/2020/437

[ Cryptology ePrint archive ]