#044: Keeping a Secret

For as long as humans have used written symbols to convey meaning, they have also tried to keep that writing secret, so that only someone with the correct knowledge could read them. Thus, cryptography was born. And along with it cryptanalysis, the study of breaking codes and ciphers.

Early schemes relied on fairly simple algorithms and secrets (and the fact that most people were still illiterate). As time and technology as well as literacy rates marched on, the schemes became more sophisticated, but all pretty much relied on keeping both the algorithm and the key secret to ensure secure communications.

Nowadays, we having enormously fast computing machines at our disposal. This makes cryptanalysis much easier, leaving all these old schemes easily broken. In response, designers of modern encryption algorithm had to come up with entirely new schemes to encrypt data. They also took an unusual step — they made their algorithms public, so others could examine them for weaknesses, meaning these new algorithms only rely on the key alone to provide good encryption.

A modern encryption algorithm like AES (Advanced Encryption Standard) provides not only secure, but also extremely fast encryption, since it relies on fairly basic operations that computers can do very efficiently. Modern CPUs even have specific instructions for dealing with AES, meaning computers can encrypt or decrypt a lot of data very quickly.

(I’ll gloss over a lot of both the mathematical and technical details with regards to AES, but hopefully the links provided will satisfy your curiosity, should you want to know more)

The principle of such algorithms is always the same, though. Alice wants to send Bob a message, but doesn’t want Eve (the eavesdropper) to be able to read it. So, Alice and Bob agree on a special, secret number beforehand, and when Alice sends her message, she uses this number as the key for an algorithm like AES to scramble the message in such a way that Eve won’t be able to get at the contents of the message even if she knows AES was used to encrypt it. Bob can undo this scrambling because he has the same number. You can imagine AES as a set of shuffle, swap, and scramble operations on a set of bytes according to some rules (the key). Even if Eve knows what operations were done on the bytes, without knowing the specific rules, she won’t be able to undo the scrambling, and her only way of breaking it is to just make random guesses. With AES, assuming the key length is sufficient, just randomly guessing keys means even if you use every bit of computing power available on earth on nothing else, you have to wait many times the age of the universe to have a good chance of finding the key. Therefore, AES and its modern brethren are the workhorse of securing communications around the world.

So what would happen if Eve found a new way of factoring huge numbers quickly, or gets her hands on one of those fabled quantum computers? Nothing much, actually. These algorithms don’t involve dealing with prime numbers, or factoring of numbers into primes, so such developments don’t threaten it. In practice, unless someone finds a specific attack against AES, it is a very secure way to encrypt data, and will stay so for the foreseeable future.

The thing is, remember when I mentioned that Alice and Bob agree on a key beforehand? For AES et al. to work, this key must stay a secret between Alice and Bob. But how can Alice and Bob exchange this key over an unsecured channel, like the internet? It’s a chicken and egg problem, because to send the key securely, they need to encrypt their traffic, but to be able to do so, they first need to securely exchange the key. Here’s where a different family of encryption algorithms come into play, and those do depend on factoring numbers into primes. More on that next week.

📖 Weekly Longread 📚

Family loyalty made the Calabrian Mob strong, but its treatment of women was its undoing. The Women Who Took on the Mafia