Keeping secrets
in the open.

Two people want to talk. Between them sits an adversary who can read, copy, delay, and rewrite every message. Cryptography is the study of what those two can still guarantee anyway. It rests on three distinct goals, and confusing them is the source of most real-world breaks.

• Confidentiality: the adversary learns nothing about the contents. This is encryption.
• Integrity: any tampering is detected. A changed message fails a check. This is hashing and MACs.
• Authenticity: the message provably came from who it claims, and only they could have produced it. This is signatures.

Encryption alone gives you none of the last two. An adversary who cannot read your ciphertext can still flip bits in it, or replay yesterday's message, unless integrity and authenticity are added on top. Modern protocols always combine all three.

To feel why obscurity fails, take the oldest cipher there is. The Caesar cipher shifts every letter forward by a fixed amount: with shift 3, A becomes D, B becomes E. The "algorithm" is the secret in a system that trusts obscurity. But once you know it is a shift cipher, there are only 26 possible keys, and you can try them all. Move the shift below to encrypt, then press Break it to have the adversary try all 26 keys and read off the one that produces English.

There is exactly one cipher that is provably unbreakable, and it was proven so by Claude Shannon in 1949. It is the one-time pad. Take your message as bits. Take a truly random key that is as long as the message. Combine them bit by bit with XOR (exclusive-or: output 1 when the two bits differ). That is the ciphertext.

Why is it perfect? For any ciphertext, every possible plaintext of that length is equally likely, because some key would produce it. The ciphertext carries zero information about the message, which is what makes this cipher special before you even look at how it is computed.

Encrypt below: the plaintext XORed with a random pad gives a ciphertext that looks like noise, and XORing the pad back recovers the plaintext exactly.

So why is not everything a one-time pad? The catch is in the name: the pad must be truly random, as long as all the traffic, and never reused. To send a gigabyte you need a gigabyte of shared secret key, delivered in advance through some already-secure channel. If you had a secure channel that big, you would just send the message on it. Perfect secrecy is real but impractical. The rest of cryptography is the search for security that is merely computationally unbreakable, in exchange for short, reusable keys.

Modern cryptography runs almost entirely on modular arithmetic: arithmetic that wraps around, like a clock. On a 12-hour clock, 10 o'clock plus 5 hours is 3, not 15. We write 10 + 5 ≡ 3 (mod 12). The modulus is the size of the clock. Everything is reduced to its remainder after dividing by the modulus.

The operation that matters most is repeated multiplication: taking a base to higher and higher powers, mod n. Watch what happens on the clock below. Press Step to compute the next power of the base, mod n. The chord jumps to basek mod n. Notice it never escapes the clock, and for many bases it eventually cycles back to 1 and repeats forever. That hidden cycle length is the seed of public-key cryptography.

Before we can build keys we need one classical tool: the greatest common divisor (GCD), the largest number that divides two integers evenly. Euclid found the algorithm for it around 300 BC, and it is still exactly how computers do it. It is also how we later invert a number mod n, the step that unlocks an RSA private key.

Picture two measuring rods, one 1071 cm and one 462 cm. Lay the shorter rod against the longer one, end to end, as many times as it fits, and look at what is left over: that leftover is shorter still. Lay the new shortest length against the previous rod the same way, and keep going. The last nonzero leftover is the longest length that tiles both original rods with no gap, which is exactly the GCD.

Step through it below. Each row is one division: a = q×b + r. The remainder r becomes the next b. When r reaches 0, the answer is the amber value on the line above.

Every public-key algorithm computes something like baseexponent mod n where the exponent is hundreds of digits long. You cannot multiply the base by itself that many times; the universe would end first. The trick that makes cryptography possible is square-and-multiply: it needs only about as many steps as the exponent has bits.

Try computing 3¹³ by hand. Thirteen in binary is 1101, which is 8+4+1. Square 3 repeatedly to build 3², 3⁴, and 3⁸, then multiply together only the powers matching a 1 bit: 3⁸ times 3⁴ times 3¹. A handful of multiplications gets you there, not the twelve you would need multiplying 3 by itself thirteen times.

Watch it run. The exponent's bits light up left to right. Each step squares, and on a 1-bit also multiplies. Every intermediate value stays reduced mod n, so the numbers never explode. The final amber value is the honest result of baseexp mod n.

Prime numbers are the atoms of arithmetic, and cryptography is built on them because they behave so predictably under modular powers. Two results, from Fermat and Euler, are the exact facts RSA needs.

Here is why Fermat's result has to be true. Multiply every nonzero number mod p by a: the set {a, 2a, 3a, ..., (p−1)a} mod p turns out to just be {1, 2, ..., p−1} shuffled into a new order, nothing lost and nothing repeated, because a shares no factor with p. Multiply both sets together and the products must match, up to a leftover factor of a^p−1. Cancel the shared part and what remains is a^p−1 ≡ 1.

Test it below. Pick a candidate n and a base a. The widget computes an−1 mod n for real. For a true prime it is always 1. For a composite it usually is not, exposing the number as composite without ever factoring it. (A rare few composites fool a given base; those are the Carmichael numbers, and using several bases catches them.)

The one-time pad failed only because the pad had to be truly random and enormous. A stream cipher keeps the pad's shape but fixes its size problem: instead of shipping a giant random pad, both sides feed a short shared key into a keystream generator, a deterministic algorithm that stretches the key into a long stream of pseudorandom bytes. XOR the message with that keystream, exactly like a pad.

Below, the key seeds a real generator that emits a keystream byte per character. The same key always reproduces the same stream, so decryption is exact. Change the key and the whole ciphertext changes. This trades the pad's perfect secrecy for computational secrecy: an attacker who cannot predict the generator cannot read the message.

The workhorse of symmetric encryption is not a stream but a block cipher: a keyed, reversible scramble of a fixed-size block of bits. The Advanced Encryption Standard (AES) scrambles 128-bit blocks through ten-plus rounds of substitution and mixing, and after decades of attack the only known break is brute force over its 2¹²⁸ keys. That is secure forever by any practical measure.

Here is the classic trap. Encrypt an image one block at a time with the same key. In ECB mode (electronic codebook), identical plaintext blocks produce identical ciphertext blocks, so the picture's outline survives encryption. In CBC mode (cipher block chaining), each block is XORed with the previous ciphertext before encryption, so repetition vanishes into noise. Both panels below run a real keyed block cipher on the same image. Watch ECB leak the shape while CBC hides it.

Every cipher so far shares one fatal assumption: both sides already hold the same secret key. But how did they get it? You cannot encrypt the key to send it, because that needs a key. This is the key-distribution problem, and for a network of people it explodes.

With symmetric keys, every pair who might talk needs their own shared secret. For n people that is n(n−1)/2 keys, growing with the square of the group. Ten people need 45 keys; a thousand need almost half a million, each delivered through some pre-existing secure channel. Slide the group size and watch the count balloon.

This is the idea that changed everything. In 1976 Whitfield Diffie and Martin Hellman showed how two people who have never met can agree on a shared secret while an eavesdropper records every message they send, and still not learn it. No pre-shared key. The magic is one-way arithmetic: easy forward, infeasible backward.

Think of it as mixing paint. Alice and Bob agree in public on one shared paint color, then each privately stirs in a secret color of their own and mails the mixture; mixing is trivial, but no one can look at the mailed color and un-mix it back into the two ingredients. Each then stirs their own secret into the mixture they receive. Because mixing does not care about order, both end up holding the identical final blend, while an eavesdropper who saw only the two mailed mixtures cannot recover either secret color. Swap paint for exponents mod a prime and that final blend is gab: Alice's mailed mixture is ga, Bob's is gb.

Everyone agrees, in public, on a large prime p and a base g. Alice picks a private number a and sends A = g^a mod p. Bob picks private b and sends B = g^b mod p. Now Alice computes Ba and Bob computes Ab, and because (gb)a = (ga)b = gab, they land on the same shared secret. The eavesdropper sees p, g, A, B but would need to undo the exponentiation to get a or b, and that is the discrete log problem: infeasible.

Run a real exchange below with small numbers so you can see it. Pick Alice's and Bob's secrets, press Run exchange, and watch the public values cross the wire while both sides converge on the identical amber secret. The eavesdropper panel shows exactly what an attacker sees, and why it does not help.

Diffie-Hellman is safe only because one specific problem is hard. Given g, p, and y = g^x mod p, find the exponent x. This is the discrete logarithm problem. Forward (exponentiate) is a handful of squarings. Backward (find x) has no known fast method: the wrapped values jump around with no order to exploit.

Below, the only known general attack: try every exponent until one matches. With a tiny prime the search finishes instantly. Watch the step count, then raise p and see it climb roughly in proportion. Now imagine p with 600 digits: the same search never finishes.

Diffie-Hellman agrees on a secret but does not, by itself, let you encrypt a message to someone or sign one. RSA, published in 1977 by Rivest, Shamir, and Adleman, does both. It is the first and most famous public-key cryptosystem: a public key anyone can use to encrypt to you, and a private key only you hold to decrypt.

Think of the public key as an open padlock you mail out to anyone who wants to reach you. They drop their message in a box and click your padlock shut around it, trivial to do and, without the matching key, practically impossible to undo. Only you, holding the private key, can open it back up. Modular exponentiation is what turns ordinary arithmetic into that padlock: raising a message to the public power e locks it, and only the private power d unlocks it.

It works because (me)d = med = m1 + kφ ≡ m (mod n) by Euler's theorem: the exponents e and d are inverses mod φ, so applying both returns the original. And you can only compute d if you know φ(n), which requires the factors p and q. Publishing n does not reveal them.

Generate a real key below, then encrypt and decrypt an actual number. Every value is computed live: n, φ, the private d from the extended Euclidean algorithm, the ciphertext, and the recovered amber plaintext. Change the message and watch c = me mod n and cd mod n = m track it.

RSA's entire security is one bet: that factoring a large number back into its two primes is infeasible. Multiplying two 300-digit primes is instant. Splitting the 600-digit product apart, with no fast algorithm known, is the wall attackers hit.

The naive attack is trial division: test each candidate divisor until one works. Below it runs for real. With small primes it finishes at once and hands the attacker p and q, and from them φ(n) and the private key. Raise the primes and watch the operation count grow toward the square root of n. For real key sizes that root has hundreds of digits: the search never ends.

Encryption hides a message. A hash function does something different: it fingerprints one. It takes any input, of any length, and returns a fixed-size digest, in a way that is fast forward and impossible to reverse or fake. Hashes are how we check integrity: change one bit of the input and the digest changes completely.

The widget below runs real SHA-256, the same algorithm securing this page's connection. Type anything and see its 256-bit digest. Then press Flip one bit of the input: a single bit change scrambles roughly half the 256 output bits, with no hint of how small the input change was. That is the avalanche effect, and it is what makes a digest a trustworthy fingerprint.

A hash detects accidental change, but an attacker who rewrites your message can just recompute the hash to match. To detect deliberate tampering you need a secret. A MAC (message authentication code) mixes a shared secret key into the hash, producing a tag only key-holders can compute or check.

Below, the tag is computed from your message and the secret key. Edit the message: the tag no longer matches the one sent, so tampering is caught. An attacker who changes the message cannot fix the tag, because they do not have the key. Toggle the key off (attacker's view) and watch every forgery attempt fail verification.

A MAC proves authenticity to someone who shares your secret. But that means they could also forge your messages. A digital signature is stronger: you sign with a private key that only you have, and anyone can verify with your public key. It gives authenticity, integrity, and non-repudiation at once, and it is exactly backwards from encryption.

Below, sign a message with the private key, then verify with the public key. The signature is real RSA arithmetic over the message's hash. Tamper with the message after signing and verification fails: the recomputed hash no longer matches what the signature unlocks. Only the private-key holder can sign; the whole world can check.

RSA needs 2048-bit keys to stay safe, and those get slow. Elliptic-curve cryptography (ECC) gets the same security from ~256-bit keys, which is why your phone and every modern TLS connection use it. The idea reuses everything from Part IV, but replaces "multiply numbers mod p" with "add points on a curve."

Watch the geometry below. Move P and Q along the curve; the line through them is drawn, its third intersection found, and the reflection gives the amber P + Q, computed with the real addition formulas. Toggle Double to add a point to itself using the tangent. Repeating this addition, P, 2P, 3P, ..., is the elliptic-curve version of exponentiation, and reversing it (finding how many times you added) is the elliptic-curve discrete log: even harder than the ordinary one.

Now assemble the pieces. Every https:// connection begins with the TLS handshake, which in a few round trips uses all of this guide at once: a key exchange to agree on a secret, a signature to prove identity, and a symmetric cipher for the bulk data. Public-key crypto is slow, so it is used only to bootstrap a fast symmetric key.

Step through a simplified handshake below. Each stage lights up and shows the real value it produces, including a live Diffie-Hellman exchange whose shared secret becomes the session key. Notice the division of labor: asymmetric crypto to establish trust and a secret, then symmetric crypto to move the data.

Every public-key scheme here leans on one of two hard problems: factoring (RSA) or discrete logs (DH, ECC). In 1994 Peter Shor found a quantum algorithm that solves both efficiently. A large enough quantum computer would break RSA and ECC outright. Symmetric ciphers and hashes are only dented (you double the key size), but public-key crypto as built today would fall.

The classical heart of the attack is real and runs below. The sequence ak mod n repeats; the widget finds its period r, then uses it to factor n for real. What a quantum computer changes is only the speed of finding r, but that is enough to collapse the whole edifice. Press Find period and watch n split.

Step back and the whole field is a single arc. We wanted three things: confidentiality, integrity, authenticity. The one-time pad gave perfect confidentiality but could not share its key. Symmetric ciphers made keys short and reusable, but still had to be shared in advance, and that did not scale.

Public-key crypto broke the deadlock with one-way functions: modular exponentiation and elliptic-curve addition, easy forward and infeasible back. Diffie-Hellman let strangers agree on a secret in public. RSA and ECC gave encryption and signatures from the same trapdoor. Hashes and MACs delivered integrity; signatures delivered authenticity you cannot repudiate. TLS wires them together on every connection you make.

And it all balances on a knife-edge of computational hardness. Factoring, discrete logs, and their elliptic-curve cousin are hard as far as we know. Shor's algorithm is the reminder that "hard" is an assumption, not a theorem, which is why the field keeps moving toward post-quantum foundations.

You now have the working model of every core primitive. To go deeper:

• Do the exercises in a real library. Re-derive RSA and Diffie-Hellman in Python with big integers, then read how a production library (libsodium, OpenSSL) hardens them against timing and padding attacks.
• Study the attacks, not just the schemes. Padding oracles, nonce reuse, side channels, and downgrade attacks break correct math through incorrect use. This is where most real breaks live.
• Follow post-quantum standardization. Lattice-based schemes (Kyber, Dilithium) are the new foundations replacing RSA and ECC. Learn why lattices are believed quantum-hard.
• Read the canonical texts. Serious Cryptography by Aumasson for the practitioner's view; the Boneh-Shoup Graduate Course in Applied Cryptography (free online) for the rigorous one.

The discipline is the same throughout: trust the math, distrust the implementation, and assume the adversary reads everything.