Hill Cipher

Another interesting multi letter cipher is the Hill cipher, developed by the mathematician Lester Hill in 1929.

THE HILL ALGORITHM 

This encryption algorithm takes $n$ successive plaintext letters and substitutes for them $n$ ciphertext letters. The substitution is determined by linear equations in which each character is assigned a numerical value $(a=0,b=1,\ldots,z=25)$. 

$C=KP$, where  $K$ is the key matrix and $P$ is the plaintext vector

$P=K^{-1}C$, where $K^{-1}$ is the inverse of key matrix $K$ in $\pmod{26}$

How the Hill Cipher Works

1. Key Matrix:

   • Choose a key matrix K of size $n \times n$ (e.g., $2 \times 2$, $3 \times 3$).
   • The key matrix should be invertible modulo 26 (the number of letters in the English alphabet).

2. Plaintext Preparation:

   • Convert the plaintext into vectors of size $n$.
   • If the plaintext length is not a multiple of $n$, pad it with extra letters (e.g., 'X').

3. Encryption:

   • Multiply the key matrix $K$ by each plaintext vector, and take the result modulo 26 to get the ciphertext vector.
   • Convert the resulting numbers back into letters.

4. Decryption:

• Calculate the inverse of the key matrix $K^{-1}$ modulo 26.
• Multiply the inverse matrix by each ciphertext vector, and take the result modulo 26 to get the plaintext vector.
• Convert the resulting numbers back into letters.

Example

Let's encrypt the plaintext "HELP" using a $2 \times 2$ key matrix.

Step 1: Key Matrix

Choose the key matrix: $K=\left[\begin{array}{cc}3& 3\\ 2& 5\end{array}\right]$

Step 2: Plaintext Preparation

Convert "HELP" into numbers: H=7, E=4, L=11, P=15

Since our key matrix is $2 \times 2$, divide the plaintext into pairs:

$$

• (H, E) -> (7, 4)
• (L, P) -> (11, 15)

Step 3: Encryption

Encrypt each pair using matrix multiplication and take modulo 26.

For (H, E): $\begin{bmatrix} 3 & 3 \\ 2 & 5 \end{bmatrix} \begin{bmatrix} 7 \\ 4 \end{bmatrix} = \begin{bmatrix} 3 \cdot 7 + 3 \cdot 4 \\ 2 \cdot 7 + 5 \cdot 4 \end{bmatrix} = \begin{bmatrix} 21 + 12 \\ 14 + 20 \end{bmatrix} = \begin{bmatrix} 33 \\ 34 \end{bmatrix}$

Take modulo 26: $\begin{bmatrix} 33 \\ 34 \end{bmatrix} \equiv \begin{bmatrix} 7 \\ 8 \end{bmatrix} \pmod{26}$

Convert back to letters: (7, 8) -> HI

For (L, P): $\begin{bmatrix} 3 & 3 \\ 2 & 5 \end{bmatrix} \begin{bmatrix} 11 \\ 15 \end{bmatrix} = \begin{bmatrix} 3 \cdot 11 + 3 \cdot 15 \\ 2 \cdot 11 + 5 \cdot 15 \end{bmatrix} = \begin{bmatrix} 33 + 45 \\ 22 + 75 \end{bmatrix} = \begin{bmatrix} 78 \\ 97 \end{bmatrix}$

Take modulo 26: $\begin{bmatrix} 78 \\ 97 \end{bmatrix} \equiv \begin{bmatrix} 0 \\ 19 \end{bmatrix} \pmod{26}$

Convert back to letters: (0, 19) -> AT

So, the ciphertext for "HELP" is "HIAT"

Step 4: Decryption

To decrypt, we need the inverse of the key matrix modulo 26.

Find the determinant of $K$: $\text{det}(K) = 3 \cdot 5 - 3 \cdot 2 = 15 - 6 = 9$

Find the modular inverse of the determinant modulo 26, which is 3 (since $9 \times 3 \equiv 1 \pmod{26}$

Compute the inverse matrix: $K^{-1} = \frac{1}{9} \begin{bmatrix} 5 & -3 \\ -2 & 3 \end{bmatrix} \equiv 3 \begin{bmatrix} 5 & -3 \\ -2 & 3 \end{bmatrix} \equiv \begin{bmatrix} 15 & -9 \\ -6 & 9 \end{bmatrix} \equiv \begin{bmatrix} 15 & 17 \\ 20 & 9 \end{bmatrix} \pmod{26}$

Decrypt the ciphertext "HIAT" using  $K^{-1}$

• Convert "HIAT" to numbers: H=7, I=8, A=0, T=19

For (H, I): $\left[\begin{array}{cc}15& 17\\ 20& 9\end{array}\right]\left[\begin{array}{c}7\\ 8\end{array}\right]=\left[\begin{array}{c}15\cdot 7+17\cdot 8\\ 20\cdot 7+9\cdot 8\end{array}\right]=\left[\begin{array}{c}105+136\\ 140+72\end{array}\right]=\left[\begin{array}{c}241\\ 212\end{array}\right]$

Take modulo 26: $\left[\begin{array}{c}241\\ 212\end{array}\right]\equiv \left[\begin{array}{c}7\\ 4\end{array}\right](\mathrm{m}\mathrm{o}\mathrm{d}26)$

Convert back to letters: (7, 4) -> HE

For (A, T): $\begin{bmatrix} 15 & 17 \\ 20 & 9 \end{bmatrix} \begin{bmatrix} 0 \\ 19 \end{bmatrix} = \begin{bmatrix} 15 \cdot 0 + 17 \cdot 19 \\ 20 \cdot 0 + 9 \cdot 19 \end{bmatrix} = \begin{bmatrix} 0 + 323 \\ 0 + 171 \end{bmatrix} = \begin{bmatrix} 323 \\ 171 \end{bmatrix}$

Take modulo 26: $\left[\begin{array}{c}323\\ 171\end{array}\right]\equiv \left[\begin{array}{c}11\\ 15\end{array}\right](\mathrm{m}\mathrm{o}\mathrm{d}26)$

Convert back to letters: (11, 15) -> LP

The decrypted plaintext is "HELP".

Python Code Hill Cipher

import numpy as np

def mod_inverse(a, m):

    # Find modular inverse using extended Euclidean algorithm

    m0, x0, x1 = m, 0, 1

    if m == 1:

        return 0

    while a > 1:

        # q is quotient

        q = a // m

        m, a = a % m, m

        x0, x1 = x1 - q * x0, x0

    if x1 < 0:

        x1 += m0

    return x1

def matrix_mod_inverse(matrix, modulus):

    det = int(np.round(np.linalg.det(matrix)))

    det_inv = mod_inverse(det % modulus, modulus)

    matrix_mod_inv = det_inv * np.round(det * np.linalg.inv(matrix)).astype(int) % modulus

    return matrix_mod_inv

def encrypt(plaintext, key):

    key_matrix = np.array(key)

    plaintext_numbers = [ord(char) - ord('A') for char in plaintext.upper() if char.isalpha()]

    # Pad with 'X' if necessary

    if len(plaintext_numbers) % 2 != 0:

        plaintext_numbers.append(ord('X') - ord('A'))

    ciphertext = ''

    for i in range(0, len(plaintext_numbers), 2):

        vector = np.array(plaintext_numbers[i:i+2])

        encrypted_vector = np.dot(key_matrix, vector) % 26

        ciphertext += ''.join(chr(num + ord('A')) for num in encrypted_vector)

    

    return ciphertext

def decrypt(ciphertext, key):

    key_matrix = np.array(key)

    key_matrix_inv = matrix_mod_inverse(key_matrix, 26)

    ciphertext_numbers = [ord(char) - ord('A') for char in ciphertext.upper() if char.isalpha()]

    plaintext = ''

    for i in range(0, len(ciphertext_numbers), 2):

        vector = np.array(ciphertext_numbers[i:i+2])

        decrypted_vector = np.dot(key_matrix_inv, vector) % 26

        plaintext += ''.join(chr(int(num) + ord('A')) for num in decrypted_vector)

    return plaintext

# Example usage

key = [[3, 3], [2, 5]]

plaintext = "HELP"

ciphertext = encrypt(plaintext, key)

decrypted_text = decrypt(ciphertext, key)

print(f"Plaintext: {plaintext}")

print(f"Ciphertext: {ciphertext}")

print(f"Decrypted: {decrypted_text}")

Output:

Plaintext: HELP

Ciphertext: HIAT

Decrypted: HELP

Encrypt the text "cryptography" using HillCipher with key 

$$K=\begin{bmatrix}5 & 7 \\ 9 & 4 \\ \end{bmatrix}$$ (University Question)

Plaintext: CRYPTOGRAPHY

Ciphertext: ZIRQLTTSBIVD