1
$\begingroup$

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 !!

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\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.