[Math] Hill cipher: why can the cipher key matrix’s determinant not share common factors with the modulus

cryptographylinear algebramatrices

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?

Best Answer

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.

Related Question