0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Hagen von Eitzen Nov 21 '18 at 21:48
  • $\begingroup$ The key matrix is not invertible in the ring $\mathbb{Z}_{26}$ that you choose to work in. $\endgroup$ – Henno Brandsma Nov 22 '18 at 4:45
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.