I am new to this subject and I have a homework problem based on Hill cipher, where encryption is done on di-graphs (a pair of alphabets and not on individuals).
The alphabet domain is $\{A\dots Z\}$ and they are numbered from $0$ to $25$ under $modulo \ 26$.
Encrypted messages is : $WKNCCHSSJ$, which can be written in numerics as $\{22,10;13,2;\dots\}$ (the ; has been used to separate pairs)
The message has been intercepted and the the first few characters are found to be : $GIVE \dots$ $\{6,8;21,4;\dots\}$
Assuming the original message to be $X$ and the decrypted message to be $Y$, the Hill cipher can be given as :
$Y=A.X$
So, $A^{-1}=X.Y^{-1}$
The problem boils down to inverting the $Y$ matrix for first 4 characters.
$Y= \left( \begin{array}{ccc}
W & N\\
K & C \\\end{array} \right)
=\left( \begin{array}{ccc}
22 & 13\\
10 & 2 \\\end{array} \right) $
$|Y|= 44-130 \equiv 18 (mod 26)$
And since $gcd (18,26)\neq 1$, we need to divide the $mod \ 26$ with $2$ and we need to work in $ mod \ 13$.
Please help me to understand how to proceed for this special case. As I am new to number theory and cryptography, it will be very helpful if you provide me a detailed solution/hint.
Many thanks !!
Best Answer
If the Hill cipher matrix (I assume you are using a 2x2 matrix?) is called $H$, then we know that $H \cdot \begin{pmatrix} 6 \\ 8 \end{pmatrix} =\begin{pmatrix} 22 \\ 10 \end{pmatrix}$ and $H \cdot \begin{pmatrix} 21 \\ 4 \end{pmatrix} =\begin{pmatrix} 13 \\ 2 \end{pmatrix}$. You could try to solve for $H$ by Gaussian elimination e.g.
In this case we get the following equations in the first row of the encryption matrix, say $[x \,\, y]$:
$$6x + 8y = 22 \\ 21x+4y = 13$$
And multiplying the second equation by $30$ (or $4$, but the inverse of $21$ is $5$ hence the $30 = 5 \times 6$) we get:
$$6x+ 16y = 0$$ (reducing modulo $26$ of course).
substracting the other equation, we get $$8b = 13$$ which has no solution as $8b$ is always even and $13$ is odd. So it seems we cannot have GIVE as the start of the plain text.