Cryptography & Security

Secret messages and unbreakable locks!

Junior level — plain language, no maths

Say you want to slip a note to a friend across a crowded room where everyone would love to read it. You reach for a cipher - a secret code. The oldest trick in the book, used by Julius Caesar two thousand years ago, just shifts every letter along by a fixed amount: A becomes D, B becomes E, and so on. Your friend, who knows the shift, reads it instantly; everyone else sees nonsense.

But there's a catch that haunted codemakers for millennia: how do you tell your friend the shift in the first place without someone overhearing? The answer, found only in the 1970s, feels like a magic trick - public-key cryptography. Picture a padlock anyone can click shut but only you hold the key to open. Post that open padlock to the whole world; anyone can lock a message inside and send it back, and only you can open it, even though you never once shared a secret.

This is how every secure website works. When the little padlock shows in your browser, your computer and the server are conjuring a shared secret out in the open - right under the nose of any eavesdropper, who still walks away with nothing. In the simulation below, watch that key exchange unfold one step at a time.

RSA, Diffie-Hellman, and the mathematics of one-way functions

Student level — the core equations

RSA (Rivest–Shamir–Adleman, 1977) rests on a beautiful asymmetry: multiplying two large primes is instant, but un-multiplying the result - factoring it - is believed to be practically impossible. Pick primes \(p, q\), set \(n = pq\) and \(\varphi(n) = (p-1)(q-1)\), choose a public exponent \(e\), and compute the private \(d \equiv e^{-1} \pmod{\varphi(n)}\). Then encryption and decryption are just modular powers: \(c = m^e \bmod n\) and \(m = c^d \bmod n\). They undo each other because Euler's theorem guarantees \(m^{\varphi(n)} \equiv 1 \pmod n\), so \(m^{ed} \equiv m\). Recovering \(d\) from the public \((e, n)\) is believed to be as hard as factoring \(n\) - unproven, but safe at 2048 bits.

Diffie–Hellman (1976) is the trick that lets two strangers agree on a secret in full view of everyone. Alice and Bob publicly fix a prime \(p\) and a generator \(g\); Alice keeps a secret \(a\) and sends \(g^a \bmod p\), Bob keeps \(b\) and sends \(g^b \bmod p\). Each raises what they received to their own secret, and both land on the same key \(K = g^{ab} \bmod p\). An eavesdropper sees \(g, p, g^a, g^b\) and still can't get \(K\) without solving the discrete logarithm problem - easy to compute forwards, believed infeasible to reverse.

Public-key maths is slow, so it's used sparingly. Real connections do a hybrid: Diffie–Hellman (or its elliptic-curve cousin) agrees a key, then a fast symmetric cipher like AES encrypts the actual traffic. Holding it all together are hash functions (SHA-256, SHA-3), which crush any input to a fixed-size fingerprint that's one-way, collision-resistant, and wildly sensitive - flip one input bit and about half the output bits change. Those fingerprints are what make digital signatures, certificates and blockchains possible.

Information-theoretic security, lattice cryptography, and zero-knowledge proofs

Scholar level — full mathematical depth

01Perfect secrecy and its impossible price

Shannon (1949) set the theoretical ceiling: a cipher is perfectly secret when the ciphertext betrays nothing whatsoever about the message, \(P(M=m \mid C=c) = P(M=m)\) for every \(m, c\). The one-time pad - XOR the message with a truly random key used exactly once, \(c = m \oplus k\) - achieves it, and Shannon proved it is essentially the only thing that does. The sting is in the requirement: the key must be as long as the message and never reused, so to secretly send a gigabyte you must already have secretly shared a gigabyte. Perfect secrecy is real, and almost useless.

02Trading perfection for practicality

Everything usable therefore drops down to computational security: a cipher is "secure" if no adversary bounded to polynomial time can do better than negligibly better than guessing. This quietly relocates all of cryptography onto unproven ground - RSA leans on factoring being hard, Diffie–Hellman on discrete logs, and none of these are proven intractable; a proof would settle \(P\) versus \(NP\). We are, in effect, betting the internet on conjectures that have merely resisted every attack so far.

03The quantum threat and the lattice answer

That bet has a known expiry date. Shor's algorithm lets a large quantum computer factor and take discrete logs in polynomial time, quietly demolishing RSA and classical Diffie–Hellman. The leading replacement is lattice-based cryptography, built on Learning With Errors: given many noisy samples \(b_i = \langle a_i, s\rangle + e_i \bmod q\), recovering the secret \(s\) appears hard even for a quantum machine. NIST's first post-quantum standards (2024) are lattice schemes, and the migration is already underway.

04Computing on data you can't read

Lattices unlocked something once thought impossible: fully homomorphic encryption (Gentry, 2009), where a server computes directly on ciphertext, \(f(\mathrm{Enc}(x)) = \mathrm{Enc}(f(x))\), and hands back an encrypted answer it never actually saw. You can run a search, train a model, or query a database with the data staying sealed the entire time. Early FHE was a million times too slow; modern schemes have clawed that down toward a few hundredfold, edging it from thought experiment toward deployment.

05Proving you know a secret without revealing it

Zero-knowledge proofs (Goldwasser–Micali–Rackoff, 1985) pull off a genuine paradox: a prover convinces a verifier that a statement is true while revealing nothing beyond its truth. The three demands are completeness (honest proofs always convince), soundness (false claims almost never slip through), and zero-knowledge (the verifier learns nothing it couldn't have made up alone). You can prove you know a password without uttering it, or that a transaction is valid without disclosing its amount.

06Succinct proofs and where this is heading

The modern workhorses are zk-SNARKs - proofs that are both non-interactive and astonishingly compact, a constant \(O(1)\) in size and verifiable in milliseconds no matter how vast the computation they attest to. They already power privacy-preserving currencies, anonymous credentials, and verifiable outsourced computation, and are creeping toward proving that a specific AI model produced a specific output without exposing the model or the input. A curiosity once dismissed as pure theory is turning into core infrastructure.