What is the Hill cipher?

The Hill cipher is a polygraphic substitution cipher built on concepts from Linear Algebra. The Hill cipher makes use of modulo arithmetic, matrix multiplicationa binary operation that produces a matrix by multiplying two matrices., and matrix inverses; hence, it is a more mathematical cipher than others. The Hill cipher is also a block cipher, so, theoretically, it can work on arbitrary sized blocks.

Polygraphic substitution is a uniform substitution where a block of letters is substituted by a word, character, number, etc.

Since the Hill cipher is fairly complex, let’s encrypt the text “CODE” and, later, decrypt the resulting ciphertext to understand how the Hill cipher works. To keep the example simple, we will use a straightforward substitution scheme where the letter A is mapped to 0, B is mapped to 1, etc. to stick to a 2x2 key matrix. The complexity of the Hill cipher increases with the size of the key matrix.

Encryption

Encrypting with the Hill cipher is built on the following operation:

E(K, P) = (K*P) mod 26 Where K is our key matrix and P is the plaintext in vector form. Matrix multiplying these two terms produces the encrypted ciphertext. Let's do so step by step:

1. Pick a keyword to encrypt your plaintext message. Let’s work with the random keyword “DCDF”. Convert this keyword to matrix form using your substitution scheme to convert it to a numerical 2x2 key matrix.

2. Next, we will convert our plaintext message to vector form. Since our key matrix is 2x2, the vector needs to be 2x1 for matrix multiplication to be possible. In our case, our message is four letters long so we can split it into blocks of two and then substitute to get our plaintext vectors.

3. Now, we can matrix multiply the key matrix with each 2x1 plaintext vector, take the moduli of the resulting 2x1 vectors by 26, and concatenate the results to get “WWVA”, the final ciphertext.

Decryption

Decrypting with the Hill cipher is built on the following operation:

D(K, C) = (K^-1 *C) mod 26 Where K is our key matrix and C is the ciphertext in vector form. Matrix multiplying the inverse of the key matrix with the ciphertext produces the decrypted plaintext. Let's do this step by step with our ciphertext, "WWVA":

1. First, we calculate the inverse of the key matrix. In doing so, we must keep​ the result between 0-25 using modulo 26. For this reason, the Extended Euclidean algorithm is used to find the modular multiplicative inverse of the key matrix determinant.

2. Next, we will multiply 2x1 blocks of the ciphertext with the inverse of the key matrix to get our original plaintext message, “CODE,” back.