## Section2.7Affine Ciphers

As you discovered in Investigation: A new cipher wheel the new cipher wheel could be represented as a combination of both a multiplicative and shift cipher. This is called an affine cipher.

###### Definition2.7.1.

An affine cipher is an encryption of the form $CT \equiv a PT + b \pmod{26}$ where $0 \leq b \leq 25$ and $a \in \{ 1,3,5,7,9,11,15,17,19,21,23,25 \}\text{.}$

Remember that the restriction on the values for $a$ is necessary for the ciphertext to be decryptable. We saw in Section 2.4 that these are the values of $a$ that have a multiplicative inverse mod 26.

If we know the encryption formula, it is easy to encrypt a message.

###### Example2.7.2.

Encrypt plaintext CAT with the formula $CT \equiv 5 PT + 3 \pmod{26}\text{.}$ Translating CAT to numbers gives $[2,0,19]\text{.}$ Applying the encryption formula gives

\begin{equation*} [ 5\times3+2,5\times0+3,5\times19+3]=[13,3,98] \equiv [13,3,20] \pmod{26}. \end{equation*}

Thus the ciphertext would be NDU.

But what do we need to do to decrypt a message? We need to solve for the PT in the above equation. We now know that we can add, subtract and multiply with modular arithmetic, but we cannot generally divide. However, often we can use the multiplicative inverse instead. To solve

\begin{equation*} CT \equiv a PT + b \pmod{26} \end{equation*}

for PT, we first substract $b$ from both sides. This gives us

\begin{equation*} CT-b=a PT \pmod{26}\text{.} \end{equation*}

Let $d$ be the multiplicative inverse of $a$ mod 26, so that $ad \equiv 1 \pmod{26}\text{.}$ Multiplying both sides by $d$ gives

\begin{equation*} d(CT - b) \equiv da PT \equiv PT \pmod{26}. \end{equation*}

Thus, the decryption formula is

\begin{equation*} PT \equiv dCT-db \pmod{26}. \end{equation*}
###### Example2.7.3.

Decrypt SVH which was encrypted with $CT \equiv 5 PT + 3 \pmod{26}\text{.}$ We first solve for the decryption formula.

\begin{equation*} 5PT \equiv CT-3 \pmod{26} \end{equation*}

The multiplicative inverse of 5 is 21 mod 26.

\begin{equation*} 21(5PT) \equiv 21(CT-3) \pmod{26} \end{equation*}
\begin{equation*} PT \equiv 21CT+15 \pmod{26} \end{equation*}

Now that we have the decryption formula, we first convert the ciphertext letters to numbers.

\begin{equation*} SVH=[18,21,7]\text{.} \end{equation*}

Then we apply the decryption formula.

\begin{equation*} PT=[21(18)+15,21(21)+15,21(7)+15]=[393,456,162] \end{equation*}

We need to reduce mod 26.

\begin{equation*} [393,456,162] \equiv [3,14,6] \mod{26}\text{.} \end{equation*}

Thus the plaintext is DOG.

Suppose, however, that we do not know the values of $a$ and $b\text{?}$ How can we perform cryptanalysis on an affine cipher? Could we use brute force? How many affine ciphers are there? We need to count the number of valid multipliers for $a$ and valid shifts for $b\text{.}$ The number of multipliers mod $26$ is the number of elements with a multiplicative inverse mod $26$ which by previous work is the just the numbers $1,3,5,7,9,11,15,17,19,21,23,25\text{.}$ There are $12$ good multipliers. All shifts are possible mod $26$ so the number of shifts mod $26$ is equal to $26\text{.}$ Since each multiplier can be combined with each shift independently this gives us $12\times 26=312$ possibilities. However, the affine cipher with a shift of zero and a multiplier of 1 is not an encryption, so we remove that one to get 311 possible affine ciphers.

Could we try 311 different values of $(a,b)\text{?}$ Probably, but its not so appealing. How else can we break affine ciphers? How can we solve them if we don't know $a$ and $b\text{.}$ Let's try to adapt some of our previous strategies. Suppose we intercept the encrypted message below.

Cipher Text: RXBDSYZYHFJDQPGHJFZKFMXSFGAFHSDRGNDCYFDGA

We saw previously that we could use letter frequency to help us. The most frequently occurring letters in the ciphertext are F (6 occurances), D (5 occurrances), and G (4 occurrances). Since the most common letters in the English language are E, T, A, O, I, N, S, R, H, we guess that F might correspond to E and D might correspond to T. This gives us the equations:

\begin{equation*} PT=aCT+b \pmod{26} \end{equation*}
\begin{equation*} 4=a(5)+b\pmod{26} \end{equation*}
\begin{equation*} 19=a(3)+b\pmod{26} \end{equation*}

Subtracting the second equation from the first gives:

\begin{equation*} -15=2a \pmod{26} \end{equation*}

However this is a problem because for all $a\text{,}$ $2a$ mod $26$ will be even, so we will never get an odd number and in particular will never get $-15\text{.}$ Thus, this equation has no solution and we must have guessed the wrong correspondence. Note this even/odd issue will always cause a problem.

You will work on this proof in the exercises.

We now guess that F might correspond to E and D might correspond to A. This gives us the equations:

\begin{equation*} PT=aCT+b \pmod{26} \end{equation*}
\begin{equation*} 4=a(5)+b\pmod{26} \end{equation*}
\begin{equation*} 0=a(3)+b\pmod{26} \end{equation*}

Subtracting the second equation from the first gives:

\begin{equation*} 4=2a \pmod{26} \end{equation*}

The theorem indicates that there is a solution this time since both $PT_1-PT_2$ and $CT_1-CT_2$ are even. An obvious solution is $a=2\text{.}$ However, we remember that $a=2$ is not a valid multiplier since 2 does not have a multiplicative inverse mod 26 so we hope there is another solution. We convert the congruence into equality using definition 4 so we have

\begin{equation*} 4=2a+26k \end{equation*}

for some integer $k\text{.}$ This is equality rather than congruence so it is ok to divide here. We can divide by 2 and get

\begin{equation*} 2=a+13k\text{.} \end{equation*}

Note this gives us a congruence mod 13 rather than mod 26. So we see that $a \equiv 2 \pmod{13}\text{.}$ This gives us TWO solutions mod 26. Both 2 and 15 are congruent to 2 mod 13 but are different mod 26. So we have either $a \equiv 2 \pmod{13}$ OR $a \equiv 15 \pmod{13}\text{.}$ Since we need $a$ to correspond to a valid encryption and decryption formula we know $a$ must be invertible mod 26. Therefore we must have $a \equiv 15 \pmod{26}\text{.}$ We can use this to solve for $b\text{.}$ Plugging $a$ into the second equation gives

\begin{equation*} 0=3(15)+b \pmod{26} \end{equation*}

so $b=0-45=-19=7\text{.}$ So we can now decrypt this affine cipher using the formula

\begin{equation*} PT=15CT+7 \pmod{26}. \end{equation*}