Section 2: Math Foundations

Modern cryptography is applied mathematics, but here is the good news: to genuinely understand the ciphers, hashes, and key exchanges in the rest of this course, you need surprisingly little. If you can add, multiply, and divide with remainders, you already have the raw material. This page builds everything else you need: modular arithmetic, primes and GCDs, Euler’s totient function, a dash of probability and entropy, and the humble XOR. Every concept comes with an interactive widget — this is the most hands-on page on the site, so play with everything.

Modular arithmetic: the clock that powers everything

Modular arithmetic is just “clock math.” On a 12-hour clock, 5 hours after 9 o’clock is 2 o’clock, not 14 o’clock — the numbers wrap around. We say the clock works modulo 12. In general, a mod n means “the remainder when a is divided by n,” and it is always a number from 0 to n−1.

The notation you will see everywhere is:

a ≡ b (mod n)     — read: "a is congruent to b modulo n"

which means a and b leave the same remainder when divided by n. For example, 17 ≡ 5 (mod 12) because both leave remainder 5, and 100 ≡ 2 (mod 7) because 100 = 14×7 + 2.

What makes modular arithmetic so useful is that addition and multiplication survive the wrap-around. You can reduce mod n at any point during a calculation and the answer comes out the same:

This is a big deal for cryptography. RSA computes things like m65537 mod n where n is a 600-digit number. Without the ability to reduce as you go, the intermediate numbers would have more digits than there are atoms in the universe. With modular reduction, every intermediate value stays smaller than n.

Fast modular exponentiation (square-and-multiply)

Even with reduction, computing ae mod n by multiplying a by itself e times is hopeless when e has hundreds of digits — that would be more multiplications than seconds in the lifetime of the universe. The trick is square-and-multiply: repeatedly square the base (each squaring doubles the exponent covered), and multiply in an extra factor whenever the binary expansion of the exponent has a 1 bit. Computing 313 mod 7: since 13 = 1101 in binary, you need only 3 squarings and 2 extra multiplies instead of 12 multiplications. For a 2048-bit exponent, that is roughly 3,000 multiplications instead of 2²⁰⁴⁸ — the difference between a millisecond and never. Every RSA signature and every Diffie-Hellman handshake your browser performs relies on this one algorithm.

Prime numbers and the Euclidean algorithm

A prime is an integer greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, 13, … Primes are the atoms of arithmetic — every integer factors into primes in exactly one way. Cryptography loves them for two reasons:

• The asymmetry we mentioned. Given the primes p = 61 and q = 53, computing p×q = 3233 is instant. Given only 3233, recovering 61 and 53 requires search. At small sizes that search is trivial; at 1024-bit primes it is intractable. RSA security rests on exactly this gap.
• Clean structure. Arithmetic modulo a prime behaves beautifully: every nonzero number has a multiplicative inverse, which makes division possible. Diffie-Hellman, elliptic curves, and AES’s internal field all exploit this.

Two numbers do not need to be prime themselves to be useful — often we only need them to be coprime (sharing no common factor except 1). The tool for checking is the greatest common divisor, and the 2,300-year-old Euclidean algorithm computes it astonishingly fast. The idea: gcd(a, b) = gcd(b, a mod b), repeated until the remainder hits zero. The last nonzero remainder is the answer.

Worked example — gcd(252, 105):

The last nonzero remainder is 21, so gcd(252, 105) = 21. Three steps, no factoring required. Since 21 ≠ 1, the two numbers are not coprime. The same algorithm, run “in reverse” (the extended Euclidean algorithm), is how RSA computes its private key from its public key parameters — you will meet it again in Section 6.

Euler’s totient function φ(n)

φ(n) (phi of n) counts how many integers from 1 to n are coprime to n. For example, φ(10) = 4, because only 1, 3, 7, and 9 share no factor with 10 — the even numbers and 5 are disqualified.

Two special cases carry almost all of RSA on their shoulders:

Check the second one by hand: the numbers 1–15 coprime to 15 are 1, 2, 4, 7, 8, 11, 13, 14 — exactly eight of them.

Now the theorem that makes public-key cryptography possible. Euler’s theorem says that if gcd(a, n) = 1, then:

a^φ(n) ≡ 1 (mod n)

Try it: φ(10) = 4, and 3⁴ = 81 ≡ 1 (mod 10). Or 7⁴ = 2401 ≡ 1 (mod 10). Exponents effectively work modulo φ(n) — raising to the power φ(n) is like going all the way around the clock and landing back at 1.

Probability and entropy: how surprised is an attacker?

The birthday paradox

In a room of just 23 people, there is a 50% chance two share a birthday. This feels wrong — 23 is tiny next to 365 — until you notice you are not comparing one person against the room, you are comparing every pair, and 23 people form 253 pairs. Collisions among random values arrive roughly at the square root of the number of possible values, not at the number itself.

This matters enormously for hash functions. A 128-bit hash has 2¹²⁸ possible outputs, but an attacker looking for any two inputs with the same hash expects success after only about 2⁶⁴ attempts — the square root. That is why a hash meant to resist collisions needs twice as many bits as your target security level: SHA-256 gives 128-bit collision resistance, not 256. You will see this used in real attacks in Section 5.

Entropy: measuring unpredictability in bits

Entropy quantifies how hard something is to guess. If a secret is chosen uniformly from N equally likely possibilities, it has log₂(N) bits of entropy — each bit doubles the attacker’s work. A fair coin flip is 1 bit; a random lowercase letter is log₂(26) ≈ 4.7 bits; a random byte is 8 bits.

For a password of length L drawn from a character set of size S, the entropy is L × log₂(S) — provided every character is chosen uniformly at random. Human-chosen passwords have far less entropy than this formula suggests, because humans pick words, dates, and keyboard patterns. Compare some honest numbers, assuming an attacker with specialized hardware making 10¹² guesses per second:

Notice the pattern: entropy grows linearly with length but cracking time grows exponentially. Length beats cleverness every time. Cryptographic keys aim for 128+ bits of entropy, at which point brute force is physically off the table regardless of hardware.

Bitwise operations: XOR, the workhorse

Computers store everything as bits, and ciphers manipulate those bits directly. The star of the show is XOR (exclusive or, written ⊕): it outputs 1 exactly when its inputs differ.

Three properties make XOR the heart of stream ciphers and the one-time pad:

• a ⊕ a = 0 — anything XORed with itself vanishes.
• a ⊕ 0 = a — XOR with zero changes nothing.
• Associative and commutative — order and grouping do not matter.

Combine them and you get the fundamental trick of symmetric encryption for free. Encrypt by XORing plaintext with a key: c = m ⊕ k. Decrypt by XORing again with the same key:

c ⊕ k = (m ⊕ k) ⊕ k = m ⊕ (k ⊕ k) = m ⊕ 0 = m

Encryption and decryption are the same operation. If the key stream is truly random, used once, and as long as the message, this is the one-time pad — the only provably unbreakable cipher. Every practical stream cipher (RC4, ChaCha20) is an attempt to fake that random key stream from a short key. XOR also appears inside AES round operations and in the padding-oracle and keystream-reuse attacks of Section 8, so build intuition for it now.

The other bit operations play supporting roles: AND masks bits off (x AND 0x0F keeps only the low 4 bits), OR forces bits on, and shifts («, ») move bits left or right — a left shift by k multiplies by 2^k. Hash functions like SHA-256 are built almost entirely from XOR, AND, rotations, and additions.

Check your understanding

Going deeper