Breaking an Affine Cipher

In an affine cipher, the letters of the original message are first identified with integer values (A=0, B=1, C=2, D=3, ... Z=25). These values are then used as inputs to a function of the following form (assuming an alphabet of 26 letters):

$$f(x) \equiv ax + b \pmod{26}$$

As an example, suppose we wished to encrypt the plaintext message "HELLO" with the function $f(x) = 3x + 7$.

  1. "HELLO" would be first turned into the sequence of numbers 7, 4, 11, 11, 14.
  2. These numbers would be fed into $f(x)$ one at a time to produce the sequence 2, 19, 14, 14, 23.
  3. Finally, we interpret the resultant numbers again as letters to produce the ciphertext "CTOOX".

Now, suppose you have intercepted this ciphertext message "CTOOX", and you didn't know what the original message was, but wished to discover it.

Suppose you guess f('L') = 'O' and f('E') = 'T'. Such guesses can come from a variety of sources, such as analyzing the frequency of certain letters; or pairs of letter; or from a known or guessed part of the original message (which is called a crib).

Continuing with the example, if we translate our guesses involving 'L', 'O', 'E', and 'T' into integers again using A=0, B=1, ... Z=25, then we have
$f(11) = 14$ and $f(4) = 19$. This tells you:
$$\begin{array}{rcl}
11a + b &\equiv& 14 \pmod{26}\\
4a + b &\equiv& 19 \pmod{26}
\end{array}$$

Treating the congruences not unlike two equations in two unknowns, we can eliminate the variable $b$ by subtracting the second congruence from the first one. This yields:

$$7a \equiv -5 \pmod{26}$$

or equivalently,

$$7a \equiv 21 \pmod{26}$$

In this particular example, we can solve for $a$ by dividing both sides by $7$ since it is relatively prime to $26$ and $7 \mid 21$.

Notice, if the coefficient on $a$ hadn't divided 21 evenly, we could have still solved for a by first finding the multiplicative inverse, x, of 7 (mod 26) by solving
$$7x \equiv 1 \pmod{26}$$

If necessary, we could employ the Euclidean Algorithm to this end.

Then, if we multiply both sides of the congruence involving $a$ by this multiplicative inverse, we again reveal the value of $a$.

Returning to the example before us, dividing both sides of $7a \equiv 21 \pmod{26}$ by $7$ yields

$$a \equiv 3 \pmod{26}$$

Now that we have the value of $a$, finding the value of $b$ is trivial. We simply plug $a=3$ back into one of the congruences involving $b$. For example, using $11a + b \equiv 14 \pmod{26}$, we find

$$33 + b \equiv 14 \pmod{26}$$

which reduces to

$$b \equiv -19 \equiv 7 \pmod{26}$$

Knowing, $a \equiv 3$ and $b \equiv 7$ gives us the encrypting function $f(x) \equiv 3x + 7 \pmod{26}$. Armed with the encrypting function (i.e., the "secret key" for the affine cipher), decrypting the message is straight-forward -- just determine what each letter becomes under the function, and do the substitutions backwards.