---

Part 0: What Is Cryptography?

Cryptography is the art of keeping secrets. That's it.

You have a message. You want only the right person to read it. Cryptography gives you the tools to make that happen.

But before we talk about keeping secrets, we need to talk about something even more basic: how we represent information.

---

Chapter 1: Encoding and Decoding — Changing the Shape of Information

What Is Encoding?

Encoding is converting information from one form to another. It has nothing to do with secrecy. Anyone who knows the format can reverse it.

You encode things every day:

• When you write the word "five" as the number 5, that's encoding.

• When a traffic light shows red to mean "stop," that's encoding.

• When your phone converts your voice into radio waves, that's encoding.

In computing, everything must eventually become numbers. Computers only understand numbers. So we need systems to turn letters, symbols, and words into numbers.

ASCII — The Simplest Encoding

ASCII assigns a number to every character on your keyboard:

Letter:   H    e    l    l    o
ASCII:    72   101  108  108  111

That's all encoding is. A lookup table. No secret. Anyone who has the ASCII table can convert back and forth.

Other Common Encodings

What Is Decoding?

Decoding is just encoding in reverse. You take the encoded form and convert it back to the original.

Encode: "Hello" → 72 101 108 108 111
Decode: 72 101 108 108 111 → "Hello"

The Golden Rule

Encoding is NOT encryption. There's no secret. No key. Anyone can decode it. If someone says "I secured the data by encoding it in Base64," that's like saying "I hid my diary by writing it in French." Anyone who reads French can read it.

---

Chapter 2: Encryption and Decryption — Actually Keeping Secrets

What Is Encryption?

Encryption takes readable information (called plaintext) and scrambles it into unreadable nonsense (called ciphertext) using a key.

Without the key, the ciphertext is meaningless. With the key, you can reverse the process and get the original message back.

Plaintext + Key → [Encryption] → Ciphertext
"HELLO"   + 3   → [Shift each letter by 3] → "KHOOR"

What Is Decryption?

Decryption reverses encryption. It takes ciphertext and the key and recovers the original plaintext.

Ciphertext + Key → [Decryption] → Plaintext
"KHOOR"    + 3   → [Shift each letter back by 3] → "HELLO"

Encoding vs Encryption — The Critical Difference

---

Chapter 3: Ciphers — The Machines of Secrecy

A cipher is the method (algorithm) used to encrypt and decrypt. Think of it as the recipe. The key is the specific ingredient that changes the result.

The Caesar Cipher — The Oldest Trick

Julius Caesar sent secret messages by shifting each letter in the alphabet by a fixed number.

With a shift of 3:

Plain:    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Cipher:   D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

So "ATTACK" becomes:

A → D
T → W
T → W
A → D
C → F
K → N

Encrypted: "DWWDFN"

To decrypt, shift backward by 3: D→A, W→T, W→T, D→A, F→C, N→K → "ATTACK".

Why is the Caesar cipher weak? There are only 25 possible shifts (1 through 25). An attacker can try all 25 in seconds. This is called a brute force attack.

The Substitution Cipher — A Bigger Keyspace

Instead of a fixed shift, you scramble the entire alphabet randomly:

Plain:    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Cipher:   Q W E R T Y U I O P A S D F G H J K L Z X C V B N M

Now "HELLO" becomes "ITSSG".

There are 26! (26 factorial) = 403,291,461,126,605,635,584,000,000 possible substitution alphabets. Brute force won't work.

But it's still weak. In English, the letter E appears most often (~13% of all letters). If you look at the ciphertext and find which letter appears most, it's probably the substitute for E. This is called frequency analysis, and it breaks any simple substitution cipher.

Lesson: Good Ciphers Need Good Math

Simple letter-shuffling tricks can be broken by clever observation. Modern cryptography replaces these tricks with mathematical operations that are provably hard to reverse. That's where the rest of this guide goes.

---

Chapter 4: Symmetric vs Asymmetric Encryption

Symmetric Encryption — One Key for Both

The Caesar cipher is symmetric: the same key (the shift number) is used to encrypt and decrypt.

Alice                          Bob
  │                              │
  ├── encrypts with Key K ──→    │
  │                              ├── decrypts with same Key K

Modern symmetric ciphers (AES, ChaCha20) are extremely fast and secure. AES-256 is used by governments and banks worldwide.

The Problem: How do Alice and Bob agree on the key K in the first place? If they've never met and all communication is public, they can't just send the key — an eavesdropper would intercept it.

This is called the key distribution problem. For thousands of years, it had no solution. Armies used couriers. Banks used armored cars. Governments used diplomatic pouches.

Asymmetric Encryption — Two Keys

In 1976, Diffie and Hellman proposed a radical idea: what if you had two keys?

• A public key that you share with the world

• A private key that you keep secret

Anyone can encrypt a message using your public key. Only you can decrypt it using your private key.

Alice                                    Bob
  │                                        │
  │  Bob publishes his public key          │
  ├── encrypts with Bob's PUBLIC key ──→   │
  │                                        ├── decrypts with his PRIVATE key
  │                                        │
  │  No one else can decrypt, because      │
  │  no one else has Bob's private key     │

This solves the key distribution problem. Bob never sends his private key anywhere. He only publishes the public key, which is useless for decryption.

The question becomes: How do you build a lock that can be locked by anyone (public key) but only unlocked by one person (private key)?

The answer is math. Specifically, one-way functions — operations that are easy to do forward but practically impossible to reverse. Building these one-way functions is what the rest of this guide teaches you.

The Three Players

In cryptography, we always use the same characters:

---

Chapter 5: Why We Need Math

Every modern cipher is built on a mathematical operation where:

• Going forward is fast (encrypt, sign, exchange keys)

• Going backward is impossibly slow without the secret (decrypt, forge, eavesdrop)

Here are the three mathematical "hard problems" that power all modern cryptography:

Don't worry about understanding these yet. The point is: all of modern cryptography comes down to math problems that are easy one way and hard the other way. The rest of this guide teaches you that math, from the ground up.

---

Part I: Foundations

Chapter 6: Modular Arithmetic — Cryptography's Number System

The Idea: Numbers That Wrap Around

Think of a clock. After 12 comes 1 again. The numbers "wrap around."

If it's 10 o'clock and you wait 5 hours:

10 + 5 = 15
But on a clock: 15 → 3 o'clock

We say: 15 is the same as 3 on a clock of size 12.

In math notation:

15 ≡ 3 (mod 12)

Read this as: "15 is congruent to 3, modulo 12."

All it means is: when you divide 15 by 12, the remainder is 3.

More Examples

17 mod 5 = ?
    17 ÷ 5 = 3 remainder 2
    Answer: 2

23 mod 7 = ?
    23 ÷ 7 = 3 remainder 2
    Answer: 2

100 mod 10 = ?
    100 ÷ 10 = 10 remainder 0
    Answer: 0

3 mod 5 = ?
    3 ÷ 5 = 0 remainder 3
    Answer: 3      (when the number is smaller than the modulus, it's already the answer)

Doing Arithmetic in Mod World

The beautiful thing: you can add, subtract, and multiply inside mod world, and the rules still work.

Addition:

(8 + 6) mod 10 = 14 mod 10 = 4

Or equivalently:
8 mod 10 = 8
6 mod 10 = 6
(8 + 6) mod 10 = 4

Multiplication:

(7 × 8) mod 10 = 56 mod 10 = 6

The key trick — reduce early: You don't have to compute the full result first. You can take mod at each step. This keeps numbers small:

Compute 7 × 8 × 9 mod 10:

Method 1 (compute first, then mod):
  7 × 8 × 9 = 504
  504 mod 10 = 4

Method 2 (reduce as you go):
  7 × 8 = 56 → 56 mod 10 = 6
  6 × 9 = 54 → 54 mod 10 = 4

Same answer. But method 2 never exceeds 56.

This "reduce as you go" trick is what makes cryptography possible. Even with numbers that have thousands of digits, we can keep them manageable by reducing mod p at every step.

Why Cryptography Lives in Mod World

Reason 1: Bounded outputs. No matter how big the input, the output is always between 0 and p-1. This is essential for computers.

Reason 2: The trapdoor. Computing g^x mod p (going forward) is easy. Finding x from the result (going backward) is impossibly hard for large p. This one-way property is the foundation of every protocol we'll study.

Practice Problems

Try these by hand:

(a) 23 mod 7 = ?          Answer: 2     (23 = 3×7 + 2)
(b) (9 + 14) mod 11 = ?   Answer: 1     (23 mod 11 = 1)
(c) (6 × 7) mod 10 = ?    Answer: 2     (42 mod 10 = 2)
(d) 50 mod 8 = ?           Answer: 2     (50 = 6×8 + 2)
(e) 0 mod 5 = ?            Answer: 0
(f) 4 mod 4 = ?            Answer: 0

---

Chapter 7: Prime Numbers — Why They Matter

What Is a Prime?

A prime number is a whole number greater than 1 that can only be divided evenly by 1 and itself.

2  — prime (only 1 × 2)
3  — prime (only 1 × 3)
4  — NOT prime (2 × 2)
5  — prime
6  — NOT prime (2 × 3)
7  — prime
8  — NOT prime (2 × 4)
9  — NOT prime (3 × 3)
10 — NOT prime (2 × 5)
11 — prime
12 — NOT prime (2 × 6, 3 × 4)
13 — prime

The first several primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, ...

Special cases:

• 1 is NOT prime (by mathematical convention)

• 2 is the ONLY even prime

• There are infinitely many primes (Euclid proved this around 300 BC)

The Fundamental Theorem of Arithmetic

Every whole number greater than 1 can be broken down into primes in exactly ONE way:

12  = 2 × 2 × 3         = 2² × 3
60  = 2 × 2 × 3 × 5     = 2² × 3 × 5
100 = 2 × 2 × 5 × 5     = 2² × 5²
17  = 17                  (already prime)

No matter how you factor a number, you always get the same primes. That's why primes are called the "atoms" of arithmetic — everything is built from them.

Why Cryptography Loves Primes

Reason 1: Clean arithmetic. When you do arithmetic mod a prime p, everything works nicely. Every number (except 0) has a "division partner" (multiplicative inverse). Mod a non-prime, some numbers don't, and things break.

Quick example — mod 7 (prime) vs mod 6 (not prime):

Mod 7: Can we "divide by 3"? Yes!
  3 × 5 = 15 ≡ 1 (mod 7)
  So dividing by 3 means multiplying by 5.
  Every number from 1-6 has a partner like this.

Mod 6: Can we "divide by 2"? No!
  2 × 1 = 2, 2 × 2 = 4, 2 × 3 = 6 ≡ 0, 2 × 4 = 8 ≡ 2, 2 × 5 = 10 ≡ 4
  We never get 1. So 2 has no inverse mod 6. Division by 2 is impossible.
  Even worse: 2 × 3 = 6 ≡ 0 (mod 6). Two non-zero numbers multiply to zero!

Cryptography needs all operations to work reliably. Primes guarantee that.

Reason 2: Hard to factor. Multiplying two large primes is instant. Factoring the result is essentially impossible for large numbers. This is the foundation of RSA.

Easy:    p × q = N
         541 × 773 = 418,193     (instant on a calculator)

Hard:    N → p, q
         418,193 = ? × ?          (how do you figure this out without trying divisors?)

For cryptographic-size numbers (600+ digits), no known algorithm can factor them in a practical amount of time.

---

Chapter 8: The Euclidean Algorithm — Finding the Greatest Common Divisor

What Is the GCD?

The Greatest Common Divisor of two numbers is the largest number that divides both of them evenly.

gcd(12, 8) = 4     because 4 divides both 12 and 8
gcd(15, 10) = 5    because 5 divides both 15 and 10
gcd(17, 13) = 1    because the only common divisor is 1
gcd(24, 9) = 3     because 3 divides both 24 and 9

When gcd(a, b) = 1, we say a and b are coprime — they share no common factors. This concept comes up constantly in cryptography.

Finding the GCD: The Slow Way

List all divisors of each number and find the biggest one they share:

Divisors of 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
Divisors of 18: 1, 2, 3, 6, 9, 18
Common: 1, 2, 3, 6
Biggest: 6

gcd(48, 18) = 6

This works but is painfully slow for large numbers.

The Euclidean Algorithm: The Fast Way

Euclid discovered (over 2000 years ago) that:

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

You keep replacing the pair with a simpler pair until one of them becomes 0. Then the other one is the GCD.

Example: gcd(48, 18)

Step 1: gcd(48, 18)
        48 mod 18 = 12     (48 ÷ 18 = 2 remainder 12)
        → gcd(18, 12)

Step 2: gcd(18, 12)
        18 mod 12 = 6      (18 ÷ 12 = 1 remainder 6)
        → gcd(12, 6)

Step 3: gcd(12, 6)
        12 mod 6 = 0       (12 ÷ 6 = 2 remainder 0)
        → gcd(6, 0)

When we reach 0, stop. The answer is the other number.
gcd(48, 18) = 6

Another example: gcd(35, 15)

gcd(35, 15):  35 mod 15 = 5   → gcd(15, 5)
gcd(15, 5):   15 mod 5 = 0    → gcd(5, 0)

gcd(35, 15) = 5

One more: gcd(17, 13)

gcd(17, 13):  17 mod 13 = 4   → gcd(13, 4)
gcd(13, 4):   13 mod 4 = 1    → gcd(4, 1)
gcd(4, 1):    4 mod 1 = 0     → gcd(1, 0)

gcd(17, 13) = 1       (they're coprime)

The Extended Euclidean Algorithm

This version goes further. It not only finds gcd(a, b), but also finds two numbers x and y such that:

a × x + b × y = gcd(a, b)

This is called Bezout's identity, and it's how we find modular inverses (covered in the next chapter).

Example: Find x and y for gcd(35, 15) = 5

Forward pass (same as before):

35 = 2 × 15 + 5      →    5 = 35 - 2 × 15
15 = 3 × 5 + 0       →    (stop)

From the first equation: 5 = 35 × 1 + 15 × (-2)

So x = 1 and y = -2.

Check: 35 × 1 + 15 × (-2) = 35 - 30 = 5 ✓

Why This Matters

The extended Euclidean algorithm is how we compute modular inverses — the "division" operation in modular arithmetic. Without modular inverses, we can't decrypt anything. This algorithm is the engine behind decryption.

---

Chapter 9: Modular Inverses — "Division" in Mod World

The Problem

In regular math, dividing by 5 is the same as multiplying by 1/5. We call 1/5 the inverse of 5 because 5 × 1/5 = 1.

But in modular arithmetic, there are no fractions. So how do we "divide"?

We find a number that plays the role of the inverse. The modular inverse of a number a (mod p) is a number a⁻¹ such that:

a × a⁻¹ ≡ 1 (mod p)

Finding Inverses by Trying

Let's find the inverse of 3 mod 11. We need x such that 3 × x ≡ 1 (mod 11):

3 × 1 = 3      3 mod 11 = 3    ✗
3 × 2 = 6      6 mod 11 = 6    ✗
3 × 3 = 9      9 mod 11 = 9    ✗
3 × 4 = 12     12 mod 11 = 1   ✓  ← found it!

So 3⁻¹ ≡ 4 (mod 11). Check: 3 × 4 = 12 = 11 + 1, so 12 mod 11 = 1. ✓

All Inverses Mod 11

Let's find every inverse in mod 11:

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

Every number from 1 to 10 has an inverse. This is because 11 is prime.

When Does an Inverse Exist?

a has an inverse mod n only when gcd(a, n) = 1 (a and n are coprime).

Does 3 have an inverse mod 11?   gcd(3, 11) = 1  → YES
Does 4 have an inverse mod 6?    gcd(4, 6) = 2   → NO
Does 7 have an inverse mod 10?   gcd(7, 10) = 1  → YES
Does 5 have an inverse mod 10?   gcd(5, 10) = 5  → NO

Key insight: When p is prime, EVERY number from 1 to p-1 is coprime to p. So every number has an inverse. This is why cryptography uses prime moduli — the arithmetic is complete.

Finding Inverses with the Extended Euclidean Algorithm

For large numbers, trying every possibility is too slow. The extended Euclidean algorithm gives us the answer directly.

To find 7⁻¹ mod 11, we solve: 7x + 11y = 1

Forward:
  11 = 1 × 7 + 4     →   4 = 11 - 1 × 7
  7  = 1 × 4 + 3     →   3 = 7 - 1 × 4
  4  = 1 × 3 + 1     →   1 = 4 - 1 × 3

Backward (substitute):
  1 = 4 - 1 × 3
    = 4 - 1 × (7 - 1 × 4)
    = 2 × 4 - 1 × 7
    = 2 × (11 - 1 × 7) - 1 × 7
    = 2 × 11 - 3 × 7

So 7 × (-3) + 11 × 2 = 1. This means 7⁻¹ ≡ -3 ≡ 8 (mod 11).

Check: 7 × 8 = 56 = 5 × 11 + 1, so 56 mod 11 = 1. ✓

Fermat's Shortcut (When the Modulus Is Prime)

If p is prime and a is not divisible by p:

a⁻¹ ≡ a^(p-2) (mod p)

This comes from Fermat's Little Theorem (covered in the next chapter on fast exponentiation). It gives another way to compute inverses — just raise a to the power p-2.

Why Inverses Matter for Cryptography

Encryption often looks like: ciphertext = message × key (mod p)

To decrypt, you need: message = ciphertext × key⁻¹ (mod p)

Without the modular inverse, there's no way to undo the encryption. The entire encrypt/decrypt cycle depends on inverses existing.

---

Chapter 10: Fast Exponentiation — The Speed Trick

The Problem

Cryptography constantly computes things like:

g^x mod p

where x might be a number with hundreds of digits. You obviously can't multiply g by itself that many times. Even a computer would take longer than the age of the universe.

The Trick: Repeated Squaring

Instead of multiplying one at a time, we square repeatedly. Squaring doubles the exponent in a single step:

g^1  → square → g^2  → square → g^4  → square → g^8  → square → g^16 ...

Each step takes only one multiplication, but the exponent doubles every time. In 10 steps, we reach g^1024. In 20 steps, g^1048576. In 100 steps, g^(2^100) — a number with 30 digits in the exponent.

Step-by-Step Example: Compute 3^13 mod 11

Step 1: Write 13 in binary.

13 = 8 + 4 + 1 = 2³ + 2² + 2⁰
Binary: 1101

So 3^13 = 3^8 × 3^4 × 3^1.

Step 2: Build powers by squaring.

3^1 = 3
3^2 = 3 × 3 = 9
3^4 = 9 × 9 = 81   → 81 mod 11 = 4    (81 = 7×11 + 4)
3^8 = 4 × 4 = 16   → 16 mod 11 = 5

(Notice we reduced mod 11 at each step. This keeps numbers small.)

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

3^13 = 3^8 × 3^4 × 3^1
     = 5 × 4 × 3
     = 60
     → 60 mod 11 = 5    (60 = 5×11 + 5)

Answer: 3^13 ≡ 5 (mod 11)

We did this in 5 multiplications instead of 12. For an exponent with 2048 bits (the size used in real cryptography), this takes about 3000 multiplications instead of 2^2048 — the difference between milliseconds and eternity.

Fermat's Little Theorem

Here's a beautiful fact about primes. If p is prime and a is not divisible by p:

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

Let's verify with a = 3, p = 11:

We need 3^10 mod 11.

3^1 = 3
3^2 = 9
3^4 = 9² = 81 mod 11 = 4
3^8 = 4² = 16 mod 11 = 5
3^10 = 3^8 × 3^2 = 5 × 9 = 45 mod 11 = 1  ✓

This works for ANY base (that's not divisible by p) and ANY prime p. Always gives 1.

Why does this matter?

1. It gives us the shortcut for modular inverses: a⁻¹ = a^(p-2) mod p

2. It tells us that powers in mod p are cyclic — they repeat

3. It's the foundation for RSA and many other protocols

---

Part II: Group Theory Basics

Chapter 11: What Is a Group?

Don't let the name scare you. A group is just a set of things plus an operation that follows four simple rules.

The Four Rules

Take a set of elements (like numbers) and an operation (like addition or multiplication). This combination is a group if:

Example 1: Integers Under Addition

Set: {..., -3, -2, -1, 0, 1, 2, 3, ...} Operation: addition

Closure:       3 + 5 = 8 (still an integer)          ✓
Associativity: (2+3)+4 = 2+(3+4) = 9                 ✓
Identity:      0 (because a + 0 = a)                  ✓
Inverse:       the inverse of 5 is -5 (5 + (-5) = 0)  ✓

This is a group. ✓

Example 2: {1, 2, 3, 4, 5, 6} Under Multiplication Mod 7

Set: {1, 2, 3, 4, 5, 6} Operation: multiply, then take mod 7

Closure: 3 × 5 = 15 ≡ 1 (mod 7)  — still in the set   ✓
         4 × 6 = 24 ≡ 3 (mod 7)  — still in the set   ✓

Associativity: always holds for multiplication           ✓

Identity: 1 (because a × 1 = a)                         ✓

Inverses:
  1⁻¹ = 1    (1 × 1 = 1)
  2⁻¹ = 4    (2 × 4 = 8 ≡ 1)
  3⁻¹ = 5    (3 × 5 = 15 ≡ 1)
  4⁻¹ = 2    (4 × 2 = 8 ≡ 1)
  5⁻¹ = 3    (5 × 3 = 15 ≡ 1)
  6⁻¹ = 6    (6 × 6 = 36 ≡ 1)
  Every element has an inverse!                          ✓

This is a group. ✓

This particular group — {1, 2, ..., p-1} with multiplication mod p — is written as F_p* and is the MOST important group in cryptography.

Why Does Cryptography Care About Groups?

When something forms a group, you're guaranteed:

• Operations always produce valid results (closure)

• Every action can be reversed (inverses exist)

• The structure is predictable and well-understood

These guarantees translate into security guarantees. Protocols like Diffie-Hellman and ElGamal are designed to work inside groups because the mathematical guarantees ensure the encryption and decryption always work correctly.

---

Chapter 12: Cyclic Groups, Generators, and Order

Order of an Element

The order of a number g (in mod p) is how many times you must multiply g by itself before you get back to 1.

In {1, 2, 3, 4, 5, 6} with multiplication mod 7:

What's the order of 2?

2^1 = 2
2^2 = 4
2^3 = 8 ≡ 1 (mod 7)    ← back to 1 after 3 steps

Order of 2 is 3.

What's the order of 3?

3^1 = 3
3^2 = 9 ≡ 2
3^3 = 6
3^4 = 18 ≡ 4
3^5 = 12 ≡ 5
3^6 = 15 ≡ 1    ← back to 1 after 6 steps

Order of 3 is 6.

Notice: the order of 3 is 6 = p - 1. That's the maximum possible. The order of 2 is 3, which is a divisor of 6.

Fact: The order of every element always divides p - 1. (This follows from Fermat's Little Theorem.)

Generators (Primitive Roots)

An element whose order equals p - 1 is special. Its powers hit EVERY element in the group before cycling back.

Look at what 3 generates mod 7:

3^1 = 3
3^2 = 2
3^3 = 6
3^4 = 4
3^5 = 5
3^6 = 1

The set of values produced: {3, 2, 6, 4, 5, 1} = {1, 2, 3, 4, 5, 6}. Every element appears.

Now look at what 2 generates:

2^1 = 2
2^2 = 4
2^3 = 1
2^4 = 2    (repeating)

The set of values produced: {2, 4, 1}. Only 3 out of 6 elements. 2 is NOT a generator.

An element that generates the entire group is called a generator or primitive root.

Cyclic Groups

A group where a single element can generate ALL other elements is called a cyclic group. The group F_p* (multiplication mod a prime p) is always cyclic. There's always at least one generator.

Why Generators Matter in Cryptography

When we pick a generator g mod p for Diffie-Hellman:

• Every number from 1 to p-1 can be written as g^x for some x

• This x is called the discrete logarithm

• Finding x from g^x is the hard problem that secures the protocol

If we accidentally picked a non-generator (like 2 mod 7), the possible secret values would be limited to a small subset {1, 2, 4}, making it easier for Eve to guess. Generators maximize the search space.

How to Check If g Is a Primitive Root Mod p

The shortcut: Factor p-1 into its prime factors. For each prime factor q, check if g^((p-1)/q) ≡ 1 (mod p). If NONE of them equal 1, then g is a primitive root.

Example: Is 3 a primitive root mod 11?

p - 1 = 10 = 2 × 5. Prime factors are 2 and 5.

Check (p-1)/2 = 5:

3^5 mod 11:
  3^1 = 3, 3^2 = 9, 3^4 = 81 mod 11 = 4
  3^5 = 3^4 × 3^1 = 4 × 3 = 12 mod 11 = 1

3^5 ≡ 1 (mod 11). Since we found a 1, the order of 3 is NOT 10.

3 is NOT a primitive root mod 11. (Its order is 5, not 10.)

Is 2 a primitive root mod 11?

Check (p-1)/2 = 5:

2^5 = 32 mod 11 = 10    (32 = 2×11 + 10)

10 ≠ 1 ✓

Check (p-1)/5 = 2:

2^2 = 4

4 ≠ 1 ✓

Neither check gave 1, so 2 IS a primitive root mod 11.

Let's verify by listing all powers:

2^1  = 2
2^2  = 4
2^3  = 8
2^4  = 16 ≡ 5
2^5  = 10
2^6  = 20 ≡ 9
2^7  = 18 ≡ 7
2^8  = 14 ≡ 3
2^9  = 6
2^10 = 12 ≡ 1

Values produced: {2, 4, 8, 5, 10, 9, 7, 3, 6, 1} = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} ✓

All 10 elements appear. 2 is a generator of F_11*.

---

Part III: The Core Hard Problems

Chapter 13: The Discrete Logarithm Problem

The Setup

Pick a prime p and a generator g. Now compute:

g^x mod p = y

This is easy. Given g, x, and p, you can compute y in milliseconds using fast exponentiation.

The Hard Direction

Now flip it:

Given g, y, and p — find x.

This is called the Discrete Logarithm Problem (DLP), and it's believed to be extraordinarily hard for large primes.

Small Example

p = 11, g = 2. Someone gives you y = 7 and asks: what power of 2 gives 7 mod 11?

From our table in Chapter 12:

2^1  = 2
2^2  = 4
2^3  = 8
2^4  = 5
2^5  = 10
2^6  = 9
2^7  = 7     ← found it!

So x = 7. Easy because 11 is tiny.

Why It's Hard for Big Numbers

With a 256-digit prime, there are roughly 10^256 possible values for x. Even trying a billion per second, you'd need 10^247 seconds. The universe is only about 10^17 seconds old. Brute force is hopeless.

The best known algorithms (like the Number Field Sieve) are faster than brute force, but still impractical for properly chosen primes. A 2048-bit prime gives roughly 112 bits of security — meaning the best attack takes about 2^112 operations.

Properties of Discrete Logarithms

Just like regular 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 are the same log rules you learned in school, but working mod p-1 instead of over real numbers.

---

Chapter 14: Diffie-Hellman Key Exchange

This solves the problem from the Prologue: how do two strangers agree on a shared secret while everyone listens?

The Protocol

PUBLIC KNOWLEDGE: prime p and generator g

Alice                                   Bob
──────                                  ────
Picks secret number a                   Picks secret number b
Computes A = g^a mod p                  Computes B = g^b mod p

────── Alice sends A to Bob ──────→
←────── Bob sends B to Alice ──────

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^(b×a) mod p
Bob computes:   A^b = (g^a)^b = g^(a×b) mod p

Since b×a = a×b, both compute the same value: g^(ab) mod p.

What Eve Sees

Eve knows g, p, A = g^a, and B = g^b. She needs g^(ab).

To get that, she'd need to find either a or b. Finding a from g^a is the Discrete Logarithm Problem. For large p, this is infeasible.

Full Worked Example

p = 23, g = 5 (you can verify 5 is a primitive root mod 23).

Alice picks a = 4.
  A = 5^4 mod 23 = 625 mod 23 = 625 - 27×23 = 625 - 621 = 4

Bob picks b = 7.
  B = 5^7 mod 23:
    5^1 = 5
    5^2 = 25 mod 23 = 2
    5^4 = 2^2 = 4
    5^7 = 5^4 × 5^2 × 5^1 = 4 × 2 × 5 = 40 mod 23 = 17
  B = 17

Alice and Bob exchange: A = 4, B = 17.

Alice computes: key = B^a = 17^4 mod 23
    17^1 = 17
    17^2 = 289 mod 23 = 289 - 12×23 = 289 - 276 = 13
    17^4 = 13^2 = 169 mod 23 = 169 - 7×23 = 169 - 161 = 8
  key = 8

Bob computes: key = A^b = 4^7 mod 23
    4^1 = 4
    4^2 = 16
    4^4 = 16^2 = 256 mod 23 = 256 - 11×23 = 256 - 253 = 3
    4^7 = 4^4 × 4^2 × 4^1 = 3 × 16 × 4 = 192 mod 23 = 192 - 8×23 = 192 - 184 = 8
  key = 8

Both got key = 8. ✓

Eve sees g=5, p=23, A=4, B=17. To find the key (8), she'd need to solve 5^a ≡ 4 (mod 23) or 5^b ≡ 17 (mod 23). For small numbers this is easy, but for 2048-bit primes it's impossible.

---

Chapter 15: RSA — Encryption Based on Factoring

RSA uses a different hard problem: instead of discrete logarithms, it relies on the difficulty of factoring large numbers.

How RSA Works

Key Generation (Bob does this once):

1. Pick two secret primes: p and q
2. Compute N = p × q                    (this is public)
3. Compute φ(N) = (p-1) × (q-1)         (this is secret)
4. Pick public exponent e such that gcd(e, φ(N)) = 1
5. Find private exponent d = e⁻¹ mod φ(N)   (this is secret)

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

Encryption (Alice sends a message m to Bob):

c = m^e mod N

Decryption (Bob recovers the message):

m = c^d mod N

Why It Works

Since d × e ≡ 1 (mod φ(N)), decryption undoes encryption:

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

(The last step uses Euler's theorem, which generalizes Fermat's Little Theorem.)

Worked Example

Step 1: Pick primes p = 5, q = 11.
Step 2: N = 5 × 11 = 55.
Step 3: φ(N) = 4 × 10 = 40.
Step 4: Pick e = 3. Check: gcd(3, 40) = 1 ✓
Step 5: Find d = 3⁻¹ mod 40.
  3 × 1 = 3, 3 × 2 = 6, ..., 3 × 13 = 39 ≡ -1, 3 × 27 = 81 ≡ 1 (mod 40)
  d = 27.

Public key: (55, 3)
Private key: 27

Encrypt message m = 13:
  c = 13^3 mod 55 = 2197 mod 55
  2197 ÷ 55 = 39 remainder 52
  c = 52

Decrypt ciphertext c = 52:
  m = 52^27 mod 55
  (using fast exponentiation, this equals 13)
  m = 13 ✓

Why It's Secure

An attacker knows N = 55 and e = 3. To find d, they need φ(N) = (p-1)(q-1). To get that, they need to factor N into p and q. For our toy example, 55 = 5 × 11 is trivial. For a 2048-bit N (a 600-digit number that's the product of two 300-digit primes), factoring is infeasible.

ElGamal — Encryption Based on Discrete Logs

ElGamal is another public-key system, but based on the DLP instead of factoring:

Key Setup: secret a, public key A = g^a mod p

Encrypt message m:
  Pick random k
  c1 = g^k mod p
  c2 = m × A^k mod p
  Send (c1, c2)

Decrypt:
  s = c1^a mod p
  m = c2 × s⁻¹ mod p

It works because: c2 × s⁻¹ = (m × A^k) × (g^(ak))⁻¹ = m × g^(ak) × g^(-ak) = m.

---

Chapter 16: Digital Signatures — Proving Who Sent a Message

The Problem

Alice sends Bob a message. How does Bob know it's really from Alice and not from Eve pretending to be Alice?

The Idea

Digital signatures flip encryption upside down:

Encryption: anyone can lock, only Bob can unlock. Signatures: only Alice can sign, anyone can verify.

RSA Signatures

Signing (Alice):
  signature = Hash(message)^d mod N      (d is Alice's private key)

Verifying (Bob):
  recovered = signature^e mod N           (e is Alice's public key)
  Check: recovered == Hash(message)?

If it matches, the signature is valid. Only Alice (who knows d) could have produced a valid signature.

Why Hash First?

We don't sign the raw message. We first hash it (using SHA-256 or Keccak-256) to produce a fixed-size fingerprint. This is faster (signing a 256-bit hash vs a multi-kilobyte document) and more secure.

Connection to Blockchain

Every transaction you send from a crypto wallet is digitally signed. Your wallet:

1. Creates the transaction data

2. Hashes it

3. Signs the hash with your private key

4. Broadcasts the transaction + signature

Every node in the network verifies the signature using your public key. If it's valid, they know YOU authorized the transaction. Your private key never leaves your device.

---

Part IV: Advanced Topics

Chapter 17: Finite Fields

What Is a Field?

A field is a set of numbers where you can add, subtract, multiply, AND divide (except by zero), and all four operations behave nicely.

Familiar fields: rational numbers (fractions), real numbers, complex numbers.

The Finite Field F_p

Take the numbers {0, 1, 2, ..., p-1} with arithmetic mod p (where p is prime). This is a finite field — a field with a finite number of elements.

F_7 = {0, 1, 2, 3, 4, 5, 6}   with + and × mod 7
F_11 = {0, 1, 2, ..., 10}       with + and × mod 11
F_101 = {0, 1, 2, ..., 100}     with + and × mod 101

All four operations work:

In F_11:
  Addition:       7 + 8 = 15 ≡ 4 (mod 11)
  Subtraction:    3 - 9 = -6 ≡ 5 (mod 11)
  Multiplication: 4 × 5 = 20 ≡ 9 (mod 11)
  Division:       7 ÷ 3 = 7 × 3⁻¹ = 7 × 4 = 28 ≡ 6 (mod 11)

Why Must p Be Prime?

If p is NOT prime, division breaks. We saw this in Chapter 7: in mod 6, the number 2 has no inverse. Without division, the structure isn't a field, and cryptographic protocols fail.

How Cryptography Uses Finite Fields

Every protocol we've studied operates inside a finite field:

• Diffie-Hellman: exponentiation in F_p*

• ElGamal: multiplication and exponentiation in F_p*

• RSA: exponentiation in Z/NZ (where N = p×q)

• Elliptic curves: point arithmetic over F_p

Understanding that you're always working inside a field gives you a unified view of all these seemingly different protocols.

---

Chapter 18: Elliptic Curve Cryptography

The Problem with Big Keys

RSA and Diffie-Hellman need very large keys (2048+ bits) to be secure. That means large numbers, slow computations, and big signatures.

Elliptic curve cryptography (ECC) achieves the same security with much smaller keys: 256 bits instead of 2048. That's 8 times smaller and significantly faster.

What Is an Elliptic Curve?

An elliptic curve is a set of points (x, y) that satisfy an equation of the form:

y² = x³ + ax + b

(plus a special "point at infinity" that acts as the identity element)

The specific curve used by Ethereum and Bitcoin is called secp256k1:

y² = x³ + 7

over a very large prime field (p is about 2^256).

The Group Operation: Point Addition

Here's the magical part: you can define an "addition" operation on points of the curve, and it forms a group.

To "add" two points P and Q:

1. Draw a line through P and Q

2. It hits the curve at a third point R'

3. Reflect R' across the x-axis to get R = P + Q

This geometric operation translates into algebraic formulas that use only addition, subtraction, multiplication, and division in the finite field. So it works over F_p just as well as over the real numbers.

The Elliptic Curve Discrete Logarithm Problem (ECDLP)

Given a generator point G and an integer k, computing:

Q = k × G = G + G + G + ... + G   (k times)

is easy (using a "double and add" technique, just like fast exponentiation).

But given G and Q, finding k is extraordinarily hard. This is the ECDLP. It's even harder than the standard DLP, which is why elliptic curves achieve the same security with smaller numbers.

How Ethereum Uses Elliptic Curves

Your Ethereum wallet:

Private key:  a random 256-bit number k
Public key:   the point Q = k × G on secp256k1
Address:      the last 20 bytes of the Keccak-256 hash of Q

When you sign a transaction, your wallet uses ECDSA (Elliptic Curve Digital Signature Algorithm). It proves you know the private key k without revealing it. The security of your funds depends entirely on the ECDLP being hard.

---

Chapter 19: Hash Functions — Fingerprinting Data

What Is a Hash Function?

A hash function takes any input and produces a fixed-size output (the "hash" or "digest"):

Hash("Hello")          → a fixed 256-bit number
Hash("Hello ")         → a COMPLETELY DIFFERENT 256-bit number
Hash(entire movie)     → still a 256-bit number

Key Properties

1. Deterministic — Same input always gives the same output

2. One-way — You cannot recover the input from the output

3. Fixed size — Output is always the same length, no matter the input

4. Avalanche effect — Change one bit of input, ~50% of output bits change

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

Hash Functions in Blockchain

Hashing is everywhere in blockchain:

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

Block linking: Each block contains the hash of the previous block. Change any past transaction → its block hash changes → every subsequent block hash changes → tampering is immediately obvious. This is what makes the "chain" in blockchain.

Addresses: Your Ethereum address = Keccak-256(public key), truncated to 20 bytes.

Merkle trees: Transactions are organized in a tree of hashes, so you can efficiently prove a transaction is included in a block.

Proof of Work: (Bitcoin, pre-merge Ethereum) Miners search for a number that, when hashed with the block data, produces a hash below a target value. This is computationally expensive (by design) and is what secures the network.

---

Chapter 20: Zero-Knowledge Proofs — Proving Without Revealing

The Problem

You want to prove you know a secret without revealing the secret itself. Sounds impossible?

The Cave Analogy

Imagine a cave shaped like a ring with a locked door in the middle:

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

Alice claims she knows the password to the locked door. Bob wants proof.

The protocol:

1. Bob waits outside. Alice enters the cave and randomly goes left or right.

2. Bob enters and shouts: "Come out the LEFT side!" (he picks randomly)

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

4. If Alice is lying, she can only succeed if Bob happens to pick the side she's already on — a 50% chance.

Repeat 100 times. If Alice succeeds every time, the probability she's faking is 1/2^100 — essentially zero. Bob is convinced. But he never learned the password.

The Three Properties

Every zero-knowledge proof has:

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

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

3. Zero-knowledge — The verifier learns nothing beyond "the statement is true"

Why Blockchain Cares About ZK Proofs

Scaling (ZK-Rollups): Process thousands of transactions off-chain, then post one small proof on Ethereum that proves "all these transactions are valid." Ethereum verifies one proof instead of re-executing thousands of transactions. Projects like zkSync and StarkNet use this approach.

Privacy: Prove a transaction is valid (correct amounts, authorized sender) without revealing who sent what to whom. Zcash uses this for private transactions.

Identity: Prove you're over 18 without revealing your age. Prove you have sufficient funds without revealing your balance.

---

Chapter 21: How Everything Connects

Here's the complete picture of how every concept in this guide is used:

When You Create an Ethereum Wallet

Random 256-bit number → your private key
Private key × Generator point → your public key     [Elliptic Curves, Ch 18]
Hash(public key) → your address                      [Hash Functions, Ch 19]

When You Send a Transaction

Build transaction data
Hash the transaction                                  [Hash Functions, Ch 19]
Sign the hash with your private key                   [Digital Signatures, Ch 16]
  (internally uses modular inverse, field arithmetic) [Mod Inverse Ch 9, Finite Fields Ch 17]
Broadcast to network

When Nodes Validate Your Transaction

Recover public key from signature                     [Elliptic Curves, Ch 18]
Verify signature matches transaction hash             [Digital Signatures, Ch 16]
If valid → include in block

When a Block Is Created

Organize transactions into a Merkle tree              [Hash Functions, Ch 19]
Link to previous block via hash                       [Hash Functions, Ch 19]
Validators sign attestations with BLS signatures      [Elliptic Curves, Ch 18]

When ZK-Rollups Scale Ethereum

Process 1000 transactions off-chain
Generate a ZK proof that all are valid                [Zero-Knowledge, Ch 20]
Post proof on-chain (one transaction)
Ethereum verifies the proof                           [Finite Fields Ch 17, Elliptic Curves Ch 18]

---

The Dependency Map

Every concept builds on what came before:

Encoding/Decoding (Ch 1)
  │
  └──→ Encryption/Decryption (Ch 2)
         │
         ├──→ Ciphers (Ch 3)
         │      └──→ Symmetric vs Asymmetric (Ch 4)
         │
         └──→ Need for Math (Ch 5)
                │
                ├──→ Modular Arithmetic (Ch 6)
                │       │
                │       ├──→ Prime Numbers (Ch 7)
                │       │       │
                │       │       └──→ Finite Fields (Ch 17)
                │       │               │
                │       │               └──→ Elliptic Curves (Ch 18)
                │       │
                │       ├──→ Euclidean Algorithm (Ch 8)
                │       │       │
                │       │       └──→ Modular Inverses (Ch 9)
                │       │
                │       └──→ Fast Exponentiation (Ch 10)
                │
                ├──→ Groups (Ch 11)
                │       │
                │       └──→ Cyclic Groups & Generators (Ch 12)
                │               │
                │               └──→ Discrete Logarithm Problem (Ch 13)
                │                       │
                │                       ├──→ Diffie-Hellman (Ch 14)
                │                       ├──→ ElGamal (Ch 15)
                │                       └──→ Digital Signatures (Ch 16)
                │
                ├──→ RSA (Ch 15)
                │
                ├──→ Hash Functions (Ch 19)
                │
                └──→ Zero-Knowledge Proofs (Ch 20)

---

Your Study Path

Phase 1: Get Comfortable (Chapters 1-10)

• Understand encoding vs encryption

• Do modular arithmetic by hand until it feels natural

• Run the Euclidean algorithm on several number pairs

• Find modular inverses

• Compute g^x mod p using fast exponentiation

• Verify Fermat's Little Theorem with several examples

Phase 2: Understand the Structure (Chapters 11-12)

• Verify the group properties for F_7* and F_11*

• Compute the order of every element mod 11

• Find all generators (primitive roots) mod 11 and mod 13

• Build complete power tables

Phase 3: Understand the Protocols (Chapters 13-16)

• Walk through Diffie-Hellman with your own numbers

• Encrypt and decrypt with RSA by hand

• Explain to someone why each protocol is secure

• Explain the difference between encryption and signing

Phase 4: See the Bigger Picture (Chapters 17-21)

• Understand why elliptic curves need smaller keys

• Explain the cave analogy for zero-knowledge proofs

• Trace an Ethereum transaction from wallet to block

• Map every concept to its role in blockchain

Practice Is Everything

Reading about cryptography is like reading about swimming. You won't learn until you get in the water. After each chapter:

1. Compute by hand. No calculators for small examples.

2. Verify your work. Check that 3 × 4 ≡ 1 (mod 11) really works.

3. Break things. Try Diffie-Hellman with a non-prime modulus. See what goes wrong.

4. Code it. Implement the Euclidean algorithm, fast exponentiation, Diffie-Hellman in any language.