Paper 2020/437

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.

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