The Mathematics of Cryptography: From Caesar to RSA

The Mathematical Foundations of Cryptography

Cryptography is the science of secure communication — transforming readable information (plaintext) into an unreadable form (ciphertext) that only authorized parties can decode. At its core, cryptography relies on mathematical problems that are easy to perform in one direction but computationally infeasible to reverse. This principle, known as a one-way function, underpins every modern encryption system, from the RSA algorithm protecting online banking to the elliptic curve cryptography securing cryptocurrency transactions.

The history of cryptography traces a path from simple letter substitutions to some of the most sophisticated mathematics in use today, including number theory, modular arithmetic, abstract algebra, and computational complexity theory.

Classical Ciphers: Where It Began

The Caesar Cipher

One of the earliest known encryption methods, the Caesar cipher (used by Julius Caesar around 58 BCE) shifts each letter of the alphabet by a fixed number of positions. With a shift of 3, A becomes D, B becomes E, and so on. Mathematically, for a letter with position x in the alphabet (0–25), the encrypted letter is: E(x) = (x + k) mod 26, where k is the key (shift value). Decryption reverses the process: D(x) = (x − k) mod 26.

The Caesar cipher has only 25 possible keys, making it trivially breakable by trying all shifts (brute force).

The Vigenere Cipher

Blaise de Vigenere's polyalphabetic cipher (1553) uses a keyword to vary the shift for each letter. If the keyword is "MATH," the first letter shifts by 12 (M), the second by 0 (A), the third by 19 (T), and the fourth by 7 (H), then the pattern repeats. This was considered unbreakable for centuries until Charles Babbage and Friedrich Kasiski independently developed frequency analysis techniques to crack it in the 19th century.

Classical vs. Modern Cryptographic Approaches

The Mathematics Behind Modern Cryptography

Modular Arithmetic

Modular arithmetic — "clock arithmetic" — is fundamental to cryptography. The expression a ≡ b (mod n) means that a and b have the same remainder when divided by n. For example, 17 ≡ 2 (mod 5) because both leave remainder 2 when divided by 5. Modular arithmetic ensures that encrypted values stay within a fixed range and provides the algebraic structure needed for key generation and encryption operations.

Prime Numbers and Factorization

The security of RSA encryption rests on a simple but profound asymmetry: multiplying two large prime numbers is easy, but factoring their product back into the original primes is extraordinarily difficult. Multiplying two 300-digit primes takes milliseconds on a modern computer; factoring the resulting 600-digit product would take longer than the age of the universe using the best known classical algorithms.

The RSA Algorithm

RSA (Rivest-Shamir-Adleman, 1977) was the first practical public-key cryptosystem — a system where the encryption key can be made public without compromising security. The algorithm works as follows:

• Key generation: Choose two large primes p and q. Compute n = p × q and φ(n) = (p−1)(q−1). Choose public exponent e (commonly 65537) such that gcd(e, φ(n)) = 1. Compute private exponent d such that e × d ≡ 1 (mod φ(n)).
• Encryption: Ciphertext C = Mᵉ mod n, where M is the plaintext message (as a number).
• Decryption: Plaintext M = Cᵈ mod n. This works because of Euler's theorem: M^(ed) ≡ M (mod n).

The public key (n, e) can be freely shared. The private key d can only be computed by someone who knows p and q — which requires factoring n.

Other Key Cryptographic Systems

Elliptic Curve Cryptography (ECC)

Elliptic curve cryptography, proposed independently by Neal Koblitz and Victor Miller in 1985, offers equivalent security to RSA with much smaller key sizes. An ECC key of 256 bits provides security comparable to a 3072-bit RSA key.

ECC operates on points of an elliptic curve over a finite field, defined by equations of the form y² = x³ + ax + b (mod p). The security relies on the elliptic curve discrete logarithm problem (ECDLP): given points P and Q on the curve where Q = kP (point addition performed k times), finding k is computationally infeasible for large values.

Benefits of ECC include:

• Smaller keys: 256-bit ECC ≈ 3072-bit RSA security
• Faster computation: Significantly less processing power required
• Lower bandwidth: Smaller key and signature sizes reduce data transmission
• Ideal for constrained devices: Smartphones, IoT sensors, smart cards

The Quantum Threat and Post-Quantum Cryptography

Quantum computers pose an existential threat to current cryptographic systems. In 1994, Peter Shor developed a quantum algorithm that can factor large integers and solve discrete logarithm problems in polynomial time — rendering RSA, Diffie-Hellman, and ECC insecure once sufficiently powerful quantum computers exist.

In response, researchers have developed post-quantum cryptography — algorithms believed to resist quantum attacks. In 2024, the U.S. National Institute of Standards and Technology (NIST) published the first post-quantum cryptographic standards, including lattice-based schemes (ML-KEM, ML-DSA) and hash-based signature schemes (SLH-DSA). These systems rely on mathematical problems — such as finding the shortest vector in a high-dimensional lattice — for which no efficient quantum algorithm is known.

The transition to post-quantum cryptography represents one of the largest infrastructure upgrades in the history of information security, affecting everything from web browsers and banking systems to government communications and military encryption.