Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Hill Cipher
3.
Cryptanalysis of Hill Cipher
4.
Frequently Asked Questions
4.1.
What is a Cipher?
4.2.
What is a Polyalphabetic Cipher?
4.3.
What is a Symmetric Cipher?
4.4.
What is Asymmetric Cipher?
4.5.
What is Cryptography?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Cryptanalysis of Hill Cipher

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

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.

Cryptanalysis of Hill Cipher

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 = 

Key Matrix

Plain Text Matrix = 

Plain Text Matrix

Now, performing the encryption:

C = PK

C = PK

Thus,

Ciphertext Matrix

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.

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:

Decryption Strategy

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

After combining both equations, we get the following:

Decrepted text computation

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. 

Decrepted text computation

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:

Value of Determinanat

Now let us determine the value of the determinant.

Value of Determinanat

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:

Adjoint of a Matrix

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

Adjoint Computation

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:

Decrepted text computation

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:

Decrypted Text

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:

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

Happy Learning!

Previous article
Cryptanalysis of Vigenere Cipher
Next article
What is the theory introduced by Claude Shannon?
Live masterclass