## How Many Keys Are Possible? A private key is just a string of bits. A key that is `n` bits long has **2ⁿ** possible values — and every extra bit **doubles** that number. Your real key is one single point chosen at random from that whole space, and an attacker knows the space but not *which* point is yours. <viz id="1"></viz> **Drag the key length** and watch the space grow — every key shrinks to a smaller dot as there are more of them. **Press "Pick a random key"** to drop your secret somewhere in the space; press it again and it lands somewhere completely different. That randomness is the whole point. Each cell is one possible key, and exactly one of them — a random one — is the real secret. At a few bits the space is small enough to eye by hand. But every bit you add *doubles* it, and real keys are hundreds of bits long. Next, we'll watch an attacker actually **try to find** that one random point. ## Trying Every Possible Key We saw in <ref slide="1">How Many Keys Are Possible?</ref> that the secret is one needle in a haystack of `2^ℓ` keys. So let's just **try them all** — that's a **brute-force attack**: start at the first key, check it, move to the next, and keep going until one works. The question is no longer *can* it work — brute force always finds the key eventually. The question is *how long it takes*, and that depends entirely on how big the haystack is. <viz id="2"></viz> **Press Start** with a small key length and watch the scan land on the secret almost instantly. Now **drag "Key length" up by a few bits and press Start again** — and again. Notice the search take longer each time, until it barely moves at all. Each extra bit **doubles** the keys to check, so it doubles the time to find one. A few bits is cracked in the blink of an eye. But watch the **"time at 1 billion guesses/sec"** readout: even with hardware trying a billion keys every second, adding bits pushes the search from microseconds, to years, to **longer than the universe has existed.** That's the whole game. Brute force never stops *working* — it stops being *possible*. Next, we'll pin down the exact reason with one idea: an attacker's effort grows like a **polynomial**, but the key space grows like an **exponential** — and an exponential always wins. ## A Cleverer Attack To find a key you try possibilities — one after another, in order or at random. In the worst case you try *all* of them: **2ⁿ** attempts. We just saw how hopeless that gets as the key grows. But trying every key is the *dumb* way. What if the attacker were **clever**? A smarter attack might not need to try them all — it might need only **nᶜ** operations (the key length raised to some small power) instead of the full `2ⁿ`. <viz id="3"></viz> **Press "Next step ▶"** to build the idea one piece at a time: first the towering cost of trying every key (`2ⁿ`), then the clever shortcut (`nᶜ`). **Drag the key length** to grow the brute-force tower, and **turn up the attacker's cleverness** to shrink the clever one — fewer and fewer attempts, until the key is easy to find. That single idea — `nᶜ` instead of `2ⁿ` — is the whole game. The gap between them is astronomical, so *if* a clever `nᶜ` attack exists, the key falls easily. Everything about a key's safety comes down to one question: does such a shortcut exist? ## The Attacker's Full Power Slide 3 gave us the *work* an attack needs: brute force takes **2ⁿ** attempts, while a clever attack needs only **nᶜ**. Now the last piece — how many attempts can an attacker actually run? That's their **hardware, `k`**: the operations they can afford. The key cracks only when the attack's work fits inside that budget: **`nᶜ ≤ k` (brute force's `2ⁿ` never fits)** <viz id="4"></viz> The **gold line** is the attacker's hardware budget `k`. **Turn up cleverness** to shrink the clever tower *below* the line — crack! — or **raise hardware** to lift the line. Notice **brute force (2ⁿ) always towers far above the line**: hardware alone can never reach it. Hardware `k` lifts the line only so far, and brute force's `2ⁿ` stays hopelessly out of reach no matter the budget. The *only* way in is a clever attack whose work `nᶜ` is small enough to duck under the line — and the longer the key, the harder even that becomes. That's the whole picture: **`nᶜ` vs `k`, with `2ⁿ` forever above.** ## The Formal Statement Everything so far adds up to one precise claim cryptographers make: > **No *polynomial-bounded* adversary can break the scheme, except with *negligible probability*.** Three loaded pieces: - **Polynomial-bounded adversary** — an attacker who can only run a *feasible* number of operations `k` (any hardware, from a laptop to every computer on Earth — but still bounded). Brute force needs `2ⁿ` operations, which is *not* feasible. - **For every such adversary** — the claim holds for *any* budget `k`, and for *any* cleverness they might bring. - **Negligible probability** — they can still just *guess*, checking `k` of the `2ⁿ` keys, so the chance is `k / 2ⁿ`. It shrinks faster than `1/nᶜ` for every `c` — vanishingly close to zero, smaller with every extra bit. <viz id="5"></viz> Two real-world dials. **Hardware `k`** rides a compute scale (laptop → GPU → supercomputer → Bitcoin network → all Earth's computers); push it as high as you like and the chance stays negligible — `2ⁿ` sits far off to the right, past all real hardware. **Cleverness** rides an attack-complexity scale (linear `n`, quadratic `n²`, cubic `n³`, …); real crypto lives at the red "no polynomial attack — best is `2ⁿ`" mark. Only if a clever attack's work `nᶜ` drops under the budget does the key break — try it, but no such attack is known. The one honest footnote: this can't be proven outright. The real theorem is conditional — ***if*** no polynomial-time shortcut exists (a **hardness assumption**, like the discrete logarithm), ***then*** no feasible adversary wins more than negligibly. Pick `n = 128` or `256`, and the chance is smaller than any threat you'll ever face.