6.4 Continuing to Investigate Figure 33, e.g. The Mysterious Right Column

Here are some further observations about Figure 33.

• As suggested in Section 5.1, we can read the bottom line of canonical (sorted top-line) encryption keys shown in Figure 32 off of the labels of the tables in the left column of Figure 33. Why? Well, if we unscramble frequencies, then the ciphertext labels should match up with the plaintext labels.

• Again, as in Section 5.1, in this example, we were matching frequencies for ciphertext to frequencies for plaintext, which is an unusual situation: Usually, we do not know the plaintext -- that is why we need to crack the cryptosystem! Thus, normally we try to match ciphertext frequencies as best we can with training text frequencies.

• Aside: Here is a sanity check.

  Remember, the frequencies at each Stage are those of the ciphertext obtained by applying the encryption key to the plaintext. Note that there is nothing in that description about the path taken, i.e. which swaps were used and what order they were performed. Thus, the frequencies should depend on the key but not the path taken to reach the key. We see that at least in Figure 33 that this is indeed the case.

  Consider the ciphertext at Stage 2:

  c ccc cbbc cbd cd ca cac caa bcc bca dcb db dad acb aca acac ad
  Observe that Figure 33 shows two ways to reach the ciphertext from plaintext:
  Stage 0 $\rightarrow$ Stage 1 $\rightarrow$ Stage 2 and Stage 2 $\leftarrow$ Stage 3 $\leftarrow$ Stage 4.
  Figure 33 also shows two ways to reach plaintext from the ciphertext:
  Stage 0 $\leftarrow$ Stage 1 $\leftarrow$ Stage 2 and Stage 2 $\rightarrow$ Stage 3 $\rightarrow$ Stage 4.
  In all cases above, the path taken to reach Stage 2 or Stage 0/4 does not affect the resulting frequencies.

• At Stage 2, we can easily compute (count frequencies!) the middle table from the ciphertext but not the left table -- figuring out the order of the labels is equivalent to decrypting!

• At Stage 2, the left table (which matches the table for plaintext) is (assumed to be) close to training text.

• The contents of the middle table are not close to the original table in Stage 0. Therefore, the middle table is not close to training text.

Thus, using bigram frequencies still looks hopeful, i.e. it looks like maybe ciphertext frequencies appear to (usually) be far from intrinsic frequencies.

Let us elaborate a bit on ``read key off of the labels''. Suppose we go back to Stage 2 and copy the middle table into the right column. What happens if, when we perform the swaps shown in the middle column, we modify both the labels and the contents? This is shown in the right column. Observe that again, no matter whether we take the path Stage 0  $\leftarrow$ Stage 1  $\leftarrow$ Stage 2 or Stage 2  $\rightarrow$ Stage 3  $\rightarrow$ Stage 4 we end up with a table that is (close to) the original, i.e. we have unscrambled frequencies. Furthermore, in both paths, we can indeed read off the encryption key!

Thus, we use swaps to generate and search for the best table, i.e. the table closest to the table of intrinsic frequencies (as approximated from training text). When we do a swap, we modify both the labels and the corresponding rows and columns of frequencies. (Conceptually, this means we do not rename letters during the search, merely reorganize the frequency information.) When we get a close match to training text --which we assume is close to plaintext-- we read off the encryption/decryption key from the labels, which allows us to decipher the ciphertext.

It remains now only to clarify how to perform the search.

Roadmap
Section 3.7	Encipher plaintext $\Rightarrow$ scramble frequencies.
Section 3.7	Decipher ciphertext $\Rightarrow$ unscramble frequencies.
Section 4.2	(Hope) Unscramble frequencies $\Rightarrow$ decipher ciphertext
Section 4.3	Unscramble = Bring ``close'' to intrinsic frequencies
	Approximate intrinsic frequencies with training text
	Assume ciphertext is medium to large so that unscrambled frequencies resemble intrinsic frequencies
Section 4.4	Use the L1 distance to measure ``closeness''; ignore labels.
Section 5.1	Sorting unigram frequencies does not work, but ``almost'' does.
	(Hope) When the frequency table for ciphertext matches the table for training text, read the encryption key off of the labels
Section 5.2	``Sort bigram frequencies'' is problematic.
Section 5.3	Exhaustive search is too slow; therefore, need an incomplete search.
Section 6.1	(Idea) Hill-Climbing: pick the best ``neighbor''
Section 6.2	Why swaps are so important, e.g. used to generate ``neighbors''
Section 6.3	The effect of swaps on bigram tables
$(\rightarrow)$     Section 7.1	Clarifying Hill-Climbing