The shift ciphers may be generalized and slightly strengthened as follows. Choose two integers $\alpha$ and $\beta$, with $\text{gcd}(\alpha \text{,}26)=1$, and consider the function (called an affine function)

For example, let $\alpha =9$ and $\beta =2$, so we are working with $9x+2$. Take a plaintext letter such as $h(=7)$. It is encrypted to $9\cdot 7+2\equiv 65\equiv 13(\text{mod}26)$, which is the letter $N$. Using the same function, we obtain

How do we decrypt? If we were working with rational numbers rather than mod 26, we would start with $y=9x+2$ and solve: $x={\displaystyle \frac{1}{9}}(y-2)$. But ${\displaystyle \frac{1}{9}}$ needs to be reinterpreted when we work mod 26. Since $\text{gcd}(9\text{,}26)=1$, there is a multiplicative inverse for $9(\text{mod}26)$ (if this last sentence doesn’t make sense to you, read Section 3.3 now). In fact, $9\cdot 3\equiv 1(\text{mod}26)$, so 3 is the desired inverse and can be used in place of ${\displaystyle \frac{1}{9}}$. We therefore have

Let’s try this. The letter $V(=21)$ is mapped to $3\cdot 21+20\equiv 83\equiv 5(\text{mod}26)$, which is the letter $f$. Similarly, we see that the ciphertext $CVVWPM$ is decrypted back to affine. For more examples, see Examples 2 and 3 in the Computer Appendices.

Suppose we try to use the function $13x+4$ as our encryption function. We obtain

If we alter the input, we obtain

Clearly this function leads to errors. It is impossible to decrypt, since several plaintexts yield the same ciphertext. In particular, we note that encryption must be one-to-one, and this fails in the present case.

What goes wrong in this example? If we solve $y=13x+4$, we obtain $x={\displaystyle \frac{1}{13}}(y-4)$. But ${\displaystyle \frac{1}{13}}$ does not exist mod 26 since $\text{gcd}(13\text{,}26)=13\ne 1$. More generally, it can be shown that $\alpha x+\beta$ is a one-to-one function mod 26 if and only if $\text{gcd}(\alpha \text{,}26)=1$. In this case, decryption uses $x\equiv {\alpha }^{\ast }y-{\alpha }^{\ast }\beta (\text{mod}26)$, where $\alpha {\alpha }^{\ast }\equiv 1(\text{mod}26)$. So decryption is also accomplished by an affine function.

The key for this encryption method is the pair $(\alpha \text{,}\beta )$. There are 12 possible choices for $\alpha$ with $\text{gcd}(\alpha \text{,}26)=1$ and there are 26 choices for $\beta$ (since we are working mod 26, we only need to consider $\alpha$ and $\beta$ between 0 and 25). Therefore, there are $12\cdot 26=312$ choices for the key.

Let’s look at the possible attacks.

1. Ciphertext only: An exhaustive search through all 312 keys would take longer than the corresponding search in the case of the shift cipher; however, it would be very easy to do on a computer. When all possibilities for the key are tried, a fairly short ciphertext, say around 20 characters, will probably correspond to only one meaningful plaintext, thus allowing the determination of the key. It would also be possible to use frequency counts, though this would require much longer texts.

2. Known plaintext: With a little luck, knowing two letters of the plaintext and the corresponding letters of the ciphertext suffices to find the key. In any case, the number of possibilities for the key is greatly reduced and a few more letters should yield the key.

   For example, suppose the plaintext starts with if and the corresponding ciphertext is $PQ$. In numbers, this means that 8 $(=i)$ maps to 15 $(=P)$ and 5 maps to 16. Therefore, we have the equations

   $$8\alpha +\beta \equiv 15\text{and}5\alpha +\beta \equiv 16(\text{mod}26)\text{.}$$

   Subtracting yields $3\alpha \equiv -1\equiv 25(\text{mod}26)$, which has the unique solution $\alpha =17$. Using the first equation, we find $8\cdot 17+\beta \equiv 15(\text{mod}26)$, which yields $\beta =9$.

   Suppose instead that the plaintext go corresponds to the ciphertext $TH$. We obtain the equations

   $$6\alpha +\beta \equiv 19\text{and}14\alpha +\beta \equiv 7(\text{mod}26)\text{.}$$

   Subtracting yields $-8\alpha \equiv 12(\text{mod}26)$. Since $\text{gcd}(-8\text{,}26)=2$, this has two solutions: $\alpha =5\text{,}18$. The corresponding values of $\beta$ are both 15 (this is not a coincidence; it will always happen this way when the coefficients of $\alpha$ in the equations are even). So we have two candidates for the key: $(5\text{,}15)$ and $(18\text{,}15)$. However, $\text{gcd}(18\text{,}26)\ne 1$ so the second is ruled out. Therefore, the key is $(5\text{,}15)$.

   The preceding procedure works unless the gcd we get is 13 (or 26). In this case, use another letter of the message, if available.

   If we know only one letter of plaintext, we still get a relation between $\alpha$ and $\beta$. For example, if we only know that $g$ in plaintext corresponds to $T$ in ciphertext, then we have $6\alpha +\beta \equiv 19(\text{mod}26)$. There are 12 possibilities for $\alpha$ and each gives one corresponding $\beta$. Therefore, an exhaustive search through the 12 keys should yield the correct key.

3. Chosen plaintext: Choose $ab$ as the plaintext. The first character of the ciphertext will be $\alpha \cdot 0+\beta =\beta$, and the second will be $\alpha +\beta$. Therefore, we can find the key.

4. Chosen ciphertext: Choose $AB$ as the ciphertext. This yields the decryption function of the form $x={\alpha }_{1}y+{\beta }_1$. We could solve for $y$ and obtain the encryption key. But why bother? We have the decryption function, which is what we want.