Sequentia Explores: The Mathematics of Crypto
Part II: The Mathematician’s Toolkit
Lecture 17: Probability & Randomness: Why “Guessing” is Impossible
We’ve now assembled a formidable mathematical toolkit. We have modular arithmetic, primes, Euclid’s algorithm, Fermat’s and Euler’s theorems, and the one-way “trapdoor” functions from discrete logarithms and elliptic curves. We know that the security of these systems relies on the secrecy of a key.
But this raises a critical question: what if our adversary, Eve, simply tries to guess the key?
In movies, we see hackers furiously typing as they “brute-force” a password, trying millions of combinations per second until the lock clicks open. Could Eve do the same for a cryptographic key? The answer, thanks to the mind-boggling scale of modern cryptography, is a resounding no.
Today, we’ll explore the roles of probability and randomness to understand why “just guessing” a modern cryptographic key is, for all practical purposes, impossible.
The Size of the Haystack: Understanding Keyspace
The keyspace of a cryptosystem is the total number of possible keys that can be used. Think of it as the size of the haystack in which the single “needle” (your correct key) is hidden.
Let’s start with a simple lock. A standard 4-digit PIN code (using digits 0-9) has 10 × 10 × 10 × 10 = 10^4 = 10,000 possible combinations. Guessing this is feasible.
Now let’s consider a modern cryptographic standard, the Advanced Encryption Standard (AES), which is used to secure everything from government secrets to your Wi-Fi connection. A common key size for AES is 128 bits.
Remember from our lecture on binary, a “bit” is a 0 or a 1. A 128-bit key is a sequence of 128 ones and zeroes. How many possible 128-bit keys are there?
The total number of combinations is 2^128.
This number, 2^128, is the size of our keyspace. It’s easy to write down, but almost impossible to comprehend. Let’s try to put it in perspective.
2^128 ≈ 340,282,366,920,938,463,463,374,607,431,768,211,456
That’s over 340 undecillion keys.
The Impossibility of Brute Force
Let’s imagine Eve has the most powerful supercomputer imaginable, one that could test one trillion (10^12) keys per second. This is far beyond the capabilities of any current technology, but let’s be generous.
How long would it take this supercomputer, on average, to find the correct 128-bit key? (On average, you’d find it after searching half the keyspace).
- Total keys: 3.4 x 10^38
- Keys to check (on average): 1.7 x 10^38
- Keys per second: 1 x 10^12
- Seconds required: (1.7 x 10^38) / (1 x 10^12) = 1.7 x 10^26 seconds.
1.7 x 10^26 seconds is roughly 5.4 quintillion years.
To put that in perspective, the universe is estimated to be about 13.8 billion years old (1.38 x 10^10 years). Our hypothetical supercomputer would need to run for about 390 quadrillion times the current age of the universe to have a 50% chance of guessing a single 128-bit AES key.
And that’s just for a 128-bit key. AES also uses 192-bit and 256-bit keys. The keyspace for a 256-bit key (2^256) is so vast that it’s often compared to the number of atoms in the known universe. A brute-force attack is not just impractical; it violates the known laws of physics regarding computation (Landauer’s principle).
The Importance of True Randomness
The entire security of this system hinges on one critical assumption: that the key Alice chose was truly random.
If Alice chooses a “predictable” key—like her birthday, her name spelled out in binary, or a simple pattern like 010101…—then Eve doesn’t need to search the entire 2^128 haystack. She can start by searching a much smaller haystack of “common” or “guessable” keys. This is why “password123” is a terrible password.
A cryptographically secure key must be generated by a true random number generator (TRNG) or a cryptographically secure pseudorandom number generator (CSPRNG).
- TRNGs derive randomness from unpredictable physical phenomena, like atmospheric noise, radioactive decay, or the timing of your mouse movements.
- CSPRNGs are algorithms that, given a truly random starting “seed,” can produce long sequences of numbers that are computationally indistinguishable from true randomness.
Without a source of good randomness, even the strongest cryptographic algorithm is worthless. The security of the lock is irrelevant if you leave the key under the doormat.
Probability in Practice: Bitcoin Keys
Let’s look at another real-world example. A Bitcoin private key is essentially a 256-bit number. This means the total number of possible Bitcoin private keys is 2^256.
When you generate a new Bitcoin wallet, your software is essentially picking one number, at random, from this unimaginably large set. The chance of two people ever randomly generating the same private key is so infinitesimally small that it is considered a practical impossibility.
It is far, far more likely that you would win the lottery every second for a hundred years than that you would randomly guess an already-used Bitcoin private key.
This is the power of probability and large numbers. Cryptography doesn’t make guessing hard; it makes it so statistically improbable that it will never, ever happen in the lifetime of our universe. It replaces the physical impossibility of opening a vault with the computational and probabilistic impossibility of finding a needle in a cosmic haystack.
This concludes Part II of our series, “The Mathematician’s Toolkit.” We are now equipped with the core concepts needed to understand real-world ciphers. In Part III, we will finally put these tools to use, starting with the historical ciphers that paved the way for the digital security we rely on today.
