(New page: Some definitions and explainations 1.Let A be the 3x3 matrix used to encrypt the message. <math>\,A=\left[ \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{3...)
 
(→‎How can Bob Decrypt the Message?)
 
(9 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
Some definitions and explainations
+
== How can Bob Decrypt the Message? ==
 +
Bob can use the inverse of the secret matrix
 +
 
 +
Explaination:
  
−
1.Let A be the 3x3 matrix used to encrypt the message.
+
Let A be the 3x3 secret matrix message.
  
 
<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>
  
−
Note:this can also be written as <math>\,B=\left[ \begin{array}{ccc} B_{1} & B_{2} & B_{3} \end{array} \right] \,</math>
+
Correspondingly, let C be the crypted message
  
−
Correspondingly,
+
From the poblem:  <math>\,C = B * A\,</math>
  
−
2.  
+
So <math>\,C*A^{-1} = B * A * A^{-1} = B\,</math>, i.e. <math>\,B = C*A^{-1}</math>
  
−
Some defines:
+
Thus Bob can decrypt the message by finding the inverse of the secret matrix.
  
−
<math>\,m=\left[ \begin{array}{ccc} x & y & z \end{array} \right] \,</math> is the message
+
== Can Eve decrypt the message without finding the inverse of the secret matrix? ==
  
−
<math>\,e=\left[ \begin{array}{ccc} s & t & u \end{array} \right] \,</math> is the encrypted message
+
YES. Here is the explaination:
  
−
== How can Bob Decrypt the Message? ==
+
Let,
−
We have the equation
+
<math>\,B=B_1+B_2+B_3\,</math> and <math>\,C=C_1+C_2+C_3\,</math>
  
−
<math>\,e=mA\,</math>
+
Thus,we can have:
  
−
which is how the message is being encrypted.  If we multiply both sides by the inverse of <math>\,A\,</math>, we get
+
<math>\,B_1 = C_1*A^{-1}\,</math>
  
−
<math>\,eA^{-1}=mAA^{-1}=mI=m\,</math>
+
<math>\,B_2 = C_2*A^{-1}\,</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.
+
<math>\,B_3 = C_3*A^{-1}\,</math>
  
−
== Can Eve Decrypt the Message Without Finding the Inverse of A? ==
+
if we can decompose <math>\,C_new=n*C_1+p*C_2+q*C_3\,</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.
+
we have:
  
 +
<math>\,B_1new = n*C_1*A^{-1} = n*B_1\,</math>
  
−
'''Proof of Linearity'''
+
<math>\,B_2new = p*C_2*A^{-1} = p*B_2\,</math>
  
−
Say we have two inputs <math>\,m_1\,</math> and <math>\,m_2\,</math> yielding outputs
+
<math>\,B_3new = q*C_3*A^{-1} = q*B_3\,</math>
  
−
<math>\,e_1=m_1A\,</math> and
+
So we can get:
  
−
<math>\,e_2=m_2A\,</math>, respectively.
+
<math>\,B_new = B_1new+B_2new+B_3new = n*B_1+p*B_2+q*B_3 \,</math>
  
−
thus,
+
so all Eve need to do is to express each row of the encrypted message in terms of a*[2,0,0]+b*[0,1,0]+c*[0,0,3]
  
−
<math>\,ae_1+be_2=am_1A+bm_2A</math> for any <math>\,a,b\in \mathbb{R}\,</math>
+
then the corresponding row of the original code is a*[1,0,4]+b*[0,1,0]+c*[1,0,1]
−
 
+
−
 
+
−
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? ==
−
The given encrypted message is
+
The encrypted message is
−
 
+
−
<math>\,e=(2,23,3)\,</math>
+
−
 
+
−
 
+
−
This can be rewritten as a linear combination of the given system result vectors
+
−
 
+
−
<math>\,e=ae_1+be_2+ce_3\,</math>
+
−
 
+
−
<math>\,e=(2,23,3)=1\cdot (2,0,0)+23\cdot (0,1,0)+1\cdot (0,0,3)\,</math>
+
  
 +
<math>\,C=(2,23,3)\,</math>
  
−
Because the system s linear, we can write the input as
+
we can write it as
  
−
<math>\,m=am_1+bm_2+cm_3\,</math>
+
<math>\,C=1\cdot (2,0,0)+23\cdot (0,1,0)+1\cdot (0,0,3)\,</math>
  
−
<math>\,m=1\cdot (1,0,4)+23\cdot (0,1,0)+1\cdot (1,0,1)=(2,23,5)\,</math>
+
Given system is linear, the corresponding output is
  
 +
<math>\,B=1\cdot (1,0,4)+23\cdot (0,1,0)+1\cdot (1,0,1)=(2,23,5)\,</math>
  
−
Therefore, the unencrypted message is "'''BWE'''".
 
  
−
==How can Bob decrypt the message?==
+
So, the original message is "B,W,E".

Latest revision as of 17:17, 18 September 2008

How can Bob Decrypt the Message?

Bob can use the inverse of the secret matrix

Explaination:

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?

YES. Here is the explaination:

Let, $ \,B=B_1+B_2+B_3\, $ and $ \,C=C_1+C_2+C_3\, $

Thus,we can have:

$ \,B_1 = C_1*A^{-1}\, $

$ \,B_2 = C_2*A^{-1}\, $

$ \,B_3 = C_3*A^{-1}\, $

if we can decompose $ \,C_new=n*C_1+p*C_2+q*C_3\, $ we have:

$ \,B_1new = n*C_1*A^{-1} = n*B_1\, $

$ \,B_2new = p*C_2*A^{-1} = p*B_2\, $

$ \,B_3new = q*C_3*A^{-1} = q*B_3\, $

So we can get:

$ \,B_new = B_1new+B_2new+B_3new = n*B_1+p*B_2+q*B_3 \, $

so all Eve need to do is to express each row of the encrypted message in terms of a*[2,0,0]+b*[0,1,0]+c*[0,0,3]

then the corresponding row of the original code is a*[1,0,4]+b*[0,1,0]+c*[1,0,1]

What is the Decrypted Message?

The encrypted message is

$ \,C=(2,23,3)\, $

we can write it as

$ \,C=1\cdot (2,0,0)+23\cdot (0,1,0)+1\cdot (0,0,3)\, $

Given system is linear, the corresponding output is

$ \,B=1\cdot (1,0,4)+23\cdot (0,1,0)+1\cdot (1,0,1)=(2,23,5)\, $


So, the original message is "B,W,E".

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

Alumni Liaison

Ph.D. 2007, working on developing cool imaging technologies for digital cameras, camera phones, and video surveillance cameras.

Buyue Zhang