## 5.6  Going Farther: Cryptanalysis

### 5.6.1  The Basics

We begin this section with a simple example of cryptanalysis, the practice of breaking codes. Suppose that Alice and Bill have been exchanging messages using an affine cipher. Oscar suspects that they have been talking about him, and desperately wants to know the contents of their messages. As usual, we may assume that Oscar knows that an affine cipher is being used, and that the message is being encoded one letter at a time. Thus Oscar knows that all he has to do is determine the values of a and b that form the key, and then he can decode everything passed between Alice and Bill. Bill is confident that the code can't be broken, and decides to taunt Oscar by telling him "In our code, the 'a' is encoded to 'M' and the 'w' is encoded to 'b'."

Although he doesn't realize it, Bill has actually given Oscar all the information that is needed to break the code. (No one has ever accused Bill of being the sharpest tack in the box.) To see why, recall that the encoding formula is

C aP + b (mod 95).

Here are the numerical equivalents for the four letters given by Bill.

Your browser does not support java.

Plugging into our encoding formula, we see that

45 65a + b (mod 95)

and

66 87a + b (mod 95).

We now have two congruences in two unknowns a and b. Although these are congruence equations, we can use the same methods as we would for algebraic equations to find a solution. Subtracting the first congruence equation from the second eliminates the unknown b, and leaves us with the single congruence

21 22a (mod 95).

We know all about this type of congruence equation. Let's use our usual applet to find the solution.

Your browser does not support java.

This tells us that a 83 (mod 95). We can then find b by back substitution (i.e., plugging back into either of our original congruence equations). Using the first congruence equation, we have

45 65 · 83 + b (mod 95).

After simplifying, we find that b 65 (mod 95).

#### Exercise 3

The message recorded in the applet below was sent to Bill from Alice using an affine cipher with the keys found above. Help Oscar decode the messsage.

Your browser does not support java.

#### Exercise 4

Alice and Bill have changed their keys. However, Bill has left a scrap of paper lying around which shows that "OK" is now encoded as "na". Use this information to help Oscar decode the message below.

Your browser does not support java.

### 5.6.2  Frequency Analysis

Alice and Bill have learned more about cryptosystems, and now know that they should never let anyone else know both the coded and unencoded versions of the same text. However, it is still possible for Oscar to break their code using a basic method of cryptanalysis called frequency analysis. This involves counting the number of occurances of each character in the coded message, guessing at the correspondence to the original message, and then using this information as we did earlier to find the key.

For example, suppose that Alice has sent the encoded message below to Bill. In this message, the most common character is "R" and the second most common is "F". We can see this by counting by hand, or by using the applet, which will give the frequency of all characters occuring in the message.

Your browser does not support java.

Thus "R" occurs 12 times, "F" occurs 8 times, and so on. In English, the most common characters are " " (a space), "e", and "t" in that order. Thus we might guess that in the encoding process, " " goes to "R" and "e" goes to "F". Here are the numerical equivalents.

Your browser does not support java.

This leads us to the pair of congruences

38 69 · a + b (mod 95)

and

50 0 · a + b (mod 95).

We see immediately from the second congruence equation that b 50 (mod 95). Plugging this into the first congruence gives us

83 69 · a (mod 95).

We can use our applet for solving congruences to handle this equation.

Your browser does not support java.

Thus we see that a 37 (mod 95). We next determine (you may check that this is true) that a–1 18 (mod 95), and then decode the message.

Your browser does not support java.

Sometimes frequency analysis requires more than one try to find the key. Here's an example where the characters occuring in the text do not have the same relative frequency as they generally do in English. Below is an encoded note from Bill to Alice responding to her earlier message. We'll follow the exact same procedure as above, starting with a frequency count for the encoded message.

Your browser does not support java.

We see that "Z" occurs 7 times and "%" occurs 6 times. Thus we initially guess that in the encoding process, " " goes to "Z" and "e" goes to "%". Here are the numerical equivalents.

Your browser does not support java.

This leads us to the pair of congruences

58 0 · a + b (mod 95)

and

5 69 · a + b (mod 95).

We see immediately from the first congruence that b 58 (mod 95). Plugging this into the second congruence gives us

42 69 · a (mod 95).

Using our usual applet, we find that

Your browser does not support java.

Hence a 13 (mod 95), so that a–1 22 (mod 95). Decoding gives us

Your browser does not support java.

What happened? Well, as foreshadowed above, our first guess for the cipher text corresponding to " " and "e" was not correct. Let's try reversing things, and guess that " " goes to "%" and "e" goes to "Z". This gives us the pair of congruence equations

5 0 · a + b (mod 95)

and

58 69 · a + b (mod 95).

Solving (we leave the details to you) yields a 82 (mod 95) and b 5 (mod 95) Since a–1 73 (mod 95), we decode as follows:

Your browser does not support java.

Although Bill's response is a little bizarre, it is clearly English, and so we may conclude that the code has been broken.

#### Exercise 5

Decode the following message:

Your browser does not support java.

#### Exercise 6

Decode the following message:

Your browser does not support java.

Section 5.1 | Section 5.2 | Section 5.3 | Section 5.4 | Section 5.5 | Section 5.6