Hill cipher.

Encryption: To encrypt a message using the Hill cipher.

• We must first turn our keyword into a key matrix ( a $ \ 2 \times 2$ matrix for working with digraphs, a $ 3 \times 3$ matrix for working with trigraphs, etc)

• We also turn the plain text into digraphs or trigraphs and each of these into a column vector.

• We then perform matrix multiplication modulo the length of the alphabet i.e. 26 on each vector.

• These vectors are then converted back into letters to produce the ciphertext.

Example:

1] plain-text : ‘ACT’ (n = 3)

Key : ‘G Y B N Q K U R P’

SOLUTION:

Step 1: $n \times n $ key matrix.

Step 2: Plain-text message ‘ACT’ is written in vector.

$ \begin{bmatrix}0 \\ 2 \\ 19 \\\end{bmatrix}$

Step 3: Encrypted vector is given as

$C = [K] [P] mod \ 26$

$\begin{aligned} &= \begin{bmatrix}6 \times 0 + 24 \times 2 + 1 \times 19 \\ 13 \times 0 + 16 \times 2 + 10 \times 2 \\ 20 \times 0 + 17 \times 2 + 15\times 19 \\\end{bmatrix} mod \ 26 \\ &= \begin{bmatrix}67 \\ 222 \\ 319 \\\end{bmatrix} mod \ 26 \\ &= \begin{bmatrix}15 \\ 14 \\ 07 \\\end{bmatrix} \\ i.e, C &= \begin{bmatrix}P \\ O \\ H \\\end{bmatrix} \end{aligned}$

Example 2.

Plain text = “short example”

Keyword = “hill” and a $2 \times 2$ matrix.

Steps:

To turn the keyword into a matrix, if the keyword was longer than the 4 letters needed, we would only take the first 4 letters and if it was shorter, we would fill it up with the alphabet in order.

• The keyword written as a matrix as

  $ = \begin{bmatrix}H & I \\ L & L \\\end{bmatrix}$

• With the keyword in a matrix, we need to convert this into a key matrix. We do this by converting each letter into a number by its position in the alphabet (starting at 0), So, A = 0, B = 1, C = 2, D = 3, etc.

  $ = \begin{bmatrix}7 & 8 \\ 11 & 11 \\\end{bmatrix}$

  The key matrix (each letter of the keyword is converted to number)

• Now, we split the plain text into digraphs and write these as column vectors, that is the first column vector we write the first plain text letter at the top and the second letter at the bottom. Then we move to the next column vector, where the third plain text letter goes at the top and the fourth at the bottom. This continues for the whole plain-text.

  $ \begin{bmatrix}s \\ h \\\end{bmatrix} \begin{bmatrix}o \\ r \\\end{bmatrix} \begin{bmatrix} t \\ e \\\end{bmatrix} \begin{bmatrix}x \\ a \\\end{bmatrix} \begin{bmatrix}m \\ p \\\end{bmatrix} \begin{bmatrix}l \\ e \\\end{bmatrix}$

  The plain text “short example” split into the column vectors.

• Now, we convert the plain text column vectors in the same way that we converted the keyword into the key matrix. Each letter is replaced by its appropriate number.

  $ \begin{bmatrix}18 \\ 7 \\\end{bmatrix} \begin{bmatrix}14 \\ 17 \\\end{bmatrix} \begin{bmatrix} 19 \\ 4 \\\end{bmatrix} \begin{bmatrix}23 \\ 0 \\\end{bmatrix} \begin{bmatrix}12 \\ 15 \\\end{bmatrix} \begin{bmatrix}11 \\ 04 \\\end{bmatrix}$

  The plain text converted into number column vectors.

• Next step is to perform matrix multiplication. We multiply the key matrix by each column vector in turn. We write the key matrix first, followed by the column vector.

  $\begin{aligned} \begin{bmatrix}7 & 8 \\ 11 & 11 \\\end{bmatrix} \begin{bmatrix}18 \\ 7 \\\end{bmatrix} \ mod \ 26 & = \begin{bmatrix}7 \times 18 + 8 \times 7 \\ 11 \times 18 + 11 \times 7 \\\end{bmatrix} \ mod \ 26 \\ &= \begin{bmatrix}182 \\ 275 \\\end{bmatrix} mod \ 26 \\ &= \begin{bmatrix}0 \\ 15 \\\end{bmatrix} mod \ 26 \\ \end{aligned}$

Finally, we have to convert these numbers back to letters, so ‘o’ becomes ‘A’ and ‘15’ becomes ‘p’ and our first two letters of the ciphertext are AP

Thus,

$ \begin{bmatrix}H & I \\ L & L \\\end{bmatrix} \begin{bmatrix}S \\ H \\\end{bmatrix} = \begin{bmatrix} 7 & 8 \\ 11 & 11 \\\end{bmatrix} \begin{bmatrix}18 \\ 7 \\\end{bmatrix} = \begin{bmatrix} 182 \\ 275 \\\end{bmatrix} = \begin{bmatrix}0 \\ 15 \\\end{bmatrix} \ mod \ 26 \ = \begin{bmatrix} A \\ P \\\end{bmatrix} $

Follow the same procedure for the next column vectors of plain text.

The final ciphertext is “A P A D J T F T W L F J”

Decryption:

$P \ = \ [C] \ [K^{-1}] \ mod \ 26$

$k^{-1} \ = \ \frac{1}{|d|} \ adj \ [k]$

Key = k = $ \begin{bmatrix} H & I \\ L & L \\\end{bmatrix} $ = $\begin{bmatrix}7 & 8 \\ 11 & 11 \\\end{bmatrix} = 11 \times 7 - 88$

= - 11 mod 26

D = 15

We want $\frac{1}{D}$ i.e. $d \times d^{-1} = 1 \ mod \ 26$

$\begin{aligned} 15 * x &= 1 \ mod \ 26 \\ d^{-1} &= 7 \\ &= adj \begin{bmatrix} a & b \\ c & d \\\end{bmatrix} = \begin{bmatrix} d & -b \\ -c & a \\\end{bmatrix} \\ &= \begin{bmatrix} 11 & -8 \\ -11 & 7 \\\end{bmatrix} = \begin{bmatrix} 11 & 18 \\ 15 & 7 \\\end{bmatrix} mod \ 26 \\ & = \ 7 \times \begin{bmatrix} 11 & 18 \\ 15 & 7 \\\end{bmatrix} = \begin{bmatrix} 77 & 126 \\ 165 & 49 \\\end{bmatrix} mod \ 26 \\ \end{aligned}$

$\Rightarrow \ k^{-1} = \begin{bmatrix} 25 & 22 \\ 1 & 23 \\\end{bmatrix}$

$\begin{aligned} \Rightarrow \ P & = \begin{bmatrix} 25 & 22 \\ 1 & 23 \\\end{bmatrix} \begin{bmatrix} A \\ P \\\end{bmatrix} \\ &= \begin{bmatrix} 25 & 22 \\ 1 & 23 \\\end{bmatrix} \begin{bmatrix} 0 \\ 15 \\\end{bmatrix} \\ & = \ \begin{bmatrix} 25 \times 0 + 22 \times 15 \\ 1 \times 0 + 23 \times 15 \\\end{bmatrix} \ \begin{bmatrix} 330 \\ 345 \\\end{bmatrix} \\ & = \ \begin{bmatrix} 18 \\ 7 \\\end{bmatrix} \ mod \ 26 \\ &= \begin{bmatrix} S \\ H \\\end{bmatrix} \\ \end{aligned}$

Follow the same procedure for the next column vectors of ciphertext.

So the final plaintext is short example