There are various encryption methods present in modern-day cryptography. Hill Cipher is one of the famous ciphers and is also rather difficult to break.

In this article, we will discuss Hill Cipher's cryptanalysis.

Hill Cipher

Hill Cipher is an encryption method that is based on linear algebra. It is a polyalphabetic substitution cipher. It is like solving a linear equation system using matrix multiplication. The matrices involved in the encryption and decryption of Hill Cipher are all considered modulo 26.

The Hill Cipher has two matrices for obtaining the encryption text. One is the plain text matrix, whereas the other is the Key Matrix.

Let P be the plain text matrix, and K be the Key matrix. The Cipher Text matrix C can be obtained as

C = PK

The above equation is the matrix multiplication of the Plain Text and the Key Matrix.

Let us see an example:

We have been given the phrase “code is ready” and a 4 X 4 key matrix. We can append some bogus characters (“z”) to the plain text making the plain text “codeisreadyz” and making it into a 3 X 4 plain text matrix.

Key Matrix =

Plain Text Matrix =

Now, performing the encryption:

C = PK

Thus,

The cipher text obtained from the ciphertext matrix is: “OHKNIHGKLISS”

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Cryptanalysis of Hill Cipher

Cryptanalysis is the study of ciphers. When doing Cryptanalysis, we understand the working of the ciphers to the best extent. Cryptanalysis also helps determine the cipher's strength and how to break the cipher.

A known Plain Text attack is the best course of action to decrypt a Hill Cipher. Let us take an example where a 2X2 matrix is used to encrypt a text using Hill Cipher.

Since Hill Ciphers are linear, we only need to find a two-lettered sequence to determine the key here. Since we are performing a known plain text attack, we know a part of the plain text.

Let’s assume that we have the following cipher text given to use:

fupcmtgzkyukbqfjhuktzkkixtta

We know that the phrase “of the” exists somewhere in the original text. Therefore one of the following situations must be true as Hill Cipher encrypts the letters in pairs.

Assuming that the second line is correct, it would mean that “ft” is encrypted as “pc” and “he” is encrypted as “mt”.

We can try to perform decryption using this information now. The following equations can be used:

We must determine the Decryption Key Matrix in the above equations, which is D.

After combining both equations, we get the following:

Since we need D from basic algebra, we can determine that if we multiply both sides of the equations with the inverse of the matrix on the LHS of the equation, we can get D.

Now we can compute the inverse o the matrix and perform matrix multiplication to obtain D.

To compute the inverse of the matrix, first, we need to determine the value of its determinant using the following method:

Now let us determine the value of the determinant.

Note that for an inverse of a matrix to exist, it should have a non-zero determinant value. If during the cryptanalysis of Hill Cipher, the value of the matrix’s determinant is found to be zero, then we have to consider different sets of values.

Now, we have to find the adjoint of the matrix to compute the inverse:

By using the above formula, we can determine the adjoint of the matrix as:

All values are taken modulo 26.

Now since the determinant value is 1, the matrix's inverse is equal to the adjoint of the matrix. Therefore going back to the equation to determine D:

When we try to decrypt the plain text using this decryption key D, we still get a gibberish message. This means that the original assumption we made for the position of the text ‘of the’ was incorrect.

Upon further computations, it is found that the text ‘of the’ lies in the 18th position. The decryption key determined for the same is as follows.

We obtain D as:

With this decryption key, the decrypted text is obtained as:

defendtheeastwallofthecastle

Frequently Asked Questions

What is a Cipher?

A Cipher is an encrypted mode of communication so that if the message is intercepted, the attacker can not determine the meaning of the message.

What is a Polyalphabetic Cipher?

A Ployalphabetic Substitution Cipher is a substitution cipher where an alphabet can be encrypted into different alphabets. There is no fixed pattern.

What is a Symmetric Cipher?

A Symmetric Cipher has the same key for the decryption and encryption of messages.

What is Asymmetric Cipher?

An Asymmetric Cipher uses different keys for the encryption and decryption of messages. The key used for decryption is called the Private Key, and the key used for encryption is called the Public Key.

What is Cryptography?

Cryptography is the science or the study of secure communication methods between users.

Conclusion

In this article, we briefly discussed what Hill Cipher is and then, in detail, discussed how the cryptanalysis of a Hill Cipher is carried out.