X25519 original specification

Adapted from the original specification:

This section defines what is now known as the X25519 function.

Theorem 2.1: Let $p$ be a prime number with $p\geq 5$. Let $A$ be an integer such that $A^2 – 4$ is not a square modulo $p$. Define $E$ as the elliptic curve $y^2=x^3+Ax^2+x$ over the field $\mathbb{F}_p$. Define $X_0:E\left(\mathbb{F}_{p^2}\right)\to\mathbb{F}_{p^2}$ as follows: $X_0\left(\infty\right)=0;X_0\left(x,y\right)=x$. Let $n$ be an integer. Let $q$ be an element of $\mathbb{F}_p$. Then there exists a unique $s\in\mathbb{F}_p$ such that $X_0\left(nQ\right)=s$ for all $Q\in E\left(\mathbb{F}_{p^2}\right)$ such that $X_0\left(Q\right)=q$.

In particular, define $p$ as the prime $2^{255}-19$. Define $\mathbb{F}_p$ as the prime field $\mathbb{Z}/p=\mathbb{Z}/{(2^{255}-19})$. Note that $2$ is not a square in $\mathbb{F}_p$; define $\mathbb{F}_{p^2}$ as the field $\left(\mathbb{Z}/{(2^{255}-19)}\right){[\sqrt{2}]}$. Define $A=486662$. Note that $486662^2-4$ is not a square in $\mathbb{F}_p$. Define $E$ as the elliptic curve $y^2=x^3+Ax^2+x$ over $\mathbb{F}_p$. Define a function $X_0: E\left(\mathbb{F}_{p^2}\right)\to\mathbb{F}_{p^2}$ as follows: $X_0\left(\infty\right)=0;X_0\left(x,y\right)=x$. Define $E$ as the elliptic curve $y^2=x^3+Ax^2+x$ over $\mathbb{F}_p$. Define a function $X: E\left(\mathbb{F}_{p^2}\right)\to\left\{\infty\right\}\cup\mathbb{F}_{p^2}$ as follows: $X\left(\infty\right)=\infty;X\left(x,y\right)=x$.

Given $n\in 2^{254}+8\left\{0,1,2,3,\ldots,2^{251}-1\right\}$ and $q\in\mathbb{F}_p$, the $\text{X25519}$ function produces $s$ in Theorem 2.1.

Now $\text{X25519}:\left\{\text{X25519 secret keys}\right\}\times\left\{\text{X25519 public keys}\right\}\to{\{0,1,\ldots 2^{8}-1\}}^{32}$ is defined as follows. Fix $q\in\left\{0,1,\ldots,2^{256}-1\right\}$ and $n\in 2^{254}+\left\{0,1,2,3,\ldots,2^{251}-1\right\}$. By Theorem 2.1, there is a unique integer $s\in\left\{0,1,2,\ldots,2^{255}-20\right\}$ with the following property: $s=X_0\left(nQ\right)$ for all $Q\in E\left(\mathbb{F}_{p^2}\right)$ such that $X_0\left(Q\right)=q\text{ mod }2^{255}-19$. Finally, $\text{X25519}{(\underline{n},\underline{q})}$ is defined as $\underline{s}$. Note that $\text{X25519}$ is not surjective: in particular, its final output bit is $0$ and need not be transmitted.

The author then proceeds to give some highly applied implementation details to do with bit twiddling algebraic polynomials, reductions around the CPU register size for constant-time arithmetic and whatnot… but, if my understanding is correct, the above quote contains the full specification of the function itself, if you have enough mathematical knowledge to wring it out of there (left, canonically, as an exercise for the reader; the paper excuses its terseness by recommending some math textbooks).

There have been some fantastic attempts [Martin Kleppman; Bill Buchanan] to bridge this gap and explain the core function at a humanly-comprehensible level, but they, like the original paper, all jump straight from the mathematically pure high-level descriptions of "point operations on generating curves" to the extremely technical low-level "scalar multiplications with montgomery ladders", without ever taking a segue through "just normal numbers". If I cannot find such an explanation myself, I may have to learn the relevant mathematics and write one.

Though, perhaps crafting such a document wouldn't be worth the investment: X25519 isn't quantum-safe, and what may be the best upcoming quantum-safe algorithm (produced by—among others—the very same gentleman that made X25519) has already got a fantastic explainer by Ashley Valentijn of Syracuse University, published as her honors capstone project. Better, perhaps, to study up about that, instead.