Summarize the mathematical problem at the heart of breaking a Curve25519 public key

It's pretty easy to generate a Curve25519 private key: generate 32 random bytes of data and then do:

e &= 248
e &= 127
e |= 64

You can then generate a public key by doing fancy math on the private key. For example, here's a random keypair I just generated:

secret: e3c0e8b20ba7894882ddb37522dbe90867befcf9f31a5ce29c0d7997e0bd856d

The whole safety of public key encryption is that it is hard to take a public key and reverse the operation. Elliptic curve cryptography, as I understand it, relies on the fact that a discrete logarithm is hard to find. In particular, for a given large b and g, it is hard to find an integer k such that

$b^k = g$

How does that equation relate to Curve25519? Specifically, if I had a public key like the one above, how would I express, in math terms, the problem I need to solve to find the private key? How does it relate to the equation I see from time to time - $y^2 = x^3+486662x^2+x$, and the number $2^{255} - 19$?

I am guessing it is not as simple as "the private key is k and the public key is b and/or g" in the equation above. I'm also a little confused because the keys would appear to have roughly the same number of digits, which would seem to imply that there aren't many feasible values for k?

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:

1. 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.

2. 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} + 2774231777737235353585193779088364849$, 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.
• Minor errors: 1) the order of the twist is $4p_2$ not $8p_2$. 2)the twist is not "The group of $\mathbb{F}_{p^2}$-rational points with $x$ coordinates in $\mathbb{F}_{p}$" as this definition also includes points of curve25519. – Ruggero Jul 26 '17 at 9:13
• Ruggero: Thanks, fixed. @fgrieu: Not necessary to say X25519 doesn't distinguish $(x, y)$ from $(x, -y)$ because I think I made it quite clear that X25519 works exclusively in the $x$ coordinates of points, though I did sometimes loosely call a point rather than its $x$ coordinate a public key. I didn't go into detail of encoding because this is the mathematical background on what hard problem X25519 relies on, not how to implement it. I started with ‘all roots of the polynomial’ because that's what intro algebraic geometry texts do, and one must be careful with what $x^{-1}(x_0)$ can be. – Squeamish Ossifrage Jul 26 '17 at 14:13
• One should also consider extension fields because sometimes one uses them intentionally, e.g. in Snowshoe or FourQ, which are both defined on the group of $\mathbb{F}_{q^2}$-rational points of a twisted Edwards curve, for $q = 2^{127} - 1$. – Squeamish Ossifrage Jul 26 '17 at 15:33
• @fgrieu: I added some more emphasis on the significance of specific finite extension fields, and relegated the mention of algebraic closure to a parenthesis. Does it look better? – Squeamish Ossifrage Jul 26 '17 at 18:43
• Impressive answer! – CurveEnthusiast Jul 27 '17 at 2:18

It's not $b^k = g$ because $b$ and $g$ are not integers but elliptic curve points.

So keeping your notation what you are doing is $[k]B = G$ where you take point addition on Curve25519 and then add $B$ to itself $k$ times. On Curve25519 the points are also represented with only their $x$ coordinate. Your public key will therefore be the x-Coordinate of the Curve25519 point $G$.

• It is also $b^k = g$, this is simply notation. – CurveEnthusiast Jul 25 '17 at 22:47
• That's true but the notation I used is more common and I didn't want to confuse the OP who doesn't seem to be familiar with the topic. – Elias Jul 25 '17 at 22:49
• So k is the private key. What's B in this case? – Kevin Burke Jul 26 '17 at 2:53
• @KevinBurke: B is the curve generator; in the Curve25519 case, the point with x=9 – poncho Jul 26 '17 at 3:30
• @KevinBurke Yes, what poncho said, so $B$ is the same for everybody. – Elias Jul 26 '17 at 7:22