Linxz' Blog

Still trying to think of something witty, I will let you know once I get something...

Home Blog
23 February 2019

Caeser Cipher - Monoalphabetic Substitution Ciphers

Tags: crypto

Introduction

Now that we’ve outlined the history behind cryptography quite thoroughly, we’re going to get stuck into some of the more “fun” elements of cryptography. I really wanted this course to be a cryptography ground up course which is why we spent so long on the preface side of things however I think that it is/will be beneficial to people reading this series so I decided that we’ll stick with it and re-title it to “Preface to Cryptography”.

With that said, now let’s move into the more fun stuff and start taking a look at some of the historic ciphers, seeing what they get right, what they get wrong and analysing why we don’t use them, in a separate post we’ll explain how to attack them but for now, let’s just take a look at the design side of things and get involved in a very small amount of maths!

Monoalphabetic Substitution Ciphers

Everyone will know what this is! Perhaps you’ve never heard the term “Monoalphabetic Substitution cipher” before and that’s fine as it’s really just the more technical way of saying “simple substitution cipher” - you might be thinking, “oh, like Caeser ciphers?” and that is exactly correct! That is exactly what this is. A Monoalphabetic Substitution Cipher can be defined as a cipher scheme where we rely on a fixed replacement structure. That means the substitution is fixed for every letter based on the “shift” that we decide on. Let’s use a Caeser Cipher as an example to get a better understanding of this.

  1. Alice decides she wants to send a message to Bob, her plaintext message is $ \text{alice is cool} $ she decides to use a simple substitution cipher (monoalphabetic sub cipher) to make this message unintelligible to everyone except Bob.
  2. Alice & Bob agree that they will use a shift of 3 (Making this a Caeser Cipher)
  3. Alice shifts every letter by 3 turning $ \text{alice is cool} $ into $ \text{dolfh lv frro} $. (You might already be able to see what we mean by fixed replacement structure :D)
  4. Bob then decrypts this by doing the opposite of what Alice did, so where Alice took every letter and did >>>3 Bob will now take every letter and do <<<3 thus giving him the original message.

So, for those that don’t see where the “fixed replacement structure” comes into this. Let’s take the last word in the message; $ \text{cool} $ as you can see we see the letter $ o $ twice. Now let’s look at the corresponding cipher text for $ \text{cool} $ when we shift by three, oh look it is $ \text{frro} $. Do you notice how we see a double $ r $ appear? That is what it means to have a fixed replacement structure. So, in short if we have the letter $ a $ and it becomes $ g $ then every time we use this encryption function $ a $ will become $ g $ and that is guaranteed! This is the entire idea behind a Monoalphabetic Substitution Cipher and it is the reason this became known as a “simple substitution cipher”.

You might be thinking - okay Linxz, that is great! But what about if we have the letter $ z $ & we shift by three? What happens?! Well, we simply wrap around! You will hear that term a lot and all it means is, if we take $ z $ in a shift of three, it will become $ c $ you might be thinking; “what the hell is this guy talking about!?” I’ll show you below.

A B C D E F G H I J K L M N O P Q R X T U V W X Y Z
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
A B C D E F G H I J K L M N O P Q R X T U V W X Y Z

You see how simple that is!? Couldn’t be easier, right? As I said, we won’t talk much about the attacks here, but if an attacker wanted to decrypt this all they would need to do is try all possible shift values for the cipher text. So, we’ve seen how decryption works but I did actually miss a very important point! In this encryption scheme we are using an injective function, or in other words a one-one mapping. For example, if A ↔ D then we cannot do Z ↔ D. This is because of this “injective function” that we’re using in this type of encryption scheme, this is quite important to remember as imagine if I sent you a message where A ↔ D and Z ↔ D how as the receiver would you know what I meant? Of course in this case, it’d probably be pretty obvious however in other cases it might not be so obvious thus we’re using this “injective function” which as I said basically just means letters have a one-one mapping.

Although we have been talking heavily about a Caeser cipher here, it is not the only Monoalphabetic substitution cipher, there are more! However, I won’t talk about those here, if you’re interested in them you can go away and research them in your own time but they’re very weak and we don’t use these any more, well I would hope not. With that said, we will look at the Affine Cipher as it is a little different from your typical/common Monoalphabetic Substitution cipher and although weak, I thought it might be a nice little introduction into some maths, haha! :D

For those of you who are nerds (like myself) it is worth noting that the below is the mathematical notation for a simple substitution cipher. Where $ e $ is our encryption function, $ p $ is our input text/plaintext, $ k $ is our key/shift value and $ \bmod 26 $ is modulo 26 for the total number of letters in the English alphabet.

As for the decryption function? Well, just as simple! It is really that easy! If you don’t know what the Modulo function is, I suggest you either A. read my previous post on it or B. read up on it, it’s very important in cryptography C. do both :D

Just some final few math things for this post, I’ll quickly lay out the mathematical defintion of a Shift Cipher, it’s not super important but seen as we spent so long looking at the math, I figured it was the right thing to do.

Essentially, we map the alphabet into the ring $ \mathbb{Z} $ which is as we mentioned in the last post the most basic ring in math, with an index of 26 elements (for our alphabet).

Closing Notes

I believe that is everything for the post this week, next week we will look at the Affine cipher, this is where we will first see some application of multiplicative inverse which we covered last week. Thank you for reading, I hope the post was of adequate length, did not want to go for too long because I wanted to convey the application of the math we’ve been learning properly to avoid later confusion.

Dedicating this post to Uber for being supportive of my bucket passion.