## 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 ofaandbthat 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

CaP+b(mod 95).Here are the numerical equivalents for the four letters given by Bill.

Plugging into our encoding formula, we see that

45 65 a+b(mod 95)and

66 87 a+b(mod 95).We now have two congruences in two unknowns

aandb. 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 unknownb, and leaves us with the single congruence21 22 a(mod 95).We know all about this type of congruence equation. Let's use our usual applet to find the solution.

This tells us that

a83 (mod 95). We can then findbby back substitution (i.e., plugging back into either of our original congruence equations). Using the first congruence equation, we have45 65 · 83 + b(mod 95).After simplifying, we find that

b65 (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.

## 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.

## 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.

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.

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

b50 (mod 95). Plugging this into the first congruence gives us83 69 · a(mod 95).We can use our applet for solving congruences to handle this equation.

Thus we see that

a37 (mod 95). We next determine (you may check that this is true) thata^{–1}18 (mod 95), and then decode the message.

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.

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.

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

b58 (mod 95). Plugging this into the second congruence gives us42 69 · a(mod 95).Using our usual applet, we find that

Hence

a13 (mod 95), so thata^{–1}22 (mod 95). Decoding gives us

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

a82 (mod 95) andb5 (mod 95) Sincea^{–1}73 (mod 95), we decode as follows:

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:

## Exercise 6

Decode the following message:

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

Copyright © 2001 by W. H. Freeman and Company