alt="2 Superscript 128"/> or more.
Now, back to the simple substitution cipher. If we only allow shifts of the alphabet, then the number of possible keys is far too small, since Trudy can do an exhaustive key search very quickly. Is there any way that we can increase the number of keys? In fact, there is no need not to limit the simple substitution to a shifting by
| 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: |
Z P B Y J R G K F L X Q N W V D H M S U T O I A E C
|
In general, a simple substitution cipher can employ any permutation of the alphabet as a key, which implies that there are
2.3.2 Cryptanalysis of a Simple Substitution
Suppose that Trudy intercepts the following ciphertext, which she suspects was produced by a simple substitution cipher, where the key could be any permutation of the alphabet:
Since it's too much work for Trudy to try all
Figure 2.2 English letter relative frequencies
From the ciphertext frequency counts in Figure 2.3, we see that “ F ″ is the most common letter in the encrypted message and, according to Figure 2.2, “ E ″ is the most common letter in the English language. Trudy therefore surmises that it's likely that “ F ″ has been substituted for “ E .″ Continuing in this manner, Trudy can try likely substitutions until she recognizes words, at which point she can be confident in her guesses.
Figure 2.3 Frequency counts for ciphertext in 2.2
Initially, the easiest word to determine might be the first word, since Trudy doesn't know where inter‐word spaces belong in the text. Since the third plaintext letter appears to be “ e ,″ and given the high frequency counts of the first two letter, Trudy might reasonably guess (correctly, as it turns out) that the first word of the plaintext is “ the .″ Making these substitutions into the remaining ciphertext, she will be able to guess more letters and the puzzle will begin to unravel. Trudy will likely make some missteps along the way, but with sensible use of the statistical information available, she will find the plaintext in considerably less time than 4450 millennia.
This attack on the simple substitution shows that a large keyspace is not sufficient to ensure security. It also shows that cipher designers must guard against clever attacks. How can we protect against attacks when new attacks are developed all the time? The answer is that we can't and, as a result, a cipher must be subjected to extensive analysis by skilled cryptographers before we can trust it—the more skilled cryptographers who have tried to break a cipher and failed, the more confidence we have in the cipher.
2.3.3 Definition of Secure
There are several reasonable definitions of a secure cipher. Ideally, we would like to have a rigorous mathematical proof that there is no feasible attack on a system, but such ciphers are few and far between, and provably secure ciphers are impractical for most uses.
Lacking a proof that a cipher is secure, we could require that the best‐known attack on the system is impractical, in the sense of being computationally infeasible. While this would seem to be the most crucial property, we'll use a slightly different definition. We say that a cryptosystem is secure if the best‐known attack requires as much work as an exhaustive key search. In other words, no shortcut attack is known.
Note that by our definition, a secure cipher with a small number of keys could be easier to break than an insecure one with a large number of keys. While this may seem counterintuitive, there is a method to the madness. The rationale for our definition is that a cipher can never offer more security than an exhaustive key search, so the key size could be considered its “advertised″ level of security. If a shortcut attack is known, the algorithm fails to provide its advertised level of security, as indicated by the key length. In short, a shortcut attack indicates that the cipher has a fundamental design flaw.
Note also that in practice, we must select a cipher that is secure (in the sense of our definition) and has a large enough key space so that an exhaustive key search is impractical. Both factors are necessary when choosing a cipher to protect sensitive data.
2.3.4 Double Transposition Cipher
In this section we discuss another classic cipher that illustrates some important basic concepts. The double transposition presented here is a weaker form of the usual double transposition cipher. We use this form of the cipher since it provides a slightly simpler means of illustrating all of the points
