4.1. General Substitution#
Before we get to a rigid system of mapping letters to each other, we should discuss substitution ciphers more generally. We can mathematically describe a substitution cipher as a permutation of the alphabet, perhaps most easily visualized as we’ve already seen, with 2 rows of letters. The top row is our normal plaintext alphabet, and the bottom row the permutated ciphertext alphabet. Here’s an example inspired by looking at my keyboard
plaintext: a b c d e f g h i j k l m n o p q r s t u v w x y z
ciphertext: Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
Using this mapping to encipher phrase would result in the following:
plaintext: mathematics
ciphertext: DQZIT DQZOE L
This system is relatively easy to use by hand, both to encrypt and decrypt messages, as long as both the sender and the recipient have the correct mapping between letters. In this system, the mapping is the key. How many possible keys are there?
Counting Keys#
Counting the number of keys in a given cryptosystem is a common task for any cryptologist. It provides a rough measure security for a given system: a system with many keys is typically more secure than a system with very few keys, since the chance of guessing the correct key is much lower.
In this general system, where there’s discernable pattern used to map plaintext letters to ciphertext letters, there are quite a few possibilities. You might be tempted to guess \(26^{26}\), as there are \(26\) choices for each letter; however not all of these choices are simultaneously possible. Remember, we defined earlier that no two letters can be mapped to the same letter in the ciphertext. Therefore, once we’ve determined which ciphertext letter is mapped with plaintext letter a, it’s no longer longer a choice that can be mapped to plaintext letter b, and only \(25\) choices remain.
Therefore, the number of possible keys in a general subsitution system can be computed by:
\(26\cdot25\cdot24\cdot23 \cdot \ldots \cdot4\cdot3\cdot2\cdot1\)
The mathematical function known as the factorial, which uses the exclamation point as its notation (\(!\)) can more compactly express such products where each subsequent factor is one fewer than the previous factor. This is a specific type of recursive function, which is defined to be a method where the solution depends on smaller instances of the same problem. For example, to compute \(5!\), you can take the solution to \(4!\) and multiply it by \(5\), since \(5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5 \cdot 4!\). Recursive functions are widely used in computer science, so we’ll likely see more examples of these in the future.
The factorial function: Let \(n\) be a nonnegative integer. We define the factorial of \(n\), written \(n!\), recursively by setting \(0! = 1\) and \(n! = n \left( n - 1 \right)!\) for \(n \geq 1\). Thus \(2! = 2 \cdot 1 = 2\), \(3! = 3 \cdot 2 \cdot 1 = 6\), and in general \(n! = n \cdot \left( n - 1 \right) \cdots 2 \cdot 1 \)
We can use Python to evaluate \(26!\):
# Initialize a counter variable at 1
counter = 1
# This loop iterates `number` from 26 down to 2
# and multiplys it against the value of `counter`
# and then stores the new value back to `counter`
for number in range(26,1,-1):
counter = counter * number
# Print the results
print(counter)
403291461126605635584000000
So \(26\) factorial is written as \(26!\) and is equal to \(403,291,461,126,605,635,584,000,000 \approx 4.03 \cdot 10^{26}\)
That means there are well over \(10^{26}\) distinct mappings, or keys, for this type of system. That’s quite a lot! While at first this may seem like a great feature, we’ll see it also introduces some problems as well. The benefits are that we have a huge number of possible keys at our disposal, so if the message is intercepted the chance of the eavesdropper correctly guessing the one we used is extremely low. However, the downside is that both the sender and receiver need to find a way to agree upon one of the many keys available. This means that everyone who plans to use this system with each other would need to memorize the bottom row of the mapping table, which is not always an easy task. One possible way to ease this process is to use a keyword.
Keyword Substitution#
A keyword subsitution scheme will greatly cut down on the possible number of mappings between plaintext and ciphertext letters, but it has the benefit of being much easier to remember. Start by choosing a word or phrase. We’ll use science math for our keyword. Remove any spaces and then remove any repeated letters, leaving us with scienmath, and use this reduced keyword to start the mapping between plaintext and ciphertext letters:
plaintext: a b c d e f g h i j k l m n o p q r s t u v w x y z
ciphertext: S C I E N M A T H
To finish out the mapping, go from A to Z in order, skipping over any already used letters:
plaintext: a b c d e f g h i j k l m n o p q r s t u v w x y z
ciphertext: S C I E N M A T H B D F G J K L O P Q R U V W X Y Z
You can probably see that this does a pretty good job mapping letters near the keyword, but not near the end of the alphabet, where in this example u through z in the plaintext are mapped to the same letters in the ciphertext. One way around this is to use longer keywords that contain a variety of letters, including those at the end of the alphabet.
keyword: quick brown fox jumped over the lazy dog
plaintext: a b c d e f g h i j k l m n o p q r s t u v w x y z
ciphertext: Q U I C K B R O W N F X J M P E D V T H L A Z Y G S
Another way around this is to use a secondary piece of information, a keyletter, to offset where you place the keyword.
Keyletters#
Suppose we chose a keyletter of g to go with the keyword/keyphrase of science math. We would begin the same way, reducing the keyword down to scienmath. However, instead of placing this reduced keyword at the start of the cipher alphabet, we would place it underneath the position indicated by the keyletter of g.
plaintext: a b c d e f g h i j k l m n o p q r s t u v w x y z
ciphertext: S C I E N M A T H
Then, we carry on as normal placing the unused letters of the alphabet in order after the keyword. When we reach the position underneath z in the plaintext alphabet, we wrap back around to a. This has the benefit of ensuring that the letters at the end of the alphabet don’t always get mapped to themselves.
plaintext: a b c d e f g h i j k l m n o p q r s t u v w x y z
ciphertext: U V W X Y Z S C I E N M A T H B D F G J K L O P Q R
Exercise for the Reader#
Could you write a Python program that takes in a keyword or phrase and outputs the ciphertext alphabet that would be paired with the standard plaintext alphabet?