Q. 87

Question

Cryptography; One method of encryption is to use a matrix to encrypt the message and then use the corresponding inverse matrix to decode the message. The encrypted matrix, $E$ , is obtained by multiplying the message matrix, $M$ , by a key matrix, $K$ . The original message can be retrieved by multiplying the encrypted matrix by the inverse of the key matrix. That is, $E = M \cdot K$ and $M = E \cdot K^{- 1}$ .

(a) Given the key matrix $K = [\begin{matrix} 2 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{matrix}]$ , find its inverse, $K^{- 1}$ . [Note: This key matrix is known as the ${Q_{2}}^{3}$ Fibonacci encryption matrix.]

(b) Use your result from part (a) to decode the encrypted matrix $E = [\begin{matrix} 47 & 34 & 33 \\ 44 & 36 & 27 \\ 47 & 41 & 20 \end{matrix}]$

(c) Each entry in your result for part (b) represents the position of a letter in the English alphabet ( $A = 1, B = 2, C = 3,$ and so on). What is the original message?

Step-by-Step Solution

Verified

Answer

(a) The inverse of the key matrix $= [\begin{matrix} 1 & 0 & - 1 \\ - 1 & 1 & 1 \\ 0 & - 1 & 1 \end{matrix}]$

(b) The message matrix is $M = [\begin{matrix} 13 & 1 & 20 \\ 8 & 9 & 19 \\ 6 & 21 & 14 \end{matrix}]$

1Step 1. Given data

The encrypted matrix $E$ , is obtained by multiplying the message matrix $M$ , by a key matrix $K$ . The original message can be retrieved by multiplying the encrypted matrix by the inverse of the key matrix. That is, $E = M . K$ and $M = E \cdot K^{- 1}$ .

We have the given key matrix $K = [\begin{matrix} 2 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{matrix}]$

2Step 2. Inverse matrix

(b) First we have to find $[K ∣ I_{3}]$ first, we have to form

$[K ∣ I_{3}] = [\begin{array}{cccccc} 2 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 \end{array}]$

Now let us convert the left side of the matrix into its reduced echelon form.

By performing the operation $R_{1} = \frac{r_{1}}{2}$ ,

$[\begin{array}{cccccc} \frac{2}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{0}{2} & \frac{0}{2} \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 \end{array}] \to [\begin{array}{cccccc} 1 & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 \end{array}]$

Substracting the first row from the second row,

$[\begin{array}{cccccc} 1 & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ 1 - 1 & 1 - \frac{1}{2} & 0 - \frac{1}{2} & 0 - \frac{1}{2} & 1 - 0 & 0 - 0 \\ 1 & 1 & 1 & 0 & 0 & 1 \end{array}] \to [\begin{array}{cccccc} 1 & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ 0 & \frac{1}{2} & - \frac{1}{2} & - \frac{1}{2} & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 \end{array}]$

subtracting the first row from the third row,

$[\begin{array}{cccccc} 1 & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ 0 & \frac{1}{2} & - \frac{1}{2} & - \frac{1}{2} & 1 & 0 \\ 1 - 1 & 1 - \frac{1}{2} & 1 - \frac{1}{2} & 0 - \frac{1}{2} & 0 - 0 & 1 - 0 \end{array}] \to [\begin{array}{cccccc} 1 & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ 0 & \frac{1}{2} & - \frac{1}{2} & - \frac{1}{2} & 1 & 0 \\ 0 & \frac{1}{2} & \frac{1}{2} & - \frac{1}{2} & 0 & 1 \end{array}]$

Multiply the second row by $2$

$[\begin{array}{cccccc} 1 & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ 2 \cdot 0 & 2 \cdot \frac{1}{2} & 2 (- \frac{1}{2}) & 2 (- \frac{1}{2}) & 2 \cdot 1 & 2 \cdot 0 \\ 0 & \frac{1}{2} & \frac{1}{2} & - \frac{1}{2} & 0 & 1 \end{array}] \to [\begin{array}{cccccc} 1 & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ 0 & 1 & - 1 & - 1 & 2 & 0 \\ 0 & \frac{1}{2} & \frac{1}{2} & - \frac{1}{2} & 0 & 1 \end{array}]$

Perform the operation $R_{3} = r_{3} - \frac{r_{2}}{2}$ we get,

$[\begin{array}{cccccc} 1 & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ 0 & 1 & - 1 & - 1 & 2 & 0 \\ 0 - 0 & \frac{1}{2} - \frac{1}{2} & \frac{1}{2} + \frac{1}{2} & - \frac{1}{2} + \frac{1}{2} & 0 - 1 & 1 - 0 \end{array}] \to [\begin{array}{cccccc} 1 & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ 0 & 1 & - 1 & - 1 & 2 & 0 \\ 0 & 0 & 1 & 0 & - 1 & 1 \end{array}]$

Perform the operation $R_{1} = r_{1} - \frac{r_{2}}{2}$

$[\begin{array}{ccccccc} 1 - 0 & \frac{1}{2} - \frac{1}{2} & \frac{1}{2} + \frac{1}{2} & \frac{1}{2} + \frac{1}{2} & 0 - 1 & 0 - 0 \\ 0 & 1 & - 1 & - 1 & 2 & 0 \\ 0 & 0 & 1 & 0 & - 1 & 1 \end{array}] \to [\begin{array}{rrrrrr} 1 0 1 1 - 1 0 \\ 0 1 - 1 - 1 2 0 \\ 0 0 1 0 - 1 1 \end{array}]$

Subtract the third row from the first row,

$[\begin{array}{cccccc} 1 - 0 & 0 - 0 & 1 - 1 & 1 - 0 & - 1 - (- 1) & 0 - 1 \\ 0 & 1 & - 1 & - 1 & 2 & 0 \\ 0 & 0 & 1 & 0 & - 1 & 1 \end{array}] \to [\begin{array}{cccrrr} 1 & 0 & 0 & 1 & 0 & - 1 \\ 0 & 1 & - 1 & - 1 & 2 & 0 \\ 0 & 0 & 1 & 0 & - 1 & 1 \end{array}]$

Add second and third row, we get

$[\begin{array}{cccccc} 1 & 0 & 0 & 1 & 0 & - 1 \\ 0 + 0 & 1 + 0 & - 1 + 1 & - 1 + 0 & 2 - 1 & 0 + 1 \\ 0 & 0 & 1 & 0 & - 1 & 1 \end{array}] \to [\begin{array}{cccrrr} 1 & 0 & 0 & 1 & 0 & - 1 \\ 0 & 1 & 0 & - 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & - 1 & 1 \end{array}]$

Therefore, the inverse key matrix is $[\begin{array}{rrr} 1 0 - 1 \\ - 1 1 1 \\ 0 - 1 1 \end{array}]$

3Step 3. Messege matrix

(b)To find the message matrix $M$ ,we have to find the product of the two matrices $K^{- 1}$ and $E$ .

$E K^{- 1} = [\begin{array}{lll} 47 & 34 & 33 \\ 44 & 36 & 27 \\ 47 & 41 & 20 \end{array}] [\begin{array}{rrr} 1 & 0 & - 1 \\ - 1 & 1 & 1 \\ 0 & - 1 & 1 \end{array}] = [\begin{array}{ccc} 47 - 34 & 34 - 33 & - 47 + 34 + 33 \\ 44 - 36 & 36 - 27 & - 44 + 36 + 27 \\ 47 - 41 & 41 - 20 & - 47 + 41 + 20 \end{array}] = [\begin{array}{ccc} 13 & 1 & 20 \\ 8 & 9 & 19 \\ 6 & 21 & 14 \end{array}]$