The math underneath: modular arithmetic & one-way functions

A one-way function is easy to compute in one direction and computationally infeasible to reverse. Multiplying two large primes together is easy; taking the product and recovering the original primes is hard. Raising a number to a power modulo another number is easy; working backward to find the exponent (the discrete logarithm) is hard. Nearly every public-key algorithm in this catalog is built on one of these two asymmetries.

Modular arithmetic is arithmetic that wraps around, the way a clock wraps from 12 back to 1. "7 mod 5" means: divide 7 by 5 and keep the remainder — 2. Cryptography works almost entirely inside these wrapped, finite number systems (rather than the infinite integers) because they have exactly the algebraic structure needed: every operation stays inside a fixed, finite set of possible values, which is what makes both the 'easy direction' and the 'hard direction' well-defined and analyzable.

Ordinary addition and multiplication both work fine mod n — you just reduce the result back into range afterward: (a + b) mod n and (a × b) mod n both stay inside {0, 1, ..., n−1}, no matter how large a and b started out. This closure property is what makes it possible to do enormous exponentiations (as in RSA and Diffie-Hellman) without the numbers ever growing unmanageably large — every intermediate result gets folded back into the same fixed-size range.

Division is trickier: instead of dividing by a, you multiply by a's modular inverse — a number a⁻¹ such that a × a⁻¹ ≡ 1 (mod n). That inverse exists only when a and n share no common factors (gcd(a, n) = 1), and when it does exist, the extended Euclidean algorithm finds it efficiently. This is exactly the computation the RSA module uses to derive the private exponent d from the public exponent e.

Strip away the specific numbers, and modular arithmetic mod a prime p, the integers under ordinary addition, and the points on an elliptic curve all share the same abstract shape: a set of elements, one operation for combining them, an identity element that does nothing, and every element has an inverse. Mathematicians call any structure with these properties a group.

This abstraction is what lets completely different-looking systems run the identical algorithm. Diffie-Hellman's "raise g to a power mod p" and ECC's "add a curve point to itself k times" are the same group-theoretic operation — repeated combination of an element with itself — performed in two different groups. Learn the operation once, in the abstract, and it explains both modules at once.

A trapdoor function is a one-way function with a secret that makes the hard direction easy again — but only if you know the secret. RSA's trapdoor is knowledge of the two prime factors of the modulus; with them, decryption is a fast modular exponentiation, but without them, an attacker faces the full difficulty of factoring. This single idea — one-way in general, easy with a secret — is the mechanism that makes a public key public and a private key private.

Every public-key module in this catalog is a variation on the same theme: pick a one-way function, build a key pair around it. The specific hard problem changes; the shape of the argument doesn't.

None of these problems are impossible in a mathematical sense — given unlimited time, trying every possible private key eventually finds the right one. "Hard" here means the best known algorithm still takes longer than is practically useful, even on the fastest computers available. RSA's factoring problem has a sub-exponential classical algorithm (the General Number Field Sieve, covered in the RSA module); the elliptic curve discrete logarithm has no known algorithm even that fast, which is exactly why ECC reaches equivalent security with dramatically smaller keys.

This distinction — computationally hard rather than mathematically impossible — is also precisely what a large enough quantum computer would change. Shor's algorithm, covered in the quantum threat module, doesn't find a flaw in the math; it's simply a faster algorithm for the same two problems (factoring and discrete logarithms) that happens to only run on hardware that doesn't yet exist at the necessary scale.