Linxz' Blog

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

Home Blog OSCP Journey
24 February 2019

Affine Cipher - Monoalphabetic Substitution Ciphers

Tags: crypto

Introduction

The formula for an Affine cipher is a little bit different to your typical Monoalphabetic Substitution cipher which is why I thought I would explain it a little more in this blog post. So,what is the Affine cipher? Well, the Affine cipher is a Monoalphabetic Substitution cipher whereby each letter in some alphabet is mapped to it’s numeric equivalent using a simple math function. I’m going to do my best to explain this as simply as I can as there is a little bit more math here to a typical Monoalphabetic cipher.

Encryption

  1. We need to select an alphabet in our case we will choose English which will give us the value 26 as there are 26 letters.
  2. We will put this value inside a variable $ m $ and we will map this as $ 0 \; \text{to} \; m - 1 $.
  3. We must decide on a value for $ a $ and a value for $ b $. Now, to get a value for $ a $ it must be coprime with $ m $, in our case it needs to be coprime of 26 as $ m $ stores the size of our alphabet and our alphabet is 26 characters. Because $ a $ has this restriction that it must be coprime with $ m $ we can only choose between the following values $ 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25 $.
  4. We must also decide on a value for $ b $ however, there is no restriction on what our $ b $ can hold as long as $ a $ is not equal to 1 as that is our shift.
  5. For each plaintext letter we will perform $ E(x) ≡ (ax + b) \bmod m $ which will give us our resulting cipher text.

Note: you might remember in post five where we used the gcd function to see if the inverse exists, you can do this with the set in point 3 above to check whether or not these numbers I gave you have an existing inverse.

Before we look at an example let us first take a look at the below encryption function in a little bit more detail. Firstly we have the encryption function that is $ E(x) $ where E is the function and x is our input/plaintext. Moving on we can see that we take a which is a key (that must be coprime to m) we then multiply that with x from there we add b which is another key and we do the whole thing modulo m which is the size of the alphabet in our case 26.

Let’s look at an example for encryption where our plaintext is $ x = \text{AFFINECIPHER} $ and our $ a = 5 \; \& \; b = 8 $ we will map the plaintext in the below table.

$ \mathcal x $ A F F I N E C I P H E R
$ \mathcal x $ 0 5 5 8 13 4 2 8 15 7 4 17
$ (5x + 8) $ 8 33 33 48 73 28 18 48 83 43 28 93
$ (5x + 8) \bmod 26 $ 8 7 7 22 21 2 18 22 5 17 2 15
$ \mathcal y $ I H H W V C S W F R C P

Don’t worry if the table does not make sense! I’ll explain it now. So, firstly we map all letters $ \mathcal{x} $ to their position in the alphabet starting from 0, i.e - $ a = 0, \; b = 1, \; c = 2, \cdots, m-1 $ (this is where our range $ 0 \; to \; m-1 $ plays its part). Next we compute our $ ax + b $ that we talked about earlier in the encryption function, in our case we said $ a = 5, \; b = 8 $ So what we do is 5 times their current position, e.g if $ F = 5 $ then $ 5 \cdot 5 = 25 $ then we just add eight so $ 25 + 8 = 33 $. Finally we take the result and we do $ \bmod 26 $ so for example, $ 33 \bmod 26 = 7 $ and so on,finally we map that to the new position in the alphabet, for example $ F ≡ H $ because $ H $ is the 7th letter in the alphabet and $ 33 \bmod26 = 7 $. See that was not so hard, was it? Remember, we need to do this for all the letters but for each letter the exact same steps apply.

You might be thinking - that’s great! But how do we decrypt? Well, I’ll show you now! If you did not already guess it involves some maths but I promise, it is not that hard!

Decryption

Decryption for an Affine cipher is a little more difficult than decryption for the Caesar cipher for example and there are some important thing that we should note. The multiplicative inverse of a only exists if a and m are coprime, this is why we place the aforementioned restriction on a, if we didn’t place that restriction on a it’s likely that decryption would not be possible. Another thing to note is that a Caesar cipher is just an Affine cipher with $ a = 1 $.

  1. calculate $a^{-1}$ or in other words the inverse of $a$.
  2. we then compute $21(y-8)$ then take the remainder when divided by 26.
  3. the final step is to convert the numeric values back into letters.

Before we finish the example we’re going to look at the decryption function itself. So D is our decryption function, y is our input/ciphertext, we then calculate the inverse of a and multiply that with y minus b and then do the whole thing modulo m.

We can easily derive the decryption function from the encryption function by writing the following.

Now that we’ve analysed the decryption function, lets finish off our example taking the same message that we encrypted and now following the aforementioned steps for decryption.

$ \mathcal y $ I H H W V C S W F R C P
$ \mathcal y $ 8 7 7 22 21 2 18 22 5 17 2 15
$ 21(y - 8) $ 0 -21 -21 294 273 -126 210 294 -63 189 -12 147
$ 21(y - 8) \bmod 26 $ 0 5 5 8 13 4 2 8 15 7 4 17
$ \mathcal y $ A F F I N E C I P H E R

and there we have it, our decrypted cipher text following the same three steps that I gave you. It’s pretty easy! In-fact, it’s so easy you can do it on pen & paper and when these types of cipher were in-use that was kinda’ the point! There’s not an awful lot to this, all you really need to know is A. how modulo works, B. how inverse works and C. basic math operations, as long as you know these three things - you can do this!

Despite the Affine cipher having a more complicated formula than the Caeser cipher, it is still weak as we still see a fixed mapping - this is bad! We will talk more about that in the next post!

Closing Notes

I’m really sorry for the length of time this post took to write/push out. The truth is; I have lately had no energy, motivation or interest to really do anything and for that I am sorry, I don’t know how many people read these posts but that doesn’t really matter so to anyone that reads these, my apologies.

As some of you know I will be starting my OSCP soon so I won’t have time to write these posts however, I am going to try my best to get at least one more out before I start the OSCP and once I finish that, I’ll be back hopefully with plenty of time to work really hard on this series as cryptography is a massive passion of mine and I love to share that with people, I’ve just had a tough time as of late.

In the next post we will look at cryptanalysis on monoalphabetic substitution cipher such as the ones we’ve covered. From there we’re going to move onto polyalphabetic substitution ciphers, the analysis of polyalphabetic substitution ciphers and after that we’re going to move into the real fun stuff which is Stream Ciphers & Block Ciphers. It’s worth noting that each of those will be a lot of the content of this series so start looking forward to that! :D Anyway, that’s my whole spiel that I had/wanted to say, take care and thanks for reading!