# Background

The Hill cipher works by:

1. defining a letter-to-number substitution table/list/pattern/etc.;
2. encoding a cypher-word into a column vector $$u$$ whose components are determined by the said list;
3. multiplying $$u$$ with a random “key” matrix $$K$$ of corresponding dimension, rendering another column vector $$z$$;
4. converting $$z$$ into a cypher-word.

Decryption works by:

1. considering the number of characters in the list to be $$m$$;
2. multiplying $$z$$ by $$K^{-1}$$ to give another column vector $$w$$;
3. attaining $$u$$ via the relationship $$u\equiv w\pmod m$$ where all components of $$u$$ are in the list; and
4. obtaining the original word using the list.

There is a caveat: In addition to $$K$$ needing to be invertible, the determinant of the key $$\det K$$ must share no common factors with the modulus $$m$$.

# Personal investigation

In order to understand why this condition is required, I created my own example in which I use the pattern

$$\begin{array}{ccccccccc} \text{a} & \text b & \text c & \text d & \text e & \text f & \text g & \cdots & \text z \\ 0 & 1 & 2 & 3 & 4 & 5 & 6 & \cdots & 25 \end{array}$$

and the key $$K = \pmatrix{2&1\\2&2}$$ to encrypt the word $$\text{ab}\mapsto \pmatrix{0\\1}=u$$ (like the muscle), in which I know $$\det K=2$$ shares a factor with the modulus $$26$$.

The cipher-word is attained by

$$z=Ku=\pmatrix{2&1\\2&2}\pmatrix{0\\1}=\pmatrix{1\\2}\mapsto\text{bc}$$

The original word is obtained by

$$K^{-1}z=\pmatrix{1&-1/2\\-1&1}\pmatrix{1\\2}=\pmatrix{0\\1}\mapsto\text{ab}$$

as originally planned. . . .

# Question

At first I thought there was a possibility that my cipher working was due to the matrix components being small numbers, but after working out several additional examples, it seems that no matter what key I choose, it works flawlessly if the key matrix is invertible.

Is it even necessary that the key matrix not share factors with the modulus? If so, why?

• In your example, what is $-\frac 12\cdot y\bmod{26}$ when $y$ is odd? Upon closer look, whatever you encode by multiplying with $K$, will have even second letter! This means that you reach only $26\cdot 13$ code words instead of $26\cdot 26$. Thus you cannot regain your originally possible $26\cdot 26$ clear texts – Hagen von Eitzen Nov 21 '18 at 21:48
• The key matrix is not invertible in the ring $\mathbb{Z}_{26}$ that you choose to work in. – Henno Brandsma Nov 22 '18 at 4:45

The matrix $$K^{-1}$$ that you propose is only the inverse over the rational numbers, not in the ring $$\mathbb{Z}_{26}$$ that you are working over (the characters are $$0$$ to $$25$$). The determinant is not coprime with $$n$$ so has no inverse in the ring. This means that you don't always get the right result with your "pseudoinverse"

To see where things go wrong concretely in your example:

$$an$$ is encrypted to $$na$$ but applying your inverse you'd get $$nn$$ as the decrypt. In fact anyone receiving $$na$$ as a ciphertext cannot tell whether to decrypt it to $$an$$ or $$nn$$. Both plaintexts give that same ciphertext. Encryption is thus not 1-1 and hence cannot be invertible.

Other such cases (it goes wrong in half of the $$26^2$$ pairs):

$$ao \rightarrow oc \rightarrow no$$ (Last step is your pseudo inverse)

$$es \rightarrow as \rightarrow rs$$

$$do \rightarrow ui \rightarrow qo$$ etc. Write a program to generate all such pairs (I did).

You can see that the requirement is truly essential.