Please Login to access more options.

Problem 27 (Matrix Encryption Mod 5)

In the Problem (Simple Matrix Encryption), we took a plain text message written in columns of a matrix $M$ and a matrix $A$ and used the product $AM$ to encode a message. Let's now combine matrix encryption with modular arithmetic to obtain a new encryption scheme. Once we have done this, we'll be one step closer to understanding modern encryption techniques. To simplify our work, let's use a small alphabet consisting of 5 letters. Instead of using the set $S=\{a,b,c,d,e\}$, let's just use numbers for our letters and we'll consider the alphabet $S=\{0,1,2,3,4\}=\mathbb{Z}_5$. Given the plain text "bad bed" or "10 31 43", we can encode it in the columns of the matrix $$M=\begin{bmatrix}1&3&4\\0&1&3\end{bmatrix}.$$ An 2 by 2 encryption key using coefficients mod 5 is a 2 by 2 matrix $A=\begin{bmatrix}a&b\\c&d\end{bmatrix}$ where $a,b,c,d\in \mathbb{Z}_5$. Here are the steps to our encryption scheme.

  • First convert the plain text to a matrix $M$ where the letters are place in the matrix top to bottom, column by column.
  • Take the encryption key $A$ and compute the product $AM$.
  • Reduce all the entries in $AM$ mod 5. So the cipher text only consists of the numbers in $\mathbb{Z}_5$.

Answer the following questions.

  1. Suppose we let $A=\begin{bmatrix}4&2\\1&3\end{bmatrix}$. Why is this matrix not suitable as an encryption key? (Hint: what is the determinant, and why is that a problem?)
  2. Suppose we let $A=\begin{bmatrix}2&1\\4&3\end{bmatrix}$. The inverse of $A$ if we ignore modular arithmetic is $\frac{1}{2}\begin{bmatrix}3&-1\\-4&2\end{bmatrix}$. We know that we can replace $-4$ with $1$ when working modular 5. Similarly we can replace $-1$ with a positive number. We need to find the multiplicative inverse of 2 when working modular 5. Find a value $b\in \mathbb{Z}_5$ so that $2b\mod 5=1$. This number $b$ is the inverse of $2$ modular 5.
  3. State a matrix $B$ with coefficients in $\mathbb{Z}_5$ so that $AB$ is the identity matrix after reducing each entry mod 5. Actually perform the product by hand, and show how this matrix product reduces to the identity.
From Ben: This one has very few errors, and is just about done. Here is what needs fixing:
  • You are using a colon to start a computation. Don't. Just delete the colon. If it were not a math equation, then we would write, "We compute 'stuff'" instead of "We compute: 'stuff'". Math equations are just words, and don't need a colon. You did a great job in part 3, but part 2 has this extra colon.
  • Sentences end with a period, even if the sentence ends with a centered computation. You are missing two of these. Please add them.

Solution

1. The Matrix $A=\begin{bmatrix}4&2\\1&3\end{bmatrix}$ is not a suitable matrix for this particular type of encryption because we have $\det{A}=2(3)-4(1)=10$, and when we perform modular arithmetic on it we have $\det{A}=10\mod{5}=0$. This poses a problem when trying to invert $A$.

2. We have $$\begin{align} A^{-1}&=\frac{1}{2}\begin{bmatrix}3&-1\\-4&2\end{bmatrix}\mod{5}\\ &=2^{-1}\begin{bmatrix}3&4\\1&2\end{bmatrix}\mod{5}. \end{align}$$ We complete the inversion by finding a $b$ such that $2(b)\mod{5}=1$. Let $b=3$. Thus we have $2(b)\mod{5}=2(3)\mod{5}=6\mod{5}=1$.

3. Let $B=3\begin{bmatrix}3&4\\1&2\end{bmatrix}\mod{5}=\begin{bmatrix}9&12\\3&6\end{bmatrix}\mod{5}=\begin{bmatrix}4&2\\3&1\end{bmatrix}$. Thus we have $$\begin{align} AB&=\begin{bmatrix}2&1\\4&3\end{bmatrix}\begin{bmatrix}4&2\\3&1\end{bmatrix}\mod{5}\\ &=\begin{bmatrix}11&5\\25&11\end{bmatrix}\mod{5}\\ &=\begin{bmatrix}1&0\\0&1\end{bmatrix}. \end{align}$$

Tags

Change these as needed.

  • When you are ready to submit this written work for grading, add the phrase [[!Submit]] to your page. This will tell me that you have completed the page (it's past rough draft form, and you believe it is in final draft form). Don't type [[!Submit]] on a rough draft.
  • If I put [[!NeedsWork]] on your page, then your job is to review what I've written, address any comments made, and then delete all the comments I made. When you have finished reviewing your work, leave [[!NeedsWork]] on your page and type [[!Submit]]. (Both tags will show up). This tells me you have addressed the comments.
  • I'll mark your work with [[!Complete]] after you have made appropriate revisions.