We now focus our attention on the specific elliptic curve chosen by Satoshi Nakamoto for Bitcoin: secp256k1. This curve, defined in the "Standards for Efficient Cryptography" (SEC) document, possesses remarkable properties that make it both efficient to compute and resistant to known attacks.
Understanding secp256k1 in detail is essential for anyone seeking to comprehend Bitcoin at its deepest level. Every private key, every public key, every digital signature in Bitcoin emerges from operations on this curve.
5.1 The Name Decoded
The cryptic name "secp256k1" encodes several pieces of information:
Koblitz Curves.
The "k" indicates this is a Koblitz curve, named after Neal Koblitz, one of the inventors of elliptic curve cryptography. Koblitz curves have coefficients chosen for computational efficiency rather than from seemingly random seeds. The simplicity of these parameters (in secp256k1: a = 0, b = 7) means there is no suspicion of hidden backdoors.
5.2 The Curve Equation
Definition 5.1 (The secp256k1 Curve)
The secp256k1 curve is defined by the equation:
y² = x³ + 7
over the prime field 𝔽ₚ, where:
a = 0, b = 7
The simplicity of this equation—the absence of the ax term—makes certain optimizations possible. It also means that the curve parameters are completely transparent: there are no mysterious constants that might conceal a mathematical trapdoor.
5.3 The Field Parameters
The curve is defined over a prime field of size approximately 2²⁵⁶. The specific prime was chosen for its special form, which allows efficient modular reduction.
Definition 5.2 (The Field Prime p)
The prime p for secp256k1 is:
p = 2²⁵⁶ − 2³² − 2⁹ − 2⁸ − 2⁷ − 2⁶ − 2⁴ − 1
Or equivalently:
p = 2²⁵⁶ − 2³² − 977
Example 5.1 (The Prime in Various Representations)
Hexadecimal:
p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF
FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
Decimal:
p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
This is a 256-bit number, approximately 1.158 × 10⁷⁷.
Why This Specific Prime?
The form p = 2²⁵⁶ − 2³² − c (where c = 977 is small) enables fast modular reduction. When computing x mod p for a 512-bit number x, we can use the identity:
2²⁵⁶ ≡ 2³² + 977 (mod p)
This allows the high bits of x to be folded back into the low bits with simple additions, avoiding expensive division.
5.4 The Generator Point
Every point operation in Bitcoin begins with a fixed generator point G. This point generates a cyclic subgroup of prime order.
Definition 5.3 (The Generator Point G)
The generator point G = (G_x, G_y) has coordinates:
G_x (hexadecimal):
79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
G_y (hexadecimal):
483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
The generator point was chosen such that its order n is a large prime. Starting from G, we can reach any point in the cryptographic subgroup by scalar multiplication.
5.5 The Group Order
The order of the generator point G—and hence the size of the cryptographic subgroup—is a prime number slightly less than 2²⁵⁶.
Definition 5.4 (The Group Order n)
The order of G is:
Hexadecimal:
n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE
BAAEDCE6 AF48A03B BFD25E8C D0364141
Decimal:
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337
This means nG = 𝒪 and n is prime.
The fact that n < p might seem surprising. Hasse's theorem guarantees that |n - (p+1)| ≤ 2√p, but it doesn't specify whether n is slightly above or below p + 1. For secp256k1, we have n ≈ p - 4.3 × 10³⁸.
Proposition 5.1 (Cofactor)
The cofactor of secp256k1 is h = 1.
This means the entire curve group is cyclic and generated by G:
#E(𝔽ₚ) = n × h = n × 1 = n
Security Implication.
A cofactor of 1 is cryptographically ideal. It means there are no "small subgroup" attacks to worry about, and every point on the curve (except 𝒪) has order n.
5.6 Complete Parameter Summary
For reference, here are all the secp256k1 parameters collected together:
| Parameter | Symbol | Value |
|---|---|---|
| Curve equation | — | y² = x³ + 7 |
| Coefficient a | a | 0 |
| Coefficient b | b | 7 |
| Field prime | p | 2²⁵⁶ − 2³² − 977 |
| Group order | n | ≈ 2²⁵⁶ − 4.3 × 10³⁸ |
| Cofactor | h | 1 |
| Generator x-coord | G_x | 79BE667EF9DCBBAC... |
| Generator y-coord | G_y | 483ADA7726A3C465... |
| Security level | — | ~128 bits |
5.7 Private and Public Keys
With the curve parameters established, we can now precisely define what constitutes a Bitcoin private key and public key.
Definition 5.5 (Private Key)
A private key is an integer k satisfying:
1 ≤ k ≤ n − 1
In Bitcoin, this is typically a 256-bit random number. The private key must be kept secret; anyone who knows it can spend the associated funds.
Definition 5.6 (Public Key)
Given a private key k, the public key is the point:
P = kG = (x, y)
This point can be shared publicly. The security of the system relies on the infeasibility of computing k from P and G.
Example 5.2 (A Simple Private Key)
Let the private key be k = 1. Then the public key is:
P = 1 × G = G
So the public key is simply the generator point itself. While this is mathematically valid, it would be a catastrophically weak key in practice!
For k = 2, the public key is P = 2G, computed via point doubling.
Key Space Size.
There are approximately 2²⁵⁶ possible private keys. For comparison:
- Atoms in the observable universe: ~10⁸⁰ ≈ 2²⁶⁶
- Possible secp256k1 private keys: ~2²⁵⁶
- Grains of sand on Earth: ~10¹⁸ ≈ 2⁶⁰
The key space is astronomical. A randomly chosen key has negligible probability of collision with any other key ever generated.
5.8 Public Key Encoding
A public key is a point (x, y) on the curve. There are several ways to encode this point as a byte sequence.
Definition 5.7 (Public Key Formats)
Uncompressed format (65 bytes):
04 || x (32 bytes) || y (32 bytes)
The prefix 04 indicates uncompressed format.
Compressed format (33 bytes):
(02 or 03) || x (32 bytes)
The prefix is 02 if y is even,
03 if y is odd.
Proposition 5.2 (Point Recovery)
Given x and the parity of y, the full point (x, y) can be recovered:
- Compute y² = x³ + 7 mod p
- Compute y = (y²)^{(p+1)/4} mod p (valid since p ≡ 3 (mod 4))
- If the parity of y doesn't match the prefix, use p − y
Compression Benefits.
Compressed public keys save 32 bytes per key. In Bitcoin transactions, this reduces transaction size and hence fees. Modern Bitcoin software uses compressed keys by default.
5.9 Why Satoshi Chose secp256k1
When Satoshi Nakamoto designed Bitcoin, he chose secp256k1 over the more common NIST curves. Several factors likely influenced this decision:
Advantages of secp256k1
- Efficiency: The special form of p and the fact that a = 0 allow for faster field operations. Optimized implementations can be 30% faster than NIST curves.
- Transparency: The simple parameters (a = 0, b = 7) are clearly not derived from any hidden structure. There is no suspicion of "nothing up my sleeve" numbers concealing a backdoor.
- Cofactor 1: The absence of small subgroups simplifies implementation and removes a class of potential attacks.
- Endomorphism: secp256k1 possesses an efficiently computable endomorphism that can accelerate signature verification.
Historical Note.
The NIST curves (P-256, etc.) were specified with seed values used to generate their parameters, but these seeds were never fully explained. This has led to speculation about potential NSA influence. secp256k1's verifiable simplicity sidesteps these concerns entirely.
5.10 Security Analysis
The security of secp256k1 has been extensively analyzed. The main conclusion: for well-implemented systems, the curve provides excellent security.
Security Properties of secp256k1
- ECDLP hardness: No algorithm better than O(√n) ≈ O(2¹²⁸) is known.
- Not anomalous: n ≠ p, so the anomalous curve attack doesn't apply.
- High embedding degree: The curve is not supersingular, so the MOV attack doesn't apply.
- Twist security: The quadratic twist of secp256k1 also has near-prime order, providing resistance to twist attacks.
To put 2¹²⁸ operations in perspective: if every computer on Earth performed one billion operations per second, and they all worked together for the age of the universe, they would still be nowhere close to completing 2¹²⁸ operations.
Exercises
02 or 03.
Explain why the y-coordinate's parity determines which prefix to use.