---
slug: montgomerys-ladder
title: "Montgomery's Ladder"
date: "2024-09-09T02:00:29-04:00"
draft: true
---

In response to a question in the comments of an [article][] I posted the
comment below.

----


Short answer: To protect against timing side-channel attacks, the
implementation should use a constant-time version of [Montgomery's
ladder][montgomery's ladder].

Longer answer...

Definitions:

- Inversion: a{{< sup "-1" >}}. Calculate the number *b* such that a * b = 1
- Modular Inversion: a{{< sup "-1" >}} mod p. Calculate the number *b* such that a * b = 1 (mod p).


From [Fermat's little theorem][], we know that if *p* is prime, then
a{{< sup "p-1" >}} = 1 (mod p). Doing a bit of arithmetic:

a{{< sup "p-1" >}} = 1 (mod p) \
a * a{{< sup "p-2" >}} = 1 (mod p)

So a{{< sup "p-2" >}} (mod p) is the multiplicative inverse of *a*, modulo
*p*.

**Example:** Calculate 2{{< sup "-1" >}} mod 5

= 2{{< sup "-1" >}} mod 5 \
= 2{{< sup "5-2" >}} mod 5 \
= 2{{< sup "3" >}} mod 5 \
= 8 mod 5 \
= 3

Check result by verifying a * a{{< sup "-1" >}} = 1 (mod 5):

= 2 * 3 mod 5 \
= 6 mod 5 \
= 1

The numbers used in cryptography are extremely large. For example, the
primes for [Ed25519][] and [Poly1305][] are 2{{< sup "255" >}}-19 and
2{{< sup "130" >}}-5, respectively ([djb][] naming :D). To do modular
exponentation with large numbers you use a technique called
[exponentation by squaring][].

A common method of exponentation by squaring is [Montgomery's ladder][],
but it is not constant-time. You can make Montgomery's ladder
constant-time by changing the contents of the loop in Montgomery's
ladder from this:

> if n{{< sub "i" >}} = 0 then \
> &nbsp;&nbsp;&nbsp;&nbsp;x{{< sub "2" >}} = x{{< sub "1" >}} * x{{< sub "2" >}}; x{{< sub "1" >}} = x{{< sub "1" >}}{{< sup "2" >}} \
> else \
>  &nbsp;&nbsp;&nbsp;&nbsp;x{{< sub "1" >}} = x{{< sub "1" >}} * x{{< sub "2" >}}; x{{< sub "2" >}} = x{{< sub "2" >}}{{< sup "2" >}} \
> end


To something like this:

> a = x{{< sub "1" >}} * x{{< sub "2" >}} \
> b = x{{< sub "1" >}}{{< sup "2" >}} \
> c = x{{< sub "2" >}}{{< sup "2" >}} \
> d = is\_non\_zero(n{{< sub "i" >}})
>
> swap(x{{< sub "2" >}}, a, !d) \
> swap(x{{< sub "1" >}}, b, !d) \
> swap(x{{< sub "1" >}}, a, d) \
> swap(x{{< sub "2" >}}, c, d)


Where `swap()` is a constant-time function that swaps the values of the
first two arguments if the third argument is true and does nothing if
the third argument is false.

Usually `swap()` is implemented with careful bitmasking to prevent
overeager compilers from "optimizing" it.

[article]: https://arstechnica.com/security/2024/09/yubikeys-are-vulnerable-to-cloning-attacks-thanks-to-newly-discovered-side-channel/
[comment]: https://arstechnica.com/security/2024/09/yubikeys-are-vulnerable-to-cloning-attacks-thanks-to-newly-discovered-side-channel/?comments=1&comments-page=4
[montgomery's ladder]: https://en.wikipedia.org/wiki/Exponentiation_by_squaring#Montgomery%27s_ladder_technique
[fermat's little theorem]: https://en.wikipedia.org/wiki/Fermat%27s_little_theorem
[ed25519]: https://en.wikipedia.org/wiki/EdDSA
  "Edwards-curve Digital Signature Algorithm (EdDSA)"
[poly1305]: https://en.wikipedia.org/wiki/Poly1305
[exponentation by squaring]: https://en.wikipedia.org/wiki/Exponentiation_by_squaring
[djb]: https://en.wikipedia.org/wiki/Daniel_J._Bernstein
  "Daniel J. Bernstein"