A secret in plain sight

The cipher bureau of the last chapter closed on an awkward question. All its ciphers, from Caesar to AES, need a shared key, and someone has to deliver that key ahead of time, in secret. The internet doesn’t work that way. You open a site you have never visited, your packets pass through dozens of strangers’ routers, and any one of them can record every byte. How do you agree on a secret when every word is overheard?

Cryptographers call the two people talking Alice and Bob, and the one listening in Eve, for “eavesdropper.” The problem looks hopeless. If Eve hears everything Alice and Bob say, she knows everything they know, so where would they get anything she doesn’t have? And yet there is a solution, and it was found twice. Once in the open, by American researchers who published it and became famous. And once earlier, in secret, by mathematicians at a British intelligence agency who for more than twenty years were not allowed to tell anyone. The chapter tells both stories at once, the open one and the secret one, their episodes side by side, until they meet in 1997. In between we’ll build for ourselves everything that the padlock in your browser’s address bar rests on.

The trouble with keys

Both sides were stuck at the same point. They needed a lock that anyone could snap shut but only its owner could open. An ordinary padlock works like that: it snaps shut without a key, at a push. If Alice had such a padlock, she could send it to Bob open, Bob could lock a box with his letter inside, and nobody could open the box on the way, not even someone who had seen the padlock. In mathematics, a padlock like that is a function that is easy to compute and very hard to invert.

A one-way street

In 1874 the English economist and logician William Stanley Jevons wrote in The Principles of Science: “Can the reader say what two numbers multiplied together will produce the number 8,616,460,799? I think it unlikely that anyone but myself will ever know.” He wasn’t thinking about ciphers. His point was that many operations are easy to perform and hard to undo. Here is how a computer fares.

A computer factors Jevons’s number in milliseconds. People factored it without one, too, in 1889, and later Solomon Golomb showed that a pocket calculator and some ingenuity are enough. But Jevons’s idea holds; it only needs bigger numbers. Multiplying two $k$-digit numbers takes on the order of $k^2$ operations, while trial division of a $2k$-digit number takes on the order of $10^k$. Every two extra digits make the search ten times slower, and a number with six hundred digits can’t be factored this way while the Sun still shines.

A function that is easy to compute but practically impossible to invert is called one-way. One caveat up front: nobody has proved that one-way functions exist at all. If they do, then $\mathrm P \ne \mathrm{NP}$ (checking an answer is easy, finding one is hard), and that is the open problem of Chapter 57. All of modern cryptography rests on the fact that the best mathematicians in the world have spent decades looking for a fast way to invert a handful of specific functions, and haven’t found one.

A second function of this kind is modular exponentiation. Computing $g^x \bmod p$ is easy even for numbers hundreds of digits long. You don’t multiply $g$ by itself $x$ times: with a 600-digit exponent that would be more multiplications than there are atoms in the universe. Instead you square: $g, g^2, g^4, g^8, \ldots$, and multiply together the squares that correspond to the ones in the binary representation of $x$. It is the same halve-and-square method as in the task “A power in twenty steps” from Chapter 9, except that after every multiplication you take the remainder, so the numbers don’t grow. A 2048-bit exponent takes about three thousand multiplications. The details, with a proof, are in the math course; in Python the built-in pow(g, x, p) with three arguments does all of it.

The inverse problem, finding $x$ from $A = g^x \bmod p$, is called the discrete logarithm. An ordinary logarithm has a clue to follow: the bigger $x$, the bigger $g^x$. Remainders offer no such clue; the powers jump around the circle in no visible order. All that’s left is to try them one by one.

The module cs.pk is this chapter’s helper: random_prime(bits) returns a random prime of the given length, testing candidates with the Miller–Rabin test from Chapter 26. Every two extra bits of the modulus make the search four times longer. For a 2048-bit modulus, the size used in practice, the search would take on the order of $2^{2048}$ steps, a number more than six hundred digits long. The best known algorithms are far cleverer than brute force, but even they need about $2^{112}$ operations, beyond all the computers on Earth put together.

Paint

Before doing any arithmetic, picture an exchange of paints. Alice and Bob agree in public on a common paint, yellow, say. Each takes a secret paint of their own, stirs it into the yellow and sends the mix to the other. Eve sees the yellow and both mixes. When Bob’s mix arrives, Alice adds her secret paint to it. Bob does the same with Alice’s mix. Now each of them has a can holding the yellow and both secret paints, and so the same color. Eve can’t mix that color. She has no way to separate a mixture back into its paints, and if she pours the two mixes together, she gets twice as much yellow and a different color.

In numbers it all works the same way. The common paint is a publicly known prime $p$ and a base $g$. Alice’s secret paint is a random exponent $a$, and her mix is $A = g^a \bmod p$. Bob has $b$ and $B = g^b \bmod p$. Adding your paint to the other side’s mix means raising it to your own power: Alice computes $B^a$, Bob computes $A^b$, and they get the same number:

Eve knows $p$, $g$, $A$ and $B$, but to get $g^{ab}$ she needs $a$ or $b$, and that is a discrete logarithm. This is the Diffie–Hellman key exchange. Here it is in a group used in practice, a 2048-bit prime from RFC 3526, the standard that defines groups for internet protocols.

A few dozen milliseconds in all, and Alice and Bob share a secret more than six hundred digits long that was never once said aloud. From it both sides derive a key for AES, for example by hashing it (hash functions come a few sections on), and from then on they talk using the fast symmetric cipher of the last chapter.

Eve changes tactics

The Diffie–Hellman exchange protects against someone who listens. But what if Eve does more than listen? Suppose she sits in the middle of the line and can swap messages. Turn on “Eve swaps the mixes” in the widget. Eve intercepts Alice’s mix and sends Bob her own instead, and on the way back she replaces Bob’s mix with hers too. Alice agrees on a key with Eve, thinking it’s Bob; Bob also agrees on one with Eve. From then on Eve decrypts every letter from Alice with the first key, reads it, encrypts it with the second and passes it on to Bob. Both are sure they are talking to each other in private. This is a man-in-the-middle attack.

Encryption is no help here. The trouble is that Alice doesn’t know who she is talking to. She needs a way to prove that the mix came from Bob: a signature that anyone can check but only Bob can make. The second public-key cipher provided one.

A padlock anyone can snap shut

Here is the recipe. The owner of the key picks two large primes $p$ and $q$ and keeps them secret, publishing only their product $n = pq$ and a number $e$, usually $65\,537$. Privately, the owner computes $d$, the inverse of $e$ modulo $\varphi = (p - 1)(q - 1)$: the number for which $e \cdot d$ leaves a remainder of 1 when divided by $\varphi$. The pair $(n, e)$ is the public key; you could print it in a newspaper. The number $d$ is the private key. Anyone can encrypt a number $m$: $c = m^e \bmod n$. Only the holder of $d$ can decrypt it: $m = c^d \bmod n$.

Why $c^d$ gives back $m$ follows from Fermat’s little theorem; the full proof is in the math course, and here we’ll build the cipher in code. The modular inverse comes from the same pow, with an exponent of −1. Inside it runs the extended Euclidean algorithm, a relative of the greatest common divisor from Chapter 5.

So here is the padlock anyone can snap shut. A cipher with two different keys, a public one for encrypting and a private one for decrypting, is called public-key encryption, or asymmetric encryption, as opposed to the symmetric ciphers of the last chapter. And $d$ is a trapdoor: knowledge that turns a hard inverse problem into an easy one. Without $p$ and $q$, nobody knows how to compute $\varphi$, and so $d$, any faster than by factoring $n$.

In the lab below you can do the same with keys of any length, and also sign a letter and break a key.

What factoring costs

The security of RSA rests on how hard it is to factor $n$. Here is what that looks like in numbers if you try every divisor up to the square root:

Four more bits, four times as long: the search runs up to $\sqrt n$, and the square root doubles with every two bits. There are much cleverer methods. Pollard’s rho method, the one running in the lab, relies on the birthday paradox from Chapter 16 and finds a divisor $p$ in about $\sqrt p$ steps, that is, the fourth root of $n$; you’ll write it yourself in one of the tasks. The best known method, the number field sieve, is faster still. The record is RSA-250, a number with 250 decimal digits, or 829 bits: in February 2020 it was factored in time equal to about 2,700 years of work by a single processor core. Between that and the 2048 bits used today lies a chasm; there is more about it in the math course.

A factor in common

But there’s no need to factor head-on if the keys were made badly. In 2012 Nadia Heninger, Zakir Durumeric, Eric Wustrow and J. Alex Halderman collected RSA public keys from every server on the internet they could reach and computed the greatest common divisor of the moduli for every pair of keys. For properly made keys it is one. But some pairs turned out to share a prime factor, and then both keys fall apart at once: $\gcd(n_1, n_2) = p$, and $q_1 = n_1 / p$, $q_2 = n_2 / p$. This way the researchers computed the private keys of 0.5% of TLS servers and 0.03% of SSH servers. The culprits were mostly routers, firewalls and other network devices. Such a device creates its key the first time it is switched on, when it has almost none of the randomness Chapter 26 talked about, and different devices end up choosing the same prime.

The keys in the cell are shorter than the ones in use so that they can be made quickly, but Euclid’s algorithm doesn’t care how long the numbers are, and it gets through tens of thousands of pairs in an instant. For millions of keys the researchers needed a cleverer method, computing the common divisors of all the keys at once with a product tree. The idea is the same. The mathematics of RSA had nothing to do with it. What failed was the randomness at the moment the key was born.

Signatures

RSA has a property that Diffie and Hellman had been looking for from the start: the keys can swap roles. If the owner raises a number to the private power $d$, anyone can recover the original with the public power $e$. That is no use for secrecy, since everyone can decrypt it. But it is a proof: only someone who has $d$ could have made that number. This is a digital signature.

You don’t sign the letter itself, which may be longer than the modulus. You sign its fingerprint: a short number computed from the whole letter that changes with any edit. Fingerprints like that come from a hash function. Hash functions are the next section; for now we’ll use a ready-made one.

A signature stops Eve in the middle. If Bob signs his mix, Alice checks the signature with his public key, and a swapped mix fails the check, because Eve can’t forge the signature. Turn on “Signed mixes” in the paint widget, and the man-in-the-middle attack falls apart. One last question remains: how does Alice know Bob’s public key? If Eve slips Alice her own key under Bob’s name, we’re back where we started.

The answer is a chain of signatures. A site’s public key, together with its name, is signed by a certificate authority, and the signed document is called a certificate. The certificate authority’s own key is signed by a higher authority, and so on up to a root authority whose public key already sits in your browser or operating system; it came installed with them. The browser checks the chain of signatures from the top down, and only then believes that the key belongs to this particular site. Signatures also guard software updates: your phone won’t install an update whose signature doesn’t match the manufacturer’s key.

A 256-bit fingerprint

We built hash functions in Chapter 16 for hash tables, and saw there how an adversary picks keys with the same hash. A hash for signatures has to withstand an adversary with enormous computing power who knows the function down to the last bit. Such a function is called a cryptographic hash function, and three things are required of it. You can’t find an input from its hash. Given one input, you can’t find another with the same hash; otherwise a signed contract could be swapped for a different one. And you can’t find any two inputs with the same hash at all. The most widely used today is SHA-256, from the SHA-2 family. It was designed by the US National Security Agency and published as a standard by NIST, the American standards institute: a draft in 2001, the final text in 2002. It turns an input of any length into 256 bits.

Over three megabytes of the novel fit into 64 hexadecimal digits. Change one letter anywhere in the novel, and the fingerprint comes out completely different. How different, the second half of the cell shows: a single period at the end of the title changed about half of the 256 bits. This is the avalanche effect: any change to the input flips on average half the bits of the output, and nobody can predict which half. If it were otherwise, similar hashes would give away similar inputs.

The length of 256 bits was chosen because of birthdays. As we found in Chapter 16, a repeat among random values drawn from $N$ possibilities turns up after about $\sqrt N$ tries. For a $k$-bit hash that is $2^{k/2}$. The cell below checks this on a shortened SHA-256 that keeps only its first few bits.

A forty-bit fingerprint gives in within about a second. For the full SHA-256 you would have to wait for $2^{128}$ tries to see a collision; that is its safety margin, the same as AES-128’s. Its predecessor SHA-1, with 160 bits, was broken by something cleverer than birthdays: in February 2017 researchers from CWI, the Dutch national research institute in Amsterdam, and Google presented two different PDF files with the same SHA-1. It took about $2^{63}$ hash computations, roughly 6,500 years of work for one processor and 110 years for one graphics card, and since then SHA-1 has been no good for signatures. Git, from Chapter 40, still addresses files by their SHA-1, because it cares more about noticing corruption than about withstanding an adversary. But it already has a SHA-256 mode.

Passwords: storing what you don’t know

Hashes also solve an everyday problem that every site with user accounts runs into. Passwords mustn’t be stored as they are: databases leak, and then the passwords leak with them, passwords that people also use on other sites. So sites store a hash of the password instead. At login the site hashes what was typed and compares. The site never needs the password itself, and, as we’ve seen, the hash won’t give it back. Here is such a database as it reaches an attacker.

A hash won’t give the password back, but the password can be guessed. People choose the same passwords, and an attacker only has to hash the million most common ones once and keep a table of “hash → password.” Worse still, Amy and Dave have identical hashes: you can see that they share a password without knowing what it is. That is what happened at LinkedIn: in June 2012 about 6.5 million password hashes leaked, computed with SHA-1 and no salt at all, and many of them were quickly cracked.

The remedy was invented back in the 1970s for Unix and described by Robert Morris and Ken Thompson in a paper published in 1979, Password Security: A Case History. Morris, by one account, was the first to put the word “hashing” into print, and his son wrote the worm of Chapter 61; we met Thompson in Chapter 52. Before each user’s password is hashed, a random string is attached to it, a salt, as in the hash tables of Chapter 16, except that here every password gets its own salt, which is stored openly next to the hash. Identical passwords get different hashes, and a precomputed table is useless: it would have to be computed again for every salt. In Unix the salt was twelve bits; today it is 16 bytes or more.

A salt doesn’t stop anyone from guessing the password of one particular user: the attacker takes that user’s salt and runs through the dictionary. The second remedy deals with that: a slow hash. SHA-256 was designed to be fast, and for passwords that is a disaster. A password hash is made expensive on purpose: the computation is repeated hundreds of thousands of times, or it is forced to use a lot of memory. The user pays about a tenth of a second at login and doesn’t notice; for the attacker, every guess costs the same.

The function hashlib.pbkdf2_hmac implements the PBKDF2 standard: it runs the password and its salt through the hash a given number of times. Six hundred thousand rounds is what OWASP, a community of web application security experts, currently recommends for PBKDF2 with SHA-256. Compared with a single SHA-256, that is hundreds of thousands of times slower: checking a dictionary of a million passwords against one account would take the attacker on the order of a day on one processor core instead of a fraction of a second, and the same again for every other user. Such functions are called slow password hashes. Besides PBKDF2 there are bcrypt, scrypt and Argon2. Argon2 won an open password hashing competition in 2015, and it is OWASP’s first recommendation: it needs a lot of memory, so graphics cards can’t speed it up much.

Twenty years of silence

The padlock in the address bar

Now we have everything we need to read the padlock. Here is what this site’s server said when the openssl utility connected to it on October 2, 2026, going through the same procedure your browser went through when it opened this page. We kept only the lines of its output that we are going to discuss.

Read it from the bottom up. TLSv1.3 is the version of the TLS protocol approved in 2018; we worked out what its handshake costs in Chapter 43. Peer Temp Key: X25519 is a Diffie–Hellman exchange, except that instead of exponentiation modulo a prime it runs on the elliptic curve Curve25519. It is the same idea of mixing paints, with points on a curve in place of remainders, and a 256-bit key there holds out as long as a 3000-bit modulus. Elliptic curves have a chapter in the math course. The word “Temp” means that the keys for the exchange are new every time and are erased after the conversation. Even if someone steals all of the server’s keys a year from now, a conversation recorded today stays unreadable.

Peer signature type: ecdsa_secp256r1_sha256 means the server signed its part of the exchange, so that no Eve can get in the middle. The signature is ECDSA on the P-256 curve. It works differently from an RSA signature, but the rule is the same (sign with the private key, check with the public one), and its fingerprint is computed with SHA-256. Your browser checks it with the public key from the certificate CN=legost.in. That certificate is signed by the Let’s Encrypt authority, and Let’s Encrypt’s by the ISRG root, whose key is already in your system. Let’s Encrypt certificates currently last 90 days, and they are normally renewed automatically. Finally, TLS_AES_256_GCM_SHA384: the data itself travels under the symmetric cipher AES, with a 256-bit key derived from the shared secret of the exchange.

The quantum shadow

This whole construction faces one known threat. In 1994 Peter Shor devised an algorithm for a quantum computer that factors numbers and finds discrete logarithms quickly, in time that grows as a power of the number of digits. The quantum part of the algorithm finds the period of the sequence $a, a^2, a^3, \ldots \bmod n$, and ordinary modular arithmetic does the rest; the details are in the math course, and what qubits are, in Chapter 64. A quantum computer capable of this doesn’t exist yet. But the estimates of how many qubits it would need keep falling: in May 2025 Craig Gidney of Google estimated that a 2048-bit RSA number could be factored with “less than a million noisy qubits” in less than a week.

Waiting is risky: encrypted traffic can be recorded today and read once such a computer exists. So on August 13, 2024, the same NIST approved the first post-quantum standards: FIPS 203, the ML-KEM key agreement, and FIPS 204 and FIPS 205, the ML-DSA and SLH-DSA signatures. The first two are built on lattice problems, about short vectors in many-dimensional grids of points, and the third on hash functions; no fast quantum algorithms are known for any of them. Post-quantum cryptography is already in use: on October 2, 2026, the day we queried this site, the google.com server agreed on a key with openssl using the hybrid scheme X25519MLKEM768, the classical curve and ML-KEM at once. If one of the two is broken, the other still holds.

That hybrid isn’t excess caution. One of the candidates in the same NIST competition, a scheme called SIKE, made it to the fourth and final round, and in the summer of 2022 it was broken in about an hour on an ordinary computer, with mathematics invented for quite different purposes. It is the lesson of the cipher bureau again: strength isn’t declared, it is tested, and new one-way functions earn trust only after many years of attacks.

Tasks

Four tasks: a key exchange, the whole of RSA, breaking a short key, and storing passwords. The module cs.pk has is_prime, random_prime, the group MODP_P, MODP_G, and rsa_keys; you may use them in the tasks, except where a task asks you to do the work yourself.

What next

The question that sounded like a paradox at the start of the chapter has an answer: two people agree on a secret in front of witnesses, a signature can’t be forged, and a password is stored without being known. All of this rests on a few one-way functions: factoring, the discrete logarithm, lattice problems. Nobody knows how to invert them, in open universities or, as far as anyone can tell, in closed agencies, and no computer on Earth would be enough to break a 2048-bit key.

And yet along the way we have already seen where such systems break. Euclid’s algorithm alone factored thousands of RSA keys, because there wasn’t enough randomness when the keys were born. LinkedIn’s hashes were stored without a salt, and after the leak many of the passwords were quickly cracked. The telegrams Venona read were given away by one pad used for two messages. The mathematics holds, but systems are broken through the mistakes of the people who build them: a forgotten length check, a query glued together from strings, too many privileges. How that happens, and how to write code that doesn’t break that way, is the subject of the next chapter, a training range.