Chapter 13 · Switching to the Real Curve

Part IV · Surviving the long run No new concepts here. Just one demonstration, and it is the most persuasive in the book.

In chapter 2 you hopped around a curve mod 97. In chapter 3 you signed on a curve mod 23 with twenty-nine points.

Those curves were small enough to work through by hand — and small enough that you personally brute-forced a private key out of one.

This chapter swaps them for the curve Bitcoin actually uses: secp256k1.

And you will find that almost none of your code has to change.

13.1 The real parameters¶

The curve equation is still the familiar shape:

y^2 = x^3 + 7 \pmod p

(1)

Only p, G and n are enormous.

# ===== secp256k1: Bitcoin's real curve parameters =====
# y^2 = x^3 + 7 (mod p)
p  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a, b = 0, 7
# The generator G
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
G  = (Gx, Gy)
# The order n: how many hops before G returns to the start. A huge prime.
n  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

print("how big is p:", p)
print("bit length:", p.bit_length())
print("possible private keys ~ 2^256 ~", 2**256)

how big is p: 115792089237316195423570985008687907853269984665640564039457584007908834671663
bit length: 256
possible private keys ~ 2^256 ~ 115792089237316195423570985008687907853269984665640564039457584007913129639936

Be clear what those five lines are: five integers.

Chapter 2: p = 97, G = (0, 10)
This chapter: p is a 78-digit decimal number, G a pair of 78-digit coordinates

Structurally identical. The numbers are simply larger. In fact a, b = 0, 7 is simpler than chapter 2’s 2, 3 — secp256k1’s a is zero, so the equation does not even have an ax term.

The shape of p is worth one glance: FFFF...FFFE FFFFFC2F. It is nearly 2²⁵⁶, just barely short. That was chosen deliberately — primes of this form let the modular reduction be implemented with bit tricks.

2²⁵⁶ possible private keys — roughly the number of atoms in the observable universe (~10⁸⁰).

The crack() you wrote in chapter 2 is still perfectly correct against this curve. It simply never finishes.

13.2 Point addition: not one character changed¶

def inv(x, m): return pow(x % m, m-2, m)

def point_add(P, Q):
    '''Chapter 2's point addition, verbatim.'''
    if P is None: return Q
    if Q is None: return P
    x1, y1 = P; x2, y2 = Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return None
    if P == Q:
        s = (3*x1*x1 + a) * inv(2*y1, p) % p
    else:
        s = (y2 - y1) * inv(x2 - x1, p) % p
    x3 = (s*s - x1 - x2) % p
    y3 = (s*(x1 - x3) - y1) % p
    return (x3, y3)

def on_curve(P):
    if P is None: return True
    x, y = P
    return (y*y - (x*x*x + a*x + b)) % p == 0

print("is the generator G on the real curve:", on_curve(G))
print("is G + G on it as well              :", on_curve(point_add(G, G)))

is the generator G on the real curve: True
is G + G on it as well              : True

Put this next to section 2.2 — it is the same code.

Not one character differs. Tangent slope, chord slope, inv(), % p: all carried over intact.

Mathematics does not care how large the numbers are. That is the first thing worth pausing on: everything you learned on a 97-position curve holds without modification on a curve with 2²⁵⁶ points. No patches required.

(That pow(x, m-2, m) inside inv still works too — Fermat’s little theorem is size-agnostic, and Python’s pow is fast modular exponentiation, so a 256-bit exponent costs a few hundred steps.)

13.3 The one thing that must change¶

Chapter 2’s scalar_mul looked like this:

def scalar_mul(k, G):
    R = None
    for _ in range(k):      # <- loop k times
        R = point_add(R, G)
    return R

On the real curve k can be as large as 2²⁵⁶. That for loop would still be running after the sun burns out.

So the algorithm has to change: double-and-add.

The idea: to compute k·G, don’t add one at a time. Double repeatedly, and add selectively according to the binary digits.

def scalar_mul(k, P):
    '''Hop k times via double-and-add: ~256 steps instead of 2^256.'''
    R = None            # the result, starting from infinity (zero)
    k %= n
    addend = P
    while k:
        if k & 1:                            # this binary digit is 1 -> add the current addend
            R = point_add(R, addend)
        addend = point_add(addend, addend)   # double: G, 2G, 4G, 8G, ...
        k >>= 1                              # move to the next digit
    return R

priv = 0x1234567890ABCDEF1234567890ABCDEF
print("private key:", hex(priv))
pub = scalar_mul(priv, G)               # instant
print("public key x:", hex(pub[0]))
print("           y:", hex(pub[1]))
print("is the public key on the curve:", on_curve(pub))

private key: 0x1234567890abcdef1234567890abcdef
public key x: 0x9377c312145a5afb911bf9e8c067bcf6094c533603687850df502b61290bbf5e
           y: 0x742ba607d6ae1fc82dcccb176e7c8f9bdc7bb61e3ab527cecaf6144b679779fb
is the public key on the curve: True

Double-and-add is just long multiplication in binary.

To compute 13 · G, and 13 in binary is 1101:

13 · G = 8G + 4G + 1G
       = (G doubled three times) + (G doubled twice) + G

So you keep doubling the addend (G → 2G → 4G → 8G) and add it into the result wherever the binary digit is 1.

A 256-bit k needs at most 256 doublings. From 2²⁵⁶ steps down to 256.

This is the other face of chapter 2’s complexity intuition:

	Steps	Time
Forwards (private → public)	double-and-add, ~256	instant
Backwards (public → private)	no shortcut, 2²⁵⁶	never

That asymmetry is where the security of every bitcoin in existence lives.

And note carefully: the asymmetry is not a theorem. It is “nobody has found a shortcut yet.” If someone ever did — a sufficiently large quantum computer, say (appendix B) — the asymmetry disappears.

A deep sanity check¶

# n is the order of G: n hops returns to the point at infinity.
print("does n * G give the point at infinity (None)?:", scalar_mul(n, G) is None)

does n * G give the point at infinity (None)?: True

Prints True.

That single line is a consistency check on the entire parameter set. In chapter 2 you computed 50G = None on a fifty-point curve. Here n·G = None, where n is a 78-digit number.

Same property, same line of code, a scale difference of about 2²⁵⁰.

13.4 Signing and verifying: still chapter 3¶

import hashlib

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

def sign(priv, msg, k):
    '''Chapter 3's sign, verbatim.'''
    z = hash_to_int(msg)
    R = scalar_mul(k, G); r = R[0] % n
    s = (inv(k, n) * (z + r*priv)) % n
    return (r, s)

def verify(pub, msg, sig):
    '''Chapter 3's verify, verbatim. Still: no priv.'''
    r, s = sig
    if not (1 <= r < n and 1 <= s < n): return False
    z = hash_to_int(msg); w = inv(s, n)
    X = point_add(scalar_mul((z*w) % n, G), scalar_mul((r*w) % n, pub))
    return X is not None and X[0] % n == r

k = 0xDEADBEEF12345678DEADBEEF12345678    # a nonce (must be secret and random for real)
sig = sign(priv, "Alice pays Bob 1 BTC", k)
print("a signature on the real curve:")
print("  r =", hex(sig[0]))
print("  s =", hex(sig[1]))
print()
print("verify           :", verify(pub, "Alice pays Bob 1 BTC", sig))
print("tampered amount  :", verify(pub, "Alice pays Bob 1000 BTC", sig))

a signature on the real curve:
  r = 0xa5969d43528f2eaff287f9e892cad49948c547e8024c4925cd3c3b19524c22f2
  s = 0x276cf789dffe223227be004dede85f09d0cc0454a331e6618d28fe93262f746d

verify           :

 True

tampered amount  : False

Compare these two functions with chapter 3’s: not one character has changed.

z, w, u1, u2, that verification equation — all of it is what you derived by hand in chapter 3.

It now runs on the curve Bitcoin actually uses and produces a genuine 256-bit signature.

Change one character (1 → 1000) and it fails. Everything from chapter 3 holds at full scale.

This is what the chapter exists to show you:

What you hand-wrote in chapter 3 is not “a toy that resembles Bitcoin.” It is Bitcoin’s signature algorithm. The only difference is the size of the parameters.

(And verify still contains no priv. That fact holds identically at scale 29 and at scale 2²⁵⁶.)

13.5 Check against a real library¶

If you have the ecdsa library installed:

# Requires: pip install ecdsa. Skipping it does not affect anything above.
try:
    from ecdsa import SigningKey, SECP256k1
    sk = SigningKey.from_secret_exponent(priv, curve=SECP256k1)
    lib_pub = sk.verifying_key.pubkey.point
    same = (lib_pub.x() == pub[0]) and (lib_pub.y() == pub[1])
    print("our hand-written public key:", hex(pub[0])[:24], "...")
    print("the library's public key   :", hex(lib_pub.x())[:24], "...")
    print("identical?", same)
except ImportError:
    print("ecdsa not installed (optional). With it you can see your key match the library's.")
    print("pip install ecdsa, then rerun this cell.")

our hand-written public key: 0x9377c312145a5afb911bf9 ...
the library's public key   : 0x9377c312145a5afb911bf9 ...
identical? True

A few dozen lines of your Python and an audited cryptographic library produce the same public key.

13.6 Please do not use this¶

This chapter can give you a dangerous kind of confidence, so let me be direct:

This code is mathematically correct and not safe to use. The gap is here:

	Yours	A real implementation
Where `k` comes from	passed in by hand	RFC 6979 deterministic derivation (section 3.6)
Execution time	varies with the bits of the key	constant time, to resist side channels
Memory	the key is copied all over the Python heap	wiped immediately after use
Input validation	essentially none	strict: point on curve, not infinity, etc.

The second row is the killer.

Look at that line in scalar_mul: if k & 1: R = point_add(R, addend). If a bit of the private key is 1, an extra addition happens. If it is 0, it does not.

So the running time of this function leaks how many 1 bits your private key has. More refined attacks — measuring power draw, cache timing, electromagnetic emissions — can read the key out one bit at a time. This is a side-channel attack, one of the most common ways real keys leak in the field, and it has nothing to do with mathematics.

The real libsecp256k1 defends against this by ensuring that the exact same instruction sequence executes regardless of the key. That code is hundreds of times more complex than what you just wrote, and most of the complexity is not about computing correctly. It is about computing indistinguishably.

This is the third time the same lesson has appeared — after section 3.6 (reusing k) and section 11.6 (CVE-2012-2459): correct mathematics is not a safe system.
Chapter 18 brings it a fourth time.

13.7 The ledger¶

What you wrote	Field
secp256k1’s real parameters	Cryptography
`point_add()` — unchanged	Cryptography (chapter 2’s)
`scalar_mul()` — double-and-add	Algorithmic optimization
`sign` / `verify` — unchanged	Cryptography (chapter 3’s)
Side channels, constant time	Engineering safety

This is the second and last time in eighteen chapters that the ledger tips left.

Part IV ends here. Your chain now survives the long run and runs on real cryptographic parameters.

An interim total¶

Through thirteen chapters:

Part	Chapters	Field
I · Bricks	1–3	Cryptography
II · The ancestors	4–5	Systems
III · The house	6–9	Systems + game theory + economics + social coordination
IV · Long run	10, 12	Economics + control theory + statistics
IV · Long run	11, 13	Cryptography

Five chapters of cryptography, eight of everything else. And those eight solved the problem nobody solved for thirty years.

Next¶

Part V begins: toward real engineering.

Thirteen chapters have produced a self-consistent machine. The next five connect it to the real world:

Ch 14: a spending condition is not a database field — it is a running program
Ch 15: how twelve words grow a tree of addresses
Ch 16: why the private key should live in a room with no network cable
Ch 17: running your chain as an actual network across several machines
Ch 18: why Bitcoin’s scripting language is deliberately feeble

Chapter 14 overturns an assumption you have been carrying since chapter 6: that “who can spend this” equals “who holds the private key.”

In real Bitcoin, that is only the simplest case.