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.

Solution

1. To create an encryption scheme using the matrix $A=\begin{bmatrix}4&2\\1&3\end{bmatrix}$ mod $5$, we must be able to invert $A \mod 5$. To invert a $2\times2$ matrix $\begin{bmatrix}a&b\\c&d\end{bmatrix}$, we find $\begin{bmatrix}a&-b\\-c&d\end{bmatrix} {1\over ad-bc}$, so we must find the determinant and multiply by it's inverse. The determinant of $A$ is $4(3)-2(1) = 10$. Then we can only invert $A \mod 5$ if we can find the modular multiplicative inverse of $10 \mod 5$. We can easily check that $10z \mod 5 = 0$ for all $z\in \mathbb{Z}_5$. Since the the product of an element of $\mathbb{Z}_5$ and its inverse must equal $1\mod 5$, we see that the modular multiplicative inverse of $10 \mod 5$ does not exist. This means that we cannot invert $A$ in $\mathbb{Z}_5$.

2. With $A = \begin{bmatrix}2&1\\4&3\end{bmatrix}$, we can invert in $\mathbb{Z}_5$. The determinant of $A$ is $2$. Because $2(3) \mod 5 = 1$, the modular multiplicative inverse of $2\mod5$ is $3$.

3. The inverse matrix $A^{-1}$ of $A \mod 5$ is $\begin{bmatrix}4&2\\3&1\end{bmatrix}$. We can check this by multiplying it with $A$. We see that $$ \begin{align} \begin{bmatrix}2&1\\4&3\end{bmatrix} \begin{bmatrix}4&2\\3&1\end{bmatrix} &= \begin{bmatrix}2(4)+3(1)&2(2)+1\\4(4)+3(3)&2(4)+3\end{bmatrix}\\ &=\begin{bmatrix}1&0\\0&1\end{bmatrix} & \mod 5. \end{align} $$

Since the resultant matrix is the identity matrix, we have found the correct inverse for $A$.

Tags

Change these as needed.

  • Week3 - Which week are you writing this problem for?
  • Christian - Sign your name by just changing "YourName" to your wiki name.
  • Complete
  • 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.