Blogs, STEM and leaf Information

Message Encryption

In Bijective Mappings, we showed that a mapping was bijective by showing that it had an inverse. In the process, we had to compute matrices and inverses thereof in order to show that an inverse exists. Coupled with the fact that I am starting to think what I will be teaching in linear algebra this summer, I wanted to take the time to write a post about cryptography using matrices. We will begin by going through the process of encrypting and decrypting messages using matrices, then I will leave it up to you to decrypt a message.

Invertible Mappings

In the process of encryption of information, it is important that you be able to decrypt the information afterwards as well. Because of this, whatever process you use for coding, you will need to have an inverse process to undo the coding. In this way, what we are really doing is mapping a set of information to a new set using an invertible mapping. As we saw before, this means that the mapping will need to be a bijection.

One way to construct such a mapping is to give the mapping in terms of matrix multiplication. In the last post, we were able to map \(\mathbb{Z} \times \mathbb{Z} \to \mathbb{Z} \times \mathbb{Z}\) by using the mapping
\[f(n,m)=\begin{bmatrix}
5 & 4 \\
4 & 3
\end{bmatrix} * \begin{bmatrix}
m \\
n
\end{bmatrix}.
\]

That is, we would map the ordered pair \((m,n)\) to \((5m+4n,4m+3n)\). Because we were able to prove that such a mapping was invertible, the idea is that, if you were given the end result and told the mapping, you would be able to determine precisely where you started. However, if you are only given the answer, it would be difficult to determine where you started.

As an example, suppose I sent you the message \((1,1)\). Without knowing the original matrix, determining what I meant to send would be difficult. However, since we know the inverse matrix is
\[\begin{bmatrix}
-3 & 4 \\
4 & -5
\end{bmatrix}\] we could find that the original message was
\[\begin{bmatrix}
-3 & 4 \\
4 & -5
\end{bmatrix} *
\begin{bmatrix}
1 \\
1
\end{bmatrix}
=\begin{bmatrix}
1 \\
-1
\end{bmatrix}.\]

While this isn’t an overly exciting message, the idea can be generalized to give encoding of much more interesting messages.

Our encoding

In order to make your encoding even more difficult to decrypt without the key, you can do things like use matrices larger than \(2 \times 2\). You can also work over a set of numbers other than the real numbers. For example, if you entries are from the integers mod some prime number, you can still find invertible matrices, but trying to see the pattern becomes more difficult. Furthermore, using the integers mod some number will help to keep the output options within a predetermined range.

For our example, we will want to encrypt and decrypt the message “hello.” Because we plan on using matrices, we will need to find a way to convert letters to numbers. In this case, I would suggest 0 is a space, 1-26 are a-z, 27 is “,” and 28 is “.” That is, we will be able to encode the lower case English letters as well as spaces, commas and periods. You can, indeed, include many more symbols by using a larger set of numbers, but these will be sufficient for our example. Therefore, we would turn hello. into the ordered tuple
\[\begin{bmatrix}
h& e &l & l & o & .
\end{bmatrix}=\begin{bmatrix}
8 & 5 & 12 & 12 & 15 & 28
\end{bmatrix}\]

The next thing we will need to do is determine our encoding and decoding matrix. Here, I will use the same matrix as above to encode the information, that is, we will use
\[\begin{bmatrix}
5 & 4 \\
4 & 3
\end{bmatrix}\]

Since we decided to use a \(2 \times 2\) encoding matrix, we cannot leave the hello. matrix as previously given, because multiplication for these matrices is not defined. Therefore, we will create a matrix of size \(2 \times n\) where \(n\) is however many columns we need to complete the message. We therefore get
\[\begin{bmatrix}
h & l & o \\
e &l & .
\end{bmatrix}=\begin{bmatrix}
8 & 12 & 15 \\
5 & 12 & 28
\end{bmatrix}\]

Now as one extra step, I also want to work with entries in the integers mod 29. In particular, I went to do this so that my resulting message will be ensured to only give number between 0 and 28. As such, we will be able to convert our message into to. Since we are using the integers mod 29, (for more on modular arithmetic visit Modular Arithmetic: 2+2=1!) we will need to give our new inverse matrix.

Our decryption matrix

The process for finding the inverse matrix over \(\mathbb{Z}_{29}\) (the integers mod 29) is the same as if we were working over the integers. That is, we will augment our matrix with the identity matrix, row reduce and look at the resulting matrix. The only difference is that we will do our operation in \(\mathbb{Z}_{29}\). We will therefore have
\[\begin{bmatrix}
5 & 4 & 1 & 0\\
4 & 3 & 0 & 1
\end{bmatrix}\] We then want to turn the \(5\) into a \(1\). Since \(\frac{1}{5}\) is not an integer in \(\mathbb{Z}_{29}\) we will have to find the multiplicative inverse in the new set. Since this is \(6\), we will multiply the first row by 6 and get
\[\begin{bmatrix}
1 & 24 & 6 & 0\\
4 & 3 & 0 & 1
\end{bmatrix}\] Next, we would want to take \(-4\) times the first row and add it to the second. However, since we are working mod 29, we instead take \(-4 \equiv 25 mod 29\), so we multiply by 25 then add and get
\[\begin{bmatrix}
1 & 24 & 6 & 0\\
0 & 23 & 5 & 1
\end{bmatrix}\] We next find that instead of dividing the second row by \(23\), we would multiply by \(24\). We then get
\[\begin{bmatrix}
1 & 24 & 6 & 0\\
0 & 1 & 4 & 24
\end{bmatrix}\] Now, we multiply row two by \(-24=5 \mod 29\) and add it to row one and get
\[\begin{bmatrix}
1 & 0 & 26 & 4\\
0 & 1 & 4 & 24
\end{bmatrix}\] Hence, the inverse matrix is
\[\begin{bmatrix}
26 & 4 \\
4 & 24
\end{bmatrix}\]

In order to check our work, we should note that this should correspond with our original inverse when the entries are converted to the integers mod 29. Since \(26 \equiv -3 \mod 29\) and \(24 \equiv -5 \mod 29\), we get that these are indeed the same matrices. As a further note, it would have sufficed just to make this conversion to begin with instead of doing all of the calculations over again; however, I thought this would be a good opportunity to work more with modular arithmetic.

Encoding and Decoding

In order to encrypt our message “hello.” we can now take
\[\begin{bmatrix}
5 & 4 \\
4 & 3
\end{bmatrix}*
\begin{bmatrix}
8 & 12 & 15 \\
5 & 12 & 28
\end{bmatrix}
=\begin{bmatrix}
2 & 21 & 13 \\
18 & 26 & 28
\end{bmatrix}\]

Hence, our encoded message will be “bruzm.” In order to check that you would understand the answer, we find that
\[\begin{bmatrix}
26 & 4 \\
4 & 24
\end{bmatrix}*
\begin{bmatrix}
2 & 21 & 13 \\
18 & 26 & 28
\end{bmatrix}
=\begin{bmatrix}
8 & 12 & 15 \\
5 & 12 & 28
\end{bmatrix}\] which would then be converted back to “hello.”

Your turn!

As a final step, I will let you decrypt the message “stdcw toj.h ttkslirbvbaug,l,rjsaaw.i”

When you figure it out, watch the video below. I hope you take the time to decrypt the message, I think it will be worth the time. However, if you give up, please feel free the watch the video and we’ll give you the answer. If you like the post, be sure to share it with anyone else that might want to see it and follow or blog on Social Media to see more.

We'd love to hear your thoughts!

This site uses Akismet to reduce spam. Learn how your comment data is processed.