How Cryptography Math Works: Primes, Modular Arithmetic, and RSA

Why Mathematics Secures Communication

Every time you send a message, make an online payment, or log into a website, your data is protected by cryptographic algorithms grounded in pure mathematics. The core insight behind modern cryptography is the existence of mathematical operations that are computationally asymmetric: easy to perform in one direction but extraordinarily difficult to reverse without specific secret information. These one-way functions make it possible to share information securely across public, untrusted networks — a feat that would seem paradoxical without understanding the underlying math.

Cryptography has existed for millennia — Julius Caesar used simple letter-substitution ciphers — but modern cryptography emerged from a revolution in the 1970s when Whitfield Diffie, Martin Hellman, and Ralph Merkle published foundational papers on public-key cryptography, followed shortly by the invention of RSA by Ron Rivest, Adi Shamir, and Leonard Adleman. These innovations moved cryptography from the realm of secret codebooks to mathematics, enabling the open, scalable key exchange that underlies the entire security infrastructure of the internet.

Modular Arithmetic: The Mathematics of Remainders

The mathematical bedrock of most cryptographic systems is modular arithmetic — arithmetic performed on remainders after division. In modular arithmetic, we write a ≡ b (mod n) to mean that a and b have the same remainder when divided by n, or equivalently, that n divides (a - b). The number n is called the modulus. For example, 17 ≡ 5 (mod 12) because both 17 and 5 leave a remainder of 5 when divided by 12, and 23 ≡ 2 (mod 7) because 23 = 3×7 + 2.

Modular arithmetic creates a finite "clock-like" number system. Addition and multiplication work as usual — (a + b) mod n and (a × b) mod n — but numbers wrap around after reaching n. This wrapping creates mathematical structures called groups and rings that have properties essential to cryptography. Crucially, modular exponentiation — computing a^b mod n — can be done efficiently even when the numbers involved have hundreds of digits, but reversing it (finding b given a, a^b mod n, and n) is computationally hard under certain conditions. This asymmetry is the engine of public-key cryptography.

Prime Numbers and Their Role

Prime numbers — integers greater than 1 divisible only by themselves and 1 — play a central role in cryptography because of fundamental theorems about their properties. The most important for RSA is the difficulty of factoring large composite numbers into their prime factors. While any child can multiply 61 × 53 = 3,233 in seconds, finding the prime factors of a large number like 3,233 (without knowing they are 61 and 53) becomes exponentially harder as the number grows. Modern RSA uses numbers with 2,048 or more bits, representing primes with over 300 decimal digits — factoring such numbers would take current computers longer than the age of the universe even using the best known algorithms.

Fermat's Little Theorem — stating that for any prime p and integer a not divisible by p, a^(p-1) ≡ 1 (mod p) — and its generalization, Euler's theorem, provide the mathematical foundation for RSA's correctness proof. The totient function φ(n), which counts integers from 1 to n that share no common factor with n, enables RSA key generation. For a product n = p × q of two distinct primes, φ(n) = (p-1)(q-1), and this value is kept secret (since computing it requires knowing the prime factors) while n is made public.

RSA Encryption: How It Works Step by Step

RSA encryption begins with key generation. Choose two large prime numbers p and q, compute n = p × q (the public modulus), and compute φ(n) = (p-1)(q-1). Select a public exponent e — typically 65,537, chosen for computational efficiency — that is coprime to φ(n) (shares no common factor). Compute the private exponent d such that e × d ≡ 1 (mod φ(n)) — this is done using the extended Euclidean algorithm. The public key is the pair (n, e); the private key is d (and the factors p and q are discarded or kept secret).

To encrypt a message m (converted to a number less than n), compute the ciphertext c = m^e mod n. To decrypt, compute m = c^d mod n. The mathematical reason this works is that e and d are modular inverses with respect to φ(n), so by Euler's theorem, (m^e)^d = m^(ed) ≡ m (mod n). Anyone with the public key (n, e) can encrypt a message, but only the holder of the private key d can decrypt it — because computing d from e and n requires knowing φ(n), which requires factoring n into p and q, which is computationally infeasible for large enough values.

Diffie-Hellman Key Exchange and Discrete Logarithms

RSA is not the only mathematically important cryptographic system. The Diffie-Hellman key exchange solves a fundamental problem: how can two parties establish a shared secret over a public channel without having met beforehand? The answer relies on the discrete logarithm problem — the difficulty of finding x in the equation g^x ≡ h (mod p), even when g, h, and p are known.

In Diffie-Hellman, two parties agree on a prime p and a generator g (both public). Alice chooses a private integer a and sends g^a mod p to Bob. Bob chooses a private integer b and sends g^b mod p to Alice. Alice computes (g^b)^a mod p = g^(ab) mod p, and Bob computes (g^a)^b mod p = g^(ab) mod p — arriving at the same shared secret without ever directly transmitting it. An eavesdropper sees g^a mod p and g^b mod p but cannot efficiently compute g^(ab) mod p, the discrete logarithm problem standing as an impassable barrier. Elliptic Curve Diffie-Hellman (ECDH), used in modern TLS, applies the same principle to points on elliptic curves, achieving equivalent security with much smaller keys.

Hashing, Signatures, and Beyond

Cryptographic hash functions — MD5, SHA-256, SHA-3 — are another mathematically important component. A hash function maps arbitrary-length input to a fixed-length output (a digest) in a way that is deterministic, fast to compute, but infeasible to reverse. Small changes in input produce completely different outputs (the avalanche effect), and finding two different inputs with the same hash (a collision) should be computationally impractical. Hash functions enable message integrity verification, password storage (storing hashes rather than passwords), and digital signatures.

Digital signatures combine RSA or elliptic curve cryptography with hashing: Alice hashes her message, encrypts the hash with her private key, and appends the result. Anyone with Alice's public key can decrypt the signature, hash the message independently, and verify they match — confirming both the message's integrity and Alice's authorship without Alice having to share her private key. As quantum computing advances, current RSA and elliptic curve systems face potential threats from Shor's algorithm, which can factor integers and solve discrete logarithms in polynomial time on a sufficiently large quantum computer. Post-quantum cryptography — based on lattice problems, hash-based signatures, and other mathematical structures believed resistant to quantum attack — is currently being standardized and will secure the next generation of digital communication.