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
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
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
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
ap + b (mod 95).
Subtracting b from both sides and then multiplying by a–1 (mod 95) yields
a–1(c – b)
a–1c –
a–1b (mod 95).
Note that this is just another affine cipher with key a–1 and –a–1b.
Thus, to decode we first need to compute
a–1 (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?
Exercise 2The message recorded in the applet below was encoded using an affine cipher with key a = 59 and b = 34. Decode the message. |