Hill Cipher

Nerd Cafe

The Hill Cipher is a polygraphic substitution cipher that uses linear algebra to encrypt and decrypt messages. It operates on blocks of text (usually in groups of 2 or 3 characters), treating each block as a vector of numbers, and applies matrix multiplication to perform the encryption.

Here’s a step-by-step guide to understanding and using the Hill Cipher with a practical example.

Step 1: Understand the Hill Cipher Matrix

The key in the Hill cipher is a square matrix (let's call it key matrix), usually of size 2×2 or 3×3. The matrix is used for both encryption and decryption, so it needs to be invertible (its determinant should not be 0).

• For a 2×2 matrix: The matrix will look like this:

$$\begin{bmatrix} a & b \\ c & d \end{bmatrix}$$

• For a 3×3 matrix: The matrix will look like this:

$$\begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \end{bmatrix}$$

Step 2: Choose a Key Matrix

For encryption, we need to choose a key matrix. Let's choose a 2×2 key matrix for simplicity.

Example key matrix 𝐾:

$$\begin{bmatrix} 3 & 2 \\ 1 & 1 \end{bmatrix}$$

Step 3: Assign Numbers to the Letters

The alphabet is mapped to numbers:

A = 0, B = 1, C = 2, ..., Z = 25

Example: "HI" (which we want to encrypt):

H = 7
I = 8

So the plaintext "HI" is represented as the vector:

$$Plaintext\;Vector=\begin{bmatrix} 7 \\ 8 \end{bmatrix}$$

Step 4: Perform Matrix Multiplication

Now, the encryption process involves multiplying the key matrix 𝐾 by the plaintext vector 𝑃. The formula for encryption is:

$$C=K.P=\begin{bmatrix} 3 & 2 \\ 1 & 1 \end{bmatrix} \times \begin{bmatrix} 7 \\ 8 \end{bmatrix}=\begin{bmatrix} 37 \\ 15 \end{bmatrix}$$

Step 5: Take Modulo 26

To make sure the result fits into the range of 0 to 25 (the alphabet), we take the modulo 26 of each element.

• 37 mod 26 = 11

• 15 mod 26 = 15

Thus, the encrypted vector is:

$$\begin{bmatrix} 11 \\ 15 \end{bmatrix}$$

Step 6: Convert the Encrypted Numbers Back to Letters

Using the same alphabet-to-number mapping, we convert the numbers back to letters:

• 11 = L

• 15 = P

So the ciphertext corresponding to "HI" is "LP".

Step 7: Decryption (Optional)

The formula for the inverse of a 2x2 matrix is given by:

$$K^{-1}=\frac{1}{det(K)}\begin{bmatrix} d & -b \\ -c & a \end{bmatrix}\;\;mod\;\;26$$

We first need to compute the determinant.

$$det(K)=(3\times 1)-(2\times 1)=1$$

Since the determinant is 1, the inverse exists and we can proceed. Next, we apply the formula for the inverse:

$$K^{-1}=\frac{1}{1}\begin{bmatrix} 1 & -2 \\ -1 & 3 \end{bmatrix}\;\;mod\;\;26$$

Now, we simplify the matrix modulo 26:

$$K^{-1}=\begin{bmatrix} 1 & 24 \\ 25 & 3 \end{bmatrix}\;\;mod\;\;26$$

So the inverse key matrix is:

$$K^{-1}=\begin{bmatrix} 1 & 24 \\ 25 & 3 \end{bmatrix}$$

The ciphertext "LP" corresponds to the following numerical values:

• L → 11

• P → 15

So, the ciphertext vector 𝐶 is:

$$C=\begin{bmatrix} 11 \\ 15 \end{bmatrix}$$

Now, the decryption process involves multiplying the inverse key matrix 𝐾⁻¹ by the ciphertext vector 𝐶. The formula for decryption is:

$$P=K^{-1}.C\;\;mod\;\;26$$

Let's perform the matrix multiplication:

$$P=\begin{bmatrix} 1 & 24 \\ 25 & 3 \end{bmatrix}\times \begin{bmatrix} 11 \\ 15 \end{bmatrix}=\begin{bmatrix} 371 \\ 320 \end{bmatrix}$$

and so we have:

$$\begin{bmatrix} 371 \\ 320 \end{bmatrix}\;\;mod\;\;26=\begin{bmatrix} 7 \\ 8 \end{bmatrix}$$

So, the plaintext vector 𝑃 is:

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

Finally, we convert the numbers back to letters:

• 7 → H

• 8 → I

Step 8: Python Code for Hill Cipher:

Sure! Below is a Python code implementation for the Hill Cipher encryption and decryption.

import numpy as np

# Function to create a matrix of the given size
def mod_inv(a, m):
    for i in range(1, m):
        if (a * i) % m == 1:
            return i
    return None

# Function to calculate the matrix determinant modulo 26
def det_mod_26(matrix):
    return int(np.round(np.linalg.det(matrix))) % 26

# Function to calculate the inverse matrix modulo 26
def inverse_matrix(matrix, mod=26):
    det = det_mod_26(matrix)
    det_inv = mod_inv(det, mod)
    
    if det_inv is None:
        raise Exception("Matrix is not invertible")
    
    matrix_adj = np.round(np.linalg.inv(matrix) * det).astype(int) % mod
    return (matrix_adj * det_inv) % mod

# Function to convert plaintext to numbers
def text_to_numbers(text):
    return [ord(char) - ord('A') for char in text.upper()]

# Function to convert numbers back to text
def numbers_to_text(numbers):
    return ''.join([chr(num + ord('A')) for num in numbers])

# Hill Cipher Encryption Function
def hill_encrypt(plaintext, key_matrix):
    text_numbers = text_to_numbers(plaintext)
    
    # Ensure that the length of the text is a multiple of the matrix size
    while len(text_numbers) % len(key_matrix) != 0:
        text_numbers.append(0)  # Padding with 'A' (0)
    
    # Split the plaintext into blocks and apply matrix multiplication
    ciphertext_numbers = []
    for i in range(0, len(text_numbers), len(key_matrix)):
        block = np.array(text_numbers[i:i + len(key_matrix)])
        encrypted_block = np.dot(key_matrix, block) % 26
        ciphertext_numbers.extend(encrypted_block)
    
    return numbers_to_text(ciphertext_numbers)

# Hill Cipher Decryption Function
def hill_decrypt(ciphertext, key_matrix):
    text_numbers = text_to_numbers(ciphertext)
    key_matrix_inv = inverse_matrix(key_matrix)

    decrypted_numbers = []
    for i in range(0, len(text_numbers), len(key_matrix)):
        block = np.array(text_numbers[i:i + len(key_matrix)])
        decrypted_block = np.dot(key_matrix_inv, block) % 26
        decrypted_numbers.extend(decrypted_block)

    return numbers_to_text(decrypted_numbers)

# Example usage
if __name__ == "__main__":
    key_matrix = np.array([[3, 2], [1, 1]])  # Key matrix (2x2)
    plaintext = "HI"  # Plaintext to encrypt

    # Encrypting the message
    encrypted_text = hill_encrypt(plaintext, key_matrix)
    print(f"Encrypted Text: {encrypted_text}")

    # Decrypting the message
    decrypted_text = hill_decrypt(encrypted_text, key_matrix)
    print(f"Decrypted Text: {decrypted_text}")

Output

Encrypted Text: LP
Decrypted Text: HI