Cryptography: Extreme Basics
If you’ve spent some time on CT, you’ve probably heard terms like “private key” and “public key”, but you probably don’t know what it actually means. After all, you don’t really need to know anything other than a private key is like a password. But what is cryptography anyways?
Warning: do not attempt to use any of the information contained to encrypt valuable information, as it is intended to be a non-rigorous overview of the topic.
Basic Motivation
The original motivation behind cryptography was the need to send coded military plans in a language only you and your friends can understand. For example, if you’re Julius Caesar, and you want your legions to cross the Rubicon at dawn, it would be a pretty useful thing to be able to send that message to your loyal subordinates without risking the message being comprehensible if captured by a senator. This is the mythological origin of the first encryption method we know of, the Caesar cipher.
Basic Terminology
Cryptography means “hidden writing”.
Encryption is converting your message in plain writing (a “plaintext”) into a scrambled message known as a “ciphertext” that can only be understood by your friends.
Decryption is the process of converting a ciphertext back into plaintext.
A cryptosytem is a system for encryption and decryption.
Encryption
An encryption function is a function that takes a plaintext and encryption key as an input and outputs a ciphertext.
Decryption
A decryption function is a function that takes a ciphertext and decryption key as an input and outputs the original plaintext.
Some cryptosystems use the same key for encryption and decryption. These cryptosystems are known as symmetric cryptosystems. Other cryptosystems, like RSA, use a different key for encryption and decryption. These cryptosystems are known as asymmetric cryptosystems.
Let’s put the knowledge we now know to use in a basic example.
The Caesar Cipher
The Caesar cipher is the most basic cryptosystem known to humanity. It works as follows:
Bob wants to pass notes to Alice without his teacher Mallory being able to tell the contents of the message if she catches them, since the details of the message are about how much weed they’re going to smoke later that day. To do so, he shifts all of the letters in his message down 3 in the alphabet- for example, the letter “a” becomes “d”, and “b” becomes “e“, and so on. Bob tells Alice before class that the key is 3.
During class, he wants to write “I cant wait to smoke weed in my moms basement later”. By shifting all the letters over 3, the ciphertext becomes
L fdqw zdlw wr vprnh zhhg lq pb prpv edvhphqw odwhu
Pretty incomprehensible right? Not for Alice. Since she knows the key is 3, she can simply shift all the letters backwards 3 and recover the plaintext. Try it yourself if you don’t believe me- it’s a bit easier if you write the alphabet down first.
Of course, this encryption method is extremely trivial to break in practice. For starters, it leaks a massive amount of information about the plaintext- notice how the length of each word is the same. It’s a bit better if you remove all the spaces when you send it, and still easy to decipher, but even then you’d be in trouble if you actually used this cryptosystem in real life, since there’s only 25 possible keys. Think about it: you can only shift the letters forward 25 spaces before you just loop it back to the original plaintext, and shifting forward by 27 is the same as shifting forward 2. Because of this, a remotely intelligent adversary can just try each of the 25 possible keys and recover the plaintext. We need something a bit better.
Zimmerman Ciphers
The Zimmerman cipher was used in the early 20th century to send encrypted messages from Germany to Mexico. Unlike the Caesar cipher, we don’t shift individual letters to other ones- instead, we map each word to a random number. For example, “hello” could be mapped to “156” and “world” could be mapped to “11518”. Thus, “hello world” would be encrypted to "156 11518”. So a really long message like “We intend to begin on the first of February unrestricted submarine warfare” becomes “130 13042 13401 8501 115 3528 416 17214 8491 11310 18147 18222”. Seems pretty hard to crack right? It’s still a bit of an issue that we have to send the mapping of each word in the dictionary to a number via a secure channel in order for them to be able to read any of our messages sent later on, but if we send the mappings before war starts we can then communicate a ton later on without worrying our enemies know what we’re up to.
Unfortunately, Zimmerman Ciphers are also trivial to break using modern methods. The reason is that considerable information about the plaintext is still present in the ciphertext- most importantly the frequency of words. If someone captures our ciphertexts, they’ll notice over time that the number “1847” is the most common, and conclude that it means “the”, and so on. Using such frequency analysis, it’s relatively trivial to break a Zimmerman cipher over time.
Modern Encryption
Modern encryption methods take advantage of some wonderful properties of the universe. Firstly, it’s possible to convert any information into binary- for example, we can convert “hello” into “0101101” (this isn’t actually hello in binary but you get the idea). Using this property, we can then use various methods to scramble the resulting binary plaintext into a string of 0’s and 1’s where there are equal amounts of 0’s and 1’s regardless of the contents of the plaintext. This prevents leaking information of the plaintext like a Zimmerman cipher does. As an example of a simple yet impractical modern cipher, we can look to Vernam ciphers.
Vernam Ciphers
To begin, a Vernam cipher converts a plaintext message into binary. Let’s say that the result of this process is
1000100101110010
We then choose a random key of the same binary length, let’s say
0010101011001101
We then perform the XOR operation on the plaintext message and key. The XOR operation is simple: imagine that the plaintext and key are stacked on top of each other. Take the first digit in each row: “1”, and “0”. If the numbers are different, output “1”. If they’re the same, output “0”. Iterate until you have no remaining 0’s or 1’s. In our case:
1000100101110010
XOR
001010101100110
=
1001110000010100
That’s all we have to do for encryption! Note that the key length is as long as the message we wanted to send though…
To perform decryption, just XOR the ciphertext with the key like so:
1001110000010100
XOR
001010101100110
=
1000100101110010
Wow! We actually got our plaintext back, and it seems pretty much impossible to break without knowing the key we used. There’s a huge problem though: for this to work, we have to send a secret key as long as the original message, and since the key length has to be the same as the plaintext, we can’t reuse the same key over and over or we’d leak information about our key and plaintexts to an attacker. Consequently, you may as well just send the original message via the same secure channel you used to send the key.
Asymmetric (Public and Private Key) Encryption
Public and private key encryption make the internet possible. Without it, you couldn’t conduct commerce or exchange any valuable information, since the contents of internet traffic are public knowledge if not encrypted. This is a huge problem though, as it’s extremely frequent for people who have never met to need to send encrypted information back and forth, and there’s no way for those people to send secret Vernam cipher keys to each other over the internet without having met.
This problem was unsolved until the 1970’s, with the invention of RSA and similar techniques like Diffie-Hellman key exchange.
At an extremely high level, the way RSA works is that Bob makes a public key available on the internet that’s composed of two numbers, e and n, and Bob also chooses a private key d based on two random prime factors of n that he keeps to himself. (A prime number is a number that can only be divided by 1 and itself. A prime factorization of n is two prime numbers that can be multiplied together to get n). People wishing to communicate with Bob can then encrypt their message using this public key and send it to Bob, and only Bob can decrypt it since only Bob knows d and computing random prime factors of a large n is extremely computationally intensive. This is an absolutely amazing innovation: We can now send secret messages over the internet to anyone with a properly chosen public and private key! There’s no need at all to send a key along a secure channel like a Vernam cipher.
This technology made the Silk Road possible, and it also plays an important role in Cryptocurrencies like Bitcoin, since only someone with the correct private key can move Bitcoin to a different wallet.