In the previous chapter, we explored elliptic curves over the real numbers, where our geometric intuition could guide us. Now we make a profound transition: we move from the continuous realm of real numbers to the discrete world of finite fields.
This transition may seem like a leap into abstraction, yet the algebraic structure survives intact. The same addition formulas work, the same group laws hold. What changes is the visual nature of the curve—instead of a smooth flowing shape, we have a finite collection of discrete points.
It is in this discrete setting that cryptography becomes possible.
4.1 Definition over Finite Fields
Definition 4.1 (Elliptic Curve over 𝔽ₚ)
Let p > 3 be a prime. An elliptic curve over the finite field 𝔽ₚ is the set of points (x, y) with x, y ∈ 𝔽ₚ satisfying:
y² ≡ x³ + ax + b (mod p)
where a, b ∈ 𝔽ₚ and 4a³ + 27b² ≢ 0 (mod p), together with the point at infinity 𝒪.
We denote this curve by E(𝔽ₚ).
The key insight is that all our previous formulas work in 𝔽ₚ simply by performing all arithmetic modulo p. Division becomes multiplication by the modular inverse.
Example 4.1 (A Small Curve: E(𝔽₂₃))
Consider the curve y² = x³ + x + 1 over 𝔽₂₃. Here a = 1, b = 1.
To find all points, we check each x ∈ {0, 1, 2, ..., 22} and see if x³ + x + 1 is a quadratic residue mod 23.
For x = 0: 0³ + 0 + 1 = 1 = 1². So (0, 1) and (0, 22) are on the curve.
For x = 1: 1³ + 1 + 1 = 3. Is 3 a square mod 23? We need y² ≡ 3. Testing: 7² = 49 ≡ 3. Yes! Points: (1, 7) and (1, 16).
Continuing this process yields all 28 points (plus 𝒪).
Notice that the visual "curve" has disappeared. We have only isolated points scattered across the plane. Yet these points still form a group under the same algebraic rules.
4.2 Point Addition over 𝔽ₚ
The addition formulas from Chapter 3 carry over directly, with all arithmetic performed in 𝔽ₚ. Division becomes multiplication by the modular inverse.
Theorem 4.1 (Addition Formulas over 𝔽ₚ)
Let P = (x₁, y₁) and Q = (x₂, y₂) be points on E(𝔽ₚ). Then P + Q = (x₃, y₃) where:
If P ≠ Q:
λ = (y₂ − y₁) · (x₂ − x₁)⁻¹ mod p
If P = Q:
λ = (3x₁² + a) · (2y₁)⁻¹ mod p
In both cases:
x₃ = λ² − x₁ − x₂ mod p
y₃ = λ(x₁ − x₃) − y₁ mod p
Example 4.2 (Point Addition in 𝔽₂₃)
On E(𝔽₂₃): y² = x³ + x + 1, compute P + Q where P = (3, 10) and Q = (9, 7).
Step 1: Compute the slope λ.
- y₂ − y₁ = 7 − 10 = −3 ≡ 20 (mod 23)
- x₂ − x₁ = 9 − 3 = 6
- Find 6⁻¹ mod 23: Since 6 × 4 = 24 ≡ 1, we have 6⁻¹ = 4.
- λ = 20 × 4 = 80 ≡ 11 (mod 23)
Step 2: Compute x₃.
- x₃ = λ² − x₁ − x₂ = 11² − 3 − 9 = 121 − 12 = 109 ≡ 17 (mod 23)
Step 3: Compute y₃.
- y₃ = λ(x₁ − x₃) − y₁ = 11(3 − 17) − 10 = 11(−14) − 10
- = −154 − 10 = −164 ≡ −164 + 8×23 = −164 + 184 = 20 (mod 23)
Result: P + Q = (17, 20).
Verification: 20² = 400 ≡ 9 (mod 23) and 17³ + 17 + 1 = 4913 + 18 = 4931 ≡ 9 (mod 23). ✓
4.3 The Order of a Curve
Unlike curves over the reals, which have infinitely many points, curves over finite fields have finitely many. The number of points is called the order of the curve.
Definition 4.2 (Curve Order)
The order of an elliptic curve E(𝔽ₚ), denoted #E(𝔽ₚ) or |E(𝔽ₚ)|, is the total number of points on the curve, including the point at infinity.
Theorem 4.2 (Hasse's Theorem)
For an elliptic curve E over 𝔽ₚ:
|#E(𝔽ₚ) − (p + 1)| ≤ 2√p
Equivalently, writing #E(𝔽ₚ) = p + 1 − t, we have |t| ≤ 2√p. The integer t is called the trace of Frobenius.
Intuition.
Hasse's theorem says that the number of points on an elliptic curve is roughly p, the size of the underlying field. The deviation from p + 1 is at most 2√p, which for large p is negligible in comparison.
4.4 Cyclic Subgroups and Generators
For cryptographic applications, we typically work with a cyclic subgroup of the elliptic curve group, generated by a specific point G.
Definition 4.3 (Order of a Point)
The order of a point P on an elliptic curve is the smallest positive integer n such that:
nP = 𝒪
The subgroup generated by P is ⟨P⟩ = {𝒪, P, 2P, 3P, ..., (n−1)P}.
Theorem 4.3 (Lagrange for Elliptic Curves)
The order of any point P divides the order of the curve #E(𝔽ₚ).
Definition 4.4 (Generator Point)
A point G is called a generator (or base point) of a subgroup if every point in the subgroup can be expressed as kG for some integer k.
For cryptographic purposes, we choose G to generate a subgroup of prime order n.
Definition 4.5 (Cofactor)
If E(𝔽ₚ) has order N and we use a subgroup of prime order n, then the cofactor is:
h = N / n
For cryptographic security, we prefer curves with small cofactor, ideally h = 1.
Why Prime Order?
Working in a subgroup of prime order n ensures that the discrete logarithm problem is as hard as possible. If n had small factors, the Pohlig-Hellman algorithm could exploit this structure to solve the DLP more efficiently.
4.5 The Elliptic Curve Discrete Logarithm Problem
We now formalize the computational problem upon which all elliptic curve cryptography rests.
Definition 4.6 (ECDLP)
The Elliptic Curve Discrete Logarithm Problem (ECDLP) is:
Given points G and Q = kG on an elliptic curve E(𝔽ₚ), find the integer k.
While computing Q = kG is efficient (using double-and-add), finding k given only G and Q is believed to be computationally infeasible for properly chosen curves.
Theorem 4.4 (Best Known Algorithms for ECDLP)
For a generic elliptic curve group of order n:
- Brute force: O(n) operations
- Baby-step giant-step: O(√n) operations, O(√n) storage
- Pollard's rho: O(√n) operations, O(1) storage
No algorithm significantly better than O(√n) is known for properly chosen elliptic curves.
For Bitcoin's secp256k1 curve, n ≈ 2²⁵⁶, giving a security level of approximately √(2²⁵⁶) = 2¹²⁸ operations—well beyond any foreseeable computational capability.
4.6 Choosing Secure Curves
Not all elliptic curves provide adequate security. The following criteria guide the selection of cryptographic curves:
Criteria for Cryptographic Curves
- Large prime order subgroup: The curve should have a subgroup of order n where n is prime and at least 256 bits.
- Small cofactor: The cofactor h = N/n should be small (ideally 1).
- Resistance to MOV attack: The embedding degree should be large (the curve should not be supersingular).
- Resistance to anomalous attack: #E(𝔽ₚ) ≠ p.
- Verifiable randomness: The parameters should be generated in a way that doesn't allow hidden trapdoors.
NIST vs. Koblitz Curves.
The NIST curves (P-256, P-384, P-521) were selected with opaque "random" seeds, leading to suspicion that they might contain hidden weaknesses. In contrast, Koblitz curves like secp256k1 have simple, verifiable parameters (a = 0, b = 7) that leave no room for hidden trapdoors. This transparency was one reason Satoshi Nakamoto chose secp256k1 for Bitcoin.
4.7 From Groups to Cryptography
The elliptic curve group (E(𝔽ₚ), +) provides the mathematical foundation for several cryptographic constructions:
| Cryptographic Primitive | Based On | Used In Bitcoin |
|---|---|---|
| Key Generation | Scalar multiplication: Q = kG | Private/public key pairs |
| ECDSA | ECDLP hardness | Legacy transaction signing |
| Schnorr Signatures | ECDLP hardness | Taproot (BIP-340) |
| ECDH | CDH assumption | Encrypted messaging |
In the next chapter, we shall study the specific curve chosen for Bitcoin: secp256k1.