Affine Cipher

Method

By encoding letters as $A=0,Z=25$, the Caesar Cipher of a shift $5$ can be seen as applying the transformation

$$E(x)=(x+5)\mathrm{mod}26$$

We can try other linear operators:

$$E(x)=(ax+b)\mathrm{mod}26$$

If we want this to be decryptable, $E(x)$ must be injective (and thus forces surjectivity). We are merely just applying an affine transformation to the letters.

Example 1

Show that

$$E(x)=(2x)\mathrm{mod}26$$

loses information but

$$E(x)=(3x)\mathrm{mod}26$$

does not.

We see that $E(x=13)=26\mathrm{mod}26=0$, so $N\to A$, but $E(x=0)=0$, and $A\to A$. However, for each $x\in {\mathbb{N}}_{\le 25}$, we have a unique $E(x)$.

Theorem (Valid Affine Cipher)

More generally,

$$E(x)=(ax+b)\mathrm{mod}26$$

gives a valid Affine Cipher if and only if $a$ is invertible $\mathrm{mod}26$, which by the modular inversion theorem happens if and only if $\gcd (a,26)=1$.

Definition (Decipher Function)

Write

$$E(x)=(ax+b)\mathrm{mod}26$$

with $\gcd (a,26)=1$. Let $r$ be an inverse of $a\mathrm{mod}26$. We write $y=ax+b$ which yields

$$\begin{array}{rlr}y& =ax+b& \\ y-b& =ax& \\ r(y-b)& =rax& \\ ry-rb& =x& \text{since }r\text{ is an inverse of }a\mathrm{mod}26\end{array}$$

Thus,

$$D(y)=(ry-rb)\mathrm{mod}26$$

So for each number $0\dots 26$, the following are the only invertible numbers (along with their inverse):

$$1,13,95,217,1511,1917,2325,25$$

Example 2

What is the decryption function for

$$E(x)=3x+10$$

So,

$$D(y)=(9y-90)\mathrm{mod}26=(9y-14)\mathrm{mod}26$$

Theorem (Affine Ciphers are Finite)

How many different Affine Ciphers are there? Since we have $12$ possible keys for $a$. Then for $b$, we have $\{0,\dots ,25\}$ possible choices $(26)$. We get $12\cdot 26=312$ affine ciphers.

For alphabet size $n$, note that the following invertible numbers are coprime with $26$. We apply the same rule for alphabet size $n$.