Hill cipher is a kind of a block cipher method. Actually, it was the first one appearing in the history. This makes block ciphers popular today. Even though it is a type of classical and historical cryptography method, it has a special place in my heart because of strong math background and easy adaptation. On the other hand, cryptoanalysis is still partially hard. The cipher is basically based on matrix multiplication for both encryption and decryption. Luckily, we can handle this with python and numpy easily for today. On the other hand, hill cipher could be adapted into the telegraph framework on those days. Even though new generation wouldn’t see a telegraph communication, we have been familiar with telegraph in Lucky Luke.
Choosing a Key
First, sender and receiver parties need to agree with a secret key. This key must be a square matrix.
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
key = np.array([
[3, 10, 20],
[20, 9, 17],
[9, 4, 17]
])
key_rows = key.shape[0]
key_columns = key.shape[1]
if key_rows != key_columns:
raise Exception('key must be square matrix!')
The key matrix must have an inverse matrix. This means that determinant of the matrix must not be 0.
if np.linalg.det(key) == 0:
raise Exception('matrix must have an inverse matrix')
Plaintext
Hill cipher is language dependent encryption method. That’s why, all character will be in lowercase and we’ll remove blank characters as well. Then, every letter will be replaced with its index value in the alphabet.
def letterToNumber(letter):
return string.ascii_lowercase.index(letter)
raw_message = "attack is to night"
print("raw message: ",raw_message)
message = []
for i in range(0, len(raw_message)):
current_letter = raw_message[i:i+1].lower()
if current_letter != ' ': #discard blank characters
letter_index = letterToNumber(current_letter)
message.append(letter_index)
Matrix size
Encryption will be handled by multiplying message and key. This requires that column size of the message must be equal to row size of the key. Otherwise, multiplication cannot be handled. We can append beginning letter of the alphabet to the end of the message until multiplication can be handled. Hill cipher is a block cipher method and repetition won’t be cause weakness. Still, I prefer to append beginning of the message instead of repeating characters. BTW, column number of my message and row number of my key are equal. The following code block won’t be run for this case.
if len(message) % key_rows != 0:
for i in range(0, len(message)):
message.append(message[i])
if len(message) % key_rows == 0:
break
Now, we can transform the message into a matrix.
message = np.array(message) message_length = message.shape[0] message.resize(int(message_length/key_rows), key_rows)
Now, my message is stored in a 5×3 sized matrix as illustrated below.
[[ 0 19 19] [ 0 2 10] [ 8 18 19] [14 13 8] [ 6 7 19]]
Encryption
The message is 5×3 sized matrix and the key is 3×3 sized matrix. Message’s column size is equal to key matrix’s row count. They can be multiplied. Multiplication might produce values greater than the alphabet size. That’s why, we will apply modular arithmetic. Here, 26 refers to the size of English alphabet. We can consume either matmul or dot functions.
encryption = np.matmul(message, key) encryption = np.remainder(encryption, 26)
Encrypted text will be stored in 5×3 sized matrix as illustrated below.
[[ 5 13 22] [ 0 6 22] [ 9 6 9] [10 3 13] [17 17 16]]
Remember that plaintext was attackistonight. Please focus on the 2nd and 3rd letter in plaintext. They are both letter of t. However, 2nd and 3rd characters in the ciphertext are 13 and 22 respectively. Same characters substituted with different characters. This is idea behind block ciphers.
Inverse Key
Multiplying ciphertext and inverse of key will create plaintext. Here, we need to find the inverse of key. Finding matrix inverse is a complex operation. Even though numpy has a matrix inverse function, we also need to apply modular arithmetic on this decimal matrix. On the other hand, SymPy handles modular arithmetic for matrix inverse operations easily.
from sympy import Matrix inverse_key = Matrix(key).inv_mod(26) inverse_key = np.array(inverse_key) #sympy to numpy inverse_key = inverse_key.astype(float)
We could find the inverse key.
[[11. 22. 14.] [ 7. 9. 21.] [17. 0. 3.]]
We can validate inverse key matrix. Multiplication of key and inverse key must be equal to idendity matrix.
check = np.matmul(key, inverse_key) check = np.remainder(check, module)
This is really produces the identity matrix.
[[1. 0. 0.] [0. 1. 0.] [0. 0. 1.]]
Decryption
Bob found the inverse key and he has the ciphertext. He need to multiply ciphertext and inverse key matrices.
decryption = np.matmul(encryption, inverse_key) decryption = np.remainder(decryption, module).flatten()
As seen, decrytpion stores the exact message Alice sent.
decryption: [ 0. 19. 19. 0. 2. 10. 8. 18. 19. 14. 13. 8. 6. 7. 19.]
We can restore these values into characters.
decrypted_message = "" for i in range(0, len(decryption)): letter_num = int(decryption[i]) letter = numberToLetter(decryption[i]) decrypted_message = decrypted_message + letter
This restores the following message.
decrypted message: attackistonight
Intellectual Property
Inventor Lester S. Hill registered this idea to patent office. You should have a view on his drawings. He designed an encrypted telegraph machine at the beginning of 1930’s and named message protector. Today, we call this Hill’s Cipher Machine.
Complexity
In this post, we’ve worked on 3×3 sized key and its key space is 269. Patented mechanism works on 6×6 sized keys. This increases key space to 2636. This is very large even for today computation power. Increasing the size of key matrix makes the cipher much stronger. We can say that Hill is secure against ciphertext only attacks.
However, if an attacker can capture a plaintext ciphertext pair, then he can calculate key value easily. That’s why, ciphertext is weak against known plaintext attacks. That’s why, this cipher got out of the date.
The source code of this post is pushed into the GitHub.
If you enjoy to apply Hill Cipher step by step according to a video, it would be better to watch the following video.
Support this blog if you do like!
