Overview: Hill Cipher (Encryption and Decryption) With Examples | UNext Jigsaw

Introduction

Cryptography is the science of securely studying and practicing communication using unique methods, thus preventing any third person or organization from accessing any kind of sensitive information. Various aspects, such as authentication, data integrity, confidentiality, etc., play a crucial role in modern cryptography concepts. Cyphers was a common concept to deliver secret messages in the early days. Several methods have emerged in the history of cryptography that built the fundamentals of modern algorithms.

Hill Cipher has figured out several primary methods in classical cryptography, using multiple methods of mathematics. Despite modern advancements, Hill Cipher provides a simple and unique way of hiding messages in plain sight.
Hill Cipher in cryptography was invented and developed in 1929 by Lester S. Hill, a renowned American mathematician. Hill Cipher is Digraphic in nature but can expand to multiply any size of letters, adding more complexity and reliability for better use.

1. What is Hill Cipher?
2. Hill Cipher Encryption
3. Hill Cipher Decryption
4. Security Aspects for Hill Cipher
5. Advantages Of Hill Cipher 

1) What is Hill Cipher?

In the pretext of classical cryptography, Hill Cipher represents a polygraphic substitution cipher that follows a uniform substitution across multiple levels of blocks.

Here, polygraphic substitution cipher defines that Hill Cipher can work seamlessly with digraphs (two-letter blocks), trigraphs (three-letter blocks), or any multiple-sized blocks for building a uniform cipher.
Hill Cipher is based on a particular mathematical topic of linear Algebra and the sophisticated use of matrices in general, as well as rules for modulo arithmetic. As a prerequisite, it would be better for learners and professionals to have a sound understanding of both linear Algebra and Matrices. Thus, most of the problems and solutions for Hill Ciphers are mathematical, making it easy to withhold or hide letters precisely.
We will study Hill Cipher encryption and decryption procedures in solving 2×2 and 3×3 matrices. Although it can be used for higher matrices (4×4, 5×5, or 6×6), it also requires a higher and advanced level of mathematics, adding more complexity. Here, we have used simple examples that provide in-depth knowledge on this topic.

2) Hill Cipher Encryption

Generally, the below-mentioned structure of numbers and letters are used in the Hill Cipher Encryption, but this can be modified as per requirement.

For encrypting a message, one starts with each block having n letters and then multiplied with an n x n matrix, in parallel with modulus 26. Subsequently, each block needs to be multiplied by the inverse matrix for decryption.

Hill Cipher 2×2 example

In this Hill Cipher, 2×2 matrix process, the primary step starts with a keyword that we must convert into a matrix. Depending on the length of the keyword, if it is shorter than three words, then fill it up in alphabetical order. And for longer than 4 words, the first four letters are used in the matrix.

Following the above, in the letter and number table, each letter is converted into a specific number in parallel with its position. Here, the input message is SHORTER EXAMPLE with key as HILL and from the table, we can take:

H = 7, L = 11

I = 8, L = 11

They are represented in the vector or key matrix form as below.
These digraphs follow a simple pattern for transforming into a matrix. The first letter goes to the top of the matrix, and the second at the bottom of the first column only, and so on.
So for the input message ‘shorter example’, it can be represented as the following
Similarly, these vector forms are subsequently taken in the number form, as each letter takes the appropriate parallel number.
Now for the next step, we take the key matrix and multiply it with the first column, using the standard algebraic rules in the case of matrix multiplication.
So in this Hill Cipher example, we can write this as:
And then following the rules, it becomes:
Or in the matrix form as,
And then we will be performing the modulo 26 (i.e., dividing the number by 26, and then using the remainder)
Subsequently, then we can change these two letters into ciphertext represented as ‘AP’.
Here the whole calculation for this Hill Cipher encryption can be taken in the following form:

Hill Cipher 3×3 example

Now we will take an example for a 3×3 matrix for encryption, using the input message ‘retreat now’. Here the key phrase is given as BACK UP, and we have to convert this key phrase into a matrix.
As we can see, there are only 6 letters, and we need at least 9 letters for a 3×3 matrix. So we are going to fill the rest of the matrix as the flow of the alphabets.
Changing these letters with parallel numbers for a key matrix:
Now take the input message of ‘retreat now’ into trigraphs (in the form of a 3×3 matrix as a group of 3 letters) and write them as column vectors.
Also, we can see there are 10 letters, and it will not fit perfectly into column vectors. So we will add some null characters to fill them accordingly.
And replacing them with the numbers as:
Now we will perform multiplication with each column with the key matrix. Here all the standard rules are followed for matrix multiplication.
Here the process for multiplication involves using the first or top row (a,b,c) to multiply with each element of the column vector (x,y,z), and then adding them respectively for one large number as (ax + by + cz), and then following the same rule for each of the three vectors.
So for our example, we place the key matrix with our first column of the message as:
And now performing multiplication for these two as:
Now the result comes as:
And then performing the modulo 26 as per the encryption process.
Then changing them into letters as;
The complete calculation can be represented as the following:
The second part of the calculation is:
And the third part of the calculation is:
And the last part of the matrix calculation is:
The rest of the three multiplication performances give us a complete final ciphertext represented as ‘DPQ,’ ‘RQE,’ ‘VKP,’ and ‘QLR.’

3) Hill Cipher Decryption

Starting the Decryption process in Hill Cipher cryptography, the first step is to get the inverse matrix. Here, it is a crucial aspect to calculate and find the key matrix represented as the general method:
Here,
K = key matrix of the message,
d = determinant for the key matrix,
adj(K) = adjugate matrix for the K.
Once we obtain the inverse matrix, then it is multiplied with column text of the ciphertext, then modulo to get the remainder, and then transformed into letters for the desired result.
So the process for decryption is the same, with the inverse matrix being the main difference.

Hill Cipher example 2×2 decryption

And now, following the same 2×2 matrix from the above encryption example, with keyword ‘hill’ and ciphertext as ‘APADJ TFTWLFJ’.
Starting the keyword in the matrix form and then the subsequent numerical form as:
Now we will find the inverse matrix as follows:
Step 1: Calculate the multiplicative inverse for the determinant.
The determinant is essential and directly related to the matrix values. We can find the determinant value by multiplying the top left number and the right bottom number and then subsequently subtracting this from the product of the other two (i.e., top right corner and bottom left number).
So the formula for a 2×2 matrix is given as:
Determinant = (top left number x right bottom number) – (top right number x left bottom number)
Note: The determinant value is a direct value, not any bracket or matrix around that.
Once we have the value, the numerical values are passed through modulo 26 for a reminder, and it can be represented as:
And now for the multiplicative inverse of this determinant value:
Calculate a number between 1 and 25 respectively that gives the remainder 1 when multiplied by the determinant. For our example, we have to find a number that multiplied by 15 gives a remainder of 1 for the modulo 26.
Now, with huge advancements, there are algorithms to find this value. But you can also use the trial and error method to find the exact value.
On simple calculations, we can find the number 7 that satisfies the above equation and also lies between 1 and 25, respectively.
Step 2: Value for Adjugate Matrix
Adjugate matrix is defined as the transpose of its original cofactor matrix. A general method for adjugate matrix is given by:
Here, you can just swap the inner elements of the matrix and its sign for the inner elements.
And for negative values, we have to add them with 26 to get the desired values between 0 and 25 for use in the decryption formula.
So for your example, we have the following procedure:
Now taking the values from step 1 and step 2 for the Multiplicative inverse and Adjugate matrix, respectively, we come to the following calculations:
In our example, we can do this by following:
And we can stand with the inverse key matrix as:
Now use the first two letters from the ciphertext as AP and then multiply with the inverse matrix for modulo 26. Here, the whole equation can be represented as follows:
Now we get the first two letters as ‘sh.’ Similarly, we solve for the rest of the ciphertext as APADJ TFTWLFJ. In conclusion, you will find the original message for a ‘short example.’

Hill Cipher 3×3 example

Now let us take an example for a 3×3 matrix, with ciphertext SYICHOLER and keyword as an alphabet. Starting with the first step to transform this key phrase into a matrix:
You might have observed an extra A in the end. This is done to complete the matrix in case there are fewer elements in the keyword by following the alphabet’s order.
The key matrix is then changed for each letter with a number:
Now we will follow the steps for finding the inverse matrix for this message:
Step 1: Calculate the multiplicative inverse for the Determinant.
There are some changes to the 3×3 matrix in finding the determinant method. Here the 3×3 matrix is multiplied with a 2×2 matrix. This 2×2 matrix is made of the same matrix elements by removing both the top row and the left column. And then, the middle value of the multiplication is subtracted from the other two. Here the formula looks like this:
And for our example, we have the following values:
With the multiplicative inverse process, we have to find a number between 1 and 25 that gives the value of 1 on multiplication with the determinant value.
For our case, we have to find the number of multiplication by 11 that satisfies 1 modulo 26.
With modern algorithms, these values can be seamlessly obtained, but they can also be found using the trial and error method.
For our example, the value that satisfies the above equation is 19. And we will use this number to find the inverse key matrix for the decryption process.
Step 2: Calculate the Adjugate Matrix.
For the 3×3 matrix, the formula to obtain the Adjugate matrix is represented as
At first look, we can see it is quite complex. Now there are 9 2×2 matrices and different sign arrangements to obtain 9 determinant values. Then you have to pass the value with modulo 26 to obtain the Adjugate matrix, respectively
Step 3: Finalising the inverse matrix value.
The inverse matrix value can be obtained by multiplying the multiplicate values inverse from step 1, and the Adjugate matrix from step 2, respectively, and then using module 26 to get the exact values for the inverse matrix for use in the decryption process.
This inverse matrix can be found in the following way:
To better understand the example, here is a key and inverse key matrix representation.
And then using this inverse matrix with our key phrase first column as,
And the second column as
Finally, the third column as
We can then assemble the three values as ‘WEA’, ‘RES,’ and ‘AFE’ to get the hidden message as ‘We are safe’ with the Hill Cipher decryption method.

Hill Cipher 3×3 example

Let’s take another example of the input message ‘ACT’ with key GYBNQKURP and the output value for ciphertext as ‘POH.’ We will follow Hill Cipher Encryption and Decryption methods in this example.
Starting with ACT as represented in the matrix as A = 0, C = 2, and T as 19, respectively, given in the form of the following matrix.
And the key matrix here comes with GYBNQKURP. Taking the clues from the top table of alphabets and numbers values now:
GYB = 6 24 1
NQK = 13 16 10
URP = 20 17 15
Now, here the complete matrix is enciphered as the following vector form of a matrix:
And if you look closely, the last column in the above image represents the ciphertext as ‘POH’.
Similarly, if we have an input message as CAT, then the values in the matrix are:
CAT = ( 2 0 19) or
Now this time, the enciphered values in the vector will be:
The desired values now can be represented as ‘FIN’ from (F = 5, I = 8, N = 13) respectively.
And for the Hill Cipher Decryption process, we use the ciphertext to find the inverse matrix.
And then using the last ciphertext again as ‘POH’; to get the original message of ACT.
Note: You can use any programming method to implement Hill Cipher cryptography, such as C++, C#, Java, Python, etc.

4) Security Aspects for Hill Cipher

Hill Cipher, when dealing with 2×2 matrices, is easily solvable. And with modern cryptography solutions taking on as high as 256 combinations of numbers, Hill Ciphers are fairly weak, even when compared with similar Bifid or Playfair cypher systems.
Hill Cipher has a proven vulnerability to the known-plaintext attack, as it has a linear dependency. Systems with linear ciphertext pairs can easily break the Hill Cipher matrices that follow only the standard algebraic algorithms for solutions.
Using a higher level of matrix multiplications doesn’t add more security to the system but can complement diffusion on mixing with non-linear operations. Several Modern advanced encryption methods (AES) use different diffusion to further secure their system.

5) Advantages Of Hill Cipher 

• It is extremely effective in concealing single-letter frequencies 
• For hiding both single-letter and two-letter frequency information, 3×3 hill ciphers are extremely efficient.  
• Cipher provides great security against any kind of attack made through cipher text.

Conclusion

Hill Cipher in cryptography was among the first polygraphic cypher systems that were built on the practical system using more than three symbols or letters in one.
Encryption and Decryption both play a crucial aspect in understanding the use of Hill Cipher in general. Here, the learners should know that any possible matrix in the system does not represent a key matrix. But to decrypt a cypher, you must have an inverse key matrix.
Now, you can use the determinant method to know whether the inverse exists or not. So, if the value of the determinant comes out to be 0, or shares a factor other than 1, it represents that the matrix does not have an inverse. In that case, you have to find or choose a different key matrix to decrypt a cypher.

On the other hand, a usable or key Matrix with non-zero determinants must have a coprime component directly to the alphabet’s overall length for getting results from a cypher.
The use of Hill Cipher in the modern era is quite less or non-existent. Still, in the learning curve of cryptography, it played a crucial role. Security of the Hill Cipher, when compared with Playfair or Bifid cyphers, are the same, or slightly less.
Hill Cipher 2×2 matrices are quite simple, and messages are solvable, but as you proceed further, these calculations become complex, requiring an in-depth understanding of the higher mathematics. Lester S. Hill designed a unique machine for a 6×6 matrix cypher that had proven a higher level of security, though its key settings were still not configurable, which limited its practical applications. Learn more about Ciphers and navigate your way with them via our Postgraduate Certificate Program in Cybersecurity. Master the nuances of Cybersecurity in just 8-month with this robust program.

Also Read

• Playfair Cipher: A Beginner’s Guide In 5 Important Points
• Ethical Hacking: A Comprehensive Guide In 2020