MATHEMATICAL
CRYPTOGRAPHY

A substitution cipher maps each plaintext letter to a fixed ciphertext letter. Caesar's shift is a special case: c ≡ p + k (mod 26).

The key space looks enormous — 26! ≈ 4 × 10²⁶ permutations — yet any natural-language ciphertext leaks structure.

PLAIN  → THE QUICK BROWN FOX
CIPHER → YDW UPHKB OAJZQ MJC

English letter frequency

Lesson: security cannot rest on key-space size alone. Distribution matters.

Encrypt by XOR-ing the message with a uniformly random key of equal length:

Decrypt the same way: m = c ⊕ k. If k is truly random and used only once, the ciphertext reveals nothing about the plaintext.

The catch

• Key must be as long as the message.
• Key must be truly random — not pseudorandom.
• Key must never repeat (Venona broke Soviet pads precisely because they did).
• Key distribution is the original problem in disguise.

m = 01001000 01001001
k = 10110101 11001100
⊕
c = 11111101 10000101

Perfect secrecy is achievable. But every modern system is a compromise around the impracticality of OTP.

Working mod n means we identify integers that differ by a multiple of n:

When n = p is prime, the set ℤ/pℤ becomes a finite field: every nonzero element has a multiplicative inverse.

Examples

Computation in finite fields is fast; inversion via the extended Euclidean algorithm is the workhorse of key generation.

What this gives us

If n = p·q with primes p, q, then

Choose e coprime to φ(n); compute its inverse d ≡ e⁻¹ (mod φ(n)). Then for any m:

Encryption and decryption are both modular exponentiation — cheap if you know the factorization, intractable if you don't.

• Pick large primes p, q (~1024 bits each).
• Compute n = pq and φ(n) = (p−1)(q−1).
• Choose public exponent e (often 65537).
• Solve ed ≡ 1 (mod φ(n)) for private d.
• Public key: (n, e). Private key: d.

encrypt: c = m^e mod n
decrypt: m = c^d mod n

Two strangers establish a shared key over an open wire. Public parameters: a prime p and generator g.

• Alice picks secret a, sends A = g^a mod p.
• Bob picks secret b, sends B = g^b mod p.
• Both compute s = g^ab mod p.

Eve sees: g, p, g^a, g^b
Eve wants: g^ab

Why it's beautiful

Modular exponentiation is a one-way function with structure: easy forward, hard inverse, but it commutes — (g^a)^b = (g^b)^a.

That single algebraic property — commutativity of exponents — is what allows two parties to converge on the same secret without ever transmitting it.

An elliptic curve over a field is the set of points satisfying:

The points form an abelian group under a chord-and-tangent addition law. "Multiplication" of a point P by integer k is repeated addition: kP.

256-bit ECC ≈ 3072-bit RSA in security — smaller keys, faster operations, less power. Why your phone uses Curve25519.

A cryptographic hash H : {0,1}^* → {0,1}ⁿ compresses any input to a fixed-length digest. Three properties matter:

• Pre-image resistance. Given h, hard to find m with H(m) = h.
• Second pre-image. Given m, hard to find m′ ≠ m with H(m′) = H(m).
• Collision resistance. Hard to find any pair (m, m′) colliding.

SHA256("hello") =
2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

A signature scheme is a triple (KeyGen, Sign, Verify):

• Sign(sk, m) → σ requires the private key.
• Verify(pk, m, σ) → {0,1} requires only the public key.
• No one without sk can forge a valid σ on a new m.

Naive RSA signing: σ = H(m)^d mod n; verify: σ^e ≡ H(m) (mod n).

Modern schemes

Encryption hides; signatures bind. They are dual operations on the same key pair.

Goldwasser, Micali, Rackoff (1985): a zero-knowledge proof lets a prover convince a verifier of a statement without leaking anything else.

Three properties:

• Completeness. Honest prover convinces honest verifier.
• Soundness. A cheating prover can't fool the verifier (except with negligible probability).
• Zero-knowledge. The verifier learns nothing beyond the statement's truth.

Modern instantiations

Applications: anonymous credentials, private blockchains, verifiable computation, identity without disclosure.

Shor's algorithm (1994) factors integers and computes discrete logs in polynomial time on a sufficiently large quantum computer. RSA, DH, and ECC all fall.

NIST's post-quantum standardization (2022–24) selected new primitives based on problems Shor cannot crack.

Three families

The migration is the largest crypto transition in history — already underway in TLS, Signal, and OS-level key stores.

Canonical references

• Introduction to Modern Cryptography — Katz & Lindell.
• A Course in Number Theory and Cryptography — Neal Koblitz.
• Cryptography Engineering — Ferguson, Schneier, Kohno.
• The Code Book — Simon Singh (popular).
• NIST FIPS 186-5, 197, 202, 203, 204, 205.

"Every secret has a structure. Cryptography is the study of which structures keep their shape under adversarial scrutiny."

Watch — YouTube

// nav: ← → arrows, space, click
// 13 / 13 — transmission complete