Chapter II · Part I — Primitives
Modular Arithmetic 🕰️
Zero knowledge is built on a clock. Seriously: the "wrap-around" arithmetic you use every time you read a clock face is the setting for secrets that are easy to use and (as far as we know) impossibly hard to undo.
Life on a clock
a mod n means: the remainder when a is divided by n. If it's 9 o'clock now, in 7 hours it's (9+7) mod 12 = 4 o'clock — we silently discard the 12s. The numbers form a closed little universe: add, subtract or multiply as much as you like, you never leave the set {0, 1, …, n−1}.
The rules of the universe
Modular arithmetic keeps all the algebra you know — with one twist, everything is "up to wrap-around":
- (a + b) mod n = ((a mod n) + (b mod n)) mod n — same for multiplication. Reduce early, reduce often.
- When n is prime, every non-zero element has a multiplicative inverse, and the exponents of any element cycle with a fixed period (its order, which divides n−1).
- Powers grow terrifyingly — yet remainders are cheap. Squaring repeatedly (a → a² → a⁴ → a⁸ …) computes aᵏ mod n in about log₂ k steps. Cryptography runs on this trick.
🔍 Deeper dive · why we insist on prime moduli
Division is where clock math gets picky: a has a multiplicative inverse mod n exactly when gcd(a, n) = 1. For a prime p, every non-zero element qualifies — multiplication can always be undone, making the residues a field: a little universe where +, −, × and ÷ all behave. Fermat's little theorem even hands you a formula for the inverse: a⁻¹ ≡ a^(p−2) (mod p) — one more square-and-multiply away. Composite moduli have "zero-divisor potholes" (2 × 3 ≡ 0 mod 6) that leak information and break inverses, which is why discrete-log systems live over primes or over elliptic curves, their streamlined cousins.
Powers that orbit
Fix a base g and a prime p, and list the powers g¹, g², g³, … mod p. They orbit through the residues and eventually return to 1, then repeat. If g is a generator, its powers visit every non-zero residue before repeating — a perfect shuffle with no pattern.
🧪 The one-way street: Discrete Log Hunt
Here's the asymmetry that makes modern cryptography possible. Computing y = gˣ mod p is instant — a few squarings. But given only g, p and y, recovering x (the discrete logarithm) appears to require grinding through candidates one by one. Multiply p by 10 and your grind grows by 10×; but add one measly bit to x and the honest direction barely notices.
Scale check
Level 3 uses p ≈ 10⁶ so the robot can still grind it in seconds. Real systems use p ≈ 2²⁵⁶ (or elliptic-curve groups of similar size). Brute force there means ~2¹²⁸ operations — thousands of times the age of the universe for all of humanity's computers combined. Meanwhile the honest direction stays microsecond-fast. Easy forward, hopeless backward.
🔍 Deeper dive · Diffie–Hellman, the 1976 trick that started it all
Two strangers can grow a shared secret in the open — because exponentiation commutes under wraps:
public: p = 23, g = 5
Alice: secret a = 6 → sends A = 5⁶ mod 23 = 8
Bob: secret b = 15 → sends B = 5¹⁵ mod 23 = 19
Alice computes: B^a = 19⁶ mod 23 = 2
Bob computes: A^b = 8¹⁵ mod 23 = 2 ← shared secret!
eavesdropper sees (23, 5, 8, 19) and is stuck:
recovering a needs 5^x ≡ 8 (mod 23) — the discrete log you just hunted.
Why it works: (gᵇ)ᵃ = (gᵃ)ᵇ = g^(ab) — each side unmixes the other's envelope with its own secret. "New Directions in Cryptography" (Diffie–Hellman, 1976) launched public-key cryptography on exactly this identity. (Real deployments add authentication on top, or an active attacker simply impersonates each side — the math gives secrecy, not identity.)
🔍 Deeper dive · even clever attacks only bend the curve
Brute force costs p steps. Baby-step giant-step (1978) does it in ~√p steps and memory — for our level-3 prime (10⁶), that's ~1,000 steps instead of a million; you may have noticed the robot plowing through it anyway. On plain finite fields, index calculus does better still (subexponential — that's why finite-field DH wants 3000+ bit primes). Practice's answer: elliptic curves, where only the generic √ attacks are known, so a 256-bit curve already delivers ~128-bit security. None of this breaks the asymmetry — it just moves the price tag, and it's why your phone's crypto is almost certainly elliptic.
Why this matters for ZK
- Secrets live in exponents. "I know x such that y = gˣ" is the canonical statement Schnorr proofs prove in zero knowledge (Chapter 6) — without ever revealing x.
- Keys from public noise. Diffie–Hellman lets two strangers mix exponents in public and emerge with a shared secret, because unwinding the mixing is a discrete log problem.
- Pedersen commitments (Chapter 4) are exponentials C = gᵐ·hʳ — hiding precisely because discrete logs are hard.
📌 Week 2 — key takeaways
- a mod n is remainder arithmetic on a clock — reduce early, all of algebra survives the wrap.
- Fast forward, slow backward: gˣ mod p costs ~log x steps; the reverse (discrete log) has no known fast algorithm — the workhorse asymmetry of cryptography.
- Prime moduli make it a field: every non-zero element has an inverse (a⁻¹ ≡ a^(p−2)); powers of a generator orbit all residues with period dividing p−1.
- Diffie–Hellman mixes exponents in public: (gᵇ)ᵃ = (gᵃ)ᵇ — shared secrets with no shared history, and security resting exactly on your Log Hunt experience.
- Best known attacks (baby-step giant-step √p, index calculus) only trim the exponent; elliptic curves keep even those at arm's length.
🎯
Checkpoint: Clock Universe
What is 2⁹ mod 19? (Hint: 2⁹ = 512… and 512 = 26×19 + 18)
- 26
- 0
- 18
- 512
512 mod 19: 19×26 = 494, remainder 18. Notice we never need big numbers: 2⁴=16, 2⁸=256=9 mod 19, 2⁹ = 18 — reduce early, reduce often.
Why is gˣ mod p fast to compute even when x has 256 bits?
- Because mod makes the result small, so everything is small.
- Repeated squaring computes it in ~256 multiply-and-reduce steps.
- Because quantum computers help.
- Because we precompute all powers of g.
Square-and-multiply turns the exponent's binary length into the step count — logarithmic in x. Precomputing all powers is exactly what attackers can't afford.
"Discrete logarithm is hard" means:
- No known efficient algorithm finds x from (g, p, gˣ mod p), even though the reverse direction is trivial.
- Division in modular arithmetic is impossible.
- Logarithms don't exist for primes.
- It has been mathematically proven that no fast algorithm exists.
It's a conjectured asymmetry (a "candidate one-way function"), not a theorem — and note answer 4 is deliberately wrong: no proof exists, which is why post-quantum research matters.
In ZK protocols, what typically plays the role of the secret x?
- The modulus p.
- The base g.
- A hash of the protocol transcript.
- A hidden exponent, with only y = gˣ made public.
The public key is the "output" of the one-way function; the witness is the input. Proving knowledge of the input without revealing it is exactly what's coming in Chapter 6.