Learn Hill Cipher with 3x3 Matrix Multiplicative Inverse Example

WHAT IS HILL CIPHER?

The Hill cipher is a polygraphic substitution cipher that is based on the concepts of linear algebra. A polygraphic substitution is a cipher where uniform substitution is performed on letter blocks. The techniques used in the Hill cipher comprise linear algebra, which is an area of mathematics and requires an elementary understanding of matrices. The Hill cipher is also a block cipher, which takes input in plaintext bits and generates a block of cipher bits. The Hill cipher was invented by Lester S. Hill in 1929 and was the first polygraphic cipher that operated on more than three symbols or letters at a time. The formulae mentioned in the picture below are used for encryption and decryption:

Let's try to understand the encryption and decryption process of the Hill Cipher using the below example:

ENCRYPTION

To encrypt a plaintext, follow these steps:

1. Turn the keyword to matrix

The first step is to convert the given keyword to a 3x3 matrix form. Next, convert the keyword matrix into a key matrix by replacing the letters with corresponding numeric values.

2. Split plaintext into trigraphs

The second step is to convert the keyword matrix into trigraphs, i.e., groups of 3 letters since we are using a 3x3 matrix) and further converting them into column vectors. However, if the plaintext does not fit perfectly into column vectors, we can add null values to make the right length's plaintext.

3. Matrix multiplication

The third step is to perform matrix multiplication by multiplying the key matrix by each column vector. We combine the six numbers to receive a single number.

4. Modulus of column vectors

The final step is to take modulus 26 of the column vectors and convert them back to letters. Hence, we receive the encrypted ciphertext.

DECRYPTION

To decrypt the ciphertext, follow these steps:

1. Find Determinant of Key

The determinant of a matrix directly relates to the entries of the matrix. Once the determinant is calculated, take the modulus 26 with the determinant.

2. Transpose Key Matrix

Now, the transpose of the key matrix needs to be calculated. Transpose is just a flipped form of the original matrix and can be achieved by simply switching the rows with columns.

3. Find Minor

The third step is calculating the minor of the transpose of the key matrix. Minor is the determinant of a smaller square matrix by removing one or more of its rows or columns.

4. Find Cofactor

The fourth step is calculating the cofactor of the minor matrix. A cofactor is usually used to find the inverse of the matrix. It's the number received by eliminating the row and column of a specific element in the form of a square/rectangle. Convert the matrix received to the corresponding alphabets. Hence, we receive the decrypted Plaintext.

SECURITY OF HILL CIPHER

The basic implementation of the Hill cipher was vulnerable to a known plaintext attack because it was linear. An attacker who will intercept plaintext or ciphertext alphabet pairs forms a linear system that can be easily solved. If the system is indeterminate, it's necessary to add a few more plaintext/ciphertext pairs because calculating the solution by the standard linear algebra algorithms consumes a minute amount of time.

Matrix multiplication does not result in a secure cipher solely but is still an essential step when combined with other non-linear operations applied on the matrix as it leads to diffusion. For example, if a matrix is chosen wisely and appropriately, it might guarantee small differences, but the matrix will result in large differences in performing matrix multiplication. A few modern ciphers such as AES use matrix multiplication to provide diffusion.

REFERENCES

https://crypto.interactive-maths.com/hill-cipher.html https://en.wikipedia.org/wiki/Hill_cipher https://en.wikipedia.org/wiki/Hill_cipher