Climbing Montgomery Ladder

Climbing Montgomery’s Ladder

Peter Montgomery, RIP

Imagine you had to find a book on shelves which spanned up to the top of a building, but you don’t want to give away the shelf that you take the book from. Just imaging you could create a ladder which you could use no matter the shelve it is on, but where the ladder will always be the same length. Then the length of the ladder will not give away the shelf. This is like the way that the Montgomery Ladder works, and where we can create a fixed time method to multiply a point in elliptic curve, with a scalar value.

Peter RIP

Much of the core security of our current world is built on the amazing work done by individuals in the 1980s. It is to Ron Rivest (including RSA, digital signatures, and MD5), Adi Shamir (including RSA, Shamir Sharing, Cryptoanalysis, and Zero-Knowledge Proofs), Whitfield Diffie (the Diffie-Hellman method), Ralph Merkle (Merkle Trees) and many others, that we turn to for our core security. At the forefront of this was Peter Montgomery and who died yesterday (18 Feb 2020). Peter was previously a researcher in Microsoft Research, and in his amazing career, he created Montgomery multiplication, Montgomery elliptic curves, and the Montgomery ladder. Here is one of his classic papers [here]:

Montgomery Ladder

One of Peter’s great contributions, too, is the Montgomery Ladder [here][1]:

The Montgomery ladder computes a point multiplication (kP) within a fixed amount of time. This means that it is immune from timing and power attacks. A demo of the method is here:

The method is uses an approach of double-and-add approach apart from where it uses the same number of point additions and doubles regardless of the value of k:

R0 <- 0
  R1 <-P
  for i from m downto 0 do
     if di = 0 then
        R1 <- point_add(R0, R1)
        R0 <- point_double(R0)
     else
        R0 <- point_add(R0, R1)
        R1 <- point_double(R1)
  return R0

So let’s look at it implemented in the secp256k1 curve (and which is used in Bitcoin). The base point (P) for secp256k1 is: (79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8) and the prime number is FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F (2256−232−29−28−27−26−24−1) and the curve is y²=x³+7.

A sample run is [here]:

G = {55066263022277343669578718895168534326250603453777594175500187360389116729240 32670510020758816978083085130507043184471273380659243275938904335757337482424}

k =  10

kG =  {72488970228380509287422715226575535698893157273063074627791787432852706183111 62070622898698443831883535403436258712770888294397026493185421712108624767191}

The following is the Montgomery Ladder method in Golang [here]:

// taken from https://github.com/vsergeev/btckeygenie/blob/master/btckey/elliptic_test.go
// ScalarMult computes Q = k * P on EllipticCurve ec.
func (ec *EllipticCurve) ScalarMult(k *big.Int, P Point) (Q Point) {
	/* Note: this function is not constant time, due to the branching nature of
	 * the underlying point Add() function. */

	/* Montgomery Ladder Point Multiplication
	 *
	 * Implementation based on pseudocode here:
	 * See https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Montgomery_ladder */

	var R0 Point
	var R1 Point

	R0.X = nil
	R0.Y = nil
	R1.X = new(big.Int).Set(P.X)
	R1.Y = new(big.Int).Set(P.Y)

	for i := ec.N.BitLen() - 1; i >= 0; i-- {
		if k.Bit(i) == 0 {
			R1 = ec.Add(R0, R1)
			R0 = ec.Add(R0, R0)
		} else {
			R0 = ec.Add(R0, R1)
			R1 = ec.Add(R1, R1)
		}
	}

	return R0
}

The following code is based on this code [here]:

Conclusion

Peter will be sadly missed, but his methods will live on, and continue to save time and improve security.

References

[1] Montgomery, Peter L. (1987). “Speeding the Pollard and elliptic curve methods of factorization”. Math. Comp. 48 (177): 243–264. doi:10.2307/2007888.