Line 5: Line 5:
 
<math>\,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] \,</math>
 
<math>\,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] \,</math>
  
−
Let B be the 3x3 matrix for the unencrypted message.
+
Let B be the 3x3 matrix for the original message.
  
 
<math>\,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] \,</math>
 
<math>\,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] \,</math>
  
−
Correspondingly, let C be the decrypted message  
+
Correspondingly, let C be the crypted message  
  
 
From the poblem:  <math>\,C = B * A\,</math>
 
From the poblem:  <math>\,C = B * A\,</math>
Line 19: Line 19:
 
== Can Eve decrypt the message without 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 we write B as
 +
<math>\,A=\left[ \begin{array}{ccc} A_{1} \\ A_{2} \\ A_{3} \end{array} \right] \,</math>
 +
(write in conbimation of column vector)
  
−
if
+
Similarly, we write C as
 +
<math>\,C=\left[ \begin{array}{ccc} C_{1} & C_{2} & C_{3} \end{array} \right] \,</math>
  
−
<math>\,C_1 = B_1*A\,</math>, same for <math>C_2</math> and <math>C_3</math>
+
Thus,based on the multiplication of Matrix,we can have:
 +
<math>\,C_1 = B*A\,</math>, same for <math>\,C_2\,</math> and <math>\,C_3\,</math>
  
 +
which means
  
−
<math>\,e=mA\,</math>
+
<math>\,C_1 = B*A_1 = B_1*A_1+B_2*A_2+B_3*A_3\,</math>
  
−
which is how the message is being encrypted.  If we multiply both sides by the inverse of <math>\,A\,</math>, we get
+
<math>\,C_2 = B*A = B_1*A_1+B_2*A_2+B_3*A_3\,</math>
  
−
<math>\,eA^{-1}=mAA^{-1}=mI=m\,</math>
+
<math>\,C_3 = B*A = B_1*A_1+B_2*A_2+B_3*A_3\,</math>
  
−
Therefore, we can get the original message back if we multiply the encrypted message by <math>\,A^{-1}\,</math>, given that the inverse of <math>\,A\,</math> exists.
+
if we multiply <math>B_1</math> by n,<math>B_2</math> by p,<math>B_3</math> by q,
 +
we have:
  
−
== Can Eve Decrypt the Message Without Finding the Inverse of A? ==
+
<math>\,C_1new = B*A_1 = n*B_1*a_11+p*B_2*a_21+q*B_3*a_31\,</math>
−
Yes, because of the fact <math>\,e=mA\,</math> is linear and Eve was given three linearly independent vector responses to the system and their corresponding inputs.
+
  
 +
<math>\,C_2new = B*A_2 = n*B_1*a_21+p*B_2*a_22+q*B_3*a_23\,</math>
  
−
'''Proof of Linearity'''
+
<math>\,C_3new = B*A_3 = n*B_1*a_31+p*B_2*a_32+q*B_3*a_33\,</math>
  
−
Say we have two inputs <math>\,m_1\,</math> and <math>\,m_2\,</math> yielding outputs
+
and the reverse is also true
  
−
<math>\,e_1=m_1A\,</math> and
 
  
−
<math>\,e_2=m_2A\,</math>, respectively.
 
  
−
thus,
 
−
 
−
<math>\,ae_1+be_2=am_1A+bm_2A</math> for any <math>\,a,b\in \mathbb{R}\,</math>
 
−
 
−
 
−
Now, apply <math>\,am_1+bm_2\,</math> to the system
 
−
 
−
<math>\,(am_1+bm_2)A=am_1A+bm_2A\,</math>
 
−
 
−
 
−
Since the two results are equal
 
−
 
−
<math>\,am_1A+bm_2A=am_1A+bm_2A\,</math>
 
−
 
−
the system is linear.
 
−
 
−
 
−
''' Main Proof '''
 
−
 
−
Since Eve was given that for the system
 
−
 
−
<math>\,m_1=(1,0,4)\,</math> yields <math>\,e_1=(2,0,0)\,</math>
 
−
 
−
<math>\,m_2=(0,1,0)\,</math> yields <math>\,e_2=(0,1,0)\,</math>
 
−
 
−
<math>\,m_3=(1,0,1)\,</math> yields <math>\,e_3=(0,0,3)\,</math>
 
−
 
−
where <math>\,e_1, e_2, e_3\,</math> are clearly linearly independent vectors, Eve can take any encrypted message and write it as a linear combination of <math>\,e_1, e_2, e_3\,</math>
 
−
 
−
<math>\,\exists a,b,c\in \mathbb{R}\,</math> such that <math>\,e=ae_1+be_2+ce_3\,</math>, for any <math>\,e\in \mathbb{R}^{3}\,</math>
 
−
 
−
 
−
Because the system is linear, we can write the input as
 
−
 
−
<math>\,m=am_1+bm_2+cm_3\,</math>
 
−
 
−
thus, the message has been decrypted without knowing <math>\,A^{-1}\,</math>.
 
  
 
== What is the Decrypted Message? ==
 
== What is the Decrypted Message? ==

Revision as of 11:14, 18 September 2008

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 original 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 crypted 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?

if we write B as $ \,A=\left[ \begin{array}{ccc} A_{1} \\ A_{2} \\ A_{3} \end{array} \right] \, $ (write in conbimation of column vector)

Similarly, we write C as $ \,C=\left[ \begin{array}{ccc} C_{1} & C_{2} & C_{3} \end{array} \right] \, $

Thus,based on the multiplication of Matrix,we can have: $ \,C_1 = B*A\, $, same for $ \,C_2\, $ and $ \,C_3\, $

which means

$ \,C_1 = B*A_1 = B_1*A_1+B_2*A_2+B_3*A_3\, $

$ \,C_2 = B*A = B_1*A_1+B_2*A_2+B_3*A_3\, $

$ \,C_3 = B*A = B_1*A_1+B_2*A_2+B_3*A_3\, $

if we multiply $ B_1 $ by n,$ B_2 $ by p,$ B_3 $ by q, we have:

$ \,C_1new = B*A_1 = n*B_1*a_11+p*B_2*a_21+q*B_3*a_31\, $

$ \,C_2new = B*A_2 = n*B_1*a_21+p*B_2*a_22+q*B_3*a_23\, $

$ \,C_3new = B*A_3 = n*B_1*a_31+p*B_2*a_32+q*B_3*a_33\, $

and the reverse is also true



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".

Retrieved from "https://www.projectrhea.org/rhea/index.php?title=HW3.C_Hetong_Li_ECE301Fall2008mboutin&oldid=12843"
Shortcuts
Help Main Wiki Page Random Page Special Pages Log in
Search

Alumni Liaison

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett