Hill Cipher

Yaser Rahmati | یاسر رحمتی

The Hill Cipher is a polygraphic substitution cipher that uses linear algebra, particularly matrix multiplication, to encrypt and decrypt messages. It was invented by Lester S. Hill in 1929. Let's go through the steps of the Hill Cipher with detailed explanations and examples.

Step 1: Choose the Key Matrix

The key for the Hill Cipher is a square matrix (usually 2 × 2 or 3 × 3) with integer entries. The size of the matrix determines how many letters of the plaintext are encrypted at a time.

Example: Let's use a 2×2 key matrix:

$$k=\begin{bmatrix} 3 & 3\\ 2 & 5 \end{bmatrix}$$

Step 2: Convert the Plaintext into Vectors

Convert the plaintext into numerical vectors. Each letter is mapped to a number according to its position in the alphabet (A=0, B=1, C=2, ..., Z=25).

Example: Let's encrypt the plaintext "HI". The numerical equivalent of "HI" is:

• H = 7

• I = 8

So, the plaintext vector is:

$$P=\begin{bmatrix} 7\\ 8 \end{bmatrix}$$

Step 3: Multiply the Key Matrix by the Plaintext Vector

Multiply the key matrix by the plaintext vector to get the ciphertext vector.

Example: Using the key matrix K and the plaintext vector P:

$$C=k*P=\begin{bmatrix} 3 & 3\\ 2 & 5 \end{bmatrix} \begin{bmatrix} 7 \\ 8 \end{bmatrix}= \begin{bmatrix} 45 \\ 54 \end{bmatrix}$$

Step 4: Apply Modulo 26

Since the alphabet only has 26 letters, reduce the numbers in the ciphertext vector modulo 26.

Example:

$$C= \begin{bmatrix} 45 \; mod \; 26 \\ 54 \; mod \; 26 \end{bmatrix}= \begin{bmatrix} 19\\ 2 \end{bmatrix}$$

Step 5: Convert the Ciphertext Vector Back to Letters

Convert the resulting numbers back into letters.

Example:

• 19 = T

• 2 = C

So, the ciphertext for "HI" using this key matrix is "TC".

Step 6: Decrypting the Ciphertext

To decrypt the ciphertext, you need the inverse of the key matrix. Multiply the inverse matrix by the ciphertext vector and apply modulo 26 to get the original plaintext vector.

Example:

• Find the Inverse of the Key Matrix:

The inverse of a 2 × 2 is given by:

$$K^{-1}=\frac{1}{ad-bc} \begin{bmatrix} d & -b\\ -c & a \end{bmatrix}$$

For our matrix:

$$K^{-1}=\frac{1}{3\times 5-2\times 3} \begin{bmatrix} 5 & -3\\ -2 & 3 \end{bmatrix}=\frac{1}{9} \begin{bmatrix} 5 & -3\\ -2 & 3 \end{bmatrix}$$

Since we work in mod 26, we need the modular inverse of 9 modulo 26, which is 3.

$$K^{-1}=3\times \begin{bmatrix} 5 & -3\\ -2 & 3 \end{bmatrix}= \begin{bmatrix} 15 & -9\\ -6 & 6 \end{bmatrix}\;\;mode\;\;26$$

• Multiply the Inverse Matrix by the Ciphertext Vector:

$$P=K^{-1}\times C= \begin{bmatrix} 15 & -9\\ -6 & 6 \end{bmatrix}\times \begin{bmatrix} 19\\ 2 \end{bmatrix}\;\;mode\;\;26= \begin{bmatrix} 7\\ 8 \end{bmatrix}$$

• Convert the Plaintext Vector Back to Letters:

The resulting plaintext is "HI".

Keywords

Hill Cipher, encryption, decryption, matrix, key matrix, inverse matrix, modular arithmetic, mod 26, plaintext, ciphertext, polygraphic substitution, linear algebra, Lester S. Hill, cryptography, cryptanalysis, 2x2 matrix, 3x3 matrix, determinant, matrix multiplication, vector, alphabet mapping, substitution cipher, frequency analysis, security, block cipher, symmetric encryption, mathematical cipher, matrix inverse, Hill system, matrix operations, encryption algorithm, matrix determinant, mod inverse, affine transformation, hill cipher example, hill cipher key, cipher text, hill cipher decryption, encryption process, plaintext vector, hill cipher matrix, decryption key, modular inverse, key generation, cipher matrix, matrix cipher, encryption matrix, inverse key matrix, polyalphabetic cipher , Yaser Rahmati , یاسر رحمتی

External Links

🌐 Personal Website 📄 Resume 🎥 Video Archive 💼 Finance Blog 🔐 Network & Security Notebook 🎬 Aparat Channel