and she suspects that it was encrypted with a simple substitution cipher using a shift by . Then she can try each of the 26 possible keys, “decrypting″ the message with each putative key and checking whether the resulting putative plaintext makes sense. If the message really was encrypted via a shift by , Trudy can expect to find the true plaintext—and thereby recover the key—after 13 tries, on average.

      This brute force attack is something that Trudy can always attempt. Provided that Trudy has enough time and resources, she will eventually stumble across the correct key and break the message. This most elementary of all crypto attacks is known as an exhaustive key search. Since this attack is always an option, it's necessary (although far from sufficient) that the number of possible keys be too large for Trudy to simply try them all in any reasonable amount of time.

How large of a keyspace is large enough? Suppose Trudy has a fast computer (or group of computers) that can test keys each second.⁴ Then a keyspace of size can be exhausted in seconds, or about 18 hours, whereas a keyspace of size would take more than half a year for an exhaustive key search, and a keyspace of size would require more than nine quintillion years. For modern symmetric ciphers, the key is typically 128 bits or more, giving a keyspace of size 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 , since any permutation of the 26 letters will serve as a key. For example, the following permutation, which is not a shift of the alphabet, can serve as a key for a simple substitution cipher:

In general, a simple substitution cipher can employ any permutation of the alphabet as a key, which implies that there are possible keys. With Trudy's superfast computer that tests keys per second, trying all possible keys for the simple substitution would take more than 8900 millennia. Of course, she would expect to find the correct key half that time, or “just″ 4450 millennia. Since keys is far more than Trudy can try in any reasonable amount of time, the simple substitution passes the crucial first requirement of any practical cipher, namely, the keyspace is big enough so that an exhaustive key search is infeasible. Does this mean that a simple substitution cipher is secure? The answer is a resounding no, as the attack described in the next section clearly illustrates.

      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:

(2.2)

Since it's too much work for Trudy to try all possible keys, can she be more clever? Assuming the plaintext is English, Trudy can make use of expected English letter relative frequencies in Figure 2.2 together with the frequency counts for the ciphertext, which are given in Figure 2.3.