Contents
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.
How can Bob decrypt the message?
If Alice gives Bob an (assumedly) invertible matrix, all Bob has to do is invert the matrix, then send each 3-character chunk through. Assuming Alice wants to send Bob the message "abcdef" using the secret matrix $ \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 9 \\ 7 & 8 & 6 \end{bmatrix} $, the process would look something like this:
Alice sending message: $ [1,2,3,4,5,6] \rightarrow \begin{bmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{bmatrix} $ (break message into 3-bit chunks (ie, columns))
$ \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 9 \\ 7 & 8 & 6 \end{bmatrix} \begin{bmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{bmatrix} = \begin{bmatrix} 14 & 32 \\ 41 & 95 \\ 41 & 104 \end{bmatrix} $ (encrypt the message)
$ \begin{bmatrix} 14 & 32 \\ 41 & 95 \\ 41 & 104 \end{bmatrix} \rightarrow [14,41,41,32,95,104] $ (Put encrypted message back together (one column after another), then send to Bob.)
Bob receiving the message: $ [14,41,41,32,95,104] \rightarrow \begin{bmatrix} 14 & 32 \\ 41 & 95 \\ 41 & 104 \end{bmatrix} $ (break encrypted message into 3-bit chunks (ie, columns))
Since Bob knows the original matrix used to encrypt the message, he can now invert it to get back the original message:
$ {\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 9 \\ 7 & 8 & 6 \end{bmatrix}}^{-1} \begin{bmatrix} 14 & 32 \\ 41 & 95 \\ 41 & 104 \end{bmatrix} = \begin{bmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{bmatrix} $
$ \begin{bmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{bmatrix} \rightarrow [1,2,3,4,5,6] $ (Put encrypted message back together (one column after another))
...at which point, Bob would realize that he received the message "abcdef", and would wonder what the heck Alice was thinking making him go through all this work for something silly like that.
Eavesdropping Eve
Eve is eavesdropping 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?
Yes, Eve can. Think of the secret matrix as a function $ f: \mathbb{R}^3 \rightarrow \mathbb{R}^3 $ and, likewise, the inverse of the secret matrix as a function $ f^{-1}: \mathbb{R}^3 \rightarrow \mathbb{R}^3 $. So, for instance, $ f( (1,0,4) ) = (2,0,0) $, and $ f^{-1}( (2,0,0) ) = (1,0,4) $.
Both f and $ f^{-1}<math> are linear. For any input (a,b,c) and constant k, <math>f(k(a,b,c)) = kf(a,b,c) $ since scalar multiplication of a matrix is commutative. Likewise, for any inputs (a,b,c) and (d,e,f), $ f( (a,b,c) + (d,e,f) ) = f(a,b,c) + f(d,e,f) $, since matrix multiplication is distributive. Since this is the case, we can use the proprties of linearity - namely, that for constants a and b and for functions x and y, $ f(ax+by) = af(x)+bf(y) $ - to find an output given an input:
$ f^{-1}( (1,0,0) ) = \frac{1}{2} f^{-1}( (2,0,0) ) = \frac{1}{2} (1,0,4) = (\frac{1}{2}, 0, 2) $
$ f^{-1}( (0,1,0) ) = (0,1,0) ) $
$ f^{-1}( (0,0,1) ) = \frac{1}{3} f^{-1}( (0,0,3) ) = \frac{1}{3} (1,0,1) = (\frac{1}{3}, 0, \frac{1}{3}) $
So, assume we are given encryped message (a,b,c). Because of linearity, $ f^{-1}((a,b,c)) = af^{-1}((1,0,0)) + bf^{-1}((0,1,0)) + cf^{-1}((0,0,1)) = a(\frac{1}{2}, 0, 2) + b(0,1,0) + c(\frac{1}{3}, 0, \frac{1}{3}) $
$ = ( \frac{a}{2} + \frac{c}{3}, b, 2a + \frac{c}{3} ) $
is our decrypted message.
What is the decrypted message corresponding to (2,23,3)? (Write it as a text.)
Using the above conclusion, $ f^{-1}(2,23,3) = ( \frac{(2)}{2} + \frac{(3)}{3}, (23), 2(2) + \frac{(3)}{3} ) = (2,23,5) $. Translating directly to number order, our message is "BWE".
For sake of practice, and to check the validity of this answer, this could also be done using an invertible matrix. Let M be the secret matrix:
$ M \begin{bmatrix}1&0&1\\0&1&0\\4&0&1\end{bmatrix} = \begin{bmatrix}2&0&0\\0&1&0\\0&0&3\end{bmatrix} \Rightarrow M = \begin{bmatrix}2&0&0\\0&1&0\\0&0&3\end{bmatrix} {\begin{bmatrix}1&0&1\\0&1&0\\4&0&1\end{bmatrix}}^{-1} $
Given the encrypted message (2,23,3), our corresponding decrypted message would be: $ \text{Decrypted message} = M^{-1} \begin{bmatrix}2\\23\\3\end{bmatrix} = \begin{pmatrix}\begin{bmatrix}2&0&0\\0&1&0\\0&0&3\end{bmatrix} & {\begin{bmatrix}1&0&1\\0&1&0\\4&0&1\end{bmatrix}}^{-1} \end{pmatrix}^{-1} \begin{bmatrix}2\\23\\3\end{bmatrix} = \begin{bmatrix}2\\23\\5\end{bmatrix} $
So, we get the same answer either way - "BWE".
