What Makes Elliptic Curve Cryptography So Good? … Montgomery’s Ladder

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…

What Makes Elliptic Curve Cryptography So Good? … Montgomery’s Ladder

Imagine you had to find a book on shelves that 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 imagine 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 an 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 on 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 using an approach of double-and-add approach. It uses the same number of point additions and doubles regardless of the value of m:

N ← P
  Q ← 0
  for i from 0 to m do
     if di = 1 then
         Q ← point_add(Q, N)
     N ← point_double(N)
  return Q

For a=100 we have a binary value of 1100100:

1100100, thus we double the point (N=2G).
1100100, thus we double the point (N=4G).
1100100, thus we add the point (Q=4G), and then double the point (N=8G).
1100100, thus we double the point (N=16G).
1100100, thus we double the point (N=32G).
1100100, thus we add the point (Q=4G+32G=36G), and then double the point (N=64G).
1100100, thus we add the point (Q=36G+64G=100G), and then double the point (N=128G).

The result is then Q=4G+32G+64G=100G.

Coding and test run

So, let’s test the method. In this case, we will use the Coinbase Kryptology library and which implements secp256k1 and P256. We perform a point add with for Q=Q+N [here]:

Q = Q.Add(N)

For secp256k1 and for 100.G we get [here]:

Binary representation of 100: 1100100
Double
Double
Bit=1. Add Double
Double
Double
Bit=1. Add Double
Bit=1. Add Double

100.G

Compressed Point: 02ed3bace23c5e17652e174c835fb72bf53ee306b3406a26890221b4cef7500f88

Uncompressed Point: 04ed3bace23c5e17652e174c835fb72bf53ee306b3406a26890221b4cef7500f88e57a6f571288ccffdcda5e8a7a1f87bf97bd17be084895d0fce17ad5e335286e

Uncompressed Point: ed3bace23c5e17652e174c835fb72bf53ee306b3406a26890221b4cef7500f88, e57a6f571288ccffdcda5e8a7a1f87bf97bd17be084895d0fce17ad5e335286e

I have implemented here:

https://asecuritysite.com/kryptology/ecc_kr2

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.