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.

The greatest common divisor (GCD) of two integers is the largest number that divides both evenly. Euclid's algorithm finds it without ever factoring either number: repeatedly replace the larger number with its remainder when divided by the smaller, until the remainder hits zero — the last non-zero remainder is the GCD.

Worked example: gcd(1071, 462). Divide 1071 by 462: that's 2 remainder 147. Divide 462 by 147: that's 3 remainder 21. Divide 147 by 21: that's 7 remainder 0 — the remainder just hit zero, so the GCD is the previous remainder, 21.

Euclid's algorithm finds the GCD; the extended version finds something more useful for cryptography — integers x and y such that ax + by = gcd(a, b). Run backward through the division trace, substituting each remainder back in terms of the previous two.

Worked example: find x, y such that 240x + 46y = gcd(240, 46). The forward divisions are 240 = 5×46 + 10, then 46 = 4×10 + 6, then 10 = 1×6 + 4, then 6 = 1×4 + 2, then 4 = 2×2 + 0 — so gcd(240, 46) = 2. Substituting backward: 2 = 6 − 1×4, then 4 = 10 − 1×6 gives 2 = 2×6 − 1×10, then 6 = 46 − 4×10 gives 2 = 2×46 − 9×10, then 10 = 240 − 5×46 gives 2 = 47×46 − 9×240. So x = −9, y = 47 — and indeed 240×(−9) + 46×47 = −2160 + 2162 = 2.

This is precisely how a modular inverse gets computed: if gcd(a, n) = 1, the same back-substitution gives x such that ax + ny = 1 — meaning ax ≡ 1 (mod n), so x is a's inverse mod n. It's exactly the computation the RSA module uses to derive the private exponent d from e and φ(n).

Computing aᵉ mod n by multiplying a by itself e−1 times is far too slow once e has hundreds of digits, as in real RSA. Square-and-multiply computes it in roughly log₂(e) steps instead, by reading e's binary expansion and, at each bit, squaring a running result — multiplying in the base only when that bit is 1.

Worked example: compute 5¹³ mod 19. In binary, 13 is 1101. Starting from a running result of 1 and scanning the bits left to right: bit 1 → square (1² = 1), multiply (1×5 = 5). bit 1 → square (5² = 25 ≡ 6), multiply (6×5 = 30 ≡ 11). bit 0 → square only (11² = 121 ≡ 7). bit 1 → square (7² = 49 ≡ 11), multiply (11×5 = 55 ≡ 17). Final result: 17 — so 5¹³ mod 19 = 17, reached in 4 squarings and 3 multiplications instead of 12 multiplications.

Fermat's Little Theorem states that for a prime p and any integer a not divisible by p, aᵖ⁻¹ ≡ 1 (mod p). Worked example: p = 13, a = 2. Then 2¹² mod 13 = 1, exactly as the theorem predicts.

Euler's Theorem generalizes this to any modulus n, not just primes: aᶲ⁽ⁿ⁾ ≡ 1 (mod n) whenever gcd(a, n) = 1, where φ(n) (Euler's totient) counts the integers from 1 to n that are coprime to n. For n = 35 = 5×7, φ(35) = (5−1)(7−1) = 24 — and indeed 2²⁴ mod 35 = 1. This is exactly the identity RSA is built on: choosing e and d so that ed ≡ 1 (mod φ(n)) guarantees Mᵉᵈ ≡ M (mod n) for any message M, by Euler's theorem.

a is a quadratic residue mod p if x² ≡ a (mod p) has a solution — informally, if a has a "square root" in modular arithmetic. The Legendre symbol (a/p) captures this in one value: +1 if a is a quadratic residue, −1 if it isn't, and 0 if a ≡ 0 (mod p).

Euler's criterion gives a direct way to compute it without searching for a square root: (a/p) ≡ a^((p−1)/2) (mod p). Worked example: is 10 a quadratic residue mod 13? Compute 10⁶ mod 13 = 1, so (10/13) = 1 — yes, 10 is a quadratic residue mod 13 (its square roots are 6 and 7, since 6² = 36 ≡ 10 and 7² = 49 ≡ 10).

Once you know a is a quadratic residue mod p, finding an actual square root is easy for the common case where p ≡ 3 (mod 4): the square root is simply a^((p+1)/4) mod p. (Primes where p ≡ 1 (mod 4) need the more involved Tonelli-Shanks algorithm, not covered here.)

Worked example: p = 23 (23 mod 4 = 3), a = 18. Compute 18⁶ mod 23 = 8. Check: 8² = 64, and 64 mod 23 = 18 — confirmed, 8 is a square root of 18 mod 23 (the other is 23−8 = 15).

The Chinese Remainder Theorem (CRT) says a system of congruences with pairwise coprime moduli has exactly one solution modulo the product of those moduli. Worked example: find x such that x ≡ 2 (mod 3) and x ≡ 3 (mod 5). Numbers congruent to 2 mod 3 are 2, 5, 8, 11, ...; checking each mod 5 gives 2, 0, 3 — so x = 8 works, and it's the unique solution mod 15 (= 3×5).

This scales to more than two congruences by combining them two at a time — solve the first pair mod their product, then combine that result with the third congruence, and so on. It's exactly the technique behind RSA-CRT decryption (splitting one decryption into two faster ones mod p and mod q) and behind Håstad's broadcast attack covered in the RSA module, which recovers a message from the same ciphertext sent to several recipients using CRT.

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.