Hill Cipher#
The Hill cipher is a polygraphic substitution cipher based on linear algebra. It was invented by Lester S. Hill in 1929. The cipher uses an \(n \times n\) matrix to encrypt blocks of \(n\) letters at a time. The matrix must be invertible, and the determinant of the matrix must be coprime with the length of the alphabet. The matrix is multiplied by a vector of the plaintext to get the ciphertext. The inverse of the matrix is used to decrypt the ciphertext.
Hill Cipher Overview
Encrypting a Message:
Convert each letter of your message to a number (A=0, B=1, …, Z=25).
Split the numbers into small groups (vectors) that match the size of your key matrix.
Multiply each group by the key matrix and then take the result modulo 26.
Convert the resulting numbers back to letters to get your encrypted message.
Decrypting a Message:
Convert each letter of the encrypted message back to numbers.
Split the numbers into small groups (vectors) again.
Multiply each group by the inverse of your key matrix and then take the result modulo 26.
Convert these numbers back to letters to get your original message.
An example of the process:#
Algorithm 14 (Hill Cipher - Input)
Input:
Plaintext: “HELP”
Key matrix
Algorithm 15 (Hill Cipher - Encryption)
Choose an \(n \times n\) matrix \(K\) as the key for encryption. This matrix must be invertible modulo 26.
Divide the plaintext into vectors of size \(n\). For example, for a \(2 \times 2\) matrix and plaintext “HELP”:
Transform Plaintext to Numbers:
\[\begin{split} \begin{aligned} \text{H} &= 7, \\ \text{E} &= 4, \\ \text{L} &= 11, \\ \text{P} &= 15 \end{aligned} \end{split}\]Form Plaintext Vectors:
\[\begin{split} \begin{aligned} P_1 &= \begin{pmatrix} H & E \end{pmatrix} = \begin{pmatrix} 7 & 4 \end{pmatrix}, \\ P_2 &= \begin{pmatrix} L & P \end{pmatrix} = \begin{pmatrix} 11 & 15 \end{pmatrix} \end{aligned} \end{split}\]Encrypt Each Vector:
\[\begin{split} \begin{aligned} C_1 &= K \cdot P_1 \mod 26 \\ &= \begin{pmatrix} 3 & 3 \\ 2 & 5 \end{pmatrix} \cdot \begin{pmatrix} 7 \\ 4 \end{pmatrix} \mod 26 \\ &= \begin{pmatrix} 21 \\ 6 \end{pmatrix} = \text{VG} \end{aligned} \end{split}\]The plaintext “HE” corresponds to the ciphertext “VG”.
\[\begin{split} \begin{aligned} C_2 &= K \cdot P_2 \mod 26 \\ &= \begin{pmatrix} 3 & 3 \\ 2 & 5 \end{pmatrix} \cdot \begin{pmatrix} 11 \\ 15 \end{pmatrix} \mod 26 \\ &= \begin{pmatrix} 8 \\ 13 \end{pmatrix} = \text{HN} \end{aligned} \end{split}\]The plaintext “LP” corresponds to the ciphertext “HN”.
Output:
Ciphertext: “VGHN”
Algorithm 16 (Hill Cipher - Decryption)
To decrypt, use the inverse of the matrix \(K\), denoted as \(K^{-1}\).
Multiply the ciphertext vector by the inverse matrix \(K^{-1}\) modulo 26 to get the plaintext vector:
Decryption:
Transform Ciphertext to Numbers:
\[\begin{split} \begin{aligned} \text{V} &= 21, \\ \text{G} &= 6, \\ \text{H} &= 7, \\ \text{N} &= 13 \end{aligned} \end{split}\]Form Ciphertext Vectors:
\[\begin{split} \begin{aligned} C_1 &= \begin{pmatrix} V & G \end{pmatrix} = \begin{pmatrix} 21 & 6 \end{pmatrix}, \\ C_2 &= \begin{pmatrix} H & N \end{pmatrix} = \begin{pmatrix} 7 & 13 \end{pmatrix} \end{aligned} \end{split}\]Decrypt Each Vector Using Inverse Key Matrix \(K^{-1}\):
\[\begin{split} \begin{aligned} P_1 &= K^{-1} \cdot C_1 \mod 26 \\ &= \begin{pmatrix} 15 & 17 \\ 20 & 9 \end{pmatrix} \cdot \begin{pmatrix} 21 \\ 6 \end{pmatrix} \mod 26 \\ &= \begin{pmatrix} 7 \\ 4 \end{pmatrix} = \text{HE} \end{aligned} \end{split}\]The ciphertext of “VG” corresponds to the letters “HE”.
\[\begin{split} \begin{aligned} P_2 &= K^{-1} \cdot C_2 \mod 26 \\ &= \begin{pmatrix} 15 & 17 \\ 20 & 9 \end{pmatrix} \cdot \begin{pmatrix} 7 \\ 13 \end{pmatrix} \mod 26 \\ &= \begin{pmatrix} 11 \\ 15 \end{pmatrix} = \text{LP} \end{aligned} \end{split}\]The ciphertext of “HN” corresponds to the letters “LP”.
Output:
Decrypted Plaintext: “HELP” Note: The matrix \(K\) must be carefully chosen so that its determinant is coprime with 26 to ensure it has an inverse modulo 26.
Hill Cipher Algorithm#
The Hill cipher functions are implemented in the following order:
hill_cipher_encrypt: Encrypts the plaintext using the Hill cipher. It takes thekeymatrix and theplaintextas input and returns the ciphertext. It will also pad the plaintext if the length of the plaintext is not a multiple of the key matrix size.hill_cipher_decrypt: Decrypts the ciphertext using the Hill cipher. It takes thekeymatrix and theciphertextas input and returns the plaintext.hill_cipher: Is used for both encryption and decryption. It takes thekey,text, andmodeas input and returns the encrypted or decrypted text based on the mode. Then outputs the results.
Show code cell source
import sympy as sp
import random
import faker
def hill_cipher_encrypt(message, key_matrix):
n = key_matrix.shape[0]
message_numbers = [ord(char) - ord('A') for char in message.upper().replace(" ", "")]
while len(message_numbers) % n != 0:
message_numbers.append(ord('X') - ord('A'))
message_matrix = sp.Matrix(n, len(message_numbers) // n, message_numbers)
encrypted_matrix = key_matrix * message_matrix
encrypted_matrix = encrypted_matrix.applyfunc(lambda x: x % 26)
encrypted_message = ''.join(chr(num + ord('A')) for num in encrypted_matrix)
return encrypted_message, len(message_numbers)
def hill_cipher_decrypt(encrypted_message, key_matrix, original_message_length):
n = key_matrix.shape[0]
key_matrix_inv = key_matrix.inv_mod(26)
encrypted_numbers = [ord(char) - ord('A') for char in encrypted_message]
encrypted_matrix = sp.Matrix(n, len(encrypted_numbers) // n, encrypted_numbers)
decrypted_matrix = key_matrix_inv * encrypted_matrix
decrypted_matrix = decrypted_matrix.applyfunc(lambda x: x % 26)
decrypted_message = ''.join(chr(num + ord('A')) for num in decrypted_matrix)
return decrypted_message[:original_message_length]
def hill_cipher(key_matrix, message):
print(f"The key matrix is: {key_matrix}")
print(f"The message is: {message}")
encrypted_message, original_length = hill_cipher_encrypt(message, key_matrix)
print(f"The encrypted message is: {encrypted_message}")
decrypted_message = hill_cipher_decrypt(encrypted_message, key_matrix, original_length)
print(f"The decrypted message is: {decrypted_message}")
Examples of the Hill Cipher#
The following is an example of the Hill cipher in action:#
Here the key matrix is a 3 x 3 matrix and the plaintext is HELLO. You’ll notice the plaintext is padded with an X to make the length of the plaintext a multiple of 3.
key_matrix = sp.Matrix([[6, 24, 1], [13, 16, 10], [20, 17, 15]])
message = "HELLO"
hill_cipher(key_matrix, message)
The key matrix is: Matrix([[6, 24, 1], [13, 16, 10], [20, 17, 15]])
The message is: HELLO
The encrypted message is: IZRQRO
The decrypted message is: HELLOX
Explanation:
Given the key matrix:
and the message “HELLO”:
Transformation of Letters to Numbers:
The message “HELLO” is padded to “HELLOX” to fit the matrix size.
Convert letters to numbers:
\[ \text{H} = 7, \ \text{E} = 4, \ \text{L} = 11, \ \text{L} = 11, \ \text{O} = 14, \ \text{X} = 23 \]Forming the Plaintext Vector:
Group the numbers into vectors of size 3 (matching the matrix size):
\[\begin{split} P = \begin{pmatrix} 7 & 4 & 11 \\ 11 & 14 & 23 \end{pmatrix} \end{split}\]Encryption Process:
Multiply each vector by the key matrix \(K\) modulo 26:
\[C = K \cdot P \mod 26\]For the first vector \(\begin{pmatrix} 7 \\ 4 \\ 11 \end{pmatrix}\):
\[\begin{split} \begin{pmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{pmatrix} \cdot \begin{pmatrix} 7 \\ 4 \\ 11 \end{pmatrix} \mod 26 = \begin{pmatrix} 15 \\ 25 \\ 17 \end{pmatrix} \end{split}\]Repeat for the second vector \(\begin{pmatrix} 11 \\ 14 \\ 23 \end{pmatrix}\):
\[\begin{split} \begin{pmatrix} 6 & 24 & 1 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \end{pmatrix} \cdot \begin{pmatrix} 11 \\ 14 \\ 23 \end{pmatrix} \mod 26 = \begin{pmatrix} 17 \\ 16 \\ 14 \end{pmatrix} \end{split}\]Combine results to get the ciphertext:
\[ \text{Ciphertext: } \text{IZRQRO} \]Decryption Process:
Use the inverse of the key matrix \(K^{-1}\) to decrypt. Multiply each ciphertext vector by \(K^{-1}\) modulo 26 to retrieve the plaintext vectors.
So, the message “HELLO” is encrypted as “IZRQRO” using the Hill cipher with the given key matrix.
Here is the same matrix, this time with the plaintext Why hello this is my message to you, you’ll notice the plain text returned is WHYHELLOTHISISMYMESSAGETOYOUX. The spaces are removed and the text is converted to uppercase, as well as the X added to the end to make the length a multiple of 3.
key_matrix = sp.Matrix([[6, 24, 1], [13, 16, 10], [20, 17, 15]])
message = "Why hello this is my message to you"
hill_cipher(key_matrix, message)
The key matrix is: Matrix([[6, 24, 1], [13, 16, 10], [20, 17, 15]])
The message is: Why hello this is my message to you
The encrypted message is: MMCZOQESXDYXMXUNHELLEQADAAKYRL
The decrypted message is: WHYHELLOTHISISMYMESSAGETOYOUXX
Generating Invertible Key Matrix#
The following function generates an invertible key matrix for the Hill cipher. The matrix is generated by randomly selecting values between 0 and 25. The function checks if the matrix is invertible by calculating the determinant and checking if it is coprime with the length of the alphabet.
We will also user the faker library to generate a random message for encrypting.
def generate_invertible_matrix_mod_26(size):
while True:
# Generate a random matrix with elements in the range [0, 25]
matrix_elements = [random.randint(0, 25) for _ in range(size * size)]
matrix = sp.Matrix(size, size, matrix_elements)
# Check if the matrix is invertible modulo 26
if is_invertible_mod(matrix, 26):
return matrix
def is_invertible_mod(matrix, mod):
try:
matrix.inv_mod(mod)
return True
except ValueError:
return False
# Example usage
size = 3 # Size of the matrix (e.g., 3x3)
invertible_matrix = generate_invertible_matrix_mod_26(size)
print(f"Generated Invertible Matrix (mod 26):\n{invertible_matrix}")
Generated Invertible Matrix (mod 26):
Matrix([[13, 1, 15], [8, 17, 6], [9, 4, 24]])
def random_message(n):
fake = faker.Faker()
return fake.text(max_nb_chars=n).upper()
Hill Cipher with Random Key Matrix#
Now, we will use the Hill cipher with a randomly generated key matrix. We will encrypt and decrypt the plaintext thats randomly generated thanks to the faker library.
%%time
size = 3
key_matrix = generate_invertible_matrix_mod_26(size)
message = random_message(20)
hill_cipher(key_matrix, message)
The key matrix is: Matrix([[17, 13, 6], [2, 14, 15], [7, 8, 19]])
The message is: GUESS ARGUE DEAL.
The encrypted message is: QNQIKFAONPVOYBF
The decrypted message is: GUESSARGUEDEALH
CPU times: user 14.2 ms, sys: 15.1 ms, total: 29.3 ms
Wall time: 28.2 ms
%%time
size = 6
key_matrix = generate_invertible_matrix_mod_26(size)
message = random_message(90)
hill_cipher(key_matrix, message)
The key matrix is: Matrix([[5, 22, 9, 9, 8, 15], [22, 20, 12, 7, 11, 11], [15, 0, 17, 13, 2, 4], [12, 23, 23, 2, 5, 21], [23, 22, 6, 19, 1, 23], [21, 17, 16, 7, 8, 3]])
The message is: OK COLD MARKET STEP THOUSAND. SURFACE IF IF SUPPORT MARKET BUT. OF SHORT SEVERAL PURPOSE.
The encrypted message is: BSXLWUFRHNQYZSTPRALYNMOXNBFRQBVTDNBYTXOMWAJBDFIYLDOVIRNTFGWJBGDMNGNJSBCDMTVRNO
The decrypted message is: OKCOLDMARKETSTEPTHOUSANDHSURFACEIFIFSUPPORTMARKETBUTHOFSHORTSEVERALPURPOSEHXXX
CPU times: user 130 ms, sys: 11.7 ms, total: 141 ms
Wall time: 140 ms
%%time
size = 12
key_matrix = generate_invertible_matrix_mod_26(size)
message = random_message(90)
hill_cipher(key_matrix, message)
The key matrix is: Matrix([[1, 13, 15, 23, 7, 11, 16, 10, 24, 13, 8, 22], [9, 23, 10, 13, 5, 5, 21, 16, 6, 10, 13, 20], [5, 18, 8, 17, 17, 19, 20, 6, 20, 3, 22, 19], [9, 15, 5, 1, 12, 11, 21, 19, 24, 10, 9, 22], [17, 23, 21, 5, 10, 2, 8, 22, 2, 20, 20, 10], [22, 13, 23, 14, 19, 19, 3, 14, 11, 7, 13, 6], [22, 0, 6, 9, 9, 17, 5, 25, 18, 9, 16, 5], [22, 8, 24, 13, 10, 20, 21, 22, 7, 3, 16, 16], [15, 3, 17, 18, 1, 22, 0, 23, 24, 22, 24, 5], [0, 25, 4, 10, 25, 14, 15, 12, 25, 0, 2, 16], [0, 0, 24, 5, 17, 16, 3, 7, 24, 16, 11, 24], [1, 21, 16, 19, 2, 0, 11, 17, 20, 21, 24, 17]])
The message is: LOOK SISTER MIND OPERATION TRIP BALL SING. TRUTH BOTH READ ITSELF EFFORT TO HAPPY.
The encrypted message is: BRKRBFTCJBELNHVISTTWZWCPEJUMBCPYLDXJXLSOVAJUQOQESRVBZZPYGVHLPWKWIEEMPFJM
The decrypted message is: LOOKSISTERMINDOPERATIONTRIPBALLSINGHTRUTHBOTHREADITSELFEFFORTTOHAPPYHXXX
CPU times: user 1.7 s, sys: 9.16 ms, total: 1.71 s
Wall time: 1.71 s
Comparing matrix size and Execution Time#
In the following two examples, both messages are 200 charcters long, however the first one uses a \(5 x 5\) matrix which takes \(75ms\) to encrypt and decrypt, while the second one uses a \(15 x 15\) matrix which takes \(16.4s\) to encrypt and decrypt. This shows the time difference between the matrix sizes.
%%time
size = 5
key_matrix = generate_invertible_matrix_mod_26(size)
message = random_message(200)
hill_cipher(key_matrix, message)
The key matrix is: Matrix([[0, 21, 11, 18, 18], [0, 20, 2, 24, 1], [22, 1, 4, 3, 15], [6, 12, 9, 18, 6], [15, 21, 1, 23, 9]])
The message is: NATURAL FISH ITS MUST DESIGN. APPROACH COURT SAVE TALK RESOURCE MISSION FORGET PAPER. DREAM DOCTOR ELECTION FIGURE.
NONE COMMERCIAL STUDY. CONDITION SHAKE EYE COLLEGE.
The encrypted message is: YEHIYRGRUVIWWANEZPSORGBRIRYLGATWZSGTBWLAIDQTSCKEUGGMHZSWMZOCYQHVLYJEAUAMXIMXQEYICPNKJMYGSXXEBKGXVGVOZNTTYEGXEYLKJOZKVKMFEGIDEDJFFDABDATGVOELSTCYT
The decrypted message is: NATURALFISHITSMUSTDESIGNHAPPROACHCOURTSAVETALKRESOURCEMISSIONFORGETPAPERHDREAMDOCTORELECTIONFIGUREHXNONECOMMERCIALSTUDYHCONDITIONSHAKEEYECOLLEGEH
CPU times: user 69.2 ms, sys: 7.96 ms, total: 77.2 ms
Wall time: 75.4 ms
%%time
size = 19
key_matrix = generate_invertible_matrix_mod_26(size)
message = random_message(200)
hill_cipher(key_matrix, message)
The key matrix is: Matrix([[9, 13, 17, 12, 4, 25, 9, 17, 22, 1, 8, 5, 23, 2, 14, 15, 2, 8, 13], [23, 1, 24, 15, 1, 23, 7, 2, 20, 20, 25, 8, 3, 4, 16, 13, 13, 3, 1], [5, 16, 0, 21, 5, 21, 5, 21, 16, 5, 2, 20, 9, 20, 8, 17, 17, 12, 9], [15, 4, 24, 16, 1, 5, 22, 15, 12, 0, 14, 12, 16, 13, 25, 23, 21, 19, 22], [2, 25, 3, 17, 20, 16, 15, 4, 22, 3, 7, 24, 21, 5, 5, 20, 5, 24, 3], [25, 0, 12, 22, 3, 16, 18, 19, 9, 6, 17, 9, 1, 15, 19, 22, 22, 10, 24], [6, 22, 19, 17, 0, 21, 8, 21, 16, 21, 10, 1, 0, 8, 2, 17, 24, 1, 0], [5, 5, 9, 11, 22, 21, 12, 14, 23, 12, 0, 10, 17, 4, 0, 7, 25, 2, 23], [8, 1, 14, 3, 22, 22, 16, 21, 7, 1, 19, 6, 1, 21, 16, 3, 13, 20, 12], [17, 17, 24, 2, 7, 5, 22, 12, 21, 0, 23, 8, 8, 14, 24, 12, 2, 12, 13], [15, 2, 21, 15, 3, 19, 11, 14, 8, 24, 1, 7, 18, 2, 18, 14, 8, 4, 17], [6, 19, 8, 0, 12, 1, 19, 19, 6, 16, 5, 4, 22, 14, 24, 7, 11, 25, 18], [0, 25, 18, 18, 1, 17, 19, 4, 2, 21, 8, 21, 0, 5, 23, 2, 4, 5, 21], [19, 16, 8, 0, 13, 0, 13, 23, 8, 12, 14, 23, 9, 21, 15, 19, 3, 0, 15], [16, 6, 19, 25, 4, 16, 3, 12, 7, 4, 9, 22, 19, 10, 5, 1, 14, 14, 11], [22, 13, 25, 2, 10, 16, 10, 20, 11, 7, 10, 20, 10, 12, 4, 16, 2, 14, 20], [19, 14, 18, 15, 21, 23, 14, 1, 16, 5, 8, 7, 0, 12, 2, 14, 11, 12, 0], [23, 15, 7, 6, 2, 22, 24, 11, 9, 19, 11, 24, 2, 4, 7, 20, 6, 6, 14], [8, 20, 20, 2, 25, 14, 11, 13, 21, 8, 21, 24, 10, 8, 25, 4, 11, 14, 12]])
The message is: THE AT ACTUALLY LEVEL. SHAKE FEW VOTE BIT MEMORY.
PARTICULARLY SIX ALWAYS INCLUDE MORE REPORT SEASON. PRODUCE HOTEL ADULT PLAN MILITARY HOLD POOR.
The encrypted message is: ICYEZWDPPYXTDSARQUKHXKNQYUGWDCAIRAAAECKABXTWPZACGCIZKGNFTOWMWHBAJTMUJUHXOWIXLKRHOGBFPRGRIFLNJCALTEXNRRLPYQGFHADQVKRNMHJRPCCLQMTNQHZYR
The decrypted message is: THEATACTUALLYLEVELHSHAKEFEWVOTEBITMEMORYHXPARTICULARLYSIXALWAYSINCLUDEMOREREPORTSEASONHPRODUCEHOTELADULTPLANMILITARYHOLDPOORHXXXXXXXX
CPU times: user 16.4 s, sys: 17.9 ms, total: 16.4 s
Wall time: 16.4 s