Our first cipher!
Till now what we’ve been doing is like walking around a swimming pool and describing it in detail. But unless we dive into the pool, we’ll never really know what it’s like.
So let’s construct a cipher and see how it fares against the principles mentioned in the last post (https://bit.ly/3cjXXQT). Obviously the first one isn’t going to be robust, but we’ll attack whatever we look at and look for potential improvement in our ciphers.
If I told you that you had to encrypt the word “encrypt” in 10 seconds, how would you do it? I think you’d come up with something like this- “hqfubsw”.
It looks like a bunch of letters jumbled together right? What did I do?
It’s nothing complicated- I just shifted all the letters of the word by 3 places.
Refer to the above image to verify what I’ve said.
Anyone who’s prepared for an aptitude test or picked up a puzzle book when they were young will know this cipher. You’ve probably seen it only about a 100 times. Yet this was used by one of the foremost generals of history- this guy below:
The famous Roman leader himself, Julius Caesar. He used the Caesar Cipher for his military operations. According to his design, the letters must all be uniformly be shifted by 3. However in modern parlance, the term ‘Caesar Cipher’ refers to any scheme where the letters are uniformly shifted by an arbitrary number.
What if I want to shift the letters by 25? When we try shifting the first letter, ‘e’, itself we hit a roadblock- we reach the last letter of the alphabet, ‘z’, by the 21st shift. How are we going to shift by 25?
Well, what we do is loop back over the alphabet. So the remaining 4 shifts are started from ‘a’. And so we get ‘d’ as the first letter of the ciphertext (I hope you remember what that word means!). A more formal way to say this is, that the first letter of the ciphertext is the remainder obtained by dividing the sum of the position of the letter in the alphabet and the shift by 26. In clearer words, the corresponding ciphertext for ‘e’ is (5+25)%26, where 5 is its position, and the symbol ‘%’ is called modulo, which is an operation to find remainder. 5+25 is 30, and 30%26 is 4. So the ciphertext is ‘d’ (from the first table).
To make this more generalized, let Σ be any alphabet. It could be the alphabet of English, Mandarin, Sanskrit, your own made-up language, etc ; the symbols don’t really matter. Now let the length of this alphabet be size(Σ) = λ. If the shift is s and the position of the plaintext letter in the alphabet is i, the corresponding ciphertext is (i+s)%λ.
What is the key for this cipher? Well, the one thing that is required to stay secret for it to stay secure is the shift. So the shift is the key.
Let’s summarise what we’ve seen:
Caesar Cipher:
For a key s, plaintext p, an alphabet Σ with length λ, ciphertext c corresponding to p is (p.index + s)%λ . p can be an entire word, like ‘encrypt’- when I say p.index, I mean that we construct the ciphertext by encrypting consecutive letters of plaintext p. The index here gives us the position of the letter in Σ.
For now, let’s just look at the English alphabet.
The key is technically between 0–25 only. I could make the key 5200, but because of the modulo operation, it provides the same shift as 5200%26 =0. So the modulo operation restricts it to a range of 26 possible values. We say that the length of the keyspace is 26. Keyspace is the set of all possible keys, and it’s length in this case is 26 as there are 26 possible shifts.
This is pretty bad, because that means I could just write down all the possible shifts down on a piece of paper. For example, I could shift it by 1, then shift it by 2, by 3, etc. Especially when you consider that the original Caesar cipher only had a shift of 3, which means that we don’t have to go too far to find the actual shift.
Now, I can see why Caesar cipher might have worked in the times of the Roman Empire- the enemy might not even guess that the message has been encrypted in such a manner as the cipher was a relatively new one. This is a type of security by obscurity , which relies on the enemy not guessing the cipher. We’ve already seen in our post on Kirchkoff’s principle that this sort of scheme is inefficient.
Is there any other saving grace? Well, one I could see is that messages encrypted using this scheme might have been long - so diligently writing down 25 more messages of equal length without making an error in shifting would be time-taking and difficult, and by the time they finish decryption there might be no use of the document anymore. After all, many military plans only need to be kept secret for a few hours or days at best, so if it stays secret for that long that’s good enough. And even decrypting a long document which has a known shift of 3 isn’t going to be easy to do manually.
Unfortunately, there are 2 more tools that drive the nail into the coffin of Caesar cipher’s security, not just for the English language but for any language, even if it has 1000 letters(which of course is impractical):
(i) Linguistic analysis : As we described in the last article, we can always use our knowledge of the structure of the language or known plaintext words to make educated guesses about the plain words. For example, I asked you to encrypt the sentence “I want to buy a book on cryptography.” using this cipher, and I encrypted it with a shift of 7 to get “P dhua av ibf h ivvr vu jyfwavnyhwof.”. You know that I have been explaining cryptography, so you could guess that the 12-letter word in the sentence is something related to that, probably the word “cryptography” itself! And you shift every letter of the ciphertext by -7 (a negative shift is basically going backward) to get the original sentence!
To look at another method, you could notice that there are only 2 single-lettered words in the English language- ‘I’ and ‘a’ (barring shortcuts like ‘u’ or ‘y’- we won’t look at those things now) . There are 2 single-lettered words in this ciphertext too- ‘P’ and ‘h’. You could try both and see that when you let ‘P’ correspond to ‘a’ you get “A osfl lg tmq s tggc gf ujqhlgyjshzq.” on performing the required shift, and when you put ‘P’ as ‘I’ you get our original plaintext. So the second one is meaningful and that’s our answer. Just by checking one letter you were able to crack the entire code! Clearly this isn’t very secure.
So we’ve now used both the methods we described in the last article, of checking grammar and context, so that we didn’t have to go through the entire keyspace to find the answer.
Here the second method turned out to be better- just by guessing one letter we were able to crack the entire code! Imagine a top-grade military document being broken like that! Clearly this isn’t very secure.
Well the good side is, at least this still takes time to do manually. Unfortunately, we don’t have to do it manually, because of what we see in the next point described…
(ii) Computers : Even if this cipher had some amount of credibility by the modern, it completely lost all significance with the advent of computers.
The reason is that a general computer can do 10⁹, or 1 billion calculations, in one second. So checking 26 possible keys becomes laughably easy- you could just run a function 26 times and print out the output of each. Anyways not all 26 are going to make sense, and usually only 1 or 2 at most really make any sense.
Even better is that a computer doesn’t make a mistake if you write the function properly- meaning things like ‘manual errors’ don’t mar the decryption process anymore.
So going back to our example from long ago, if Alice planned to encrypt a message with a shift of 15 and sent it to Bob, if Eve gets it she can just decrypt it with all possible shifts and notice that it makes the most sense in terms of grammar and context when the shift is 15. And because of computers, she can do this in under a minute at most.
This sort of attack in which you iterate through the entire keyspace to decrypt a message is called a brute-force attack. It’s the most basic attack- and in fact, no cipher is safe from this sort of attack, because an attacker can always go through every possible key right? What cryptographers work on is making the the time a brute-force attack takes incredibly long- you might hear of some modern ciphers that a brute-force attack takes 2¹⁰⁰ years to decrypt with a computer. That’s like the age of the universe cubed- no attacker is going to get any luck out of attempting a brute-force attack.
That’s partly the reason why quantum computers are a problem to cryptography, because of their insanely better processing speed, making brute force attacks easier- but that’s for much later. For now we need to see if we can improve our ciphers’ resistance to brute force attacks by an outsider. And we will look at this in further posts.
