The transposition cipher provides us with a simple example, but it is not a very secure form of encryption. An attacker who is trying to read your secret messages and knows you are using a transposition cipher will find it easy to use the same algorithm to decrypt your message.

Another kind of cipher, called the substitution cipher, substitutes one letter for another throughout a message. For example, you might decide that 'a' = 't'. In this case, the letter 't' would be inserted into the ciphertext in each place where an 'a' appears in the plaintext. Substitution ciphers have been used since the time of Caesar, and they remain popular today—just look at the “Cryptoquip” in the daily newspaper.

The substitution cipher has one big advantage over the transposition cipher: It uses a key, which is a scrambled version of the alphabet. If attackers are trying to read your secret messages, knowing that you are using a substitution cipher helps them only a little bit, because they would also need to know how the alphabet letters were rearranged. FIGURE 3.5 illustrates the encryption process using a key. If we just consider the 26 letters of the alphabet, there are 26 factorial (26!), or 403,291,461,126,605,635,584,000,000 different possible rearrangements of the alphabet. So we have a lot of keys to choose from!

Let’s look at a simple example of a substitution cipher in action. We will encrypt the word 'flow' using the key 'bpzhgocvjdqswkimlutneryaxf'. Letters are matched up according to their position in the alphabet. For example, the sixth letter in the plaintext alphabet is 'f', which corresponds to the sixth letter in the key, which is 'o'. FIGURE 3.6 illustrates the process. Each letter in the word 'flow' is mapped from the regular plaintext alphabet into the corresponding letter in the key. In this case, 'f' maps to 'o', 'l' maps to 's', 'o' maps to 'i', and 'w' maps to 'y'.

Our next step is to turn this mapping process into a Python function. The important step in the encryption process is to take a letter from the plaintext alphabet and map it into a letter in the ciphertext alphabet. We can do this by using the string index method. Recall that aString.index(ch) returns the first occurrence of ch in the string aString. Using this technique, we can create a string containing all the letters in the alphabet in order and then use the index method to return the position of any letter in the alphabet. Once we know the position of a letter in the plaintext alphabet, we can use the index operator to look up a different letter in the key.

For example, in SESSION 3.13, we find a mapping from the plaintext alphabet to the key alphabet for the letter 'h'. Note that we define alphabetString to contain the letters of the alphabet in order. We include a space at the end so that we can encrypt messages containing spaces. For simplicity, our key here is simply the reverse of the alphabetString. In Session 3.13, we use the index method to find the location of 'h' in alphabetString. We then print the return value to see that the letter 'h' was found at index 7. Using 7 as the index into the key string, we find that the letter 't' should be substituted for all occurrences of the letter 'h' in the plaintext message.

Now that we know how to map characters from the plaintext to the ciphertext alphabet, what remains is to apply this mapping process to each character of the plaintext message, and to construct the final message. For these last two steps, we use iteration and the accumulator pattern. LISTING 3.5 shows a function to encrypt a string using a given key.

If you look at the code carefully, you will notice that the alphabet string contains the 26 lowercase letters of the alphabet along with a space. We add the space at the end of the alphabet so that spaces will also be encrypted. Although the ciphertext will contain spaces, the spaces will represent some other character and consequently will give no hints to an attacker. Another approach would be to delete the space from the alphabet and key and to strip out all the spaces from plaintext before applying any substitutions. This would effectively reduce the string "the quick brown fox" to the string "thequickbrownfox". Removing the spaces, however, would make the decrypted message more difficult to read.

On line 3, we convert any uppercase letters to lowercase letters so that uppercase and lowercase letters will have the same substitution value; that is, if the key substitutes 't' for 'b', then 't' will be substituted for both 'b' and 'B'. Also notice that we do not check whether the character is found on line 6. For simplicity, we assume that the plaintext contains only letters and spaces. To handle digits, punctuation, or other characters, our key would need to provide a unique substitution character for each character we might receive in the plaintext message.

SESSION 3.14 shows the substitutionEncrypt algorithm in action. Notice that even though we encrypt the same plaintext message, we get different ciphertext messages when we use different keys. This is what makes the substitution cipher superior to the transposition cipher. Even though attackers may know that we are using a substitution cipher, that information does not do them any good if they do not have the key. The substitutionDecrypt function is nearly the same as the substitutionEncrypt function.