Contents
How can Bob Decrypt the Message?
Let A be the 3x3 secret matrix message.
$ \,A=\left[ \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right] \, $
Let B be the 3x3 matrix for the unencrypted message.
$ \,B=\left[ \begin{array}{ccc} b_{11} & b_{12} & b_{13} \\ b_{21} & b_{22} & b_{23} \\ b_{31} & b_{32} & b_{33} \end{array} \right] \, $
Correspondingly, let C be the decrypted message
From the poblem: $ \,C = B * A\, $
So $ \,C*A^{-1} = B * A * A^{-1} = B\, $, i.e. $ \,B = C*A^{-1} $
Thus Bob can decrypt the message by finding the inverse of the secret matrix.
Can Eve decrypt the message without finding the inverse of the secret matrix?
Based on the multiplication of Matrix:
if
$ \,C_1 = B_1*A\, $, same for $ C_2 $ and $ C_3 $
$ \,e=mA\, $
which is how the message is being encrypted. If we multiply both sides by the inverse of $ \,A\, $, we get
$ \,eA^{-1}=mAA^{-1}=mI=m\, $
Therefore, we can get the original message back if we multiply the encrypted message by $ \,A^{-1}\, $, given that the inverse of $ \,A\, $ exists.
Can Eve Decrypt the Message Without Finding the Inverse of A?
Yes, because of the fact $ \,e=mA\, $ is linear and Eve was given three linearly independent vector responses to the system and their corresponding inputs.
Proof of Linearity
Say we have two inputs $ \,m_1\, $ and $ \,m_2\, $ yielding outputs
$ \,e_1=m_1A\, $ and
$ \,e_2=m_2A\, $, respectively.
thus,
$ \,ae_1+be_2=am_1A+bm_2A $ for any $ \,a,b\in \mathbb{R}\, $
Now, apply $ \,am_1+bm_2\, $ to the system
$ \,(am_1+bm_2)A=am_1A+bm_2A\, $
Since the two results are equal
$ \,am_1A+bm_2A=am_1A+bm_2A\, $
the system is linear.
Main Proof
Since Eve was given that for the system
$ \,m_1=(1,0,4)\, $ yields $ \,e_1=(2,0,0)\, $
$ \,m_2=(0,1,0)\, $ yields $ \,e_2=(0,1,0)\, $
$ \,m_3=(1,0,1)\, $ yields $ \,e_3=(0,0,3)\, $
where $ \,e_1, e_2, e_3\, $ are clearly linearly independent vectors, Eve can take any encrypted message and write it as a linear combination of $ \,e_1, e_2, e_3\, $
$ \,\exists a,b,c\in \mathbb{R}\, $ such that $ \,e=ae_1+be_2+ce_3\, $, for any $ \,e\in \mathbb{R}^{3}\, $
Because the system is linear, we can write the input as
$ \,m=am_1+bm_2+cm_3\, $
thus, the message has been decrypted without knowing $ \,A^{-1}\, $.
What is the Decrypted Message?
The given encrypted message is
$ \,e=(2,23,3)\, $
This can be rewritten as a linear combination of the given system result vectors
$ \,e=ae_1+be_2+ce_3\, $
$ \,e=(2,23,3)=1\cdot (2,0,0)+23\cdot (0,1,0)+1\cdot (0,0,3)\, $
Because the system s linear, we can write the input as
$ \,m=am_1+bm_2+cm_3\, $
$ \,m=1\cdot (1,0,4)+23\cdot (0,1,0)+1\cdot (1,0,1)=(2,23,5)\, $
Therefore, the unencrypted message is "BWE".
