Substitution Cipher

One of the most readily known Ciphers is called the substitution cipher, in fact you probably played with one as a kid. However what you didn't know is they are all very badly broken.

A Substitution Cipher is essentially where you create a table where you would say A = C, B = W, C = N all the way to Z = A. This table becomes your key for the cipher, we discussed keys in my earlier lesson. For instance is we had the word "ABBA" and we wanted to encrypt that using our cipher it would come out as "CWWC". To decrypt it we would just use the key in reverse.

Caesar Cipher

Back in the days of Rome when Caesar wanted to send secret messages to people he would use something he developed called the Caesar Cipher. This cipher essentially involves a shift in the letters. For example your Caesar Cipher may be a shift of 3, A = D, B = E, C = F... Y = B, Z = C.

In short this shifts all of the letters values over by 3.

Again we we had a message of "Hello" it would become, "Khoor". We do this by again shifting the letters by 3. They key in this case would be the shift of 3.

Breaking The Substitution Cipher

The first question to ask is what is the size of the Key Space? In other words how many keys could their possibly be assuming there are 26 letters. The key is simply a permutation of all of the letters, if you are a math student you should know that to calculate this you use something called a Factorial, denoted by 26!.

26! is equal to about roughly 2^88, meaning our key is an 88 bit key. A key of this size is very adequate, in fact we will be going over very secure ciphers in a bit with key spaces no bigger than that. However because of the way the Substitution Cipher works, it is very easy to break.

To break The Substitution Cipher we use letter frequencies, this is essentially using the probability of a letter occurring in the English language to break the Cipher. The most common letter in English text is the letter "e" at 12.7%, followed by "t" at 9.1% and then "a" at 8.1%.

So for example, if you gave me a Cipher Text to decrypt that was encrypted using a substitution cipher and I know the original plain text was English, I can crack it with only the cipher text and probability. I would count the frequency of letters in the cipher text, lets say "t" is the most common letter. I can say that the decrypted version of "t" is "e" with high probability.

We can then continue to do this with more letters as well as letter pairs. Frequent letters pairs like "he", "an", "in", "th" and so forth can help us even more to create the decryption table.

Next think you know your message is completely decrypted using only the cipher text, we call this kind of attack a Cipher Text only Attack. This is the lowest level of attack and if your cipher is susceptible to it, well it sucks Nono

Vigener Cipher

The Vigener Cipher combines two messages to create a new decrypted one.

k = C R Y P T O C R Y P T O C R Y P T
m = W H A T A N I C E D A Y T O D A Y

C = Z Z Z J U C L U D T U N W G C Q S

Here is an example of a Vigener Cipher. Pretend every letter has a numerical value, a=1, b=2, c=3 and so forth. In the vigener cipher we add up these values and create a new message with it. C+W=Z, R+H=Z, Y+A=Z, and so forth.

So the key in this case is the word "Crypto", replicated as many times as needed to fit the message. Again breaking this is very easy, but we must first assume we know the length of the key, in this case 6.

We would break up the cipher text into groups of 6.

Than we look at the first letter of every group. We know that the most common letter is "e" so lets suppose we went and counted all of the first letters and it turned out to be "h". We know that H is most likely the encrypted version of "e" so theoretically if we subtract "E" from "H" we should get the first letter in the key. H-E= C which is the first letter in the key.

You would continue to do this for the second letter, and then third letter until the entire set is done using letter and letter pair frequencies. Lets say for instance that you did not know the length of the key, you would simply start and assume the key is the length of 1, solve for that.When it doesn't work you would then go to a length of 2, and so forth until it is decrypted.

Rotor Machines

Another famous example is the Rotor Machine. In a rotor machine the key changes after a letter is pressed. The key actually rotates. If we had a key that said Z = E, we then hit a number, that key would cycle over and A = E now. You can decrypt these using similar Cipher Text Attacks.

Post a Comment