15. Elliptic Curves¶

Diffie-Hellman, DSA and Schnorr need numbers of 2048 bits or more, because the integers mod $p$ have structure that the number field sieve exploits. This chapter builds a different group, the points on an elliptic curve, where no such shortcut is known, so 256-bit keys are enough. You will add points on a curve by drawing lines, then do the same arithmetic mod a prime by hand, and see how ECDH, ECDSA and EdDSA reuse everything from the last three chapters. Then the practical part: which curve to pick, why X25519 and Ed25519 became the defaults, and how a curve-based random generator became the best-known backdoor in cryptography.

In this chapter

You will learn:

what an elliptic curve is, and how the chord-and-tangent rule turns its points into a group
how to add and double points over the rationals and over $\mathbb{F}_p$, by hand
why the elliptic-curve discrete log needs about $\sqrt n$ steps, and what that means for key sizes
how ECDH, ECDSA and EdDSA (Ed25519) work, and how they fail
how P-256, Curve25519 and secp256k1 differ, and what twist security, cofactors and complete formulas are
how Dual_EC_DRBG could hide a backdoor in two points

You need: Chapter 12 (groups, Diffie-Hellman, discrete logs) and Chapter 14 (DSA, Schnorr, the nonce problem). Fields mod $p$ come from Chapter 3.

Levels: 15.1 to 15.3 are for beginners; 15.4 to 15.9 are intermediate; 15.10 and 15.12 are for experts.

15.1 The problem: keys that are too big¶

By the early 1980s the price of Diffie-Hellman and DSA was clear. The best attack on discrete logs mod $p$, a sieve that uses the fact that integers factor into primes, is far faster than the generic $\sqrt N$ attacks of Chapter 12. To stay ahead of it, $p$ must have thousands of bits, and every key exchange, signature and certificate carries those big numbers around. For a smart card of the time, a 1024-bit exponentiation was a serious job.

What was needed was a group in which:

the group operation is cheap to compute,
elements can be written down compactly, and
there is no structure like "factoring into small primes" for a sieve to grab, so that the generic $\sqrt N$ attack is the best there is.

In 1985 Neal Koblitz at the University of Washington and Victor Miller at IBM proposed, independently, the group of points on an elliptic curve over a finite field. Hendrik Lenstra had just shown, that same year, that elliptic curves could factor numbers (his elliptic curve method), which had brought the curves to cryptographers' attention.

The curves themselves are old. Diophantus of Alexandria, around AD 250, found rational points on curves of this shape by a trick that amounts to drawing a line through known points, and in 1621 Claude-Gaspard Bachet found the formula that doubles a rational point on $y^2 = x^3 + c$ by its tangent. Arab mathematicians of the 10th century asked which whole numbers are the area of a right triangle with rational sides, the "congruent number problem", which turns out to be a question about the curves $y^2 = x^3 - n^2 x$. Henri Poincaré in 1901 studied the whole set of rational points under the chord-and-tangent operation; Louis Mordell proved in 1922 that the rational points of such a curve are generated by finitely many of them; and in 1995 Andrew Wiles's proof of Fermat's Last Theorem went through elliptic curves. Cryptographers borrowed a very well understood object.

Koblitz, a number theorist who had worked on these curves for years, and Miller, a researcher at IBM's Thomas J. Watson lab, saw the same thing within months of each other: the curves gave a group with all the properties Diffie-Hellman needed, and none of the structure the sieves fed on. Many cryptographers at first distrusted an idea that rested on such abstract mathematics, and it took about twenty years for the distrust to turn into the default.

Life story: elliptic-curve cryptography

Born: 1985, Neal Koblitz (University of Washington) and Victor Miller (IBM), independently · Purpose: a discrete-log group with no sieve attack, so keys can be small · Helped: smart cards, mobile devices, Bitcoin, and today almost every TLS, SSH and messaging handshake · Status: current; deprecated by NIST after 2030 and disallowed after 2035 because Shor's algorithm breaks it · Replaced by: ML-KEM and ML-DSA, through hybrids with X25519

Adoption was slow. The mathematics was unfamiliar, there were patent worries (the Canadian company Certicom held many), and RSA was entrenched. NSA's "Suite B" (2005) endorsed curves, Daniel J. Bernstein's Curve25519 (2006) and Ed25519 (2011) made them fast and hard to misuse, and today an elliptic-curve key exchange protects nearly every HTTPS connection.

Figure 15.1. Elliptic curves at a glance: two thousand years of mathematics, then forty years of cryptography.

15.2 Curves over the real numbers¶

An elliptic curve (for our purposes) is the set of points $(x, y)$ satisfying

\[ y^2 = x^3 + a x + b , \]

the short Weierstrass form, with the condition $4a^3 + 27b^2 \ne 0$, which rules out curves with a cusp or a self-crossing. (The name comes from elliptic integrals, which measure arc length on ellipses; the curves are not ellipses.) The curve is symmetric about the $x$-axis, since $(x, -y)$ is on it whenever $(x, y)$ is.

Take $y^2 = x^3 + 17$. Some of its points with whole-number coordinates are $(-2, 3)$, $(-1, 4)$, $(2, 5)$ and $(4, 9)$ (and their mirror images).

The chord-and-tangent rule¶

Here is the idea that makes points into a group. A straight line meets a cubic curve in at most three points. So:

To add $P$ and $Q$: draw the line through them. It meets the curve at one more point $R$. Reflect $R$ in the $x$-axis. That is $P + Q$.
To double $P$: use the tangent line at $P$ instead.
The zero: add one extra point $O$, the point at infinity, thought of as sitting infinitely far up (and down) every vertical line. A vertical line through $P = (x, y)$ meets the curve again at $(x, -y)$ and then at $O$, so $P + (x, -y) = O$. The inverse of $P$ is its mirror image: $-P = (x, -y)$.

Figure 15.2. Adding points on y² = x³ + 17. The line through P = (−1, 4) and Q = (4, 9) meets the curve again at R = (−2, 3); reflecting R in the x-axis gives P + Q = (−2, −3).

The formulas¶

Turning the picture into algebra: for $P = (x_1, y_1)$ and $Q = (x_2, y_2)$, the line has slope

\[ m = \frac{y_2 - y_1}{x_2 - x_1} \quad (P \ne Q), \qquad m = \frac{3x_1^2 + a}{2y_1} \quad (P = Q,\ \text{the tangent}), \]

and substituting the line into the curve and comparing coefficients of $x^2$ gives the third intersection. After the reflection:

\[ x_3 = m^2 - x_1 - x_2, \qquad y_3 = m(x_1 - x_3) - y_1 . \]

By hand, the picture's sum: $P = (-1, 4)$ plus $Q = (4, 9)$ on $y^2 = x^3 + 17$ ($a = 0$):

\[ m = \frac{9 - 4}{4 - (-1)} = 1, \qquad x_3 = 1^2 - (-1) - 4 = -2, \qquad y_3 = 1 \cdot (-1 - (-2)) - 4 = -3 . \]

So $P + Q = (-2, -3)$. Check: $(-2)^3 + 17 = 9 = (-3)^2$. Whole-number answers are luck. Adding $(-1, 4)$ and $(2, 5)$ instead gives slope $\tfrac13$, $x_3 = \tfrac19 + 1 - 2 = -\tfrac89$ and $y_3 = \tfrac13(-1 + \tfrac89) - 4 = -\tfrac{109}{27}$; check: $(-8/9)^3 + 17 = 11881/729 = (109/27)^2$. In Python, with exact fractions:

from fractions import Fraction as F

def add_q(P, Q, a=0):                    # chord and tangent over the rationals
    (x1, y1), (x2, y2) = P, Q
    m = (y2 - y1) / (x2 - x1) if P != Q else (3 * x1 * x1 + a) / (2 * y1)
    x3 = m * m - x1 - x2
    return x3, m * (x1 - x3) - y1

P, Q = (F(-1), F(4)), (F(2), F(5))      # two points on y^2 = x^3 + 17
print(*add_q(P, Q))                      # -8/9 -109/27
Q2 = add_q(Q, Q)
print(*Q2)                               # -64/25 59/125
print(*add_q(Q2, Q))                     # 5023/3249 -842480/185193

Figure 15.3. Doubling uses the tangent line. At Q = (2, 5) the tangent has slope 6/5 and meets the curve once more at x = −64/25; the reflection is 2Q, the first of the growing fractions in the code above.

Notice how fast the fractions grow: $Q$, $2Q$, $3Q$ have denominators 1, 125 and 185,193. Over the rationals, $kQ$ needs about $k^2$ times as many digits as $Q$, which makes the rationals useless for cryptography. The fix is the same as always: do the arithmetic mod a prime.

The group laws. Closure, identity and inverses are clear from the picture, and $P + Q = Q + P$ because the line through $P$ and $Q$ is the line through $Q$ and $P$. Associativity, $(P + Q) + R = P + (Q + R)$, is true but not obvious; it can be checked from the formulas by a long computation, or proved from deeper geometry (it follows from the Cayley-Bacharach theorem on cubics). So the points form an abelian group, and everything from Chapter 12 applies.

15.3 Curves over a finite field¶

Take the same formulas and do every operation mod a prime $p$, with division meaning multiplication by an inverse. The "curve" is now a finite set of points, scattered with no visible shape, but the group laws still hold, because they are algebraic identities.

Our running example: $y^2 = x^3 + 2x + 2$ over $\mathbb{F}_{17}$. Trying all $17 \times 17$ pairs finds 18 points, and with $O$ the group has 19 elements. Since 19 is prime, every point except $O$ generates the whole group (Lagrange). Take $G = (5, 1)$.

Is $G$ on the curve? $1^2 = 1$ and $5^3 + 2 \cdot 5 + 2 = 137 = 8 \cdot 17 + 1$. Yes.

$2G$, by the tangent rule.

Step	Calculation	Value
slope	$m = (3 \cdot 5^2 + 2) / (2 \cdot 1) = 77 \cdot 2^{-1}$; $77 \equiv 9$ and $2^{-1} \equiv 9$ (as $2 \cdot 9 = 18 \equiv 1$)	$m = 81 \bmod 17 = 13$
$x_3$	$13^2 - 5 - 5 = 159$	$159 \bmod 17 = 6$
$y_3$	$13 \cdot (5 - 6) - 1 = -14$	$-14 \bmod 17 = 3$

So $2G = (6, 3)$.

Figure 15.4. The whole curve over F₁₇: 18 scattered points (plus O). Mirror pairs (x, y) and (x, 17 − y) sit symmetrically about y = 8.5, which is all that remains of the picture over the reals.

$3G = 2G + G$, by the chord rule. Slope $m = (3 - 1)/(6 - 5) = 2$, then $x_3 = 4 - 6 - 5 = -7 \equiv 10$ and $y_3 = 2 \cdot (6 - 10) - 3 = -11 \equiv 6$. So $3G = (10, 6)$.

$1G = (5, 1)$. A private key is a number $d$; the public key is the point $dG$.
$2G = (6, 3)$, by the tangent at $G$. $3G = (10, 6)$, by the line through $G$ and $2G$.
$4G = (3, 1)$, $5G = (9, 16)$, $6G = (16, 13)$, $7G = (0, 6)$. The points jump around with no visible pattern.
$13G = (16, 4)$. Double-and-add gets there from 13 = 1101 in binary: $G, 3G, 6G, 12G, 13G$.
$18G = (5, 16) = -G$, the mirror image of $G$.
$19G = O$, the point at infinity. Going back from a point to its $d$ is the hard part.

Figure 15.5. The group of the toy curve as one cycle. Walking forward is easy; given a point, finding how many steps it took is the discrete log.

Scalar multiplication $dG$ uses double-and-add, the elliptic-curve version of square-and-multiply: walk through the bits of $d$, double at each bit, add $G$ when the bit is 1. A 256-bit $d$ takes about 256 doublings and 128 additions.

Figure 15.6. Double-and-add on the toy curve for d = 13: three doublings and two additions instead of twelve additions. At 256 bits it is about 256 doublings and 128 additions.

def add(P, Q):
    # None is the point at infinity, the group's zero
    if P is None: return Q
    if Q is None: return P
    (x1, y1), (x2, y2) = P, Q
    if x1 == x2 and (y1 + y2) % p == 0: return None    # P + (-P)
    if P == Q: m = (3 * x1 * x1 + a) * pow(2 * y1, -1, p) % p
    else: m = (y2 - y1) * pow(x2 - x1, -1, p) % p
    x3 = (m * m - x1 - x2) % p
    return x3, (m * (x1 - x3) - y1) % p

def mul(k, P):
    # double-and-add, one bit of k at a time
    R = None
    while k:
        if k & 1: R = add(R, P)
        P = add(P, P)
        k >>= 1
    return R

p, a, b = 17, 2, 2                       # y^2 = x^3 + 2x + 2 over F_17
points = [(x, y) for x in range(p) for y in range(p) if (y * y - x**3 - a * x - b) % p == 0]
print(len(points) + 1)                   # 19, counting the point at infinity
G = (5, 1)
print([mul(k, G) for k in range(1, 8)])
print(mul(18, G), mul(19, G))            # (5, 16) None: 18G = -G, 19G = O

Output:

19
[(5, 1), (6, 3), (10, 6), (3, 1), (9, 16), (16, 13), (0, 6)]
(5, 16) None

How many points? Helmut Hasse proved in 1933 that a curve over $\mathbb{F}_p$ has $p + 1 - t$ points with $\lvert t \rvert \le 2\sqrt p$. For $p = 17$ that allows 10 to 26; ours has 19. For a 256-bit $p$, the count is also about 256 bits. Counting points exactly takes René Schoof's algorithm (1985) and its successors; that is how designers find curves whose point count is a prime, or a prime times a small cofactor such as 4 or 8.

The code blocks in §15.4 and §15.6 reuse these add and mul functions with other curve constants.

15.4 The elliptic-curve discrete logarithm¶

Level: intermediate. Given $G$ and $Q = dG$, find $d$. This is the elliptic-curve discrete logarithm problem (ECDLP). In our toy group of 19 points it is trivial. In a group of about $2^{256}$ points:

Generic attacks work as in Chapter 12: baby-step giant-step and Pollard's rho need about $\sqrt n$ steps for a group of prime order $n$. For $n \approx 2^{256}$ that is $2^{128}$, and Pollard's rho spreads across many machines but gains nothing else.
No sieve is known. The number field sieve works mod $p$ because integers have a notion of "small" and factor into small primes. Points on a curve have no useful analogue: lifting them to curves over the rationals, as Victor Miller already argued in 1985, runs into the explosion of sizes shown in §15.2. For well-chosen curves over prime fields, nothing better than $\sqrt n$ is known, after forty years of trying.

So a curve of 256 bits gives about 128-bit security, where finite-field groups and RSA need 3072 bits:

Security (bits)	Symmetric	Elliptic curve	RSA or finite-field DH
80	(2TDEA)	160	1024
112	3TDEA	224	2048
128	AES-128	256	3072
192	AES-192	384	7680
256	AES-256	512	15360

Figure 15.7. The table above as bars. Curve keys grow in step with the security level; RSA and finite-field keys grow much faster because of the number field sieve.

(Equivalences from NIST SP 800-57 Part 1.) Published ECDLP records are around 112 to 117 bits: a 112-bit curve was solved in 2009 on over 200 PlayStation 3 consoles. A 256-bit curve is about $2^{70}$ times harder than that.

Special curves can be weak. Some families have structure that does help:

Anomalous curves, with exactly $p$ points, fall in polynomial time (Semaev, Satoh and Araki, Smart, 1997 to 1999).
Curves with a small embedding degree: a pairing maps the ECDLP into a finite field $\mathbb{F}_{p^k}$, where the sieve works (Menezes, Okamoto and Vanstone, 1993: the MOV attack). For random curves $k$ is huge; for supersingular curves it can be 2.
Group order with only small factors: Pohlig-Hellman, exactly as in Chapter 12.

Standards choose curves that avoid all three.

15.5 ECDH¶

Level: intermediate. Diffie-Hellman carries over word for word, with $g^a$ replaced by $aG$:

\[ \text{Alice sends } A = d_A G, \quad \text{Bob sends } B = d_B G, \quad \text{both compute } d_A B = d_B A = d_A d_B \, G . \]

By hand on the toy curve with $G = (5, 1)$: Alice picks $d_A = 3$ and sends $A = 3G = (10, 6)$; Bob picks $d_B = 7$ and sends $B = 7G = (0, 6)$. Alice computes $3B$ and Bob $7A$; both get $21G = 2G = (6, 3)$, since $21 \bmod 19 = 2$.

Figure 15.8. ECDH by hand: the same exchange as Chapter 12 with points instead of powers.

X25519¶

In practice the dominant ECDH is X25519, Bernstein's function on Curve25519 (2006, specified in RFC 7748 in 2016). The curve is

\[ y^2 = x^3 + 486662 x^2 + x \quad \text{over } \mathbb{F}_p, \quad p = 2^{255} - 19, \]

a Montgomery curve (Peter Montgomery, 1987). Its design choices are all about making correct, constant-time code easy:

Only $x$ is used. The Montgomery ladder computes the $x$-coordinate of $dP$ from the $x$-coordinate of $P$ alone, doing the same steps for every bit of $d$. Public keys and shared secrets are 32 bytes.
Every 32-byte string is accepted as a public key. A value that is not the $x$ of a point on the curve is the $x$ of a point on its twist, a related curve, and Curve25519 was chosen so that the twist is also secure. There is no validation step to forget.
Clamping. The secret scalar has its three low bits cleared (a multiple of the cofactor 8, which kills small-subgroup components) and bit 254 set (so every key takes the same number of ladder steps).
Fast arithmetic. $2^{255} - 19$ is close to a power of 2, so reduction is cheap.

def ladder(k, u, p, a24, bits):
    # Montgomery ladder, RFC 7748 section 5: works on u (= x) alone
    x2, z2, x3, z3, swap = 1, 0, u, 1, 0
    for t in reversed(range(bits)):
        b = k >> t & 1
        if swap ^ b: x2, x3, z2, z3 = x3, x2, z3, z2
        swap = b
        A, B, C, D = x2 + z2, x2 - z2, x3 + z3, x3 - z3
        AA, BB, DA, CB = A * A, B * B, D * A, C * B
        E = AA - BB
        x3, z3 = (DA + CB) ** 2 % p, u * (DA - CB) ** 2 % p
        x2, z2 = AA * BB % p, E * (AA + a24 * E) % p
    if swap: x2, z2 = x3, z3
    return x2 * pow(z2, p - 2, p) % p

def x25519(k, u):
    k = int.from_bytes(k, "little") & (1 << 254) - 8 | 1 << 254    # clamp
    u = int.from_bytes(u, "little") & (1 << 255) - 1
    return ladder(k, u, 2**255 - 19, 121665, 255).to_bytes(32, "little")

h = bytes.fromhex                                      # RFC 7748 section 6.1
a = h("77076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c2a")
b = h("5dab087e624a8a4b79e17f8b83800ee66f3bb1292618b6fd1c2f8b27ff88e0eb")
A, B = x25519(a, b"\x09" + bytes(31)), x25519(b, b"\x09" + bytes(31))
print(A.hex()[:16], B.hex()[:16])                      # 8520f0098930a754 de9edb7d7b7dc1b4
print(x25519(a, B) == x25519(b, A), x25519(a, B).hex()[:16])   # True 4a5d9d5ba4ce2de1
print(x25519(a, bytes(32)) == bytes(32))               # True: a low-order point gives all zeros

The outputs match the test vectors of RFC 7748. The last line is a warning: a peer who sends one of the few points of small order forces the result to all zeros whatever your key. That does not leak your key, but a protocol that needs both sides to contribute should reject an all-zero result, as TLS 1.3 does. And as with all Diffie-Hellman, the raw result goes through a KDF before use.

The invalid-curve attack on Weierstrass curves¶

ECDH on the NIST curves needs a check X25519 does not: that a received point really is on the curve. Look at the addition formulas in §15.2: they use $a$ but never $b$. So if an attacker sends a point $(x, y)$ that is not on P-256, the victim's code happily computes on the curve $y^2 = x^3 + ax + b'$ that the point is on, and the attacker can choose $b'$ so that this curve has a subgroup of small order. The result leaks the victim's key mod that small order, exactly as in the small-subgroup attack of Chapter 12; a few dozen such points and the Chinese remainder theorem give the whole key (Biehl, Meyer and Müller, 2000). In 2015 Tibor Jager, Jörg Schwenk and Juraj Somorovsky pulled TLS server keys out of two popular Java libraries this way, and in 2018 Eli Biham and Lior Neumann found that Bluetooth pairing checked only $x$-coordinates (CVE-2018-5383). Validate every point: on the curve, not $O$, coordinates in range.

Life story: the invalid-curve attack

Born: 2000, Ingrid Biehl, Bernd Meyer and Volker Müller · Purpose: an attack on ECDH code that does not check received points lie on the curve · Impact: pulled TLS keys from Java libraries (2015) and broke Bluetooth pairing (2018); made point validation mandatory · Status: defeated by validation, or by x-only designs like X25519

15.6 ECDSA¶

Level: intermediate. Scott Vanstone of the University of Waterloo, a co-founder of Certicom, proposed ECDSA in 1992 in response to NIST's call for comments on DSA. It became ANSI X9.62 (1999) and part of FIPS 186-2 (2000). It is DSA from Chapter 14 with $g^k \bmod p$ replaced by the $x$-coordinate of $kG$:

\[ \begin{aligned} \textbf{Keys:} \quad & d \in [1, n-1], \quad Q = dG \\ \textbf{Sign:} \quad & \text{fresh } k, \quad r = (kG)_x \bmod n, \quad s = k^{-1}(H(m) + r d) \bmod n \\ \textbf{Verify:} \quad & w = s^{-1}, \quad X = (H(m) w) \, G + (r w) \, Q, \quad \text{accept if } X_x \bmod n = r \end{aligned} \]

Why it works: $(H w) G + (r w) d G = s^{-1}(H + r d) G = k G$.

By hand on the toy curve ($G = (5, 1)$, $n = 19$), with private key $d = 7$:

Step	Calculation	Value
Public key	$Q = 7G$	$(0, 6)$
Hash (made up)	$H(m)$	10
Nonce	$k = 3$, $kG = (10, 6)$
$r$	$x$-coordinate of $kG$, mod 19	$r = 10$
$s$	$3^{-1} \cdot (10 + 10 \cdot 7) \bmod 19 = 13 \cdot 80 \bmod 19$	$s = 14$
Verify: $w$	$14^{-1} \bmod 19$	$w = 15$
$u_1 = H w$, $u_2 = r w$	$150 \bmod 19$, $150 \bmod 19$	$u_1 = u_2 = 17$
$X = 17G + 17Q$	$(6, 14) + (9, 16)$	$(10, 6)$
Check	$10 \bmod 19 = r$	valid

At full size on secp256k1, Bitcoin's curve ($y^2 = x^3 + 7$), reusing add and mul from §15.3:

import hashlib, secrets

# secp256k1 (SEC 2): y^2 = x^3 + 7 over F_p, base point G of prime order n
p, a = 2**256 - 2**32 - 977, 0
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
     0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)

def Hn(msg):
    return int.from_bytes(hashlib.sha256(msg).digest(), "big") % n

def sign(msg, d, k=None):
    k = k or secrets.randbelow(n - 1) + 1
    r = mul(k, G)[0] % n
    s = pow(k, -1, n) * (Hn(msg) + r * d) % n
    return r, s

def verify(msg, Q, r, s):
    if not (0 < r < n and 0 < s < n): return False
    w = pow(s, -1, n)
    X = add(mul(Hn(msg) * w % n, G), mul(r * w % n, Q))
    return X is not None and X[0] % n == r

d = secrets.randbelow(n - 1) + 1         # private key: a number
Q = mul(d, G)                            # public key: a point
r, s = sign(b"pay 1 BTC to Bob", d)
print(verify(b"pay 1 BTC to Bob", Q, r, s), verify(b"pay 9 BTC to Bob", Q, r, s))
print(verify(b"pay 1 BTC to Bob", Q, r, n - s))   # True: (r, n - s) is valid too

k = secrets.randbelow(n - 1) + 1         # the PS3 mistake: the same k twice
r1, s1 = sign(b"game one", d, k)
r2, s2 = sign(b"game two", d, k)
k_found = (Hn(b"game one") - Hn(b"game two")) * pow(s1 - s2, -1, n) % n
print((s1 * k_found - Hn(b"game one")) * pow(r1, -1, n) % n == d)   # True

Output:

True False
True
True

These functions interoperate with PyCA cryptography's ECDSA on SECP256K1 (signatures decoded to $(r, s)$). They are not constant time; use them to learn.

Three things the output shows:

Malleability. $-kG$ has the same $x$-coordinate as $kG$, so $(r, n - s)$ is a second valid signature on the same message. Bitcoin learned this the hard way (transactions could be altered in flight, changing their IDs), and its relay rules now require the "low-$s$" form.
The nonce, again. Everything in §14.5 applies unchanged: Sony's PS3 key (2010), the Android Bitcoin wallets (2013), and the timing attacks Minerva and TPM-Fail (2019) were all ECDSA.
Verification bugs. In 2020 Windows accepted certificates whose ECDSA key came with attacker-chosen curve parameters, letting an attacker supply their own generator (CurveBall, CVE-2020-0601, reported by the NSA). In 2022 Java 15 to 18 accepted the signature $r = s = 0$ for any message and any key ("psychic signatures", CVE-2022-21449); the range check in verify above is the line that was missing.

Vanstone, a mathematician at Waterloo, had co-founded Certicom in 1985 to turn curves into products, and for years the company was elliptic-curve cryptography's main advocate and patent holder. In 2003 the NSA paid Certicom for a license to some of its patents, which helped clear the way for Suite B.

Life story: ECDSA

Born: 1992, Scott Vanstone (University of Waterloo, Certicom), as a comment on NIST's DSA proposal; ANSI X9.62 (1999) and FIPS 186-2 (2000) · Purpose: DSA's signature on an elliptic curve, far smaller · Helped: most TLS certificates issued today, Bitcoin and Ethereum transactions, passkeys, smart cards · Setbacks: nonce disasters (PS3 2010, Android 2013, Minerva 2019), malleability, CurveBall and psychic signatures · Status: current, with RFC 6979 nonces; EdDSA preferred for new designs

15.7 EdDSA and Ed25519¶

Level: intermediate. Ed25519 (Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe and Bo-Yin Yang, 2011) is a Schnorr signature (Chapter 14) on a twisted Edwards curve:

\[ -x^2 + y^2 = 1 + d x^2 y^2 \quad \text{over } \mathbb{F}_p, \quad p = 2^{255} - 19, \quad d = -121665/121666 . \]

It is the same group as Curve25519, written in different coordinates. Edwards curves (Harold Edwards, 2007; Bernstein and Lange for cryptography) have one addition formula that works for every pair of points, including doubling and the neutral point $(0, 1)$, with no special cases:

\[ x_3 = \frac{x_1 y_2 + y_1 x_2}{1 + d x_1 x_2 y_1 y_2}, \qquad y_3 = \frac{y_1 y_2 + x_1 x_2}{1 - d x_1 x_2 y_1 y_2} . \]

No branches means no timing leaks from branches, and no rare inputs that give wrong answers.

The scheme (RFC 8032, 2017):

A 32-byte seed is hashed with SHA-512. The first half, clamped, is the secret scalar $s$; the public key is $A = sB$. The second half is a secret prefix.
Sign $M$: $r = H(\mathit{prefix} \,\Vert\, M) \bmod \ell$, $R = rB$, $S = (r + H(R \,\Vert\, A \,\Vert\, M) \cdot s) \bmod \ell$. The signature is $(R, S)$, 64 bytes.
Verify: $S B = R + H(R \,\Vert\, A \,\Vert\, M) \cdot A$, and $S < \ell$.

The nonce $r$ is a hash of a secret and the message. It never repeats for different messages, and there is no random generator to fail: the PS3 mistake is impossible by construction. Hashing $A$ into the challenge also means one signature can't be reused under a related key.

Figure 15.9. How Ed25519 signs. The nonce r is derived, never drawn, so the PS3 mistake of Chapter 14 cannot happen; dashed boxes are secret.

from hashlib import sha512

p = 2**255 - 19
L = 2**252 + 27742317777372353535851937790883648493    # the prime group order
d = -121665 * pow(121666, -1, p) % p                   # the curve: -x^2 + y^2 = 1 + d x^2 y^2

def add(P, Q):                    # one formula for every case, extended coordinates (X, Y, Z, T)
    A = (P[1] - P[0]) * (Q[1] - Q[0]) % p
    B = (P[1] + P[0]) * (Q[1] + Q[0]) % p
    C, D = 2 * P[3] * Q[3] * d % p, 2 * P[2] * Q[2] % p
    E, F, G, H = B - A, D - C, D + C, B + A
    return E * F, G * H, F * G, E * H

def mul(s, P):
    Q = (0, 1, 1, 0)                                   # the neutral point (0, 1)
    while s:
        if s & 1: Q = add(Q, P)
        P, s = add(P, P), s >> 1
    return Q

def enc(P):                       # 32 bytes: y, with the low bit of x on top
    zi = pow(P[2], p - 2, p)
    x, y = P[0] * zi % p, P[1] * zi % p
    return (y | (x & 1) << 255).to_bytes(32, "little")

def dec(b):                       # None if b is not a canonical point
    y = int.from_bytes(b, "little")
    sign, y = y >> 255, y & (1 << 255) - 1
    if y >= p: return None
    x2 = (y * y - 1) * pow(d * y * y + 1, -1, p) % p
    x = pow(x2, (p + 3) // 8, p)
    if (x * x - x2) % p: x = x * pow(2, (p - 1) // 4, p) % p
    if (x * x - x2) % p or (x == 0 and sign): return None
    if x & 1 != sign: x = p - x
    return x, y, 1, x * y % p

B = dec((4 * pow(5, -1, p) % p).to_bytes(32, "little"))   # base point: y = 4/5
Hq = lambda b: int.from_bytes(sha512(b).digest(), "little") % L

def sign(seed, m):
    h = sha512(seed).digest()
    s = int.from_bytes(h[:32], "little") & (1 << 254) - 8 | 1 << 254   # clamped secret scalar
    A = enc(mul(s, B))
    r = Hq(h[32:] + m)                                 # the nonce comes from the message
    R = enc(mul(r, B))
    return A, R + ((r + Hq(R + A + m) * s) % L).to_bytes(32, "little")

def verify(A, m, sig):
    Ap, R, S = dec(A), dec(sig[:32]), int.from_bytes(sig[32:], "little")
    if Ap is None or R is None or S >= L: return False
    P, Q = mul(S, B), add(R, mul(Hq(sig[:32] + A + m), Ap))
    return (P[0] * Q[2] - Q[0] * P[2]) % p == 0 and (P[1] * Q[2] - Q[1] * P[2]) % p == 0

seed = bytes.fromhex("9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60")
A, sig = sign(seed, b"")                               # RFC 8032 section 7.1, TEST 1
print(A.hex()[:16], sig.hex()[:16], verify(A, b"", sig))   # d75a980182b10ab7 e5564300c360ac72 True
print(sign(seed, b"")[1] == sig, verify(A, b"x", sig))     # True False: same signature every time

The public key and the full 64-byte signature match TEST 1 of RFC 8032.

Pitfalls that remain. A signing function must use the public key derived from the secret, never one passed in by the caller: in 2022 dozens of libraries were found whose API took the public key as a separate argument, and signing the same message under a wrong public key gives two signatures with the same $r$ and different challenges, which reveals the secret. Deterministic nonces also make fault attacks easier: a glitch during one of two identical signings gives the same situation. Hardware exposed to faults should add randomness to the nonce. And libraries disagree on edge cases (non-canonical encodings, small-order points, the cofactor), which matters when many machines must agree on validity, as in a blockchain; ZIP 215 (2020) is one written-down answer. Details: EdDSA reference.

Life story: Curve25519, X25519 and Ed25519

Born: 2006 (Curve25519, Daniel J. Bernstein) and 2011 (Ed25519, Bernstein, Duif, Lange, Schwabe and Yang) · Purpose: curves and formulas on which the straightforward implementation is also the safe and fast one · Helped: X25519 became TLS 1.3's most used key exchange and is in SSH, Signal, WireGuard; Ed25519 is the default SSH key and in FIPS 186-5 · Status: current; paired with ML-KEM in hybrids

Use a library¶

# pip install cryptography
from cryptography.hazmat.primitives.asymmetric import ec, x25519, ed25519
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes

alice, bob = x25519.X25519PrivateKey.generate(), x25519.X25519PrivateKey.generate()
shared = alice.exchange(bob.public_key())                 # 32 bytes
assert shared == bob.exchange(alice.public_key())
key = HKDF(algorithm=hashes.SHA256(), length=32, salt=None, info=b"demo v1").derive(shared)

signer = ed25519.Ed25519PrivateKey.generate()
sig = signer.sign(b"release 1.2")                         # 64 bytes, deterministic
signer.public_key().verify(sig, b"release 1.2")           # raises InvalidSignature if bad

p256 = ec.generate_private_key(ec.SECP256R1())
sig2 = p256.sign(b"release 1.2", ec.ECDSA(hashes.SHA256()))
p256.public_key().verify(sig2, b"release 1.2", ec.ECDSA(hashes.SHA256()))
print(len(shared), len(key), len(sig), len(sig2) <= 72)   # 32 32 64 True

An ECDSA signature is DER-encoded, usually 70 to 72 bytes for P-256; Ed25519's is always 64.

15.8 Choosing a curve¶

Level: intermediate. Unlike AES, where everyone uses the same cipher, curves come in competing families, and the choice has been political as well as technical.

Curve	Field prime	Shape	Cofactor	Origin	Main uses
P-256 (secp256r1)	$2^{256} - 2^{224} + 2^{192} + 2^{96} - 1$	Weierstrass, $a = -3$	1	NSA, published by NIST 1999, FIPS 186-2 (2000)	TLS certificates, smart cards, FIPS modules, WebAuthn
P-384, P-521	special primes; $2^{521} - 1$ for P-521	Weierstrass	1	same	government "top secret" profiles (P-384)
Curve25519 / Ed25519	$2^{255} - 19$	Montgomery / twisted Edwards	8	Bernstein, 2006; RFC 7748, RFC 8032	TLS 1.3, SSH, Signal, WireGuard, age
Curve448 / Ed448	$2^{448} - 2^{224} - 1$	Montgomery / Edwards	4	Hamburg, 2015	a higher-security option (about 224 bits)
secp256k1	$2^{256} - 2^{32} - 977$	Weierstrass, $y^2 = x^3 + 7$	1	Certicom, SEC 2 (2000)	Bitcoin, Ethereum
Brainpool	from the digits of $\pi$	Weierstrass	1	BSI and secunet, RFC 5639 (2010)	European government profiles

P-256 and the seeds. Each NIST curve's constant $b$ was made by hashing a 160-bit seed with SHA-1. Anyone can check the hashing, but the seeds came with no explanation, so whoever chose them could in principle have tried seed after seed until a curve had a property only they knew how to exploit. No such weakness has been found, and the families of weak curves known (§15.4) are rare enough that finding one by searching seeds is not thought feasible. Still, after 2013 (below) many people wanted curves whose every constant has an explanation. A 2026 report traced the seeds to the output of the C library's lrand48 generator started from timestamps in 1997; the Elliptic curves reference reproduces P-256's seed that way.

Curve25519 and rigidity. Bernstein chose the prime $2^{255} - 19$ for speed and then took the smallest coefficient $A = 486662$ that gives prime-order subgroups with small cofactors on both the curve and its twist. Nothing is left for a designer to tune. With Tanja Lange he built SafeCurves, a list of criteria (twist security, complete formulas, constant-time ladders, explained constants); Curve25519 and Ed448-Goldilocks pass, and the NIST curves, secp256k1 and Brainpool each fail at least one. That doesn't make those curves broken; it makes safe code for them harder to write.

Life story: the NIST curves (P-256 and friends)

Born: 1999, generated at the NSA and published by NIST, in FIPS 186-2 (2000) · Purpose: standard curves for government and industry at several security levels · Helped: smart cards, TLS certificates, FIPS modules, WebAuthn passkeys · Doubts: unexplained seeds and formulas that are hard to implement safely · Status: current, required by many standards

secp256k1 has $a = 0$, which gives it an extra fast endomorphism (the GLV method speeds up scalar multiplication). Satoshi Nakamoto chose it for Bitcoin in 2009; nobody knows exactly why, though its simple constants and the absence of NIST's seeds are often suggested.

Life story: secp256k1

Born: 2000, Certicom's SEC 2 · Purpose: a fast Koblitz-style curve with $a = 0$ · Helped: chosen by Satoshi Nakamoto for Bitcoin in 2009, then by Ethereum, whose keys it now protects · Status: current, with ECDSA and (since 2021) Schnorr signatures

Cofactors. Curve25519's group has $8\ell$ points for a prime $\ell$. Clamping handles the cofactor in X25519, but protocols that need a prime-order group (for example, to prove statements about group elements) have tripped over it. The ristretto255 and decaf448 encodings (RFC 9496) give a clean prime-order group on top of these curves.

In short: use X25519 for key exchange and Ed25519 for signatures unless a standard requires P-256 (FIPS validation, WebAuthn hardware, many certificates), and in that case use a library that validates points and computes in constant time.

Dual_EC_DRBG: a backdoor in one equation¶

The best-known suspected backdoor in modern cryptography was built from elliptic-curve points. In 2006 NIST's SP 800-90 standardized four random-number generators. One, Dual_EC_DRBG, promoted by the NSA, was far slower than the others and used two fixed points $P$ and $Q$ on P-256 with no explanation of where they came from. Its state update and output are:

\[ s_{i+1} = (s_i P)_x, \qquad \text{output } (s_{i+1} Q)_x \text{ with the top 16 bits dropped.} \]

In 2007 Dan Shumow and Niels Ferguson of Microsoft pointed out the problem: if whoever chose the points knows $e$ with $P = eQ$, then from one output they can rebuild the point $s_{i+1} Q$ (trying the $2^{16}$ missing bits), multiply by $e$ to get $s_{i+1} P$, whose $x$-coordinate is the next state, and predict every later output. Here is the idea on secp256k1, without the truncation, reusing the code of §15.6:

Figure 15.10. Dual_EC_DRBG and its trapdoor. Normal operation is the top row; the highlighted path is available only to whoever chose P and Q.

e = secrets.randbelow(n - 1) + 1         # the designer's secret
Qd = G                                   # the public point Q
Pd = mul(e, Qd)                          # the public point P = e*Q, which looks like any other point

state = secrets.randbelow(n)             # the generator's secret state
def dual_ec():                           # Dual_EC_DRBG without the truncation
    global state
    state = mul(state, Pd)[0]            # new state: x(s*P)
    return mul(state, Qd)[0]             # output: x(s*Q)

out1, out2 = dual_ec(), dual_ec()        # the victim's "random" numbers, e.g. a TLS nonce and a key

# The designer sees out1, rebuilds the point s*Q from its x, multiplies by e
y = pow((out1**3 + 7) % p, (p + 1) // 4, p)
s_next = mul(e, (out1, y))[0]            # e*(s*Q) = s*P, whose x is the next state
print(mul(s_next, Qd)[0] == out2)        # True: every later output is predictable

The documents Edward Snowden released in 2013 described an NSA program to insert weaknesses into commercial encryption, and the New York Times reported that they appeared to confirm the Dual_EC backdoor; the NSA has not acknowledged it. NIST withdrew Dual_EC_DRBG in 2014. Reuters reported that RSA Security had made it the default in its BSAFE library under a $10 million contract, and in 2015 Juniper Networks found that intruders had replaced the $Q$ in its firewalls' Dual_EC with their own. The full story is in the History section, and Chapter 4 covers random generators. The lesson for curves: unexplained constants are a liability even when no attack is known.

Life story: Dual_EC_DRBG

Born: promoted by the NSA in the early 2000s; standardized in NIST SP 800-90 (2006) and ANSI X9.82 · Purpose: officially, a random generator with a security argument from elliptic curves · Warning: Shumow and Ferguson showed in 2007 that its two points could hide a backdoor · Retired: NIST told users to stop using it in 2013 and withdrew it in 2014, after the Snowden documents · Legacy: the Juniper incident (2015) and a lasting demand for explained constants

15.9 In the real world¶

Where you meet it. X25519 is the most widely used key exchange on the internet: TLS 1.3, SSH, WireGuard, Signal and age all use it, and it is increasingly paired with ML-KEM in a hybrid. ECDSA with P-256 or P-384 signs a growing share of TLS certificates, and most WebAuthn passkeys sign with ECDSA on P-256. Ed25519 has been OpenSSH's default key type since version 9.5 (2023) and signs Git commits, DNSSEC zones (RFC 8080) and Tor relay identities. Bitcoin and Ethereum use secp256k1, with ECDSA and, since Taproot (2021), Schnorr signatures.

Standards. RFC 7748 (X25519, X448), RFC 8032 (EdDSA), FIPS 186-5 (ECDSA and EdDSA, 2023), SP 800-186 (the approved curves, 2023), SP 800-56A (ECDH), SEC 1 and SEC 2 (Certicom's encodings and curves).

Sizes and status. 256-bit curves give about 128-bit security, 384-bit about 192, Curve448 about 224. All of them fall to Shor's algorithm (Chapter 20), and estimates suggest a 256-bit curve needs a smaller quantum computer than RSA-2048. NIST IR 8547 deprecates elliptic-curve key exchange and signatures after 2030 and disallows them after 2035; the replacements are ML-KEM and ML-DSA (Chapter 21). Hybrids (X25519 with ML-KEM) are the bridge.

Full details: Elliptic curves, ECDH, ECDSA, EdDSA, Schnorr.

15.10 Going deeper¶

Level: expert.

Projective coordinates¶

Every affine addition needs a field inversion, which costs as much as dozens of multiplications. Real code works in projective coordinates $(X : Y : Z)$ with $x = X/Z$, $y = Y/Z$, or Jacobian $(X : Y : Z)$ with $x = X/Z^2$, $y = Y/Z^3$, and inverts once at the end. The Ed25519 code above uses extended coordinates $(X, Y, Z, T)$ with $T = XY/Z$ (Hisil, Wong, Carter and Dawson, 2008), in which an addition costs about 8 multiplications and no inversion.

Why the Montgomery ladder works¶

The ladder keeps a pair $(R_0, R_1)$ with $R_1 - R_0 = P$ at every step: for each bit, it replaces the pair by $(2R_0, R_0 + R_1)$ or $(R_0 + R_1, 2R_1)$. Because the difference $P$ is always known, $x(R_0 + R_1)$ can be computed from $x(R_0)$, $x(R_1)$ and $x(P)$ alone ("differential addition"). Every bit does one doubling and one addition, in the same order, and the swap is done arithmetically in constant-time code, so the sequence of operations does not depend on the key. Peter Montgomery introduced it in 1987 for factoring with elliptic curves.

Figure 15.11. The Montgomery ladder. Each bit costs one addition and one doubling whatever its value, and because R₁ − R₀ = P is known, x-coordinates alone are enough.

Twist security¶

For a given $p$, every $x \in \mathbb{F}_p$ either is the $x$-coordinate of a point on $E$ or of a point on its quadratic twist $E'$, and $\#E + \#E' = 2p + 2$. An $x$-only ladder handed an $x$ from $E'$ computes on $E'$. If $\#E'$ has small factors, an attacker who sends such $x$ values learns the key piece by piece, as in the invalid-curve attack. Curve25519's twist has order $4 \cdot \ell'$ for a large prime $\ell'$; SafeCurves puts the best attack via the twist at about $2^{124}$ for Curve25519, about $2^{120}$ for P-256 and about $2^{110}$ for secp256k1, all safe, but only $2^{58}$ for P-224 and $2^{44.5}$ for brainpoolP256t1. Code that validates points never meets the twist.

Pairings¶

A pairing is a map $e: G_1 \times G_2 \to G_T$ with $e(aP, bQ) = e(P, Q)^{ab}$. On most curves it is useless (its target group is enormous). On specially built "pairing-friendly" curves (Barreto-Naehrig, BLS12-381) it gives powerful tools: BLS signatures (Boneh, Lynn and Shacham, 2001), which are a single point and can be aggregated across many signers (Ethereum's consensus layer uses them), identity-based encryption (Boneh and Franklin, 2001), and many zero-knowledge proof systems (Chapter 23). The price is that the MOV reduction now applies by design, so the field $\mathbb{F}_{p^k}$ must be large enough to resist the sieve; improved sieves in 2016 pushed recommended sizes up.

Isogenies¶

An isogeny is a map between two curves that respects the group law. Isogeny problems were proposed as post-quantum foundations. SIDH and its KEM SIKE, a fourth-round candidate in NIST's process, were broken in 2022 by Wouter Castryck and Thomas Decru in about an hour on one core, using a 1997 theorem of Ernst Kani and the extra points SIDH had to publish. Other isogeny schemes, such as CSIDH and the signature SQIsign, are not affected. Chapter 20 and Hard problems say more.

Life story: SIDH and SIKE

Born: 2011, David Jao and Luca De Feo (SIDH); SIKE submitted to NIST in 2017 · Purpose: post-quantum key exchange from isogenies, with tiny keys · Broken: July 2022 by Wouter Castryck and Thomas Decru, on a single core in about an hour · Status: dead; other isogeny schemes such as SQIsign survive

Check yourself¶

1. Is $(3, 1)$ on $y^2 = x^3 + 2x + 2$ over $\mathbb{F}_{17}$? What is $-(3, 1)$?

$1^2 = 1$ and $27 + 6 + 2 = 35 = 2 \cdot 17 + 1$, so yes. Its negative is $(3, -1) = (3, 16)$, which is $15G$ in the list of §15.3 (and $(3, 1) = 4G$, so $4 + 15 = 19$, as it should be).

2. Compute $4G = 2G + 2G$ on the toy curve by hand, with $2G = (6, 3)$.

Tangent slope $m = (3 \cdot 36 + 2)/(2 \cdot 3) = 110 \cdot 6^{-1}$. Mod 17, $110 \equiv 8$ and $6^{-1} \equiv 3$ (since $18 \equiv 1$), so $m = 24 \equiv 7$. Then $x_3 = 49 - 12 = 37 \equiv 3$ and $y_3 = 7 \cdot (6 - 3) - 3 = 18 \equiv 1$. So $4G = (3, 1)$, as the table says.

3. Do ECDH on the toy curve with $d_A = 2$ and $d_B = 5$.

Alice sends $2G = (6, 3)$, Bob sends $5G = (9, 16)$. Both compute $10G = (7, 11)$.

4. By Hasse's theorem, how many points can a curve over $\mathbb{F}_{17}$ have?

$p + 1 - t$ with $\lvert t \rvert \le 2\sqrt{17} \approx 8.2$, so between $18 - 8 = 10$ and $18 + 8 = 26$.

5. Why does a 256-bit elliptic-curve key give about the same security as a 3072-bit RSA key?

The best known attack on a good curve is generic (Pollard's rho), costing about $\sqrt n = 2^{128}$ steps for $n \approx 2^{256}$. RSA and finite-field groups are attacked by the number field sieve, which is subexponential, so their numbers must be far larger to reach $2^{128}$.

6. Given one ECDSA signature $(r, s)$ on a message, how do you make a second valid signature without the key? How do Ed25519 verifiers prevent the analogous trick of adding $\ell$ to $S$?

$(r, n - s)$ is valid, because $-kG$ and $kG$ have the same $x$-coordinate. Ed25519 verifiers must check $S < \ell$ (RFC 8032 §8.4); without that check $(R, S + \ell)$ would also verify.

7. Why doesn't X25519 need to check that a received public key is on the curve, while ECDH on P-256 does?

Every 32-byte value is the $x$-coordinate of a point either on Curve25519 or on its twist, the twist was chosen to be secure too, and the ladder never uses $y$. On P-256 the formulas ignore $b$, so an off-curve point lies on some other curve, possibly with a small subgroup, which leaks the key (the invalid-curve attack).

8. In Dual_EC_DRBG, why is knowing $e$ with $P = eQ$ enough to predict the generator?

An output is the $x$-coordinate of $sQ$, so it gives the point $\pm sQ$. Multiplying by $e$ gives $\pm sP$, and the next state is the $x$-coordinate of $sP$, the same for both signs. From the state, every later output follows. Without $e$, getting $sP$ from $sQ$ is a Diffie-Hellman problem.

9. ECDSA signatures from one key, made over a year, show the same $r$ twice. What happened, and what is the damage?

The same nonce $k$ was used twice (or the same $kG$, which for a random $k$ is the same thing). As in §14.5, $k = (H_1 - H_2)/(s_1 - s_2)$ and $d = (s_1 k - H_1)/r \bmod n$: the private key is public. Every signature the key ever made or will make must be treated as forgeable.

What you learned¶

An elliptic curve $y^2 = x^3 + ax + b$ plus a point at infinity forms a group under the chord-and-tangent rule; over $\mathbb{F}_p$ it is a finite group of about $p$ points.
Scalar multiplication $dG$ is easy (double-and-add); recovering $d$ is the ECDLP, for which only generic $\sqrt n$ attacks are known on good curves. 256-bit curves give about 128-bit security.
ECDH, ECDSA and EdDSA are Diffie-Hellman, DSA and Schnorr on curves, with the same strengths and the same failure modes (nonces, unchecked inputs).
X25519 and Ed25519 were designed to make safe implementations easy: $x$-only ladders, twist security, complete formulas, deterministic nonces.
P-256 is required in many standards; secp256k1 runs Bitcoin. Validate points and use constant-time libraries.
Unexplained constants are a liability: Dual_EC_DRBG shows how two points can hide a backdoor.
Every curve falls to Shor's algorithm; hybrids with ML-KEM are the bridge.

Next: Chapter 16, how you know whose public key you hold.

Step	Calculation	Value
slope	\(m = (3 \cdot 5^2 + 2) / (2 \cdot 1) = 77 \cdot 2^{-1}\); \(77 \equiv 9\) and \(2^{-1} \equiv 9\) (as \(2 \cdot 9 = 18 \equiv 1\))	\(m = 81 \bmod 17 = 13\)
\(x_3\)	\(13^2 - 5 - 5 = 159\)	\(159 \bmod 17 = 6\)
\(y_3\)	\(13 \cdot (5 - 6) - 1 = -14\)	\(-14 \bmod 17 = 3\)

Step	Calculation	Value
Public key	\(Q = 7G\)	\((0, 6)\)
Hash (made up)	\(H(m)\)	10
Nonce	\(k = 3\), \(kG = (10, 6)\)
\(r\)	\(x\)-coordinate of \(kG\), mod 19	\(r = 10\)
\(s\)	\(3^{-1} \cdot (10 + 10 \cdot 7) \bmod 19 = 13 \cdot 80 \bmod 19\)	\(s = 14\)
Verify: \(w\)	\(14^{-1} \bmod 19\)	\(w = 15\)
\(u_1 = H w\), \(u_2 = r w\)	\(150 \bmod 19\), \(150 \bmod 19\)	\(u_1 = u_2 = 17\)
\(X = 17G + 17Q\)	\((6, 14) + (9, 16)\)	\((10, 6)\)
Check	\(10 \bmod 19 = r\)	valid

Curve	Field prime	Shape	Cofactor	Origin	Main uses
P-256 (secp256r1)	\(2^{256} - 2^{224} + 2^{192} + 2^{96} - 1\)	Weierstrass, \(a = -3\)	1	NSA, published by NIST 1999, FIPS 186-2 (2000)	TLS certificates, smart cards, FIPS modules, WebAuthn
P-384, P-521	special primes; \(2^{521} - 1\) for P-521	Weierstrass	1	same	government "top secret" profiles (P-384)
Curve25519 / Ed25519	\(2^{255} - 19\)	Montgomery / twisted Edwards	8	Bernstein, 2006; RFC 7748, RFC 8032	TLS 1.3, SSH, Signal, WireGuard, age
Curve448 / Ed448	\(2^{448} - 2^{224} - 1\)	Montgomery / Edwards	4	Hamburg, 2015	a higher-security option (about 224 bits)
secp256k1	\(2^{256} - 2^{32} - 977\)	Weierstrass, \(y^2 = x^3 + 7\)	1	Certicom, SEC 2 (2000)	Bitcoin, Ethereum
Brainpool	from the digits of \(\pi\)	Weierstrass	1	BSI and secunet, RFC 5639 (2010)	European government profiles