Elliptic Curves & Ed25519

Elliptic-curve cryptography gets the same security as RSA or finite-field Diffie–Hellman from dramatically smaller keys — 256 bits versus 3072 — because the best known attack on the elliptic-curve discrete log is generic square-root ($\sqrt{n}$, i.e. Pollard rho) rather than the sub-exponential index calculus that erodes RSA and finite-field DH. Smaller keys mean less bandwidth, less computation, and less battery, which is why every modern protocol defaults to curves.

The curve and its group law #

Over a prime field $GF(p)$ with $p > 3$, a short Weierstrass curve is the set of points satisfying

$$y^2 \equiv x^3 + ax + b \pmod p, \qquad 4a^3 + 27b^2 \not\equiv 0 \pmod p$$

plus a point at infinity $\mathcal{O}$ that acts as the identity. The non-vanishing discriminant condition rules out singular curves (cusps and self-intersections), where the group structure would collapse.

The points form an abelian group under a geometric "chord and tangent" addition, expressed algebraically as:

• $\mathcal{O}$ is the identity; $(x, y) + (x, -y) = \mathcal{O}$ (points are inverses when they share $x$)
• Addition, for $x_1 \neq x_2$, with $\lambda = \dfrac{y_2 - y_1}{x_2 - x_1}$:

$$x_3 = \lambda^2 - x_1 - x_2, \qquad y_3 = \lambda(x_1 - x_3) - y_1$$

• Doubling, for $y_1 \neq 0$, with $\lambda = \dfrac{3x_1^2 + a}{2y_1}$:

$$x_3 = \lambda^2 - 2x_1, \qquad y_3 = \lambda(x_1 - x_3) - y_1$$

All arithmetic is mod $p$, and the divisions are modular inverses — so each addition costs an inversion, which is why implementations work in projective coordinates to defer them.

Hasse's theorem bounds the group order $\lvert E(\mathbb F_p)\rvert$ near $p$:

$$p + 1 - 2\sqrt{p} \le \lvert E(\mathbb F_p)\rvert \le p + 1 + 2\sqrt{p}$$

Scalar multiplication $nP = P + P + \dots + P$ is computed by double-and-add in $O(\log n)$ steps. The one-way function is the ECDLP: given $P$ and $nP$, find $n$. All known algorithms are exponential — $O(\sqrt{n})$ — which is the entire source of ECC's key-size advantage.

Why the ecosystem left Weierstrass curves behind #

The group law above has a defect visible in its own statement: it is a case analysis. Adding a point to itself, adding inverses, and handling $\mathcal{O}$ are separate branches. Branches on secret data are timing side channels, and forgetting a branch is a correctness bug.

Curve25519 (Bernstein, 2006) is a Montgomery curve $y^2 = x^3 + 486662x^2 + x$ over $p = 2^{255} - 19$, with a birationally equivalent Edwards form (edwards25519) used for signatures. Its design targets the failure modes rather than the raw math:

Two primitives are what you actually use, and they are distinct:

• X25519 — Diffie–Hellman key agreement (RFC 7748). The default in TLS 1.3, SSH, Signal, WireGuard.
• Ed25519 — signatures (RFC 8032). Deterministic nonce derived from the key and message, removing the nonce footgun by construction.

Domain parameters are part of the algorithm #

A short Weierstrass deployment is not identified by “256-bit ECC.” It needs the field, coefficients, base point, base-point order, and cofactor:

$$T=(p,a,b,G,n,h).$$

SEC 2 v1.0 records this sextuple for curves including secp256k1 and secp256r1 and correctly relates a roughly 256-bit prime-order curve to about 128 bits of classical security. Its smaller curves and SHA-1-era status tables are historical, not present recommendations. NIST SP 800-186 (2023) is the current NIST domain-parameter publication and includes approved Weierstrass and Edwards curves.

secp256k1 and secp256r1 are different groups despite equal field size. Bitcoin and Ethereum consensus rules use secp256k1; much of TLS and WebPKI uses P-256/secp256r1. Keys, compressed points, and signatures cannot be moved between them merely because both are “256-bit.”

Source claims audit #

Seeded from a university lab manual (elliptic-curve lab). Status of its load-bearing claims: