Cryptanalysis of Hill Cipher

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.

fu pc mt gz ky uk bq fj hu kt zk ki xt ta

-------------------------------------------------------

of th e_ __ __ __ __ __ __ __ __ __ __ __

_o ft he __ __ __ __ __ __ __ __ __ __ __

__ of th e_ __ __ __ __ __ __ __ __ __ __

…

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.

Recommended Reading:

• Monte Carlo Simulation
• Cryptanalysis of Substitution Cipher
• What is Cryptography?
• Public Key Cryptography
• Difference between Public Key and Private Key
   

Also, check out some of the Guided Paths, Contests, and Interview Experiences to gain an edge only on Coding Ninjas Studio.

Happy Learning!