Substitution Cipher – Introduction
In the section on Caesar ciphers, we saw that there are only 26 possible ways of encrypting a message in English when using a Caesar cipher. A Caesar cipher is actually a special kind of substituion cipher and, if we turn our attention to all possible substitution ciphers based on a single alphabet (i.e. not just those created using a Caesar cipher), we will see that there are a lot more than 26 possible ways of encrypting a message.
Surprisingly, though, the more general substitution cipher is not much more difficult to crack than a Caesar cipher, as we shall see.
How to create a Substitution cipher
A substitution cipher takes the normal alphabet and swaps or substitutes each letter for another letter from the alphabet. This is what the Caesar cipher does, but the Caesar cipher does so with an additional rule: each letter is replaced by the letter that is a certain number of places away from it in the alphabet. So, if 'A' is to be replaced by 'C', then 'B' must be replaced by 'D', 'C' by 'E' and so on.
With a more general substitution cipher, the substitution letter can be chosen at random for each letter. If, therefore, we replace all 'A's with 'G's, then
we could replace all 'B's with any of the remaining letters (the whole alphabet, including 'B', but not 'G' as we have already used that for 'A'). Let us say
that we replace 'B' with 'R', we can now replace 'C' with any letter except the two we have already chosen ('G' and 'R'). And so on, until we have replaced all
26 letters. This is one possible example of what we might end up with:
How many possibilities are there?
The process for working out the number of possible substitution ciphers is as follows:
- When we choose a substitution letter for 'A', there are 26 possibilities to choose from. It is possible in a substitution cipher to replace a letter with itself.
- When we choose a substitution letter for 'B', there are 25 possibilities remaining.
- When we choose a substitution letter for 'C', there are 24 possibilities remaining.
- ...
- ...
- When we choose a substitution letter for 'X', there are 3 possibilities remaining.
- When we choose a substitution letter for 'Y', there are 2 possibilities remaining.
- When we choose a substitution letter for 'Y', there is 1 possibility remaining.
The total number of possibilities, therefore, is 26 x 25 x 24 x ... ... x 3 x 2 x 1.
This is referred to as 26 factorial and mathematicians write it as 26!.
How large is 26 factorial?
- 1! = 1
- 2! = 1 x 2 = 2
- 3! = 1 x 2 x 3 = 6
- 4! = 1 x 2 x 3 x 4 = 24
- 5! = 1 x 2 x 3 x 4 x 5 = 120
- ...
- ...
- 26! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 x 13 x 14 x 15 x 16 x 17 x 18 x 19 x 20 x 21 x 22 x 23 x 24 x 25 x 26 = ...
- 26! = 403,291,461,126,605,635,584,000,000
This is a ridiculously large number, and the substitution cipher obviously offers many more possibilities than a Caesar cipher, and yet it is not much more difficult to crack ...