Mathematics Behind Cryptography: Prime Numbers, Modular Arithmetic, and Encryption

Security Built on Mathematical Difficulty

Every time a browser displays a padlock icon, a set of mathematical problems is standing between your data and anyone trying to intercept it. Not physical locks. Not secrecy about methods. Mathematical problems — multiplication, discrete exponentiation, points on algebraic curves — that are trivially easy to compute in one direction and, with current mathematics and computing power, practically impossible to reverse.

This asymmetry between easy computation and hard inversion is the foundation of modern public-key cryptography. The shift from secret-key systems (where both parties must share a secret key in advance) to public-key systems (where anyone can encrypt but only the keyholder can decrypt) was one of the most consequential mathematical insights of the 20th century, published by Whitfield Diffie and Martin Hellman in 1976 and independently conceived by Clifford Cocks at GCHQ in 1973 (declassified 1997).

Modular Arithmetic: Clock Mathematics

The mathematical tool underlying most cryptographic systems is modular arithmetic — arithmetic that wraps around after reaching a fixed modulus, exactly as a clock resets from 12 to 1. Formally: a ≡ b (mod n) means n divides (a − b). For example, 17 ≡ 5 (mod 12), since 17 − 5 = 12 is divisible by 12.

Modular arithmetic has properties essential for cryptography:

• Addition, subtraction, and multiplication work naturally modulo n: (a + b) mod n = ((a mod n) + (b mod n)) mod n
• Modular exponentiation — computing aᵉ mod n for large exponents e — can be done efficiently using repeated squaring (O(log e) multiplications)
• The inverse operation — finding the exponent from the result (the discrete logarithm problem) — is computationally hard for appropriately chosen parameters
• Euler's theorem provides key structure: if gcd(a, n) = 1, then aᵠ⁽ⁿ⁾ ≡ 1 (mod n), where φ(n) is Euler's totient function

This last result — Euler's theorem — is the mathematical engine of RSA encryption.

The RSA Algorithm

RSA (Rivest, Shamir, Adleman, 1977) remains one of the most widely deployed public-key algorithms. Its security rests on the integer factorization problem: multiplying two large primes is fast, but factoring their product back into the primes is computationally infeasible at sufficient key sizes.

The RSA key generation process:

• Choose two distinct large primes p and q (each typically 1,024–2,048 bits in length)
• Compute n = p × q (the public modulus) and φ(n) = (p−1)(q−1)
• Choose public exponent e, typically 65,537 (a specific Fermat prime), such that gcd(e, φ(n)) = 1
• Compute private exponent d such that e × d ≡ 1 (mod φ(n)) — i.e., d is the modular inverse of e
• Public key: (n, e). Private key: d. Primes p, q are discarded or kept secret.

Encryption: C = Mᵉ mod n. Decryption: M = Cᵈ mod n. Correctness follows from Euler's theorem: (Mᵉ)ᵈ = M^(ed) = M^(1 + k·φ(n)) = M × (M^φ(n))^k ≡ M × 1 = M (mod n).

Diffie-Hellman Key Exchange and the Discrete Logarithm

Diffie-Hellman (DH) key exchange solves a different problem: how can two parties who have never met agree on a shared secret over a public channel without a third party being able to determine it? The protocol uses the discrete logarithm problem in a cyclic group.

Working modulo a large prime p with generator g:

• Alice picks secret integer a, sends A = gᵃ mod p to Bob
• Bob picks secret integer b, sends B = gᵇ mod p to Alice
• Alice computes Bᵃ mod p = gᵃᵇ mod p
• Bob computes Aᵇ mod p = gᵃᵇ mod p
• Both now share the secret gᵃᵇ mod p, which an eavesdropper cannot compute from A, B, g, and p alone

The difficulty: given g, p, A = gᵃ mod p, find a. This is the discrete logarithm problem. For appropriately sized primes (≥2,048 bits in finite-field DH), no polynomial-time algorithm is known for classical computers.

Elliptic Curve Cryptography

Elliptic curve cryptography (ECC) achieves the same security as RSA or DH with substantially smaller key sizes, reducing computational cost. An elliptic curve over a finite field is a set of points (x, y) satisfying y² = x³ + ax + b (mod p), plus a point at infinity.

These points form a group under a geometrically defined addition operation: the "sum" of two points P and Q is a third point R on the curve, found by drawing a line through P and Q and reflecting its third intersection with the curve across the x-axis. Repeated addition of a point G to itself k times yields a new point kG. Given G and kG, finding k — the elliptic curve discrete logarithm problem (ECDLP) — is believed to be harder than the standard discrete logarithm problem, enabling smaller keys for equivalent security.

The curve25519 and P-256 curves are the most widely deployed. ECDH (Elliptic Curve Diffie-Hellman) uses elliptic curve group operations for key exchange. ECDSA (Elliptic Curve Digital Signature Algorithm) provides digital signatures. TLS 1.3 — the security protocol underlying HTTPS — uses ECDH for key exchange by default.

Hash Functions: One-Way Compression

Cryptographic hash functions compress arbitrary-length inputs to fixed-length outputs with three properties: preimage resistance (can't find input from output), second-preimage resistance (can't find a different input with same output), and collision resistance (can't find any two distinct inputs with the same output). SHA-256, producing 256-bit digests, is the standard in Bitcoin mining and digital certificate verification. SHA-3 (Keccak) uses a different internal structure (sponge construction) as an alternative standard.

Post-Quantum Cryptography

Shor's algorithm, published by Peter Shor in 1994, demonstrated that a sufficiently powerful quantum computer could factor integers and compute discrete logarithms in polynomial time — breaking RSA, DH, and ECC simultaneously. NIST has spent years evaluating post-quantum candidates and in 2024 standardized several algorithms: CRYSTALS-Kyber for key encapsulation (based on lattice hard problems) and CRYSTALS-Dilithium, FALCON, and SPHINCS+ for digital signatures. These algorithms rest on mathematical problems — shortest vector in a lattice, learning with errors — for which no efficient quantum algorithm is currently known.