Cryptography is the mathematics of keeping information secret and authentic even when adversaries can see the ciphertext. A symmetric cipher uses the same secret key to encrypt and decrypt — fast, but both parties must already share the key secretly. An asymmetric (public-key) cipher uses a pair of keys — a public key anyone may know, and a private key only the owner holds — solving the problem of how two strangers agree on a secret over an insecure channel in the first place.

The best-known public-key system, RSA (Rivest–Shamir–Adleman, 1977), rests on modular arithmetic and a specific hardness assumption: multiplying two large prime numbers is fast, but factoring their product back into those primes is believed to be computationally infeasible for large enough numbers — exactly the "easy to verify, hard to solve" asymmetry from Chapter 19. Anyone can encrypt with your public key; only someone who knows the prime factorisation (your private key) can efficiently decrypt.

RSA in outline: pick two large primes p and q, compute n = p·q (the public modulus) and a public exponent e. The private key d is computed so that (mᵉ)ᵈ ≡ m (mod n) for any message m — encryption raises to the power e, decryption raises to the power d, and the modular arithmetic returns exactly the original message, thanks to a classical result (Euler's theorem) about exponents modulo n. Security hinges entirely on n being hard to factor: with today's algorithms and hardware, factoring a 2048-bit RSA modulus would take far longer than the age of the universe, while multiplying the two known primes to create it took microseconds.

This is why P vs NP is not a side note — if a fast, polynomial-time factoring algorithm were ever found for classical computers (and quantum computers already threaten this via Shor's algorithm), RSA-based security would collapse overnight. Modern systems increasingly hedge with "post-quantum" schemes based on different hard problems, such as lattice problems, precisely because of this risk.

We implement RSA with deliberately small, textbook-sized primes so every step is inspectable — never use numbers this small for anything real, but the mathematics is identical to production-grade RSA.

import math

def egcd(a, b):                              # extended Euclid: finds gcd and modular inverse
    if b == 0:
        return a, 1, 0
    g, x1, y1 = egcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

def modinv(e, phi):
    g, x, _ = egcd(e, phi)
    if g != 1:
        raise ValueError("e has no inverse mod phi")
    return x % phi

def generate_keys(p, q, e=17):
    n = p * q
    phi = (p - 1) * (q - 1)                  # Euler's totient of n
    d = modinv(e, phi)                       # private exponent: e*d = 1 (mod phi)
    return (e, n), (d, n)                    # (public key, private key)

def encrypt(m, public_key):
    e, n = public_key
    return pow(m, e, n)                       # ciphertext = m^e mod n

def decrypt(c, private_key):
    d, n = private_key
    return pow(c, d, n)                       # plaintext  = c^d mod n

# Toy primes (real RSA uses primes hundreds of digits long!)
p, q = 61, 53
public_key, private_key = generate_keys(p, q)

message = 42                                  # a number standing in for our secret
ciphertext = encrypt(message, public_key)
recovered  = decrypt(ciphertext, private_key)

print("public key: ", public_key)
print("ciphertext: ", ciphertext)
print("recovered:  ", recovered)              # -> 42, exactly

# Breaking it requires factoring n back into p and q -- trivial here (n=3233),
# effectively impossible once p and q are hundreds of digits long.
n = public_key[1]
print("factoring n =", n, "by brute force:",
      [i for i in range(2, int(math.isqrt(n)) + 1) if n % i == 0][0], "...")

The entire security argument is compressed into that last line: with toy numbers, brute-force factoring finds p almost instantly. Real RSA uses primes so large that the identical brute-force loop would not finish before the sun burns out — the algorithm hasn't changed, only the size of the haystack.