In this section, we shall consider a generalization of the shift cipher called the affine cipher. Recall that to encode a message using a shift cipher, we convert our text to a number list, rotate each number by the key k, and then convert the encoded number list back to letters.
Here's a quick example of the shift cipher, using the key k = 52. Click on "Shift text" to encode the message.
In terms of congruences, the relationship between p and c is
c p + k (mod 95).
The congruence is modulo 95 because we have a 95-character alphabet (including upper and lower case letters, digits, and punctuation). Decoding a message requires us to solve for p in the above congruence. Using simple algebra, we see that
p c k (mod 95).
Thus decoding looks a lot like encoding.
The affine cipher works in a similar manner, except that the key consists of two numbers a and b. We encode a message by applying the formula
c ap + b (mod 95).
For example, if we take a = 41 and b = 12, then we encipher by clicking on "Affine" below.
To decode a message encoded with an affine cipher, we must solve for p in the congruence
c ap + b (mod 95).
Subtracting b from both sides and then multiplying by a1 (mod 95) yields
p a1(c b) a1c a1b (mod 95).
Note that this is just another affine cipher with key a1 and a1b.
Thus, to decode we first need to compute a1 (mod 95). As noted earlier, this is equivalent to solving the congruence equation ax 1 (mod 95), which can be accomplished using the applet below. In this case, we have a = 41 and b = 1:
We can now decode the following message, which was encoded using a = 41 and b = 12. We decode using the affine applet with the decoding key that we have found.
As you know, for some values of a there will be a multiplicative inverse modulo 95, and for others there will not. Suppose that we had selected a value of a for which there is no inverse modulo 95? One such choice is a 38 (mod 95), as can be seen below.
Check out what happens if we use this value of a.
The problem is clear. Since the letters "b", "f", "k", "p" (and more) are all sent to "R" when encoded, we have no way of knowing how to decode "R". This ambiguity renders the encription system useless. After all, what fun is a secret code if the messages can't be decoded?
The message recorded in the applet below was encoded using an affine cipher with key a = 59 and b = 34. Decode the message.
Section 5.1 | Section 5.2 | Section 5.3 | Section 5.4 | Section 5.5 | Section 5.6
Chapter 5 | DNT Table of Contents
Copyright © 2001 by W. H. Freeman and Company