CRYPTOGRAPHIC ENGINE

Chapter 1: The secp256k1 Elliptic Curve — Complete Specification

1.1 Domain Parameters

Bitcoin uses the secp256k1 curve as defined by the Standards for Efficient Cryptography (SEC 2, version 2.0). These are the exact bytes that define the curve:

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
  = 2²⁵⁶ − 2³² − 2⁹ − 2⁸ − 2⁷ − 2⁶ − 2⁴ − 1
  = 115792089237316195423570985008687907853269984665640564039457584007908834671663

a = 0x0000000000000000000000000000000000000000000000000000000000000000
b = 0x0000000000000000000000000000000000000000000000000000000000000007

Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
  = 115792089237316195423570985008687907852837564279074904382605163141518161494337

h = 1 (cofactor — the curve order equals the group order, no subgroups)

Why These Numbers?

Parameter Purpose
p Pseudo-Mersenne prime — choosing p = 2²⁵⁶ − (2³² + 2⁹ + 2⁸ + 2⁷ + 2⁶ + 2⁴ + 1) = 2²⁵⁶ − 2³² − 977 makes modular reduction extremely efficient because the modulus is so close to a power of 2
a = 0, b = 7 Makes it a Koblitz curve (special endomorphism property)
n Order of the group generated by G; it is prime, making the group cyclic of prime order
h = 1 Every non-infinity point generates the full curve group — no small subgroups for twist attacks (though the twist itself has h=2, which matters for certain attacks)

1.2 The Curve Equation — Group Law in Affine Coordinates

The curve is defined over F_p (the finite field of integers modulo p):

E: y² ≡ x³ + 7 (mod p)

Point at infinity: O — the identity element of the group.

Point Addition

Given P₁ = (x₁, y₁), P₂ = (x₂, y₂) with P₁, P₂ ≠ O and P₁ ≠ ±P₂:

λ = (y₂ − y₁) × (x₂ − x₁)⁻¹  (mod p)
x₃ = λ² − x₁ − x₂             (mod p)
y₃ = λ × (x₁ − x₃) − y₁       (mod p)

Point Doubling

Given P = (x₁, y₁) with P ≠ O and P ≠ −P:

λ = (3 × x₁²) × (2 × y₁)⁻¹   (mod p)
x₃ = λ² − 2 × x₁              (mod p)
y₃ = λ × (x₁ − x₃) − y₁       (mod p)

Negation

−(x, y) = (x, −y mod p)

⚠️ Performance Note: The modular inverse (·)⁻¹ is the most expensive operation — ~50-100× slower than multiplication. This motivates Jacobian coordinates.

1.3 Jacobian Projective Coordinates

Instead of (x, y), represent points as (X, Y, Z) where:

x = X × Z⁻²  (mod p)
y = Y × Z⁻³  (mod p)

The curve equation in Jacobian form:

Y² = X³ + 7 × Z⁶

Infinity point: Z = 0 (i.e., (1, 1, 0) by convention).

Mixed Addition (Z₂ = 1)

Adding a Jacobian point to an affine point (one with Z=1) avoids Z-normalization.

Full Jacobian Addition

Given P₁ = (X₁, Y₁, Z₁), P₂ = (X₂, Y₂, Z₂):

U1 = X₁ × Z₂²        (mod p)
U2 = X₂ × Z₁²        (mod p)
S1 = Y₁ × Z₂³        (mod p)
S2 = Y₂ × Z₁³        (mod p)
H  = U2 − U1         (mod p)
R  = S2 − S1         (mod p)

X₃ = R² − H³ − 2×U1×H²   (mod p)
Y₃ = R×(U1×H² − X₃) − S1×H³   (mod p)
Z₃ = H × Z₁ × Z₂     (mod p)

Cost: 12 multiplications + 4 squarings per full addition. No inversions!

Jacobian Doubling

t = 3 × X₁² + a × Z₁⁴   (mod p)   [a = 0 for secp256k1, so t = 3×X₁²]

X₃ = t² − 8 × X₁ × Y₁²   (mod p)
Y₃ = t × (4 × X₁ × Y₁² − X₃) − 8 × Y₁⁴   (mod p)
Z₃ = 2 × Y₁ × Z₁         (mod p)

Cost: 4 multiplications + 4 squarings per doubling.

1.4 The GLV Endomorphism — secp256k1's Secret Weapon

secp256k1 has an efficiently computable endomorphism — a special property that lets you decompose a 256-bit scalar multiplication into two 128-bit scalar multiplications, effectively halving computation time.

The Endomorphism

Define the function φ:

φ(x, y) = (β × x mod p, y)

Where β is a cube root of unity in F_p (specifically β³ ≡ 1 mod p, β ≠ 1):

β = 0x7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE

For any point P on the curve, φ(P) is also on the curve. Moreover, this function acts as scalar multiplication:

φ(P) = λ × P

Where:

λ = 0x5363AD4CC05C30E0A5261C028812645A122E22EA20816678DF02967C1B23BD72

And it's a cube root of unity in the scalar field F_n:

λ³ ≡ 1 (mod n)
λ² + λ + 1 ≡ 0 (mod n)

How It Speeds Up Multiplication

To compute k × P where k is a 256-bit scalar:

1. Decompose k into two 128-bit scalars k₁, k₂ such that:

   k ≡ k₁ + k₂ × λ (mod n)

   with |k₁|, |k₂| < √n
2. Compute:

   k × P = k₁ × P + k₂ × φ(P) = k₁ × P + k₂ × λ × P

3. Since φ(P) = (βx, y), computing k₂ × φ(P) uses the same add/double circuit but the x-coordinates are multiplied by β at each step — a single field multiplication per point operation.
4. The two multiplications k₁ × P and k₂ × φ(P) happen in parallel using interleaved wNAF (windowed Non-Adjacent Form) with a joint sparse representation.

Performance Gain

~40-50% reduction in multiplication time vs. non-GLV code. Combined with wNAF with window size 4-6, a full 256-bit multiplication takes approximately:

· ~270 Jacobian doublings
· ~45 Jacobian additions

Instead of 256 doublings + ~66 additions without GLV.

1.5 Scalar Multiplication Algorithms

1.5.1 Double-and-Add (NAIVE — DON'T USE)

result = O
for bit in bits(k) from MSB to LSB:
    result = double(result)
    if bit == 1:
        result = add(result, P)
return result

Time: ~256 doublings + ~128 additions. NOT constant-time.

1.5.2 wNAF (Windowed Non-Adjacent Form)

Precompute [P, 3P, 5P, ..., (2^w-1)P] for window size w.

The scalar k is encoded in Non-Adjacent Form (no two consecutive non-zero digits) with digits in {0, ±1, ±3, ..., ±(2^w-1)}:

k = Σ(ki × 2^i) where ki ∈ {0, ±1, ±3, ..., ±(2^w-1)} and ki × ki+1 = 0

Then:

result = O
for i from m-1 down to 0:
    result = double(result)
    if ki > 0:
        result = add(result, P[ki])
    elif ki < 0:
        result = add(result, neg(P[|ki|]))
return result

For w=5: ~256 doublings + ~51 additions (average). 2.5× faster than double-and-add.

1.5.3 Montgomery Ladder (Constant-Time)

R0 = O
R1 = P

for i from 255 down to 0:
    if k[i] == 0:
        R1 = add(R1, R0)
        R0 = double(R0)
    else:
        R0 = add(R0, R1)
        R1 = double(R1)

return R0

Every iteration does exactly one addition and one doubling — regardless of the bit value. This prevents timing and power analysis side-channels.

1.5.4 Straus's Algorithm (Shamir's Trick)

For computing a × G + b × Q:

1. Precompute table of i × G + j × Q for small i, j
2. Process bits of (a, b) simultaneously
3. Each step: double the accumulator, then add one entry from the table

This is used inside Kangaroo/BSGS for batch point operations.