The Montgomery ladder is a regular arithmetic sequence for exponentiation or scalar multiplication. Its security goal is to keep secret bits from changing the observable operation pattern. section 10.4.2 section 10.5
A powering-ladder form processes exponent bits from most significant to least significant:
- Initialize R₀ and R₁ to 1 and e, respectively, then scan each bit of e. section 10.4.2
- For a 1 bit, update R₀ to R₀ × R₁ and R₁ to R₁². section 10.4.2
- For a 0 bit, update R₁ to R₀ × R₁ and R₀ to R₀². section 10.4.2
- Keep one multiplication, one squaring, and one swap operation per bit, regardless of the bit value. section 10.4.2
The ladder produces the same result as square-and-multiply while making power traces harder to distinguish between zero and one bits. Regular control flow is necessary but does not excuse variable iteration bounds or other secret-dependent behavior. section 10.4.2 section 10.5
Figure 10.6 Power trace of an RSA exponentiation showing how the square-and-multiply algorithm reveals the exponent
Contrast the ladder’s regular operation pattern with a square-and-multiply power trace that exposes exponent bits. section 10.4.2
