Cryptography Reference
In-Depth Information
The Simple Substitution Cipher therefore has a keyspace that is not just bigger
than the keyspace of DES, it is
dramatically
bigger than the keyspace of DES. In
fact, 4
10
26
is approximately 2
88
. As we will see in Section 10.2, this means that
an exhaustive key search for a Simple Substitution Cipher key is close to the limit
of what is currently practically feasible.
×
INSECURITY OF THE SIMPLE SUBSTITUTION CIPHER
There is no doubt that the Simple Substitution Cipher is a considerable
improvement on the Caesar Cipher. Perhaps most significantly, the keyspace is so
big that modern computer systems are not yet powerful enough to comfortably
search through all the possible choices of key. The Caesar Cipher can be thought
of as a highly restricted version of the Simple Substitution Cipher, where only 26
of the possible 4
10
26
letter permutations can be selected as the key.
However, the Simple Substitution Cipher has a critical design flaw, which
means that even with this enormous keyspace, this cryptosystem is easily broken
under most circumstances.
×
2.1.3
Frequency analysis
A good cryptanalyst needs many skills, including the ability to think laterally.
In order to 'break' a cryptosystem every available piece of information should
be used. We are about to see that cryptosystems such as the Caesar Cipher and
the Simple Substitution Cipher have a significant problem that can be exploited.
Intriguingly, this exploit arises because of the typical nature of
plaintexts
.
THE NATURE OF PLAINTEXTS
The job of a cryptographer would arguably be much simpler if cryptosystems
were only used to protect plaintexts consisting of randomly generated data. But,
typically, they are not! In many situations, a plaintext is a meaningful string of
letters that represents words, sentences, perhaps even an entire topic, expressed
in a language such as English. In any language there are certain letters, or
combinations of letters, that occur far more often than others, hence languages are
highly structured. Table 2.1 shows approximate letter frequencies for the English
language.
The letter frequencies in Table 2.1 are expressed to three decimal places,
indicating that, for example, in every 100 000 letters of typical English text we
would expect about 8167 As, 12 702 Es, but only 74 Zs. Of course, this is just an
approximation, but the inference is clear: given any plaintext string in English,
there are likely to be far more occurrences of the letter E than the letter Z.
LETTER FREQUENCY ANALYSIS
The next observation we need to make is that both the Caesar Cipher and the
Simple Substitution Cipher have the property that once we have chosen the
