Six-word summary: the elliptic-curve discrete log problem.
$\newcommand{\F}{\mathbb{F}}\newcommand{\Z}{\mathbb{Z}}$Summary with math: Given $x(A)$ and $x(P)$ for two points $A$ and $P$ on the elliptic curve $y^2 = x^3 + 486662 x^2 + x$ over the field $\Z/(2^{255} - 19)\Z$, find an integer $a$ such that $A = [a]P$, where $[a]P$ is scalar multiplication on the curve. We pick $a$ (in your notation, $k$) uniformly at random from $2^{251}$ possibilities, so that the best algorithms for computing it from $x([a]P)$ (in your notation, $b^k$) cost about $2^{125}$ arithmetic operations, more than any adversary can ever hope to carry out.
Or, more precisely, we rely on the computational elliptic-curve Diffie–Hellman problem: Given public keys $x(A)$, $x(B)$, and $x(P)$, find $x([ab]P)$ where $A = [a]P$ and $B = [b]P$. But it seems to be not much easier than the ECDLP.
In a little more detail:
The number $p = 2^{255} - 19$ is a prime, so every integer that is not a multiple of $p$ has an inverse modulo $p$, and thus the integers modulo $p$ form a finite field $\F_p = \operatorname{GF}(p) = \Z/(2^{255} - 19)\Z$. A field is necessary to define an elliptic curve. The number $p$ is convenient because it is under $2^{256}$ but not too much under, and very close to a power of two. Thus:
Every set of integers that are congruent modulo $p$ has a representative that can be written in 256 bits = 32 bytes (= 64 hex digits, as you have noticed). In fact, it takes only 255 bits, which leaves one extra bit that turns out to be handy for encoding curve points.
To reduce an integer $u \geq p$ to an integer $\overline{u} < p$ congruent to $u$ modulo $p$, you can exploit the fact that $2^{255} \equiv 19 \pmod p$, so if $u = 2^{255} u_\mathrm{hi} + u_\mathrm{lo}$ for $u_\mathrm{lo} < 2^{255}$, then $u \equiv 19 u_\mathrm{hi} + u_\mathrm{lo} \pmod p$.
In other words, you can shift $u$ right by 255 bits, multiply it by 19, and add it to the low 255 bits of $u$; then the result differ will from the input by a multiple of $p$—with no need to compute general integer division, which makes crypto engineers happy because fast integer division that doesn't leak the values of the inputs to an adversary with a stopwatch is hard to do.
There are two main equivalent ways to view Curve25519.
One view of Curve25519 is that it is the set of all roots of the polynomial $$y^2 - x^3 - 486662 x^2 - x$$ over $\F_p$, each point written as affine coordinates $(x, y)$, together with an additional point written $\mathcal{O}$ called the point at infinity that does not have a representation in affine coordinates.
Another view of Curve25519 is that it is the set of all lines of roots of the polynomial $$Y^2 Z - X^3 - 486662 X^2 Z - X Z^2$$ over $\F_p$, each line written as homogeneous coordinates $(X : Y : Z)$ for $X, Y, Z$ not all zero, where $(X : Y : Z)$ represents the same line as $(\lambda X : \lambda Y : \lambda Z)$ for any nonzero $\lambda$. The point at infinity has homogeneous coordinates $(0 : 1 : 0)$, and thus need not be treated separately as it is in affine coordinates. Any other point with affine coordinates $(x, y)$ can be written with homogeneous coordinates $(x : y : 1)$, and any line with homogeneous coordinates $(X : Y : Z)$ for nonzero $Z$ can be written with affine coordinates $(X/Z, Y/Z)$.
The elements of Curve25519 form a group under a somewhat elaborate definition of addition (summarized on Wikipedia, and derived from a long rich history of mathematical theory contributing to the proof Fermat's last theorem, to fast algorithms for factoring large integers, and to dreams of a grand unifying theory of mathematics) defining a point $P + Q$ given points $P$ and $Q$ on Curve25519, for which the point at infinity is an identity so that $P + \mathcal{O} = \mathcal{O} + P = P$ for every point $P$, and for which there is an inverse $-P$ with $P + -P = P - P = \mathcal{O}$.
From this, we can define the scalar multiplication $[n]P$ of a point $P$ by an integer $n$ as $[n]P = P + \dots + P$, the $n$-fold addition of $P$ to itself, which has the property that $[n]([m]P) = [nm]P = [mn]P = [m]([n]P)$ for any other integer $m$, where $nm = mn$ is the product of two integers.
For any given $x$ coordinate, there are at most two possible points on Curve25519 with that $x$ coordinate, corresponding the two roots of the quadratic polynomial $y^2 - x^3 - 486662 x^2 - x$ in $y$. There may not be any such $y \in \F_p$, if $x^3 + 486662 x^2 + x$ is nonsquare, or a quadratic nonresidue, modulo $p$, but we can augment $\F_p$ with a fabricated element $\sqrt{2}$ and all formal terms $a + b\sqrt{2}$ for $a, b \in \F_p$, giving the extension field $\F_{p^2}$ in which every nonzero element of $\F_p$ has exactly two square roots. (If you augment $\F_p$ with roots for all polynomials, you get $\overline{\F_p}$, the algebraic closure of $\F_p$, and most elliptic curve theory in algebraic geometry is developed over algebraically closed fields such as $\overline{\F_p}$ and $\mathbb{C}$.) The points on Curve25519 with coordinates in $\F_{p^2}$ are called the $\F_{p^2}$-rational points, and for every $x \in \F_p$ there are exactly two $\F_{p^2}$-rational points with that $x$ coordinate.
It turns out that for any $\F_{p^2}$-rational point $P$, if $x(P) \in \F_p$ then $x([n]P) \in \F_p$ too for all integers $n$, if we prescribe the abuse of notation that $x(\mathcal{O}) = 0$. (This is Theorem 2.1 of the Curve25519 paper, with some details omitted.) And this particular form of curve, a Montgomery curve—as opposed to, e.g., a short Weierstrass curve $y^2 = x^3 - a x + b$ for some $a, b \in \F_p$—admits very fast arithmetic to compute $x([n]P)$ given $n$ and $x(P)$ using only $X$ and $Z$ coordinates, in constant time independent of the values of $n$ and $x(P)$ so that someone who can time the computation from start to finish learns nothing about those values.
X25519 is a public-key key agreement scheme made out of elliptic-curve Diffie–Hellman over a group of $\F_p$-rational points of Curve25519. Alice's private key is a secret integer $a$ chosen uniformly at random from $2^{251}$ possibilities. Her public key is the $x$ coordinate in $\F_p$ of a point $A = [a]P$, where $P$ is a point with $x(P) = 9$. If Bob's public key is $x(B)$ for some point $B = [b]P$, their shared secret is $$H(x([a]B)) = H(x([a][b]P)) = H(x([b][a]P)) = H(x([b]A))$$ which as you can see can be computed either by Alice or by Bob from the information known to each of them, where $H$ is some standard hash function mapping $\F_p$ to octet strings.
(For the full details of how to choose $a$ and how to encode secret scalars and public keys as octet strings if you wanted to implement X25519, see the Curve25519 paper or RFC 7748. Note that when it was introduced, the name ‘Curve25519’ meant just the DH function. The names have since been changed so that ‘Curve25519’ now means the curve, and ‘X25519’ is the DH function. A birationally equivalent curve in twisted Edwards form, sometimes called Ed25519 or loosely just Curve25519 in twisted Edwards form, is used for signatures now too.)
The computational elliptic-curve Diffie–Hellman problem is to find $x([ab]P)$ given elements $x([a]P)$, $x([b]P)$, and $x(P)$ of $\F_p$. The best known ways to do this are all by way of the elliptic-curve discrete log problem, which is to find, given two elements $x(P)$ and $x(A)$ of $\F_p$, an integer $a$ such that $A = [a]P$—that is, to find the secret scalar of a scalar multiplication.
The best generic ways to do this, knowing only how to compute the group operation, are Pollard's rho and kangaroo algorithms, which cost about $2^{125}$ group operations—likely more than anyone will ever compute. If the base point $P$ had composite order—that is, if the smallest integer $n$ such that $[n]P = \mathcal{O}$ were composite—then the Pohlig–Hellman algorithm could compute $a$ faster by computing it modulo each factor of the order of $P$ independently. But $P$ has prime order $p_1 = 2^{252} + 27742317777372353535851937790883648493$, so Pohlig–Hellman doesn't help, just like it doesn't help much in finite-field Diffie–Hellman over a safe prime of the form $2q + 1$ for prime $q$ or if the FFDH generator has prime order.
In the Lim–Lee attack (adapted to elliptic curve groups), if the attacker sends Alice the $x$ coordinate of a point $Q$ that is not a scalar multiple of $P$—possibly not even an $\F_p$-rational point but only an $\F_{p^2}$-rational point—and has small order $k$, then since $[a]Q = [a \bmod k]Q$, by checking which of $k$ possible derived shared secrets Alice uses, the attacker learns a little about $a$, namely $a \bmod k$. But the only possible small orders of elements of points with $x$ coordinates in $\F_p$ divide 8, and Alice always chooses $a$ so that $a \bmod 8 = 0$—that is what (part of) the bit-twiddling at the beginning is about.
The number 8 is the cofactor of Curve25519, because the group of $\F_p$-rational points has order $8p_1$. The group of $\F_{p^2}$-rational points with $x$ coordinates in $\F_p$ and $y$ coordinates not in $\F_p$ but in $\sqrt{2}\F_p$, called the twist of the curve, has order $4p_2$ for a large prime $p_2 = 2^{253} - 5548463555474470707170387558176729699$. No legitimate public keys are on the twist, but the attacker can feed in what look like public keys that are. This is the subject of twist security, and is the reason why $\F_p$ was not the only actor in the story of fields above.
There is more to the elliptic curve security story. Further reading:
- Everything else at SafeCurves.
- A gentle introduction to the basics of algebraic geometry and computing with it:
David Cox, John Little, and Donal O'Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3rd ed., Springer UTM, 2000. ISBN: 978-0-387-35650-1.
- Throw yourself into the deep end of algebraic geometry with:
Robin Hartshorne, Algebraic Geometry, Springer GTM, 1977. ISBN: 0-387-90244-9.
- For the specific topic of computing with elliptic curves:
Joseph H. Silverman, The Arithmetic of Elliptic Curves, 2nd ed., Springer GTM, 2009. ISBN: 978-0-387-09493-9.
- For a comprehensive survey of everything you ever need to know about elliptic curve cryptography up to 2006:
Roberto M. Avanzi, Henri Cohen, Christophe Doche, Gerhard Frey, Tanja Lange, Kim Nguyen, and Frederik Vercauteren, Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman & Hall/CRC, 2006. ISBN: 978-1-58488-518-4.
