Applying Linearity
The Problem
Alice is using a 3-by-3 secret matrix to encrypt a written text and send it to Bob. Her encryption method is as follows. First, Alice tells Bob what secret matrix she is going to use. To send a message, she replaces each letter by its corresponding order in the alphabet and puts a zero for a space. This yields a vector of integers which encodes the message. The 3-by-3 matrix is applied to the first three entries of the vector, then the next three entries, etc. This yields a new vector which carries the encrypted text. Alice then sends the encrypted vector in an email.
Question 1
How can Bob decrypt the message?
Since Bob has the 3x3 encrypting matrix, he can decode the message using the inverse of the matrix.
If the encoding matrix is $ \begin{bmatrix} M \end{bmatrix} $ and the encrypted message is $ (a,b,c,d,e,f) $ then all he has to do is take
$ \begin{bmatrix} M \end{bmatrix}^{-1}\begin{bmatrix}a & d \\ b & e \\ c & f \end{bmatrix} $ = $ \begin{bmatrix}g & j \\ h & k \\ i & l \end{bmatrix} $
where $ \begin{bmatrix}g & j \\ h & k \\ i & l \end{bmatrix} $ can be put in the form $ (g,h,i,j,k,l) $ and letters substituted in for the numbers to give the final output string.
Question 2
Eve is eavesdropping on the conversation. Although she doesn’t know what the matrix is, she happens to know that the message (1,0,4,0,1,0,1,0,1) yields the encrypted vector (2,0,0,0,1,0,0,0,3).
Can Eve decrypt the message without finding the inverse of the secret matrix?
Short answer, yes, Eve can decrypt the message without the inverse of the secret matrix.
Long answer, I don't know how she would do this, but it seems others have found a way. However, she has all of the necessary information to find the inverse of the secret matrix, so I'm not sure why she would want to find a harder way to solve the problem.
Question 3
What is the decrypted message corresponding to (2,23,3)?
Solving the previous problem for the secret matrix, we find:
$ \begin{bmatrix} 1 & 0 & 4 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}\begin{bmatrix} a & d & g \\ b & e & h \\ c & f & i \end{bmatrix}=\begin{bmatrix} 2 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 3 \end{bmatrix} $
yields the equations
a+4g=2 d+4f=0 g+4i=0 d=0 e=1 f=0 a+c=0 d+f=0 g+i=3
solving these equations and putting them back into the matrix, we find the inverse of the secret matrix is:
$ \begin{bmatrix}\frac{1}{2} & 0 & \frac{1}{3} \\ 0 & 1 & 0 \\ 2 & 0 & \frac{1}{3} \end{bmatrix} $
inverting this gives us
$ \begin{bmatrix}\frac{1}{2} & 0 & \frac{1}{3} \\ 0 & 1 & 0 \\ 2 & 0 & \frac{1}{3} \end{bmatrix}^{-1} = \begin{bmatrix}-\frac{2}{3} & 0 & \frac{2}{3} \\ 0 & 1 & 0 \\ 4 & 0 & -1 \end{bmatrix} $
of course, we didn't need to invert it, but anyways, using the equation
$ \begin{bmatrix}known matrix \end{bmatrix}\begin{bmatrix}secret matrix^{-1} \end{bmatrix} = \begin{bmatrix} starting matrix \end{bmatrix} $
giving us
$ \begin{bmatrix}\frac{1}{2} & 0 & \frac{1}{3} \\ 0 & 1 & 0 \\ 2 & 0 & \frac{1}{3} \end{bmatrix} \begin{bmatrix}2\\23\\3\end{bmatrix} = \begin{bmatrix}2\\23\\5\end{bmatrix} $
Converting (2,23,5) to alphabet characters gives us "BWE".
