# Solving Simultaneous Equations - Hill Cipher

I have searched but an unable to find any examples like what I am faced with.

Plaintext = SOLVED CipherText = GEZXDS 2x2 encryption matrix

$$\left(\begin{matrix} 11 & 21 \\ 4 & 3 \end{matrix} \right)*\left( \begin{matrix} a & b \\ c & d \end{matrix} \right)= \left(\begin{matrix} 25 & 23 \\ 3 & 18 \end{matrix}\right)$$

with the result: $$11a +21c \equiv 25 \text{(mod 26)}$$ $$4a + 3c \equiv 3 \text{(mod 26)}$$

and

$$11b + 21d \equiv 23 \text{(mod 26)}$$ $$4b + 3d \equiv 18 \text{(mod 26)}$$

I have found a solution. solve for a: $$11a + 21c = 25 (mod 26)$$ $$4a + 3c = 3 (mod 26)$$

-> (multiply second equation by 7) =

$$11a + 21c = 25 (mod 26)$$ $$28a + 21c = 21 (mod 26)$$

-> apply (mod26) where required and Subtract =

$$9a = 4 (mod 26)$$ 9 inverse mod 26 = 3 $$a=3*4 =12$$

Solve for c:

$$11a = 132$$ $$2 + 21c = 25 (mod 26)$$ $$21c = 23$$ 21 inverse = 5 $$c = 5*23 (mod 26)$$ $$c=11$$

and so on.

Thanks for everyone's help

• Hey Ryan, what exactly are you trying to do? Just solve these systems of equations? – ChrisD Oct 20 '14 at 5:11
• Trying to find the values for a,b,c,d (mod 26) – user1672867 Oct 20 '14 at 5:12
• Have you tried throwing your systems into an augmented matrix and putting them into reduced row echelon form? – ChrisD Oct 20 '14 at 5:13
• Haha I wish I understood what this is but it has not been covered in my course. I am looking into it now. As I have video lectures the example my teacher has done if left at this point and it is assumed knowledge that we should be able to solve this so I am not sure what method they are looking for. – user1672867 Oct 20 '14 at 5:16
• I have the practise questions answers so I will edit the post to show them. I am just trying to figure out how they came to that answer – user1672867 Oct 20 '14 at 5:20

If you know that the congruence $$x\equiv y\pmod{26} \qquad(*)$$ is true, then you also know that the congruence $$7x\equiv 7y\pmod{26}\qquad(**)$$ is true. This is because the first congruence simply states that $x-y$ is divisible by $26$. Consequently also $7(x-y)=7x-7y$ is divisible by $26$ which is exactly what the second congruence claims. In other words $(**)$ is a consequence of $(*)$, or $(*)\implies (**)$. The logic will automatically flow in this direction and we could have used any integer in place of $7$ here. The real question is whether we can also go backwards? In other words, does $(**)\implies (*)$ or, can we deduce that $(*)$ is true if and only if $(**)$ is true.

To that end it is necessary that $7$ and $26$ are coprime. Simply stated this is a consequence of the fundamenta theorem of arithmetic (=uniqueness of prime factorization of integers): multiplying an integer by seven will not make it divisible by $26$ unless it already is. The same conclusion can be reached by using a modular inverse of $7$. You have hopefully seen how that can be found (when it exists) using the extended Euclidean algorithm, so I simply make the observation that $$7\cdot15=105=1+4\cdot26\equiv1\pmod{26}.$$ How does this help? Repeating the above logic we see that because $7\cdot15=105$ the congruence $(**)$ implies the congruence $$105x\equiv105y\pmod{26}\qquad(***).$$ But on the left hand side of $(***)$ we have $105x\equiv x$ and on the right hand side we have $105y\equiv y$, because both $104x$ and $104y$ are divisible by $26$ for all integers $x,y$. Thus $(***)\implies(*)$, and we are done.

Addressing the question of finding the key matrix (the question was edited by the OP as it turned out that he had made an unlucky choice of two ciphertex/plaintext pairs)

$$\left(\begin{matrix} 11 & 21 \\ 4 & 3 \end{matrix} \right)*\left( \begin{matrix} a & b \\ c & d \end{matrix} \right)= \left(\begin{matrix} 25 & 23 \\ 3 & 18 \end{matrix}\right).$$

You can solve this system of congruences any logical way you can/want. I show how to do it using the inverse matrix. The general recipe for inverting a $2\times2$ matrix (hopefully you have seen this in linear algebra or elsewhere) is $$\left(\begin{matrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix}\right)^{-1} =\frac1{a_{11}a_{22}-a_{12}a_{21}} \left(\begin{matrix} a_{22} & -a_{12} \\ -a_{21} & a_{11} \end{matrix}\right).\qquad(****)$$ Everything here makes sense in modulo $26$ arithmetic except possibly division by the determinant. As above, we can divide by an integer modulo $26$ by multiplying with the modular inverse provided that the inverse exists, i.e. provided that the number we divide by is coprime to $26$.

The determinant of your matrix $$A=\left(\begin{matrix} 11 & 21 \\ 4 & 3 \end{matrix} \right)$$ is $\det A=33-84=-51\equiv-51+2\cdot26=1\pmod{26},$ which is, of course, equal to its own inverse. Therefore $$A^{-1}=\left(\begin{matrix} 11 & 21 \\ 4 & 3 \end{matrix} \right)^{-1}=\frac11\left(\begin{matrix} 3 & -21 \\ -4 & 11 \end{matrix} \right)\equiv \left(\begin{matrix} 3 & 5 \\ 22 & 11 \end{matrix} \right)\pmod{26},$$ as $-21\equiv5\pmod{26}$ et cetera. We can then solve the matrix equation $(****)$ simply by multiplying it by $A^{-1}$ from the left hand side. The result is $$\left( \begin{matrix} a & b \\ c & d \end{matrix} \right)= \left(\begin{matrix} 3 & 5 \\ 22 & 11 \end{matrix} \right) \left(\begin{matrix} 25 & 23 \\ 3 & 18 \end{matrix}\right)= \left(\begin{matrix} 90 & 159 \\ 583 & 704 \end{matrix}\right) \equiv \left(\begin{matrix} 12 & 3 \\ 11 & 2 \end{matrix}\right)\pmod{26}.$$

Leaving it to you to check all the calculations and the verification that this key matrix is compatible with the third plaintext/ciphertext pair that you have.

• Thanks for your answer. Clears everything up! – user1672867 Oct 20 '14 at 13:19

Hint: $3$ is invertible mod $26$.

• so 3 * 9 = 1 (mod 26) therefore inverse is 9 – user1672867 Oct 20 '14 at 5:45
• I don't know what to do with that information – user1672867 Oct 20 '14 at 5:45
• Use it in the first equation to find $c$ in terms of $a$. Then substitute into the second equation. – Robert Israel Oct 20 '14 at 5:49
• I am trying to do this now. though I am not sure how i would use in in the first equation. Wouldn't this give me 4a + 3c = 9 (mod 26) which I am still unable to answer? forgive my stupidity, math is not really a strong point of mine. – user1672867 Oct 20 '14 at 5:56
• Why would you get $4a+3c\equiv9\pmod{26}$? You can't just magically change a 3 into a 9. What you do is multiply both sides of the congruence by 9. Then solve for $c$. Then plug into 2nd congruence. – Gerry Myerson Oct 20 '14 at 6:14