Have you ever wondered how you would secure your communication if an electromagnetic pulse destroyed all the computers around you? Do you distrust hardware manufacturers so much that you refuse to rely on anything you didn’t carve out of wood?
If you answered yes to any of these questions, this series of articles is for you, as it will explore the world of “low tech” cryptography. By this, I mean cryptographic tools that can be used without a computer while still preserving high-security standards.
As an introduction, I will talk about one of the most famous encryption technique (and the only one that’s theoretically uncrackable): One-Time Pads.
A bit of history
The One-Time Pad is one of the oldest ciphers to be still considered secure in 2019, even though it was invented in 1882, by Frank Miller. At the time, it served to secure telegraphic communications between American banks.
It only gained popularity amongst the worldwide military and diplomatic corps after being re-invented by Gilbert S. Vernam in 1917. In 1945, Claude Shannon from Bell Labs proved that one-time pads were secure, even against an adversary with unlimited computing power.
Coins, cards and dices
The one-time pad has a simple requirement to work securely: a truly random key as long as the text you want to encrypt. True randomness is something that’s not doable for computers, as they are deterministic systems that can hardly generate anything unplanned by their programs. That’s why computer random number generators are usually considered pseudo-random.
The good thing is that even if randomness is hard for computers, it doesn’t have to be hard for us. There’s plenty of good sources of randomness around that can be used to generate a key. The only thing you have to keep in mind is to pick one that’s in the same base as the kind of text you want to encrypt:
- If you have binary-encoded data (or morse code) coin flips make for a perfect base 2 random number generator
- If you want to encrypt letters from the Latin alphabet (base 26), half a 52 cards deck can work
- If your plaintext is made of letters and numbers from the Latin alphabet (36 characters in total), you can throw 6 times a 6 sided dice
OTP in practice
Once you have generated a key as long as the text you want to encrypt, you can generate a ciphertext by adding the key to the plaintext, modulo the basis.
Let’s take the string “HELLOWORLD” as an example. If you convert it to number of base 26 (0 for A, 25 for Z), it becomes [7, 4, 11, 11, 14, 22, 14, 17, 11, 3] Now using half a pack or card, or two dice of ten and a dice of 6, we pick the following random numbers [0, 23, 25, 14, 6, 15, 22, 6, 9, 23]. The last step is to add the plaintext to the key, modulo 26. In python it would match the following code:
>>> plaintext = [7, 4, 11, 11, 14, 22, 14, 17, 11, 3] >>> key = [0, 23, 25, 14, 6, 15, 22, 6, 9, 23] >>> [(p + k) % 26 for p, k in zip(plaintext, key)] [7, 1, 10, 25, 20, 11, 10, 23, 20, 0]
If anyone tried to directly decode the given ciphertext obtained above, they would read “HBKZULKXUA”. If they have the key, they can do the opposite of the previous operation which is simply subtracting the ciphertext with the key, modulo 26.
>>> ciphertext = [7, 1, 10, 25, 20, 11, 10, 23, 20, 0] >>> key = [0, 23, 25, 14, 6, 15, 22, 6, 9, 23] >>> [(c - k) % 26 for c, k in zip(ciphertext, key)] [7, 4, 11, 11, 14, 22, 14, 17, 11, 3]
Sadly, this algorithm has a big issue: since the key is as long as the plaintext, it creates a key distribution problem. You will need a secure channel over which you can send a key as long as the plaintext efficiently, which is usually exactly the kind of thing you lack if you need to use secure encryption.
The key also needs to be regenerated for every single message (or it stops being random and the cipher stops being secure). This can be a very tedious and long process, which makes one-time pad unsuitable for any lengthy message.
As I will show in my next articles, multiple cryptographers worked on solving those problems by creating more sophisticated ciphers that rely on fixed lengths key.