Prologue: Three Problems That Seem Impossible

Before we learn any math, consider three problems:

Problem 1: You and a stranger are in a crowded room. Everyone can hear everything you say. How do you agree on a secret number that only you two know — without ever whispering?

Problem 2: You want to send a locked box to someone, but you've never met and you can't share a key in advance. How do you send a message only they can open?

Problem 3: You want to prove to a guard that you know the password to a vault — but you don't want to say the password out loud, because someone might be listening. How do you prove you know it without revealing it?

These three problems sound impossible. Yet cryptography solves all three, using math you can learn starting now.

Problem 1 is solved by Diffie-Hellman key exchange. Problem 2 is solved by public-key encryption (ElGamal, RSA). Problem 3 is solved by zero-knowledge proofs.

Every concept in this guide exists to solve one of these three problems. When the math gets abstract, return here and remember: we're building toward something practical.

---

Part I: The Language of Secrets

Chapter 1: Modular Arithmetic — The World Cryptography Lives In

The Clock Intuition

You already use modular arithmetic every day. If it's 10:00 and you add 5 hours, what time is it?

10 + 5 = 15 → but clocks only go to 12 → 15 - 12 = 3

So 15 on a 12-hour clock is 3. We write this:

15 ≡ 3 (mod 12)

Read it as: "15 is congruent to 3, modulo 12." It means 15 and 3 have the same remainder when divided by 12.

The Formal Definition

For any integers a, b, and a positive integer n:

a ≡ b (mod n)    means    n divides (a - b)

Equivalently: a and b have the same remainder when divided by n.

23 ≡ 3 (mod 10)     because 23 - 3 = 20, and 10 divides 20
47 ≡ 2 (mod 5)      because 47 - 2 = 45, and 5 divides 45
100 ≡ 0 (mod 25)    because 100 - 0 = 100, and 25 divides 100

Why Cryptography Uses Modular Arithmetic

Two reasons:

Reason 1: It creates a bounded world. When you compute mod n, results stay between 0 and n-1. No matter how large the input, the output is contained. This is essential for computers working with fixed-size numbers.

Reason 2: It creates a trapdoor. Going forward (computing a^x mod n) is easy. Going backward (finding x from the result) is extraordinarily hard. This asymmetry — easy one way, hard the other — is the beating heart of every cryptographic system.

Arithmetic in the Modular World

All standard operations still work, but the results wrap around:

Addition:

(8 + 7) mod 11 = 15 mod 11 = 4

Subtraction:

(3 - 9) mod 11 = -6 mod 11 = 5

(Why 5? Because -6 + 11 = 5, and 5 is the positive representative.)

Multiplication:

(7 × 8) mod 11 = 56 mod 11 = 1

The crucial property: You can reduce at ANY point during a calculation. This prevents numbers from exploding:

Instead of computing 7^4 = 2401 then reducing mod 11:
    7^1 = 7
    7^2 = 49 ≡ 5 (mod 11)       ← reduce early
    7^3 = 7 × 5 = 35 ≡ 2 (mod 11)   ← reduce again
    7^4 = 7 × 2 = 14 ≡ 3 (mod 11)   ← reduce again

The answer is 3. We never had to handle 2401. This is how cryptographic computations with 2048-bit numbers remain feasible.

Practice: Build Your Modular Intuition

Compute these by hand:

(a) 37 mod 13 = ?       → 37 = 2×13 + 11  → answer: 11
(b) (9 + 8) mod 13 = ?  → 17 mod 13        → answer: 4
(c) (6 × 7) mod 13 = ?  → 42 mod 13        → 42 = 3×13 + 3 → answer: 3
(d) 2^10 mod 13 = ?     → let's do it step by step:
    2^1 = 2
    2^2 = 4
    2^4 = 4^2 = 16 ≡ 3 (mod 13)
    2^8 = 3^2 = 9 (mod 13)
    2^10 = 2^8 × 2^2 = 9 × 4 = 36 ≡ 10 (mod 13)

That last computation used a trick: splitting 10 = 8 + 2. That trick is the seed of fast exponentiation, which we'll cover in Chapter 4.

---

Chapter 2: The Euclidean Algorithm — Finding Common Ground

What is the GCD?

The Greatest Common Divisor of two numbers a and b — written gcd(a, b) — is the largest number that divides both of them.

gcd(48, 18) = 6     because 6 divides both 48 and 18, and nothing larger does
gcd(35, 15) = 5     because 5 divides both
gcd(17, 13) = 1     because 17 and 13 share no common factor except 1

When gcd(a, b) = 1, we say a and b are coprime (or relatively prime). This concept is central to cryptography — modular inverses only exist for coprime pairs.

The Euclidean Algorithm

Listing all divisors is slow. Euclid discovered (circa 300 BC) a fast method based on one key insight:

gcd(a, b) = gcd(b, a mod b)

Replace the larger number with the remainder. Repeat until the remainder is 0. The last nonzero value is the GCD.

Example: gcd(161, 28)

Step 1:  gcd(161, 28)
         161 = 5 × 28 + 21      →  gcd(28, 21)

Step 2:  gcd(28, 21)
         28 = 1 × 21 + 7        →  gcd(21, 7)

Step 3:  gcd(21, 7)
         21 = 3 × 7 + 0         →  gcd(7, 0)

Remainder is 0. Stop.
gcd(161, 28) = 7

The Extended Euclidean Algorithm

This is where it gets powerful. The extended version doesn't just find gcd(a, b) — it also finds integers x and y such that:

ax + by = gcd(a, b)

This is called Bezout's identity, and it's how we compute modular inverses.

Example: gcd(161, 28) with back-substitution

From the forward pass:

161 = 5 × 28 + 21    →   21 = 161 - 5 × 28      ... (i)
28  = 1 × 21 + 7     →   7  = 28 - 1 × 21       ... (ii)

Now substitute backward:

From (ii):  7 = 28 - 1 × 21
Substitute (i) for 21:
            7 = 28 - 1 × (161 - 5 × 28)
            7 = 28 - 161 + 5 × 28
            7 = 6 × 28 - 1 × 161

So: 161 × (-1) + 28 × 6 = 7

We found x = -1 and y = 6 such that 161x + 28y = 7 = gcd(161, 28).

Why does this matter for cryptography? Because when gcd(a, n) = 1, this equation gives us the modular inverse of a mod n. That inverse is essential for decryption.

---

Chapter 3: Modular Inverses — Division in the Modular World

The Problem

In regular arithmetic, the inverse of 5 is 1/5 (because 5 × 1/5 = 1).

In modular arithmetic, fractions don't exist. So how do we "divide"?

We find a number a^(-1) such that:

a × a^(-1) ≡ 1 (mod n)

This a^(-1) is the modular inverse of a mod n.

Example: Find 5^(-1) mod 11

We need x such that 5x ≡ 1 (mod 11).

Method 1: Brute force (small numbers only)

5 × 1 = 5 mod 11 = 5    ✗
5 × 2 = 10 mod 11 = 10   ✗
5 × 3 = 15 mod 11 = 4    ✗
5 × 4 = 20 mod 11 = 9    ✗
5 × 5 = 25 mod 11 = 3    ✗
5 × 6 = 30 mod 11 = 8    ✗
5 × 7 = 35 mod 11 = 2    ✗
5 × 8 = 40 mod 11 = 7    ✗
5 × 9 = 45 mod 11 = 1    ✓

So 5^(-1) ≡ 9 (mod 11).

Method 2: Extended Euclidean Algorithm (works for any size)

Apply the extended GCD to find x in: 5x + 11y = 1

11 = 2 × 5 + 1     →   1 = 11 - 2 × 5

So x = -2. But we want a positive answer mod 11: -2 + 11 = 9.

Therefore 5^(-1) ≡ 9 (mod 11). Same answer, much faster.

Method 3: Fermat's Little Theorem (when n is prime)

If p is prime and gcd(a, p) = 1:

a^(-1) ≡ a^(p-2) (mod p)

So 5^(-1) mod 11 = 5^9 mod 11.

5^1 = 5
5^2 = 25 ≡ 3 (mod 11)
5^4 = 3^2 = 9 (mod 11)
5^8 = 9^2 = 81 ≡ 4 (mod 11)
5^9 = 5^8 × 5^1 = 4 × 5 = 20 ≡ 9 (mod 11)

Again: 5^(-1) ≡ 9 (mod 11).

When Does an Inverse Exist?

a has an inverse mod n if and only if gcd(a, n) = 1.

3 has an inverse mod 11?   gcd(3, 11) = 1    → YES
6 has an inverse mod 9?    gcd(6, 9) = 3     → NO
7 has an inverse mod 13?   gcd(7, 13) = 1    → YES

This is why cryptography uses prime moduli. When p is prime, EVERY number from 1 to p-1 is coprime to p, so every element has an inverse. The arithmetic is clean and complete.

Why Inverses Matter for Cryptography

Encryption often looks like: ciphertext = message × key mod n

Decryption needs to undo that: message = ciphertext × key^(-1) mod n

Without modular inverses, there's no decryption. The extended Euclidean algorithm is the decryption key's engine.

---

Chapter 4: Fast Exponentiation — The Speed Trick

The Problem

Cryptography constantly computes things like g^x mod p where x might be 2048 bits long. That's roughly 10^617. You can't multiply g by itself that many times.

The Binary Method (Repeated Squaring)

The insight: any exponent can be written in binary, and binary gives you a recipe using only squaring and multiplication.

Example: Compute 3^41 mod 101

Step 1: Write 41 in binary.

41 = 32 + 8 + 1 = 2^5 + 2^3 + 2^0
41 in binary: 101001

Step 2: Build a table of successive squares of 3 mod 101.

3^1  = 3
3^2  = 9
3^4  = 9^2 = 81
3^8  = 81^2 = 6561 ≡ 6561 mod 101 = 6561 - 64×101 = 6561 - 6464 = 97
3^16 = 97^2 = 9409 ≡ 9409 mod 101 = 9409 - 93×101 = 9409 - 9393 = 16
3^32 = 16^2 = 256 ≡ 256 mod 101 = 256 - 2×101 = 54

Step 3: Multiply together the powers that appear in the binary expansion.

3^41 = 3^32 × 3^8 × 3^1
     = 54 × 97 × 3 (mod 101)
     = 54 × 97 = 5238 ≡ 5238 mod 101 = 5238 - 51×101 = 5238 - 5151 = 87
     = 87 × 3 = 261 ≡ 261 mod 101 = 261 - 2×101 = 59

3^41 ≡ 59 (mod 101)

We did this in 7 multiplications instead of 40. For a 2048-bit exponent, we'd need about 3000 multiplications instead of 2^2048. That's the difference between "takes a millisecond" and "takes longer than the age of the universe."

The Algorithm

function binexpmod(base, exponent, modulus):
    result = 1
    base = base mod modulus

    while exponent > 0:
        if exponent is odd:
            result = (result × base) mod modulus
        exponent = exponent >> 1          (right-shift = divide by 2)
        base = (base × base) mod modulus  (square the base)

    return result

This processes the binary digits of the exponent from right to left. Each bit triggers a squaring, and if the bit is 1, also a multiplication.

Connection to Real Code

In the TypeScript implementations you've studied, binexpmod is the workhorse function. Every protocol — Diffie-Hellman, ElGamal, RSA, digital signatures — calls it. It's the most important algorithm in practical cryptography.

---

Part II: The Architecture — Why Primes and Groups

Chapter 5: Prime Numbers — The Atoms of Arithmetic

What is a Prime?

A prime number is a positive integer greater than 1 that is divisible only by 1 and itself.

Primes:     2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ...
Not primes: 4=2×2, 6=2×3, 9=3×3, 15=3×5, 21=3×7, ...

The number 1 is not prime (by convention). The number 2 is the only even prime.

The Fundamental Theorem of Arithmetic

Every integer greater than 1 has a unique prime factorization.

360 = 2^3 × 3^2 × 5
1001 = 7 × 11 × 13
2816 = 2^8 × 11

No matter how you factor a number, you always end up with the same primes. This uniqueness is what makes primes the "atoms" of number theory — everything is built from them.

Why Primes Are Central to Cryptography

For RSA: Security rests on the fact that multiplying two large primes is easy, but factoring the result back into those primes is hard.

Easy:    p × q = N     (multiplication: instant)
Hard:    N → p, q      (factoring: years/centuries for large N)

For Diffie-Hellman and ElGamal: Arithmetic mod a prime p gives you a field — a mathematical structure where addition, subtraction, multiplication, and division ALL work cleanly. Composite moduli have "dead spots" where division breaks.

For Elliptic Curves: The curves are defined over prime fields, where every point has a well-defined inverse.

How Many Primes Exist?

Infinitely many (Euclid proved this ~300 BC). Among the first N integers, roughly N/ln(N) are prime. Primes thin out but never stop.

For cryptographic purposes, we need primes with 256 bits (~77 digits) for elliptic curves and 1024-2048 bits (~300-600 digits) for RSA. Finding primes this large is efficient because we have fast probabilistic tests (Miller-Rabin).

---

Chapter 6: Groups — When Operations Behave

What is a Group?

A group is a set G with an operation • that follows four rules:

If you also have commutativity (a • b = b • a), the group is called abelian.

The Group That Powers Cryptography

The set {1, 2, 3, ..., p-1} under multiplication mod p (where p is prime) forms a group. It's written as F_p* or (Z/pZ)*.

Let's verify with p = 11. Our set is {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.

Closure: Any product of two elements mod 11 gives another element in {1,...,10}.

7 × 8 = 56 ≡ 1 (mod 11)    ← still in the set
6 × 4 = 24 ≡ 2 (mod 11)    ← still in the set

Identity: 1 is the identity (a × 1 = a for all a).

Inverses: Every element has an inverse:

1^(-1) = 1      (1 × 1 = 1)
2^(-1) = 6      (2 × 6 = 12 ≡ 1)
3^(-1) = 4      (3 × 4 = 12 ≡ 1)
5^(-1) = 9      (5 × 9 = 45 ≡ 1)
7^(-1) = 8      (7 × 8 = 56 ≡ 1)
10^(-1) = 10    (10 × 10 = 100 ≡ 1)

Every element pairs with another (or itself) to produce 1. The group has p - 1 = 10 elements.

Why Groups Matter

Groups give you a guaranteed structure. When you know something is a group, you know inverses exist, you know operations are well-behaved, and you can use powerful theorems. Cryptographic protocols are designed to operate inside groups because the mathematical guarantees translate into security guarantees.

Rings and Fields — The Extended Family

A ring has two operations (addition and multiplication) where addition forms a group and multiplication is associative. The integers Z with + and × form a ring.

A field is a ring where multiplication (excluding 0) also forms a group. Every nonzero element has a multiplicative inverse.

Z/11Z = {0, 1, 2, ..., 10} with + and × mod 11

This is a field because 11 is prime. Every nonzero element has an inverse. You can add, subtract, multiply, and divide freely (except by 0). Cryptography lives in fields because it needs all four operations.

When the modulus is NOT prime, you don't get a field:

In Z/12Z: gcd(4, 12) = 4 ≠ 1, so 4 has no inverse mod 12.
4 × 3 = 12 ≡ 0 (mod 12) — two nonzero numbers multiply to zero!

These "zero divisors" break cryptographic operations. That's why we use primes.

---

Chapter 7: Cyclic Groups and Generators — The Power Spiral

Order of an Element

The order of an element g in a group is the smallest positive integer k such that:

g^k ≡ 1 (mod p)

It's the number of steps before the powers of g cycle back to the identity.

Example in F_13 (the group {1, 2, ..., 12} under × mod 13):*

What's the order of 3?

3^1  ≡ 3 (mod 13)
3^2  ≡ 9
3^3  ≡ 27 ≡ 1      ← hit 1 after 3 steps

Order of 3 mod 13 is 3.

What's the order of 2?

2^1  ≡ 2
2^2  ≡ 4
2^3  ≡ 8
2^4  ≡ 16 ≡ 3
2^5  ≡ 6
2^6  ≡ 12
2^7  ≡ 24 ≡ 11
2^8  ≡ 22 ≡ 9
2^9  ≡ 18 ≡ 5
2^10 ≡ 10
2^11 ≡ 20 ≡ 7
2^12 ≡ 14 ≡ 1      ← hit 1 after 12 steps

Order of 2 mod 13 is 12. That's the maximum possible (p - 1 = 12).

Fermat's Little Theorem — The Universal Ceiling

For any a not divisible by prime p:

a^(p-1) ≡ 1 (mod p)

This tells you: every element's order divides p - 1. For p = 13, every element's order divides 12.

Possible orders mod 13: 1, 2, 3, 4, 6, 12   (the divisors of 12)

Generators and Cyclic Groups

An element whose order equals p - 1 is called a generator (or primitive root). Its powers produce EVERY element of the group.

We just showed that 2 is a generator mod 13 (order = 12 = p - 1). Its powers produce:

2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1

That's all of {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}. Every element appears exactly once.

A group where a single element can generate all others through repeated application of the operation is called cyclic. The multiplicative group mod p is always cyclic (a deep theorem of number theory).

Why Generators Matter for Cryptography

In Diffie-Hellman and ElGamal, you choose a generator g. Because g generates ALL elements, every number from 1 to p-1 can be written as g^x for some x. This means:

• Given x, computing g^x mod p is easy (fast exponentiation).

• Given g^x, finding x is hard (the Discrete Logarithm Problem).

If g were NOT a generator, it would only produce a subset of elements. An attacker would know the secret x comes from a smaller range, making it easier to find. Generators maximize the search space.

---

Chapter 8: Primitive Roots — The Complete Picture

Formal Definition

g is a primitive root mod p if the multiplicative order of g is p - 1. Equivalently: the powers g^1, g^2, ..., g^(p-1) produce all of {1, 2, ..., p-1} modulo p.

How to Test if g is a Primitive Root

You don't need to compute all p-1 powers. There's a shortcut:

g is NOT a primitive root mod p if and only if g^((p-1)/q) ≡ 1 (mod p) for some prime factor q of p-1.

So the test is: factor p-1, and for each prime factor q, check whether g^((p-1)/q) ≡ 1. If none of them equal 1, g IS a primitive root.

Example: Is 6 a primitive root mod 13?

p - 1 = 12 = 2^2 × 3. Prime factors: 2 and 3.

Check (p-1)/2 = 6:

6^6 mod 13:
  6^1 = 6
  6^2 = 36 ≡ 10
  6^3 = 60 ≡ 8     (60 = 4×13 + 8)
  6^6 = 8^2 = 64 ≡ 12    (64 = 4×13 + 12)

6^6 ≡ 12 ≡ -1 (mod 13) ≠ 1 ✓

Check (p-1)/3 = 4:

6^4 = 6 × 8 = 48 ≡ 9   (48 = 3×13 + 9)

6^4 ≡ 9 (mod 13) ≠ 1 ✓

Neither equals 1, so 6 IS a primitive root mod 13.

How Many Primitive Roots Exist?

For a prime p, there are exactly φ(p-1) primitive roots, where φ is Euler's totient function (the count of numbers from 1 to n that are coprime to n).

p = 13:  p-1 = 12,  φ(12) = 4 primitive roots
p = 23:  p-1 = 22,  φ(22) = 10 primitive roots
p = 101: p-1 = 100, φ(100) = 40 primitive roots

Primitive roots are plentiful. For cryptographic primes (thousands of bits), there are astronomically many generators to choose from.

The Discrete Logarithm Table

When g is a primitive root mod p, every element h in {1, ..., p-1} can be written as g^x for a unique x in {0, ..., p-2}. This x is called the discrete logarithm of h base g.

Using g = 2 mod 13:

x:    1   2   3   4   5   6   7   8   9   10  11  12
2^x:  2   4   8   3   6   12  11  9   5   10  7   1

Reading this table forward (x → 2^x) is easy. Reading it backward (2^x → x) is the discrete logarithm. For small numbers, you can just look it up. For large numbers, no one knows how to do it efficiently. This is the Discrete Logarithm Problem.

---

Part III: The Hard Problems

Chapter 9: One-Way Functions — The Foundation of All Cryptography

The Core Concept

A one-way function is easy to compute but hard to invert.

Forward:   input ——easy——→ output
Backward:  output ——hard——→ input

Examples from everyday life:

• Mixing paint colors is easy. Unmixing them is (practically) impossible.

• Breaking a plate is easy. Reassembling it perfectly is extremely hard.

• Computing g^x mod p is easy. Finding x from the result is hard.

The Two Great One-Way Functions of Cryptography

1. The Discrete Logarithm:

Easy:  given g, x, p  →  compute g^x mod p
Hard:  given g, y, p  →  find x such that g^x ≡ y (mod p)

2. Integer Factorization:

Easy:  given p, q (large primes)  →  compute N = p × q
Hard:  given N  →  find p and q

Every major cryptographic protocol rests on the assumed hardness of one of these two problems (or their elliptic curve variants).

Trapdoor Functions

A trapdoor one-way function has a secret piece of information that makes the hard direction easy again.

In RSA:

• Forward (encrypt): anyone can compute c = m^e mod N (using the public key)

• Backward (decrypt): recovering m from c requires knowing the factorization of N

• The trapdoor: knowing p and q makes decryption efficient

This is the key insight: the function is hard for everyone EXCEPT the person who has the trapdoor. That person can efficiently invert what no one else can.

---

Chapter 10: The Discrete Logarithm Problem — The Trapdoor in Detail

Statement of the Problem

Given:

• A large prime p

• A generator g of F_p*

• A value h in {1, ..., p-1}

Find the integer x such that:

g^x ≡ h (mod p)

This x is called log_g(h) — the discrete logarithm of h base g.

A Small Example

Let p = 23, g = 5 (which is a primitive root mod 23).

If someone tells you h = 8, find x such that 5^x ≡ 8 (mod 23).

5^1  = 5
5^2  = 25 ≡ 2
5^3  = 10
5^4  = 50 ≡ 4
5^5  = 20
5^6  = 100 ≡ 8    ← found it!

So x = 6. This was easy because 23 is tiny. With a 256-digit prime, there's no known way to do this efficiently.

Properties of the Discrete Logarithm

The discrete log obeys the same rules as ordinary logarithms:

log_g(a × b) = log_g(a) + log_g(b)    (mod p-1)
log_g(a^k)   = k × log_g(a)           (mod p-1)
log_g(1)     = 0
log_g(g)     = 1

These properties mirror the familiar rules: "the log of a product is the sum of the logs" and "the log of a power is the exponent times the log."

This mirroring creates an isomorphism (a structure-preserving map):

(F_p*, ×)  ←——log_g——→  (Z_{p-1}, +)
             ←——g^(·)——

Multiplication in F_p*  corresponds to  Addition in Z_{p-1}
Powers in F_p*          corresponds to  Scalar multiplication in Z_{p-1}

In the exponent world, multiplication becomes addition. This is exactly the structure that powers Diffie-Hellman and ElGamal.

Why It's Hard

For a 2048-bit prime p, the group F_p* has roughly 2^2048 elements. The best known algorithms for DLP (like the Number Field Sieve) run in sub-exponential time — much faster than brute force, but still impractical for properly chosen parameters.

Current security recommendations:

• 2048-bit primes for DLP-based systems (Diffie-Hellman, ElGamal)

• 256-bit primes for elliptic curve DLP (same security, smaller numbers)

---

Chapter 11: Diffie-Hellman Key Exchange — Solving Problem 1

Remember Problem 1? Two strangers in a crowded room need to agree on a shared secret while everyone listens. Here's how.

The Setup (Public Information)

Alice and Bob publicly agree on:

• A large prime p

• A generator g of F_p*

Everyone — including eavesdroppers — knows p and g.

The Protocol

Alice                                    Bob
─────                                    ───
Picks secret a                           Picks secret b
Computes A = g^a mod p                   Computes B = g^b mod p
         ──── sends A ────→
         ←──── sends B ────

Computes: key = B^a mod p                Computes: key = A^b mod p

Why They Get the Same Key

Alice computes:  B^a = (g^b)^a = g^(ba) (mod p)
Bob computes:    A^b = (g^a)^b = g^(ab) (mod p)

Since ab = ba, both arrive at g^(ab) mod p. They share the same secret key.

Why Eavesdroppers Can't

An eavesdropper sees: g, p, A = g^a, and B = g^b.

To find the shared key g^(ab), they would need either a or b. Finding a from g^a is the Discrete Logarithm Problem — believed to be computationally infeasible for large p.

A Complete Numerical Example

Let p = 23, g = 5.

Alice picks a = 6.
  A = 5^6 mod 23 = 15625 mod 23 = 8      (15625 = 679×23 + 8)

Bob picks b = 15.
  B = 5^15 mod 23 = ?
  Let's compute step by step:
    5^1 = 5
    5^2 = 2       (25 mod 23)
    5^4 = 4       (2^2 mod 23)
    5^8 = 16      (4^2 mod 23)
    5^15 = 5^8 × 5^4 × 5^2 × 5^1 = 16 × 4 × 2 × 5 = 640 mod 23
    640 = 27×23 + 19
  B = 19

Alice computes: key = B^a = 19^6 mod 23
    19^1 = 19
    19^2 = 361 mod 23 = 361 - 15×23 = 361 - 345 = 16
    19^3 = 19 × 16 = 304 mod 23 = 304 - 13×23 = 304 - 299 = 5
    19^6 = 5^2 = 25 mod 23 = 2
  key = 2

Bob computes: key = A^b = 8^15 mod 23
    8^1 = 8
    8^2 = 64 mod 23 = 64 - 2×23 = 18
    8^4 = 18^2 = 324 mod 23 = 324 - 14×23 = 324 - 322 = 2
    8^8 = 2^2 = 4
    8^15 = 8^8 × 8^4 × 8^2 × 8^1 = 4 × 2 × 18 × 8 = 1152 mod 23
    1152 = 50×23 + 2
  key = 2

Both got key = 2. ✓

An eavesdropper knows g=5, p=23, A=8, B=19. To find the shared key, they'd need to solve 5^a ≡ 8 (mod 23) or 5^b ≡ 19 (mod 23). For a 2048-bit prime, this is infeasible.

The Mathematical Heart

This protocol works because of the power-of-a-power law of exponents:

(g^a)^b = g^(a×b) = g^(b×a) = (g^b)^a

Alice and Bob each have ONE exponent. The eavesdropper has ZERO. Computing g^(ab) from g^a and g^b without knowing either a or b is called the Computational Diffie-Hellman Problem, and it's believed to be as hard as the DLP.

---

Chapter 12: ElGamal Encryption — Solving Problem 2

Diffie-Hellman lets two parties agree on a shared key. But what if Alice wants to send a message to Bob without any back-and-forth? ElGamal solves this.

Key Generation (Bob does this once)

1. Choose a large prime p and generator g (public)
2. Pick a secret key:  a  (private — only Bob knows this)
3. Compute public key:  A = g^a mod p  (public)

Bob publishes (p, g, A). He keeps a secret.

Encryption (Alice does this)

Alice wants to send message m (a number between 1 and p-1).

1. Pick a random ephemeral key k
2. Compute c1 = g^k mod p
3. Compute c2 = m × A^k mod p
4. Send (c1, c2) to Bob

Decryption (Bob does this)

1. Compute c1^a mod p           (this equals g^(ak) mod p)
2. Compute (c1^a)^(-1) mod p    (the modular inverse)
3. Recover m = c2 × (c1^a)^(-1) mod p

Why It Works

c2 × (c1^a)^(-1)
= [m × A^k] × [(g^k)^a]^(-1)           (substituting definitions)
= [m × (g^a)^k] × [g^(ak)]^(-1)         (A = g^a)
= [m × g^(ak)] × g^(-ak)                (inverse cancels)
= m × g^(ak - ak)
= m × g^0
= m × 1
= m

The random k "scrambles" the message, and Bob's secret a lets him unscramble it. An eavesdropper sees c1 = g^k and c2 = m × A^k but can't extract m without knowing either a or k.

Numerical Example

Let p = 23, g = 5, Bob's secret a = 6, so A = 5^6 mod 23 = 8.

Alice wants to send m = 17.

Alice picks random k = 3.
  c1 = 5^3 mod 23 = 125 mod 23 = 10    (125 = 5×23 + 10)
  c2 = 17 × 8^3 mod 23 = 17 × 512 mod 23
     = 17 × (512 mod 23) = 17 × 6 = 102 mod 23 = 10    (512 = 22×23 + 6, 102 = 4×23 + 10)
  Alice sends: (c1, c2) = (10, 10)

Bob decrypts:
  s = c1^a mod 23 = 10^6 mod 23
    10^1 = 10
    10^2 = 100 mod 23 = 8     (100 = 4×23 + 8)
    10^3 = 80 mod 23 = 11     (80 = 3×23 + 11)
    10^6 = 11^2 = 121 mod 23 = 6    (121 = 5×23 + 6)
  s = 6

  s^(-1) mod 23: need x such that 6x ≡ 1 (mod 23)
    6 × 4 = 24 ≡ 1 (mod 23)   →  s^(-1) = 4

  m = c2 × s^(-1) = 10 × 4 = 40 mod 23 = 17  ✓

Bob recovers m = 17. The ciphertext (10, 10) is meaningless without Bob's secret a = 6.

---

Chapter 13: RSA — The Other Trapdoor

RSA uses a different one-way function: integer factorization instead of discrete logarithms.

Key Generation

1. Choose two large secret primes: p, q
2. Compute N = p × q                           (public)
3. Compute φ(N) = (p-1)(q-1)                   (secret — requires knowing p and q)
4. Choose public exponent e with gcd(e, φ(N)) = 1  (public; commonly e = 65537)
5. Compute private exponent d = e^(-1) mod φ(N)    (secret — the trapdoor)

Public key: (N, e) Private key: d

Encryption and Decryption

Encrypt:  c = m^e mod N     (anyone can do this with the public key)
Decrypt:  m = c^d mod N     (only the holder of d can do this)

Why It Works

By Euler's theorem: for any m coprime to N,

m^(φ(N)) ≡ 1 (mod N)

Since d × e ≡ 1 (mod φ(N)), we have d × e = 1 + k × φ(N) for some integer k.

c^d = (m^e)^d = m^(ed) = m^(1 + k×φ(N)) = m × (m^φ(N))^k ≡ m × 1^k = m (mod N)

Numerical Example

Choose p = 11, q = 23.
N = 11 × 23 = 253
φ(N) = 10 × 22 = 220

Choose e = 3.    (gcd(3, 220) = 1 ✓)
Find d: 3d ≡ 1 (mod 220)
  220 = 73 × 3 + 1  →  1 = 220 - 73 × 3  →  d = -73 ≡ 147 (mod 220)

Public key: (253, 3)
Private key: 147

Encrypt m = 165:
  c = 165^3 mod 253
    165^2 = 27225 mod 253 = 27225 - 107×253 = 27225 - 27071 = 154
    165^3 = 165 × 154 = 25410 mod 253 = 25410 - 100×253 = 25410 - 25300 = 110
  c = 110

Decrypt c = 110:
  m = 110^147 mod 253    (use fast exponentiation)
  ... after computation ...
  m = 165 ✓

The Security

An attacker knows N = 253 and e = 3. To find d, they'd need φ(N), which requires factoring N into p and q. For N with 2048+ bits, factoring is infeasible with current technology.

RSA vs DLP-Based Systems

---

Chapter 14: Digital Signatures — Proving Identity

The Problem

You receive a message claiming to be from Alice. How do you know Alice actually sent it? And how do you know no one changed it in transit?

Digital signatures solve both problems:

1. Authentication — only Alice could have created the signature

2. Integrity — any change to the message invalidates the signature

The RSA Signature Scheme

Using the same RSA keys:

Signing:     S = m^d mod N     (Alice uses her PRIVATE key)
Verifying:   m' = S^e mod N    (Anyone uses Alice's PUBLIC key)
             Check: m' == m?

Why it works: Since d and e are inverses mod φ(N):

S^e = (m^d)^e = m^(de) ≡ m (mod N)

The crucial asymmetry: Only Alice knows d, so only she can create valid signatures. But anyone can verify them using the public e.

Notice: encryption uses the PUBLIC key to scramble (anyone can encrypt), while signing uses the PRIVATE key to sign (only the owner can sign). They're mirror operations.

Hash-Then-Sign

In practice, you don't sign the entire message. You first hash it (compress it to a fixed-size digest) and then sign the hash:

1. Compute digest = Hash(message)       (e.g., SHA-256)
2. Sign:  signature = digest^d mod N
3. Verify: check that signature^e mod N == Hash(message)

This is faster (you're exponentiating a 256-bit hash instead of a multi-kilobyte message) and more secure (prevents certain mathematical attacks).

Connection to Blockchain

Every transaction on Ethereum is digitally signed. When you send ETH from your wallet:

1. Your wallet software creates the transaction data

2. It hashes the transaction (Keccak-256)

3. It signs the hash with your private key (using ECDSA — elliptic curve signatures)

4. Nodes verify the signature using your public key (derived from your address)

If the signature doesn't match, the transaction is rejected. This is how the network knows YOU authorized the transfer, without ever seeing your private key.

---

Part IV: The Frontier

Chapter 15: Finite Fields — The Complete Playground

Why Fields?

Cryptographic algorithms need all four arithmetic operations: +, -, ×, ÷. A field is the algebraic structure that guarantees all four work correctly.

The most important finite field is F_p (integers mod a prime p). But there are others.

Finite Fields of Prime Order: F_p

F_p = {0, 1, 2, ..., p-1} with arithmetic mod p.

Properties:

• Has exactly p elements

• Every nonzero element has a multiplicative inverse (because p is prime)

• The multiplicative group F_p* = {1, ..., p-1} is cyclic (has generators)

• Has order p - 1

Extension Fields: F_{p^n}

You can also build finite fields with p^n elements (p prime, n > 1). These are constructed using polynomial arithmetic, similar to how complex numbers extend the reals.

For cryptography, the most important extension field is F_{2^n} — used in AES encryption, where all operations are on bytes (8-bit values) in F_{2^8} = GF(256).

The Field Axioms at Work in Cryptography

Every cryptographic operation maps to a field operation:

Understanding fields is understanding WHY all these operations are well-defined and reversible.

---

Chapter 16: Elliptic Curves — Same Security, Smaller Keys

The Problem with Big Numbers

RSA and Diffie-Hellman need 2048-bit keys for adequate security. That's 617 digits. Computations with numbers this large are slow, especially on constrained devices (IoT, smart cards, mobile).

Elliptic curves achieve the SAME security level with 256-bit keys. That's 77 digits. ~8x smaller, dramatically faster.

What is an Elliptic Curve?

An elliptic curve over a field F_p is the set of points (x, y) satisfying:

y^2 = x^3 + ax + b    (mod p)

where 4a^3 + 27b^2 ≠ 0 (this ensures the curve is "smooth" — no cusps or self-intersections).

Plus a special "point at infinity" O that acts as the identity element.

The Group Operation: Point Addition

Here's the remarkable thing: you can "add" two points on the curve to get a third point, and this addition forms a group.

Geometrically (over the real numbers): to add points P and Q, draw a line through them. It intersects the curve at a third point R'. Reflect R' across the x-axis to get R = P + Q.

Algebraically (over F_p): the formulas use only field operations (addition, subtraction, multiplication, division mod p):

Given P = (x1, y1) and Q = (x2, y2), where P ≠ Q:

  slope λ = (y2 - y1) × (x2 - x1)^(-1) mod p

  x3 = λ^2 - x1 - x2  mod p
  y3 = λ × (x1 - x3) - y1  mod p

  P + Q = (x3, y3)

For point doubling (P + P):

  λ = (3 × x1^2 + a) × (2 × y1)^(-1) mod p

The Discrete Logarithm on Elliptic Curves (ECDLP)

Replace "repeated multiplication" with "repeated point addition":

Given generator point G and integer k, compute:
  Q = k × G = G + G + G + ... + G   (k times)

This is EASY (use double-and-add, analogous to square-and-multiply).

The reverse:
  Given G and Q, find k such that Q = k × G

This is the ECDLP — and it's MUCH HARDER than the standard DLP.

The best algorithms for ECDLP are fully exponential (unlike the sub-exponential Number Field Sieve for standard DLP). This means a 256-bit elliptic curve group provides roughly the same security as a 3072-bit standard DLP group.

Ethereum Uses Elliptic Curves

Ethereum uses the secp256k1 curve:

y^2 = x^3 + 7   over F_p    where p = 2^256 - 2^32 - 977

Your Ethereum private key is a 256-bit integer k. Your public key is the point Q = k × G, where G is a fixed generator point. Your address is derived from the hash of your public key.

Every transaction signature uses ECDSA (Elliptic Curve Digital Signature Algorithm) on this curve. The security of your funds rests entirely on the hardness of ECDLP.

---

Chapter 17: Hash Functions — Fingerprinting Everything

What is a Hash Function?

A hash function takes any input (of any size) and produces a fixed-size output:

Hash("hello")           → 2cf24dba5fb0a30e26e83b2ac5b9e29e...  (256 bits)
Hash("hello ")          → 7f83b1657ff1fc53b92dc18148a1d65d...  (totally different!)
Hash(entire Bible text) → e1e3f4d2a5c6b7890123456789abcdef...  (still 256 bits)

Properties

1. Deterministic — Same input always gives the same output

2. One-way — Cannot recover input from output

3. Collision-resistant — Practically impossible to find two inputs with the same output

4. Avalanche effect — Changing one bit of input changes ~50% of output bits

Hash Functions in Blockchain

Hashing is the glue that holds blockchains together:

Transaction hashes: Every transaction is hashed to create a unique identifier.

Block hashes: Each block header contains the hash of the previous block. Change any past transaction → the block hash changes → every subsequent block hash changes → the tampering is obvious.

Merkle trees: Transactions within a block are organized in a hash tree (Merkle tree). This lets you verify that a specific transaction is included in a block by checking only a few hashes, not the entire block.

Address derivation: Your Ethereum address = last 20 bytes of Keccak-256(public key).

Proof of Work: (Pre-merge Ethereum, still Bitcoin) Miners search for a nonce such that Hash(block header + nonce) < target. This requires brute force because hashes are unpredictable.

Keccak-256 vs SHA-256

Bitcoin uses SHA-256. Ethereum uses Keccak-256 (a variant of SHA-3). Both produce 256-bit outputs. Ethereum chose Keccak because it was designed after SHA-2 and uses a fundamentally different internal structure (sponge construction vs Merkle-Damgard), making it resistant to a different class of attacks.

---

Chapter 18: Zero-Knowledge Proofs — Solving Problem 3

This is the most mind-bending concept in cryptography, and also one of the most important for blockchain's future.

The Problem

You want to prove you know something without revealing what you know. This sounds impossible. It's not.

The Cave Analogy (Ali Baba's Cave)

Imagine a circular cave with a locked door in the middle:

        Entrance
           |
      ┌────┴────┐
      │         │
   Left       Right
   Path       Path
      │         │
      └──DOOR───┘
          🔒

Alice claims she knows the password to the door. Bob wants proof but Alice doesn't want to reveal the password.

The protocol:

1. Alice enters the cave and takes a random path (left or right). Bob waits outside.

2. Bob shouts: "Come out the LEFT side!" (or RIGHT — he picks randomly).

3. If Alice knows the password, she can ALWAYS come out the requested side (she opens the door if needed).

4. If Alice DOESN'T know the password, she can only succeed 50% of the time (she can only come out the side she entered from).

Repeat 100 times. If Alice comes out the correct side every time, Bob is convinced (probability of faking: 1/2^100 ≈ 0). But Bob learns nothing about the password itself.

The Three Properties of Zero-Knowledge Proofs

1. Completeness — If the statement is true, an honest prover CAN convince the verifier.

2. Soundness — If the statement is false, no cheating prover can convince the verifier (except with negligible probability).

3. Zero-knowledge — The verifier learns NOTHING beyond the truth of the statement. They can't extract the secret.

The Mathematical Version: Schnorr's Protocol

Here's a real zero-knowledge proof that Alice knows the discrete log x of a public value y = g^x mod p:

Setup: Public values g, p, y. Alice knows secret x such that y = g^x mod p.

Step 1 (Commitment): Alice picks random r, computes t = g^r mod p, sends t to Bob.

Step 2 (Challenge): Bob picks random c, sends it to Alice.

Step 3 (Response): Alice computes s = r + c×x (mod p-1), sends s to Bob.

Verification: Bob checks that g^s ≡ t × y^c (mod p).

Why it works:

g^s = g^(r + cx) = g^r × g^(cx) = g^r × (g^x)^c = t × y^c  ✓

Why it's zero-knowledge: Bob sees t, c, s. But for any specific (c, s) pair, there's a corresponding t that would make the equation hold, regardless of x. Bob could have generated the transcript himself without Alice! So the transcript reveals nothing about x.

Zero-Knowledge Proofs and Blockchain

ZK proofs are revolutionizing blockchain through:

ZK-Rollups (zkSync, StarkNet, Polygon zkEVM): Process thousands of transactions off-chain, then post a single ZK proof on-chain that proves all transactions were valid. The main chain verifies one proof instead of re-executing every transaction. This scales Ethereum by 100x+.

Privacy (Zcash, Tornado Cash): Prove that a transaction is valid (correct amounts, authorized sender) without revealing who sent what to whom. The proof says "this transaction follows all the rules" without exposing the details.

Identity: Prove you're over 18 without revealing your birthdate. Prove you have a certain credential without revealing it. Prove your balance exceeds a threshold without revealing the exact balance.

Types of ZK Systems

zk-SNARKs are the most commonly used in blockchain (Zcash, many rollups). zk-STARKs avoid trusted setup at the cost of larger proofs (StarkNet uses these).

---

Chapter 19: How Blockchains Use All of This

Every concept in this guide appears in a working blockchain. Here's the complete map:

Your Wallet

Private key:  256-bit random integer k
Public key:   Point Q = k × G on secp256k1 (elliptic curve multiplication)
Address:      Keccak-256(Q) — last 20 bytes (hash function)

Concepts used: elliptic curves (Ch 16), hash functions (Ch 17), discrete logarithm (Ch 10)

Sending a Transaction

1. Construct transaction data (to, value, gas, nonce)
2. Hash the transaction:  h = Keccak-256(transaction)
3. Sign with ECDSA:
   - Pick random k
   - Compute R = k × G (elliptic curve point)
   - Compute s = k^(-1) × (h + r×privateKey) mod n
   - Signature: (r, s)
4. Broadcast (transaction, signature)

Concepts used: hash functions (Ch 17), elliptic curves (Ch 16), modular inverse (Ch 3), fast exponentiation (Ch 4)

Verifying a Transaction

1. Recover public key from signature (or have it on record)
2. Verify:  s^(-1) × (h×G + r×Q) should equal R
3. If valid → transaction is authentic and unmodified

Concepts used: modular inverse (Ch 3), elliptic curve arithmetic (Ch 16)

Block Structure

Block Header:
  - Previous block hash     ← hash chain (Ch 17)
  - Merkle root of txns     ← Merkle tree of hash commitments (Ch 17)
  - State root              ← Merkle Patricia Trie hash (Ch 17)
  - Timestamp, number, etc.

Consensus (Proof of Stake)

Validators sign attestations using BLS signatures (a signature scheme based on elliptic curve pairings — an advanced form of Ch 16). Multiple signatures can be aggregated into one, saving space.

Layer 2 Scaling (ZK-Rollups)

1. Collect 1000 transactions off-chain
2. Execute them all, recording state transitions
3. Generate a ZK proof (Ch 18) that all 1000 transitions are valid
4. Post the proof on-chain (just one transaction)
5. Ethereum verifies the single proof instead of 1000 transactions

Concepts used: zero-knowledge proofs (Ch 18), elliptic curves (Ch 16), hash functions (Ch 17), finite fields (Ch 15)

Smart Contract Verification

When you deploy a Solidity contract, the bytecode is hashed and stored. When someone calls a function:

1. Function selector = first 4 bytes of Keccak-256(function signature)
2. EVM looks up the selector to find the right function
3. Executes the function within the gas limit
4. State changes are committed to the Merkle Patricia Trie

Even smart contract function dispatch uses hashing.

---

The Complete Dependency Map

Everything builds on what came before:

Modular Arithmetic (Ch 1)
    │
    ├── Euclidean Algorithm (Ch 2)
    │       │
    │       └── Modular Inverses (Ch 3)
    │               │
    │               ├── ElGamal Decryption (Ch 12)
    │               ├── RSA Key Generation (Ch 13)
    │               └── ECDSA Signing (Ch 16)
    │
    ├── Fast Exponentiation (Ch 4)
    │       │
    │       └── (Used in EVERY protocol)
    │
    ├── Prime Numbers (Ch 5)
    │       │
    │       ├── Finite Fields (Ch 6, 15)
    │       │       │
    │       │       ├── Elliptic Curves (Ch 16)
    │       │       │       │
    │       │       │       ├── ECDSA → Ethereum Signatures
    │       │       │       ├── BLS → Consensus Signatures
    │       │       │       └── Pairings → ZK-SNARKs
    │       │       │
    │       │       └── Groups (Ch 6-8)
    │       │               │
    │       │               ├── Generators / Primitive Roots (Ch 7-8)
    │       │               │       │
    │       │               │       └── DLP (Ch 10)
    │       │               │           │
    │       │               │           ├── Diffie-Hellman (Ch 11)
    │       │               │           ├── ElGamal (Ch 12)
    │       │               │           └── Digital Signatures (Ch 14)
    │       │               │
    │       │               └── Cyclic Group Structure → ZK Proofs (Ch 18)
    │       │
    │       └── RSA Factoring (Ch 13)
    │
    └── Hash Functions (Ch 17)
            │
            ├── Address Derivation
            ├── Merkle Trees → Block Structure
            ├── Transaction Hashing → Signatures
            └── ZK-STARKs (Ch 18)

---

Epilogue: Your Study Path Forward

Phase 1: Foundations (Where You Are Now)

Master Chapters 1-4. You should be able to:

• Compute modular arithmetic by hand

• Run the Euclidean algorithm

• Find modular inverses

• Perform fast exponentiation

Practice: Write code (TypeScript, Python, or pen-and-paper) for each algorithm. Verify your hand calculations.

Phase 2: Algebraic Structures

Master Chapters 5-8. You should be able to:

• Determine if a number is a primitive root

• Find the order of an element in a group

• Explain why primes create fields

• Identify generators of cyclic groups

Practice: Build the complete power table for F_23*. Find all generators. Verify Fermat's Little Theorem.

Phase 3: Cryptographic Protocols

Master Chapters 9-14. You should be able to:

• Walk through Diffie-Hellman with concrete numbers

• Encrypt and decrypt with ElGamal by hand

• Explain RSA key generation, encryption, and decryption

• Explain why each protocol is secure

Practice: Implement Diffie-Hellman and ElGamal in code. Encrypt a message, then decrypt it. Verify the shared secret matches.

Phase 4: Advanced Topics

Study Chapters 15-18. You should be able to:

• Explain why elliptic curves offer better efficiency

• Describe how hash functions secure blockchain structure

• Explain zero-knowledge proofs at the cave-analogy level

• Map every concept to its role in Ethereum

Practice: Read the secp256k1 specification. Trace through an Ethereum transaction from wallet to block inclusion.

Recommended Resources

• "An Introduction to Mathematical Cryptography" by Hoffstein, Pipher, Silverman — the textbook that covers Phases 1-3 rigorously

• ethereum.org — for connecting the math to the actual protocol

• Remix IDE — deploy smart contracts to see the crypto stack in action

• ZKP.science — curated resources for zero-knowledge proofs

• Vitalik Buterin's blog posts — especially the ones on elliptic curves and ZK proofs, written for a technical but not specialist audience