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 keyk, 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

pandciscp+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

pin the above congruence. Using simple algebra, we see thatpc–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

aandb. We encode a message by applying the formulacap+b(mod 95).For example, if we take

a= 41 andb= 12, then we encipher by clicking on "Affine" below.

To decode a message encoded with an affine cipher, we must solve for

pin the congruencecap+b(mod 95).Subtracting

bfrom both sides and then multiplying bya^{–1}(mod 95) yieldspa^{–1}(c–b)a^{–1}c–a^{–1}b(mod 95).Note that this is just another affine cipher with key

a^{–1}and –a^{–1}b.Thus, to decode we first need to compute

a^{–1}(mod 95). As noted earlier, this is equivalent to solving the congruence equationax1 (mod 95), which can be accomplished using the applet below. In this case, we havea= 41 andb= 1:We can now decode the following message, which was encoded using

a= 41 andb= 12. We decode using the affine applet with the decoding key that we have found.

As you know, for some values of

athere will be a multiplicative inverse modulo 95, and for others there will not. Suppose that we had selected a value ofafor which there is no inverse modulo 95? One such choice isa38 (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 2

The message recorded in the applet below was encoded using an affine cipher with key

a= 59 andb= 34. Decode the 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