## Section2.4Decimation Ciphers

For the shift cipher we constructed the cipher alphabet by shifting each plaintext letter by a fixed amount. For a decimation cipher we think of shifting the cipher alphabet. For example, for a decimation by 3 we set up the following correspondance between plaintext and ciphertext. We start by placing ciphertext A under plaintext A. Next we locate ciphertext B by moving three places in the ciphertext to place B under plaintext D. Then we move three places in the ciphertext to place C under G.

We continue this process for the whole alphabet, wrapping around to the beginning of the alphabet when we reach the end of the alphabet. Thus, the entire correspondance would like this:

You should have seen in Investigation: Decimation Ciphers that the formula for decimation ciphers corresponds to a multiplicative formula for encryption and decryption. We will now explore multiplicative ciphers in general.

###### Example2.4.3.

Let's encrypt according to the formula

\begin{equation*} CT \equiv 3 \times PT \pmod{26}. \end{equation*}

To convert the plaintext message, PT=USE CODE B, to ciphertext we first convert to the standard numbers.

\begin{equation*} PTNum=[20, 18, 4, 2, 14, 3, 4, 1]\text{.} \end{equation*}

Then we multiply each term by 3 and reduce mod 26. For example, $20\times 3 = 60 = 26 \times 2+8 \equiv 8 \pmod{26}$ and $18\times3 = 54 = 26\times2+2 \equiv 2 \pmod{26} \text{.}$ Thus, the numbers for the ciphertext are

\begin{equation*} CTNum=[8,2,12,6,16,9,12,3]\text{.} \end{equation*}

Converting these back to letters we have CT=ICMGQJMD.

You should have seen in Investigation: Multiplicative Ciphers that some numbers work well for creating a multiplicative ciphers, but many numbers do not work at all.

###### Definition2.4.4.
A multiplicative cipher is a cipher of the form
\begin{equation*} CT \equiv aPT \pmod{26} \end{equation*}
where $a$ is chosen so that the cipher is decryptable. That is, $a$ is a “good multiplier”.

In Investigation: Multiplicative Ciphers, you should have seen that 13 was an especially “bad multiplier”. Let's examine why that is with the following theorem.

If $x$ is even then $x=2k$ for some integer $k\text{.}$ Then

\begin{equation*} 13x=13(2k)=26k. \end{equation*}

Since this means $13x=0+26k\text{,}$ we can apply Definition 2.2.6 to conclude $13x \equiv 0 \pmod{26}\text{.}$ If $x$ is odd then $x=2k+1$ for some integer $k\text{.}$ Then

\begin{equation*} 13x=13(2k+1)=26k+13. \end{equation*}

Since $13x=13+26k\text{,}$ we again applyDefinition 2.2.6 to conclude, $13x \equiv 13 \pmod{26}\text{.}$

You should think about why this theorem means that multiplication by thirteen will produce a really bad cipher. You'll examine the other bad multipliers in the exercises.

But if we have a good multiplier we still need to figure out how to decrypt a message! Let's start with multiplication by 3 first since 3 turned out to be a good multiplier. Our encryption formula is

\begin{equation*} CT \equiv 3 \times PT \pmod{26}. \end{equation*}

What would a decryption formula look like. For a first guess we might try $PT = \frac{CT}{3} \pmod{26}\text{.}$ Numerically, if

\begin{equation*} CT = [8,2,12,6,16,9,12,3] \end{equation*}

then

\begin{equation*} PT = [ 8/3, 2/3, 4,2,16/3, 3,4,1] \end{equation*}

But this is a big problem! We got fractions! That doesn't work for modular arithmetic. In general, division does not work for modular arithmetic, but multiplication does so let's try it that way. We want to multiply by something to cancel out the three; i.e,. we want to solve this equation:

\begin{equation*} 3x \equiv 1 \pmod {26}. \end{equation*}

How can we solve this equation? Since mod 26 the only values for $x$ are $0,1,2,3,\cdots, 25$ we could try all the values $x=0,1,2,3, \cdots 25$ until we get a 1. We can use Sage to make a table of all these values.

From Sage, we can see that if $x=9$ then $3x \equiv 1 \pmod{26}\text{.}$

Another technique uses Definition 2.2.6 to rewrite $3x \equiv 1 \pmod {26}$ as $3x=1+26k$ for an integer $k\text{.}$ Then we can try $k=0,1,2, \cdots$ until we get something that is divisible by 3. In this case, $k=1$ gives $1+26=27=3 \times 9\text{.}$ And we again see that if $x=9$ then $3x \equiv 1 \pmod{26}\text{.}$ We say 9 is the multiplicative inverse of 3 mod 26.

###### Definition2.4.6.

The integer $x$ is the multiplicative inverse of $a$ mod $n$ if $ax \equiv 1 \pmod{n}\text{.}$

This gives us a way to solve our equation in terms of PT. Multiplying both sides of $CT \equiv 3PT \pmod{26}$ by 9 gives $9 CT \equiv 9\times3PT \equiv PT \pmod{26}$ so we have a decryption formula.

What goes wrong in the other case? To solve $CT \equiv 2 \times PT \pmod{26}$ for PT, we want to find the multiplicative inverse of 2 mod 26. Is there a solution to the equation $2x \equiv 1 \pmod{26}\text{?}$ Let's ask Sage to help us!

We see that none of these produce a solution to this equation. Maybe you notice some patterns here! You'll think about those more in the exercises. Thus, 2 does not have a multiplicative inverse mod 26. Thus, we can ask our question about good and bad multipliers in another way. Which numbers have a multiplicative inverse mod 26?