Exercises

This chapter carries no algebra, so its exercises are about reasoning rather than computation. Two of them do involve arithmetic, and both are small enough for paper.

01.1. Count the keys

In a group of $N$ people where every pair wants a private channel, symmetric cryptography needs one key per pair. How many keys for $N = 10$, $N = 1000$, and for a billion?

Answer. The count is $\binom{N}{2} = N(N-1)/2$.

For $N = 10$ that is $45$. For $N = 1000$ it is $499{,}500$. For a billion it is about $5 \times 10^{17}$.

The second number is the interesting one. Half a million keys for a thousand people is not impossible to store, but it is impossible to distribute, since each of the thousand people must receive $999$ keys by some trusted channel before any communication starts.

And the real Internet is worse than the third number suggests, because the pairs are not known in advance. You buy from a shop you had never heard of ten seconds earlier, so no pre-distribution could have covered that pair at any cost.

02.2. Break the shift cipher

Alice sends KHOOR under a shift cipher. Recover the message and the key without being told either.

Answer. There are only 26 possible keys, so try them all. Shifting back by 3 gives HELLO, which is the only shift producing English.

That exhaustive search is the entire attack, and it takes seconds by hand.

The lesson is that the cipher's structure is fine. Modular addition is a perfectly good way to combine a key with a message, and one-time pads use exactly that. What fails is the key space: 26 possibilities is not a key space, it is a list. AES uses $2^{128}$ or more, and the arithmetic is not fundamentally different.

03.3. Factor by hand, then estimate

Factor $n = 143$ by trial division and count the steps. Then estimate the steps for a 2048-bit modulus.

Answer. Testing primes up to $\sqrt{143} \approx 12$: $2$ fails since $143$ is odd, $3$ fails since $1+4+3 = 8$, $5$ fails on the last digit, $7$ leaves remainder $3$, and $11$ divides exactly, giving $143 = 11 \times 13$. Five trial divisions.

For $n$ near $2^{2048}$, trial division tests primes up to $\sqrt{n} \approx 2^{1024}$, and the prime counting function gives roughly

$$\frac{2^{1024}}{\ln 2^{1024}} \;\approx\; \frac{2^{1024}}{710} \;\approx\; 10^{305}$$

candidates. The observable universe holds about $10^{80}$ atoms, so the count exceeds it by more than two hundred orders of magnitude.

The number field sieve does far better than trial division and is still far too slow, which is the gap that makes RSA work.

04.4. Why the padlock analogy needs mathematics

The padlock story explains public-key cryptography without any numbers. Say precisely where the analogy stops being sufficient.

Answer. A padlock is hard to open because of steel and geometry. Opening one without a key requires physical work that scales with the metal.

On a network there is no metal. Everything is numbers, and any operation Bob can perform, Eve can perform too, on the same kind of hardware. There is no physical asymmetry to appeal to.

So the analogy specifies what is needed without providing it. It says: find an operation that is easy forwards, infeasible backwards, and easy backwards again with a secret. Whether such operations exist at all is an open question, as One-Way Functions and Trapdoors discusses, and the candidates are believed rather than proven.

05.5. Where the trapdoor sits in each scheme

For RSA and for Diffie-Hellman, identify what plays the role of the secret and why publishing the public part is safe.

Answer. In RSA the trapdoor is the factorisation $(p, q)$. Publishing $n = pq$ is safe because recovering the factors is believed infeasible, and the private exponent $d$ depends on $(p-1)(q-1)$, which depends on knowing the factors individually.

In Diffie-Hellman the trapdoor is the exponent. Alice keeps $a$ and publishes $g^a$, Bob keeps $b$ and publishes $g^b$. Publishing is safe because recovering $a$ from $g^a$ is the discrete logarithm problem.

The structural difference is worth noticing. RSA has one long-lived key pair and the trapdoor is a property of the modulus. Diffie-Hellman produces a fresh shared value per session, and each party contributes half of it. That is why RSA key transport and Diffie-Hellman key agreement behave differently when a key is later compromised, and why the latter can offer forward secrecy.

06.6. Why two hard problems were not insurance

Factoring and discrete logarithms were discovered separately and have different best-known attacks. Explain why relying on both did not protect against Shor.

Answer. Because they are the same problem underneath.

Both can be restated as period finding. The powers of $a$ modulo $n$ repeat with some period $r$, and knowing $r$ generally factors $n$. The powers of $g$ modulo $p$ cycle, and a discrete logarithm is a position within that cycle.

More generally both are instances of the hidden subgroup problem over commutative groups, and the quantum Fourier transform solves that whole class. Shor's algorithm is one algorithm, not two.

So the apparent independence was at the level of the best classical attacks, which really are different. It was never at the level of structure, and structure is what a quantum algorithm exploits. That is exactly why the lattice replacement is argued on the grounds of having no such structure rather than on the grounds of being newer.

07.7. Harvest now, decrypt later

Explain why the arrival date of a working quantum computer is the wrong thing to plan around.

Answer. Recording ciphertext is cheap and storage is durable, so an adversary can capture traffic today and decrypt it whenever a sufficient machine exists.

The relevant question is therefore not when the machine arrives but how long a given secret must stay secret. If a document must remain confidential for thirty years and a capable machine is twenty years away, that document is already exposed, today, by the mere expectation of the machine.

There is a second reason the arrival date misleads. Migrating the world's cryptography takes over a decade, because protocols must be specified, libraries written, hardware built and embedded devices replaced. So the work has to start well before the threat, and the lead time is the migration, not the physics.