5.5  Going Farther: Affine Ciphers

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.

Your browser does not support java.

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 === ck (mod 95).

Thus decoding looks a lot like encoding.

Your browser does not support java.

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.

Your browser does not support java.

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 a–1 (mod 95) yields

p === a–1(cb) === a–1ca–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:

Your browser does not support java.

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.

Your browser does not support java.

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.

Your browser does not support java.

Check out what happens if we use this value of a.

Your browser does not support java.

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 2

The message recorded in the applet below was encoded using an affine cipher with key a = 59 and b = 34. Decode the 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

Chapter 5 | DNT Table of Contents

Copyright © 2001 by W. H. Freeman and Company