Introduction

Cryptography is the science of studying and practising communication securely by using unique methods, thus preventing any third person or organisation from accessing any kind of sensitive information. Various aspects, such as authentication, data integrity, confidentiality, etc., play a crucial role in modern cryptography concepts. Ciphers were 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 several primary methods in classical cryptography, using multiple methods of mathematics. Despite modern advancements, Hill Cipher provides a simple and unique way for 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

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 of mathematical nature, which also makes it easy to withhold or hide letters precisely.

We will study both procedures for Hill Cipher encryption and decryption in solving 2×2 and 3×3 matrices. Although it can be used for higher matrices (4×4, 5×5, or 6×6) as well, it 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.

LetterABCDEFGHIJKLMNOPQRSTUVWXYZ
Number012345678910111213141516171819202122232425

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, for decryption, each block needs to be multiplied by the inverse matrix.

Hill Cipher 2×2 example

In this process of Hill Cipher, 2×2 matrix, 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 of the letters is then 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 taking the input message of ‘retreat now’ into trigraphs (in the form of a 3×3 matrix as a group of 3 letters) and subsequently writing 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’ ‘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 plays an essential role and is 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 and not any bracket or matrix around that.

Once we have the value, the numerical values are passed through modulo 26 for a remainder, and it can be represented as:


And now for the multiplicative inverse of this determinant value:


Calculate a number between the 1 and 25 respectively that gives 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 advancement, 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 ‘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 in the order of the alphabets. 

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: Calculating the multiplicative inverse for the Determinant.

There are some changes for 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 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 it 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 Adjugate matrix is represented as:

On 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 get a better understanding of the example, here is a representation of the key matrix and inverse key matrix.

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’, ‘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 the methods for both Hill Cipher Encryption and Decryption 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.

message vector

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

Cipherkey

Now, here the complete matrix is enciphered as the following vector form of a matrix:

enciphered vector

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.

inverse matrix

And then using the last ciphertext again as ‘POH’;

Decrypt

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 cipher systems of Bifid or Playfair cipher.

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.

Conclusion

Hill Cipher in cryptography was among the first polygraphic cipher systems that was 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 cipher, 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 cipher.

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 cipher. 
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 ciphers, 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 cipher that had proven a higher level of security, though its key settings were still not configurable, which limited its practical applications.

Also Read

SHARE
share

Are you ready to build your own career?