Implementing Curve25519/X25519: A Tutorial on Elliptic Curve Cryptography

Martin Kleppmann

Draft manuscript, October 2020.

• Paper (open access)

Abstract

Many textbooks cover the concepts behind Elliptic Curve Cryptography, but few explain how to go from the equations to a working, fast, and secure implementation. On the other hand, while the code of many cryptographic libraries is available as open source, it can be rather opaque to the untrained eye, and it is rarely accompanied by detailed documentation explaining how the code came about and why it is correct. This tutorial bridges the gap between the mathematics and implementation of elliptic curve cryptography. It is written for readers who are new to cryptography, and it assumes very little mathematical background. Starting from first principles, this paper shows how to derive every line of code in an implementation of the X25519 Diffie-Hellman key agreement scheme, based on the Curve25519 elliptic curve. The implementation is fast and secure; in particular, it is constant-time to prevent side-channel attacks.