1.2.1 Cryptanalysis of the Affine Cipher

As a simple illustration of how cryptanalysis can be performed using statistical data, let’s look first at the Affine Cipher. Suppose Oscar has intercepted the following ciphertext:

Example 1.9

Ciphertext obtained from an Affine Cipher

         FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDK
         APRKDLYEVLRHHRH

The frequency analysis of this ciphertext is given in Table 1.2.

There are only 57 characters of ciphertext, but this is sufficient to cryptanalyze an Affine Cipher. The most frequent ciphertext characters are: R (8 occurrences), D (7 occurrences), E, H, K (5 occurrences each), and F, S, V (4 occurrences each). As a first guess, we might hypothesize that R is the encryption of e and D is the encryption of t, since e and t are (respectively) the two most common letters. Expressed numerically, we have e_K(4) = 17 and e_K(19) = 3. Recall that e_K(x) = ax + b, where a and b are unknowns. So we get two linear equations in two unknowns:

This system has the unique solution a = 6, b = 19 (in ). But this is an illegal key, since gcd(a, 26) = 2 > 1. So our hypothesis must be incorrect.

Our next guess might be that R is the encryption of e and E is the encryption of t. Proceeding as above, we obtain a = 13, which is again illegal. So we try the next possibility, that R is the encryption of e and H is the encryption of t. This yields a = 8, again impossible. Continuing, we suppose that R is the encryption of e and K is the encryption of t. This produces a = 3, b = 5, which is at least a legal key. It remains to compute the decryption function corresponding to K = (3, 5), and then to decrypt the ciphertext to see if we get a meaningful string of English, or nonsense. This will confirm the validity of (3, 5).

If we perform these operations, we have d_K(y) = 9y - 19 and the given ciphertext decrypts to yield:

           algorithmsarequitegeneraldefinitionsofarit
           hmeticprocesses

We conclude that we have determined the correct key.

1.2.2 Cryptanalysis of the Substitution Cipher

Here, we look at the more complicated situation, the Substitution Cipher. Consider the following ciphertext:

Example 1.10

Ciphertext obtained from a Substitution Cipher

           YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJ
           NDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ
           NZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ
           XZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR

The frequency analysis of this ciphertext is given in Table 1.3.