# How is modular arithmetic used in cryptography and matrices?

I am a high school Mathematics C student, preparing for an upcoming exam. Sorry in advance for the long post below.

The problem I have been presented with it to encode the message "Targetbm". The method for encoding requires you to place each character into a 2x2 matrix, the results are:

|T, A, R, G| |E, T, B, M| (These are a 2, 2x2 matrices ordering in the order; 1st to 4th element).

Then you convert the letters into their corresponding placement in the alphabet (e.g a = 1 or 27, y = 25 or -1, and z = 26 or 0). It's modulo, so 52 would also = z.

After we have converted the matrices into numbers, the result is this; |20, 1, 18, 7| and |5, 20, 2, 13|

Then you multiply by the encoding key: |2, 0, -2, -2|

So the first matrix will result in:|38, -2, 22, -14| and the second: |-30, -40, -22, -26|

Finally, you convert these numbers using modulo and you get the following:

|L, X, V, L| and |V, L, D, Z|

Once this has been completed, this is where trouble ensues, it asks you to decode it. I started by inverting the encoding key and multiplying the matrices by the inverted encoding key ( |1/2, 0, -1/2, -1/2| ). After applying this, the first matrix resulted in |-6, -12, 5, -6|.

Although the first letter converts successfully to the letter 'T' (I'm assuming by coincidence), none of the others did. As far as I'm aware, there is an additional, or different method required that employs 'modulo inversion'. All my research turned up was the use of greatest common denominators, however, I'm unaware of how to apply this to my revision question.

• You're running into an issue partly because $26$ is not prime. Additionally your coding matrix elements have a common factor of $2$, which divides $26$, meaning you have immediately lost information. (To see this, run your coding with |G, N, E, G|) Are you allowed to specify a different modular base, like 29? – Joffan May 30 '17 at 17:25
• Yes, specifying a different modular base is allowed. One base that was suggested, was 27, introducing the space character: " ". If I changed the base to 27, would you be able to run me through the steps of completing this question? Thank you for your help so far! – Kajit Killer May 30 '17 at 21:20
• If you found my answer helpful, you can accept it by clicking the checkmark next to it. – Joffan May 31 '17 at 15:25

You're running into an issue partly because $26$ is not prime. Additionally your coding matrix elements have a common factor of $2$, which divides $26$, meaning you have immediately lost information. (To see this, run your coding with |G, N, E, G|).

So you need to specify a different modular base. Adding a space as a value zero (or 27) we can extend to $\bmod 27$.

Running through the process $\bmod 27$, rather than $\bmod 26$, we need to find the integer inverse of the coding matrix:

$\begin{pmatrix}\frac 12 & 0 \\ -\frac 12& -\frac 12\end{pmatrix} \equiv \begin{pmatrix}\frac {28}2 & 0 \\ \frac {26}2& \frac {26}2\end{pmatrix} \equiv \begin{pmatrix}14 & 0 \\ 13& 13\end{pmatrix} \bmod 27$

Then the coding /decoding for TARG looks like:

$\begin{pmatrix}T & A \\ R& G\end{pmatrix} \to \begin{pmatrix}20 & 1 \\18& 7\end{pmatrix}$

$\begin{pmatrix}20 & 1 \\ 18 & 7\end{pmatrix}\begin{pmatrix}2 & 0 \\ -2& -2\end{pmatrix} = \begin{pmatrix}38 & -2 \\ 22& -14\end{pmatrix} \equiv \begin{pmatrix}11 & 25 \\ 22& 13\end{pmatrix} \bmod 27$

Giving a code of KYVM, and decoding in the same way:

$\begin{pmatrix}11 & 25 \\ 22& 13\end{pmatrix}\begin{pmatrix}14 & 0 \\ 13& 13\end{pmatrix} = \begin{pmatrix}479 & 325 \\ 477 & 169\end{pmatrix} \equiv \begin{pmatrix}20 & 1 \\ 18 & 7\end{pmatrix} \bmod 27$

I'm not completely sure this is safe; we might run into problems if our characters have a lot of multiples of 3 included, due to factors of $27$. But it works for your two example strings.