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) The key matrix \(K=\left[\begin{array}{lll}2 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1\end{array}\right] .\) Find its inverse \(, K^{-1}\). [Note: This key matrix is known as the \(Q_{2}^{3}\) Fibonacci encryption matrix.] (b) Use the result from part (a) to decode the encrypted $$ \text { matrix } E=\left[\begin{array}{lll} 47 & 34 & 33 \\ 44 & 36 & 27 \\ 47 & 41 & 20 \end{array}\right] $$ (c) Each entry in the 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?

Short answer

The original message is 'THEORIG'.

Step-by-step solution

- Find the Determinant of the Key Matrix

Calculate the determinant of the key matrix using the formula for a 3x3 matrix:\[ \text{det}(K) = a(ei - fh) - b(di - fg) + c(dh - eg) \]For the matrix \(K = \left[\begin{array}{lll} 2 & 1 & 1 \ 1 & 1 & 0 \ 1 & 1 & 1 \end{array}\right]\),\[ \text{det}(K) = 2(1\footnotesize{\times}1 - 1\footnotesize{\times}0) - 1(1\footnotesize{\times}1 - 1\footnotesize{\times}1) + 1(1\footnotesize{\times}1 - 1\footnotesize{\times}0) = 2 - 0 + 1 = 3 \]

- Find the Matrix of Minors

Calculate the matrix of minors by removing the row and column of each element and finding the determinant of the remaining 2x2 matrix.For example, for the element at the first row and first column (2), the minor is the determinant of the matrix obtained by removing the first row and first column from K, which results in:\[ \begin{vmatrix} 1 & 0 \ 1 & 1 \ \ \ \end{vmatrix} = (1\footnotesize{\times}1 - 0\footnotesize{\times}1) = 1 \]

- Form the Matrix of Cofactors

Apply a checkerboard pattern of signs to the matrix of minors to obtain the matrix of cofactors. For example, the cofactors for the given key matrix K are:\[ \text{cof}(K) = \left[ \begin{array}{ccc} 1 & -1 & 0 \ -1 & 1 & -1 \ 1 & -1 & 1 \end{array} \right] \]

- Transpose the Matrix of Cofactors

Take the transpose of the matrix of cofactors to get the adjugate matrix (also called the adjoint). For example:\[ \text{adj}(K) = \text{cof}(K)^T = \left[ \begin{array}{ccc} 1 & -1 & 1 \ -1 & 1 & -1 \ 0 & -1 & 1 \end{array} \right] \]

- Multiply by the Reciprocal of the Determinant

Calculate the inverse matrix by multiplying the adjugate matrix by the reciprocal of the determinant. For the given key matrix K:\[ K^{-1} = \frac{1}{\text{det}(K)} \cdot \text{adj}(K) = \frac{1}{3} \cdot \left[\begin{array}{ccc} 1 & -1 & 1 \ -1 & 1 & -1 \ 0 & -1 & 1 \end{array}\right] = \left[\begin{array}{ccc} \frac{1}{3} & -\frac{1}{3} & \frac{1}{3} \ -\frac{1}{3} & \frac{1}{3} & -\frac{1}{3} \ 0 & -\frac{1}{3} & \frac{1}{3} \end{array}\right] \]

- Multiply Encrypted Matrix by Inverse Key Matrix

Decode the encrypted message matrix E by multiplying it by the inverse key matrix. For \( E = \left[\begin{array}{lll} 47 & 34 & 33 \ 44 & 36 & 27 \ 47 & 41 & 20 \end{array}\right] \) and \( K^{-1} \), perform the matrix multiplication as follows:\[ M = E \cdot K^{-1} = \left[\begin{array}{lll} 47 & 34 & 33 \ 44 & 36 & 27 \ 47 & 41 & 20 \end{array}\right] \cdot \left[\begin{array}{ccc} \frac{1}{3} & -\frac{1}{3} & \frac{1}{3} \ -\frac{1}{3} & \frac{1}{3} & -\frac{1}{3} \ 0 & -\frac{1}{3} & \frac{1}{3} \end{array}\right] \]Resulting in:\[ M = \left[\begin{array}{lll} 20 & 8 & 5 \ 15 & 18 & 9 \ 15 & 21 & 7 \end{array}\right] \]

- Decode the Resulting Message Matrix

Translate each entry in matrix M to its corresponding letter in the alphabet, where A=1, B=2, ..., Z=26.\( 20 = T, 8 = H, 5 = E, 15 = O, 18 = R, 9 = I, 21 = U, 7 = G \)Thus, the original message is 'THEORIG'.

Key concepts

Matrix Encryption

Matrix encryption is a method used to encode messages using matrices. To encrypt a message, we represent it as a matrix and multiply it with a key matrix. This produces an encrypted matrix. The process can be summarized as:

• Convert the message into a numerical matrix.
• Multiply this message matrix by a key matrix.

The result of this multiplication is the encrypted matrix. To decrypt the message, we use the inverse of the key matrix and multiply it by the encrypted matrix. This method ensures that only those with the correct key matrix can decode the message.

Inverse Matrix

An inverse matrix is crucial for decrypting a message that has been encrypted using matrix encryption. The inverse of a key matrix, denoted as \( K^{-1} \), is a matrix that, when multiplied with the original key matrix, produces the identity matrix. Here's an overview of finding an inverse matrix:

• Calculate the determinant of the key matrix.
• Find the matrix of minors.
• Apply a checkerboard pattern of signs to get the cofactor matrix.
• Transpose the cofactor matrix to get the adjugate matrix.
• Multiply the adjugate matrix by the reciprocal of the determinant.

This process yields the inverse matrix.

Determinant Calculation

The determinant is a value that can be computed from the elements of a square matrix. It plays a vital role in finding the inverse of a matrix. For a 3x3 matrix \( K = \left[ \begin{array}{ccc} a & b & c \ d & e & f \ g & h & i \end{array} \right] \), the determinant is calculated using:
\[ \text{det}(K) = a(ei - fh) - b(di - fg) + c(dh - eg) \]
In the given exercise, the key matrix has a determinant of 3, calculated as follows:
\[ \text{det}(K) = 2(1 \times 1 - 1 \times 0) - 1(1 \times 1 - 1 \times 1) + 1(1 \times 1 - 1 \times 0) = 2 - 0 + 1 = 3 \]

Matrix of Cofactors

The matrix of cofactors is used in the process of finding the inverse of a matrix. Each element in this matrix is obtained by taking the determinant of the minor matrix, followed by applying a checkerboard pattern of signs. The steps are:

• Find the minor for each element of the original matrix by removing the row and column of that element.
• Calculate the determinant of each minor.
• Apply a sign pattern \(\begin{array}{ccc} + & - & + \ - & + & - \ + & - & + \end{array}\) to the corresponding minors.

For example, the cofactors for the given matrix are:
\[ \text{cof}(K) = \left[ \begin{array}{ccc} 1 & -1 & 0 \ -1 & 1 & -1 \ 1 & -1 & 1 \end{array} \right] \]

Matrix Transposition

Matrix transposition involves flipping a matrix over its diagonal, turning rows into columns and vice versa. This step is essential when working with the adjugate matrix while finding an inverse matrix. For example, the transpose of the matrix of cofactors:\[ \text{cof}(K) = \left[ \begin{array}{ccc} 1 & -1 & 0 \ -1 & 1 & -1 \ 1 & -1 & 1 \end{array} \right] \]
is given by:\[ \text{adj}(K) = \left[ \begin{array}{ccc} 1 & -1 & 1 \ -1 & 1 & -1 \ 0 & -1 & 1 \end{array} \right] \]

Matrix Multiplication

Matrix multiplication is a mathematical operation that takes two matrices and produces a third matrix. This is used both in encrypting and decrypting a message. To multiply two matrices, compute the dot product of rows and columns:
Here’s the step-by-step for multiplying the encrypted matrix by the inverse matrix:
Encrypted matrix \( E \):\[ \left[ \begin{array}{ccc} 47 & 34 & 33 \ 44 & 36 & 27 \ 47 & 41 & 20 \end{array} \right] \]
Inverse key matrix \( K^{-1} \):\[ \left[ \begin{array}{ccc} \frac{1}{3} & -\frac{1}{3} & \frac{1}{3} \ -\frac{1}{3} & \frac{1}{3} & -\frac{1}{3} \ 0 & -\frac{1}{3} & \frac{1}{3} \end{array} \right]\]
Multiply each element row by each column, sum the results:
\[ M = E \cdot K^{-1} = \left[ \begin{array}{ccc} 47 & 34 & 33 \ 44 & 36 & 27 \ 47 & 41 & 20 \end{array} \right] \cdot \left[ \begin{array}{ccc} \frac{1}{3} & -\frac{1}{3} & \frac{1}{3} \ -\frac{1}{3} & \frac{1}{3} & -\frac{1}{3} \ 0 & -\frac{1}{3} & \frac{1}{3} \end{array} \right] \]

Alphabet Position Encoding

Alphabet position encoding is a simple way to convert letters to numerical values and vice versa. This encoding is fundamental in cryptography. Each letter of the alphabet is assigned a number:

• A = 1
• B = 2
• C = 3
• ...
  
• Z = 26

In the encryption exercise, after the matrix multiplication, the resulting matrix entries (like 20, 8, 5) correspond to letters of the alphabet (T, H, E). This mapping allows us to decode numerical values back into the original message text.