Question

Find all pairs of integers keys for affine ciphers for which the encryption function is the same as the corresponding decryption function.

Short answer

$$\begin{gathered} \mathbf{a}\mathbf{=}\mathbf{1}\mathbf{}\mathbf{or}\mathbf{}\mathbf{a}\mathbf{=}\mathbf{25} \\ \mathbf{b}\mathbf{=}\mathbf{0}\mathbf{}\mathbf{or}\mathbf{}\mathbf{b}\mathbf{=}\mathbf{13} \end{gathered}$$

Step-by-step solution

Step 1

Enciphering function of the shift cipher:

$\mathbf{f}\mathbf{\left(}\mathbf{p}\mathbf{\right)}\mathbf{=}\mathbf{(}\mathbf{ap}\mathbf{+}\mathbf{b}\mathbf{)}\mathbf{mod}\mathbf{26}$

Corresponding deciphering function:

${\mathbf{f}}^{\mathbf{-}\mathbf{1}}\mathbf{\left(}\mathbf{p}\mathbf{\right)}\mathbf{=}\overline{\mathbf{a}}\mathbf{(}\mathbf{p}\mathbf{-}\mathbf{b}\mathbf{)}\mathbf{mod}\mathbf{26}$

Note: $\overline{\mathbf{a}}$is the inverse of $\mathit{a}$ modulo 26

We want the two functions to be the same:

$\mathbf{(}\mathbf{ap}\mathbf{+}\mathbf{b}\mathbf{)}\mathbf{mod}\mathbf{26}\mathbf{=}\overline{\mathbf{a}}\mathbf{(}\mathbf{p}\mathbf{-}\mathbf{b}\mathbf{)}\mathbf{mod}\mathbf{26}$

Using distributive property:

$\mathbf{(}\mathbf{ap}\mathbf{+}\mathbf{b}\mathbf{)}\mathbf{mod}\mathbf{26}\mathbf{=}\mathbf{(}\overline{\mathbf{a}}\mathbf{p}\mathbf{‐}\overline{\mathbf{a}}\mathbf{b}\mathbf{)}\mathbf{mod}\mathbf{26}$

Step 2

The constant $\mathit{a}$then also has to be equal to _{$\overline{\mathbf{a}}$}

$\mathit{a}\mathbf{\equiv }\overline{\mathbf{a}}\mathbf{\left(}\mathbf{mod}\mathbf{26}\mathbf{\right)}$

Or equivalently ${\mathit{a}}^{\mathbf{2}}\mathbf{\equiv }\overline{\mathbf{a}}\mathit{a}\mathbf{\equiv }\mathbf{1}\left(\mathrm{mod}26\right)$

There are only two values that are each other inverse (modulo 26 )

_{$\mathit{a}\mathbf{=}\mathbf{1}\mathbf{}\mathbf{or}\mathbf{}\mathbf{a}\mathbf{=}\mathbf{25}$}

The constant b then has to be either 0 or 13 if the two functions are the same (result from exercise 10 when$\mathit{a}\mathbf{=}\overline{\mathbf{a}}\mathbf{=}\mathbf{1}$ , similar for_{$\mathit{a}\mathbf{=}\overline{\mathbf{a}}\mathbf{=}\mathbf{25}$})