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
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.
ZZZJUC|LUDTUN|WGCQS
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.