Cryptography

Why Number Theory?

Public-key cryptography relies on trapdoor functions — easy to compute but hard to invert. The difficulty of factoring large numbers into primes and computing discrete logarithms provides these trapdoors. What was once "pure" mathematics is now essential to internet security.

RSA Algorithm

The RSA cryptosystem (Rivest-Shamir-Adleman):

1. Key generation: Choose large primes p, q. Compute n = pq, φ(n) = (p−1)(q−1)
2. Public key: Choose e coprime to φ(n). Public key = (n, e)
3. Private key: Find d where ed ≡ 1 (mod φ(n)) — the modular inverse
4. Encrypt: c = mᵉ mod n
5. Decrypt: m = cᵈ mod n

Security relies on: factoring n = pq is hard when p, q are ~1024 bits each. Euler's theorem guarantees decryption works: m^(ed) ≡ m^(1 + kφ(n)) ≡ m (mod n).

Diffie-Hellman Key Exchange

Security relies on the Discrete Logarithm Problem: given g, p, and gᵃ mod p, finding a is computationally difficult. This uses the same modular exponentiation techniques.

Modern Topics

• Elliptic Curve Cryptography (ECC): Uses algebraic curves over finite fields — same security with smaller keys
• Hash functions: One-way mappings used in digital signatures
• Post-quantum cryptography: Lattice-based methods using high-dimensional linear algebra
• Zero-knowledge proofs: Prove knowledge without revealing information