How to implement the Hill Cipher in Python?

The Hill cipher is a multi-letter cipher. It is based on Linear Algebra operations, specifically matrix operations. It was created in 1929 by the mathematician Lester Hill.

Some concepts you might want to revisit are matrix multiplication and inversion.

The Hill cipher

To encrypt a text with the Hill cipher, we have to encrypt three letters at a time. Then, we can combine all the results.

In other words, if you want to encrypt a message that has 21 characters, you encrypt the first three letters, then the second three, and so on. You concatenate the result of each step and that is the cipher text.

In this algorithm, we represent each letter from A to Z with a number from 0 to 25.

We can express the Hill algorithm with a simple formula: C = PK mod 26.

P is a vector that represents three letters from the plaintext. If the three letters are “ABC”, then the vector P=(0,1,2).

K is a squared matrix that represents the key. You separate the key into three-letter blocks, and each block will be a row in the matrix K. Each letter is substituted by a number in the same way as the plaintext.

As an example, if you choose the key “RRFVSVCCT”, RRF represents the first row of K (17, 17, 5). ‘R’ is in position 17 from 0 to 25.

To decrypt we use the formula P = C K^-1 mod 26.

C is the ciphertext. K^-1 is the inverse of the matrix K.

Hill Cipher Python implementation

I’ll explain the code in parts. As the say goes: “How do you eat an elephant? One bite at a time.”

First, we import the NumPy library. We will use it for matrix operations, such as determinants and multiplications.

import numpy

Then, let’s implement a function that creates a matrix from the key. We will follow the procedure explained in the previous section.

def create_matrix_from(key):
    m=[[0] * 3 for i in range(3)]
    for i in range(3):
        for j in range(3):
            m[i][j] = ord(key[3*i+j]) % 65
    return m

Now, we can implement a function that receives the vector P and the matrix K, and perform the encryption operation.

# C = P*K mod 26
def encrypt(P, K):
    C=[0,0,0]
    C[0] = (K[0][0]*P[0] + K[1][0]*P[1] + K[2][0]*P[2]) % 26
    C[1] = (K[0][1]*P[0] + K[1][1]*P[1] + K[2][1]*P[2]) % 26
    C[2] = (K[0][2]*P[0] + K[1][2]*P[1] + K[2][2]*P[2]) % 26
    return C

Now, we have to transform the message we want to encrypt into the vector P. And we need to process that message in three-letter blocks.

So, we implement a function that will create P using three letters at a time, encrypt the three letters, add them to a buffer and continue processing the rest of the message.

def Hill(message, K):
    cipher_text = []
    #Transform the message 3 characters at a time
    for i in range(0,len(message), 3):
        P=[0, 0, 0]
        #Assign the corresponfing integer value to each letter
        for j in range(3):
            P[j] = ord(message[i+j]) % 65
        #Encript three letters
        C = encrypt(P,K)
        #Add the encripted 3 letters to the final cipher text
        for j in range(3):
            cipher_text.append(chr(C[j] + 65))
        #Repeat until all sets of three letters are processed.
        
    #return a string
    return "".join(cipher_text)

The following function returns the inverse of a given matrix. In this case, we assume that K is always of size 3×3. This implementation can be easily adapted for bigger matrices.

def MatrixInverse(K):
    det = int(numpy.linalg.det(K))
    det_multiplicative_inverse = pow(det, -1, 26)
    K_inv = [[0] * 3 for i in range(3)]
    for i in range(3):
        for j in range(3):
            Dji = K
            Dji = numpy.delete(Dji, (j), axis=0)
            Dji = numpy.delete(Dji, (i), axis=1)
            det = Dji[0][0]*Dji[1][1] - Dji[0][1]*Dji[1][0]
            K_inv[i][j] = (det_multiplicative_inverse * pow(-1,i+j) * det) % 26
    return K_inv

In the main function, we will define the message and the key we want to use.

We create the matrix using the key and call the function Hill which will return the ciphertext.

In this case, I create K outside of the function Hill, because that gives me the possibility of using the same function to decrypt. So I don’t have to repeat the code twice.

if __name__ == "__main__":
    
    message = "MYSECRETMESSAGE"
    key = "RRFVSVCCT"
    #Create the matrix K that will be used as the key
    K = create_matrix_from(key)
    print(K)
    # C = P * K mod 26
    cipher_text = Hill(message, K)
    print ('Cipher text: ', cipher_text)
    
    
    # Decrypt
    # P = C * K^-1 mod 26
    K_inv = MatrixInverse(K)            
    plain_text = Hill(cipher_text, K_inv)
    print ('Plain text: ', plain_text)

As an extra test, you can use the code below to make sure that KxK^-1 is the identity matrix.

    # K x K^-1 equals the identity matrix
    M = (numpy.dot(K,K_inv))
    for i in range(3):
        for j in range(3):
            M[i][j] = M[i][j] % 26
    print(M)

Output example

In this example, I’m going to use the following input:

• message = “MYSECRETMESSAGE”
• key = “RRFVSVCCT”

Notice that I’m using the implementation above, which is implemented using a 3×3 matrix as the key.

In the function Hill, I added the code print(f’P{i}={P}’) to show the vector P.

When you execute the code above, you get the following result:

Advantages of Hill cipher

The main advantage of the Hill cipher is that it hides single letter frequency.

Depending on how big the matrix that represents the key is, the more letter frequency it hides.

For instance, if you use a 3×3 matrix, it hides single letter and two-letter frequencies.

Related posts:

• Understanding symmetric cryptography through the study of several ciphers
• What is the Caesar cipher?
• How to implement the Playfair cipher in Python?
• Vigenère cipher: python implementation