# Mathematical Cryptography Canonical URL: https://shipslides.com/d/catalog-math-cryptography Raw viewer URL: https://content.shipslides.com/d/catalog-math-cryptography/raw Category: Mathematics Slides: 13 Updated: 2026-05-17T20:55:53.389Z Tags: catalog, math, cryptography ## Summary A substitution cipher maps each plaintext letter to a fixed ciphertext letter. Caesar's shift is a special case: c ≡ p + k (mod 26) . Key sections include: MATHEMATICAL CRYPTOGRAPHY; Substitution & the Statistics That Betray It; The One-Time Pad — Unbreakable, Unusable; Modular Arithmetic — Integers, Wrapped; Fermat & Euler — Why RSA Works; RSA (1977) — Factoring as a Trapdoor; Diffie–Hellman — A Secret in Public; Elliptic Curves — Same Idea, Smaller Keys; One-Way: SHA-256 and the Compression Trick; Signing — Authorship Without Disclosure. ## Slide Outline 1. MATHEMATICAL CRYPTOGRAPHY 2. Substitution & the Statistics That Betray It 3. The One-Time Pad — Unbreakable, Unusable 4. Modular Arithmetic — Integers, Wrapped 5. Fermat & Euler — Why RSA Works 6. RSA (1977) — Factoring as a Trapdoor 7. Diffie–Hellman — A Secret in Public 8. Elliptic Curves — Same Idea, Smaller Keys 9. One-Way: SHA-256 and the Compression Trick 10. Signing — Authorship Without Disclosure 11. Zero-Knowledge — Convince Without Revealing 12. Post-Quantum — Past the Reach of Shor 13. Where to Go Next ## Slide Transcript ### Slide 1: MATHEMATICAL CRYPTOGRAPHY - CLASSIFIED - EYES ONLY - DOCUMENT // 0xC1A55 - The math behind every secret — from Caesar's shift to lattice-based post-quantum schemes. - VOL. I | 13 SECTIONS | RECOMMENDED CLEARANCE: CURIOSITY ### Slide 2: Substitution & the Statistics That Betray It - § 02 — classical ciphers - 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 × 1026 permutations — yet any natural-language ciphertext leaks structure. - Frequency analysis (Al-Kindi, c. 850 CE). Letter frequencies in the plaintext are preserved. Match histograms → recover the key. - PLAIN → THE QUICK BROWN FOX - CIPHER → YDW UPHKB OAJZQ MJC - English letter frequency - Lesson: security cannot rest on key-space size alone. Distribution matters. ### Slide 3: The One-Time Pad — Unbreakable, Unusable - § 03 — perfect secrecy - Encrypt by XOR-ing the message with a uniformly random key of equal length: - c = m ⊕ k - Decrypt the same way: m = c ⊕ k. If k is truly random and used only once, the ciphertext reveals nothing about the plaintext. - For every plaintext m and ciphertext c, Pr[C = c | M = m] = Pr[C = c]. The ciphertext distribution is independent of the message: perfect secrecy. - 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. ### Slide 4: Modular Arithmetic — Integers, Wrapped - § 04 — foundations - Working mod n means we identify integers that differ by a multiple of n: - a ≡ b (mod n) ⇔ n | (a − b) - When n = p is prime, the set ℤ/pℤ becomes a finite field: every nonzero element has a multiplicative inverse. - In ℤ/pℤ, division is well-defined. We can solve ax ≡ b (mod p) uniquely — making linear algebra, polynomials, and the entire RSA/DH/ECC machinery possible. - Examples - clock - 17 + 9 ≡ 2 (mod 12) - inverse - 3 · 5 ≡ 1 (mod 7), so 3−1 ≡ 5 (mod 7) - power - 210 ≡ 1024 ≡ 24 (mod 1000) - Computation in finite fields is fast; inversion via the extended Euclidean algorithm is the workhorse of key generation. ### Slide 5: Fermat & Euler — Why RSA Works - § 05 — the engine - For prime p and a not divisible by p: - ap−1 ≡ 1 (mod p) - For any a coprime to n: - aφ(n) ≡ 1 (mod n) - where φ(n) counts integers in [1, n] coprime to n. - What this gives us - If n = p·q with primes p, q, then - φ(n) = (p−1)(q−1) - Choose e coprime to φ(n); compute its inverse d ≡ e−1 (mod φ(n)). Then for any m: - (me)d = med ≡ m (mod n) - Encryption and decryption are both modular exponentiation — cheap if you know the factorization, intractable if you don't. ### Slide 6: RSA (1977) — Factoring as a Trapdoor - § 06 — rivest, shamir, adleman - 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. - Recovering d from (n, e) requires φ(n), which requires factoring n. No classical polynomial-time algorithm is known. - encrypt: c = me mod n - decrypt: m = cd mod n ### Slide 7: Diffie–Hellman — A Secret in Public - § 07 — key exchange - Two strangers establish a shared key over an open wire. Public parameters: a prime p and generator g. - Alice picks secret a, sends A = ga mod p. - Bob picks secret b, sends B = gb mod p. - Both compute s = gab mod p. - Eve sees: g, p, ga, gb - Eve wants: gab - Given g, p, gx mod p, recovering x is believed to require sub-exponential time. No efficient classical algorithm exists. - Why it's beautiful - Modular exponentiation is a one-way function with structure: easy forward, hard inverse, but it commutes — (ga)b = (gb)a. - That single algebraic property — commutativity of exponents — is what allows two parties to converge on the same secret without ever transmitting it. - DH (1976) was the first published public-key protocol. Every TLS handshake on the modern internet is its descendant. ### Slide 8: Elliptic Curves — Same Idea, Smaller Keys - § 08 — elliptic curve cryptography - An elliptic curve over a field is the set of points satisfying: - y2 = x3 + ax + b - 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. - Given P and Q = kP on the curve, recovering k is the elliptic-curve discrete log problem. Believed to be even harder per bit than ordinary DLP. - 256-bit ECC ≈ 3072-bit RSA in security — smaller keys, faster operations, less power. Why your phone uses Curve25519. ### Slide 9: One-Way: SHA-256 and the Compression Trick - § 09 — hash functions - A cryptographic hash H : {0,1}* → {0,1}n 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. - For n-bit output, collision attacks require ~2n/2 work. SHA-256 targets ~128-bit collision security. - SHA256("hello") = - 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824 ### Slide 10: Signing — Authorship Without Disclosure - § 10 — digital signatures - 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). - Signing the hash, not the message, gives constant-size signatures, randomizes the input, and prevents algebraic forgery exploits. - Modern schemes - ecdsa - Elliptic-curve DSA — Bitcoin, TLS certificates. - ed25519 - EdDSA on Curve25519 — deterministic, fast, side-channel friendly. SSH default. - trust model - Public-key infrastructure (PKI) binds pk to identities via certificate chains rooted in trusted authorities. - Encryption hides; signatures bind. They are dual operations on the same key pair. ### Slide 11: Zero-Knowledge — Convince Without Revealing - § 11 — zero-knowledge - 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. - The Ali Baba cave: prove you know the password to a magic door without ever speaking it — by entering one tunnel and exiting the verifier's chosen tunnel, repeatedly. - Modern instantiations - zk-snarks - Succinct, non-interactive proofs — tiny, constant-size; powers Zcash, zkRollups. - zk-starks - Transparent setup, post-quantum hash-based, scalable to large statements. - bulletproofs - No trusted setup; logarithmic-size range proofs. - Applications: anonymous credentials, private blockchains, verifiable computation, identity without disclosure. ### Slide 12: Post-Quantum — Past the Reach of Shor - § 12 — the quantum horizon - 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. - "Harvest now, decrypt later." Adversaries are recording today's encrypted traffic, betting on future quantum capability. - NIST's post-quantum standardization (2022–24) selected new primitives based on problems Shor cannot crack. - Three families - lattice-based — kyber, dilithium - Security from Learning With Errors and shortest-vector in high-dimensional lattices. NIST's primary KEM & signature. - hash-based — sphincs+ - Signatures built only from hash functions. Conservative, large signatures, smallest assumptions. - code & multivariate - McEliece (error-correcting codes), Rainbow (multivariate quadratic systems). Decades of cryptanalysis behind them. - The migration is the largest crypto transition in history — already underway in TLS, Signal, and OS-level key stores. ### Slide 13: Where to Go Next - END OF - FILE - 0xC1A55 - § 13 — further reading - 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 - SEARCH · YouTube - RSA Encryption Explained - Tutorials, derivations, demos. - SEARCH · YouTube - Elliptic Curve Cryptography - Geometry, group law, ECDSA. - // nav: ← → arrows, space, click - // 13 / 13 — transmission complete ## Related Decks - [Calculus — The Mathematics of Change](https://shipslides.com/d/catalog-math-calculus) - [Game Theory — Strategy when others strategize too](https://shipslides.com/d/catalog-math-game-theory) - [Geometry — A Drafting Table Deck](https://shipslides.com/d/catalog-math-geometry) - [Linear Algebra — Vectors, Matrices, Transformations](https://shipslides.com/d/catalog-math-linear-algebra)