Hill Cipher Plaintext Attack: Dealing with Non-uniqueness of Matrix Inverses?

Question

I'm following along with my book. Here is an example of a plaintext attack from it:

It is known that:
plaintext = 'friday'
ciphertext= 'pqcfku'
$m$ = 2

We will use this to form the following matrix equation:

$$ C = PK $$ $$\pmatrix{5 & 16 \\ 2 & 5} = \pmatrix{5 & 17 \\ 8 & 3} K $$

Where $K$ is the key matrix. Note that $K = P^{-1} C$. To find that product, we must first find $P^{-1}$.
Now this is where I don't understand the book. The book says:

$$P^{-1} = \pmatrix{9 & 1 \\ 2 & 15}$$
First I tried verifying this in Mathematica. The command Inverse[{{15, 17}, {8, 3}}, Modulus -> 26] yields an error saying there is no such inverse... bizarre. I then found this online calculator to do it, and it returns the result: $$P^{-1} = \pmatrix{13 & 5 \\ 10 & 23}$$

A quick check tells us that BOTH these matrices are correct inverses mod 26. But, only the inverse provided by the book works in correctly computing the key, and thereby being able to break the cipher.

So... how can I conduct a plaintext attack in this manner? There appear to be multiple inverses. How do I know which one is "right"? And if I must brute force, how can I find ALL possible inverses?

Answer 1

More standard is that we multiply a column with a plain text vector to get the cipher text vector so the known plain text equation (the first two pairs) yield

$$KP=C = K\begin{bmatrix}5 & 8\\17 & 3\end{bmatrix} = \begin{bmatrix}15 & 2\\16 & 5\end{bmatrix}$$ so I get $P=\begin{bmatrix}5 & 8\\17 & 3\end{bmatrix}$ which is invertible as $\det(P) = 15 - 8 \cdot 17 = 9$ and $9$ is invertible modulo $26$, with inverse $3$ as $3 \times 9 \equiv 1 \pmod{26}$.

The inverse is easily computed (as for all $2\times 2$ matrices) via

$$P^{-1} = 3 \cdot \begin{bmatrix}3 & -8\\-17 & 5\end{bmatrix} = \begin{bmatrix}9 & 2\\1 & 15\end{bmatrix}$$

which is easily checked to be the inverse. Note that the matrix in your text uses the transpose (as it left multiplies by $1 \times 2$ matrices instead, so all equations transpose) and the one from the online calculator is not an inverse at all (which becomes obvious if we do the full matrix multiplication; only the first row looks OK). So that online calculation is wrong, and Mathematica is confused (and you made a typo: 15 should be 5 I think).

Anyway, knowing $P^{-1}$, $$K = CP^{-1} = \begin{bmatrix}7 & 8\\19 & 3\end{bmatrix}$$ (your text probably gives its transpose) and this indeed checks out as $$\begin{bmatrix}7 & 8\\19 & 3\end{bmatrix} \begin{bmatrix}0 \\ 24\end{bmatrix}=\begin{bmatrix} 10 \\ 20\end{bmatrix}$$

so it maps the plain ay to ciphertext KU. The decryption matrix is then $$K^{-1}=\begin{bmatrix}23 & 8\\19 & 19\end{bmatrix}$$ if you want to decrypt the rest (or its transpose if working by rows from the left, as before).