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
aP + b (mod 95).
Here are the numerical equivalents for the four letters given by Bill.
Plugging into our encoding formula, we see that
65a + b (mod 95)
and
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
22a (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 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
65 · 83 + b (mod 95).
After simplifying, we find that
b 65 (mod 95).
Exercise 3The 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 4Alice 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
69 · a + b (mod 95)
and
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
69 · a (mod 95).
We can use our applet for solving congruences to handle this equation.
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.
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
0 · a + b (mod 95)
and
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
69 · a (mod 95).
Using our usual applet, we find that
Hence
a 13 (mod 95),
so that
a–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
0 · a + b (mod 95)
and
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:
Although Bill's response is a little bizarre, it is clearly English, and so we may conclude that the code has been broken.
Exercise 5Decode the following message: |
Exercise 6Decode the following message: |