Polyalphabetic: Hill Cipher

History of Hill Cipher

The Hill Cipher is a polyalphabetic cipher method developed in 1929 by a renowned American mathematician, Lester S. Hill. This cipher encrypts a group of letters called polygraphs using multiple mathematical methods.

Hill Cipher 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. It is a more mathematical cipher as compared to the other ciphers.

Hill Cipher

 Hill Cipher is an encryption method 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.

Hill Cipher is a block cipher. It can encrypt more than one bit at a time.

To obtain the encrypted text, Hill Cipher uses two matrices. The Cipher Text matrix C can be obtained as-

C = PK

where,

P= Plain text matrix

K =  Key matrix

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

Mostly the problems and solutions for the hill ciphers are mathematical, so it becomes easy to decrypt letters with precision.

Advantages of Hill Cipher

The main advantages of Hill Cipher are as follows:

• It perfectly conceals single-letter frequencies.
• Hill Cipher is easily solvable when dealing with 2×2 matrices.
• 3×3 Hill Ciphers are extremely useful when hiding a single-letter or two-letter frequency information.
• Hill cipher has the advantage of high diffusion and strong tamper resistance without detection.
• It can withstand any attack, except if the attack is through a known plaintext.

Disadvantages of Hill Cipher

• The Hill cipher is vulnerable to known-plaintext attacks.
• In Hill cipher, a simple 2×2 matrix is quite simple and decipherable. Still, when it expands, the calculations to encrypt or decrypt the data become much more complex, requiring a deep understanding of higher mathematics.

Hill Cipher Encryption

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.

Example

To understand how the Hill Cipher works, we will encrypt the text, 'FLY'.  

Input

Mapping alphabets to numbers-

The above table represents each letter by the number modulo 26. Here, we have mapped the letter A mapped to 0, W mapped to 22, I mapped to 8, N mapped to 13, and so on.

So here, for encryption and decryption explanation, we will take an example of 3×3 matrices. 

Now to form a nxn matrix from the plain text 'FLY' (n=3) and the key is 'CODINGANU' we will write the number modulo for each letter. Similar to this:

'FLY' is written in the form of the following given vector:

The result of an encrypted vector is:

Converting the result matrix in mod of 26.

This results in the ciphertext of 'CPZ'.

Output

Implementation of Hill Cipher in Java

Now, let’s understand the code for encrypting the plain text by following the steps explained below. 

Algorithm

• Write a function to generate the 3X3 matrix for the key string, which is 'CODINGANU'.
• The second step is to create a function to encrypt the plain text, which is ‘FLY’. So we have taken 3 constants i, j, and k to multiply the 3X3 matrix by the 3X1 matrix. Then we compute mod 26 of the obtained matrix.
• We will obtain the key matrix from the key string and generate the vector for the message.
• Then we will create the function that generates the encrypted vector which in turn will generate the cipher text.

public class Main

{

/* The given function generates the
 3X3 matrix for the key string*/
static void getKeyMatrix(String key, int keyMatrix[][])
{
	int k = 0;
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			keyMatrix[i][j] = (key.charAt(k)) % 65;
			k++;
		}
	}
}

// Function for encrypting the message
static void encrypt(int cipherMatrix[][],
			int keyMatrix[][],
			int messageVector[][])
{
	int i, j, k;
	for (i = 0; i < 3; i++)
	{
		for (j = 0; j < 1; j++)
		{
			cipherMatrix[i][j] = 0;
		
			for (k = 0; k < 3; k++)
			{
				cipherMatrix[i][j] +=
					keyMatrix[i][k] * messageVector[k][j];
			}
		
			cipherMatrix[i][j] = cipherMatrix[i][j] % 26;
		}
	}
}


static void HillCipher(String message, String key)
{
	/* To implement the hill cipher
	get key matrix from the key string*/
	int [][]keyMatrix = new int[3][3];
	getKeyMatrix(key, keyMatrix);

	int [][]messageVector = new int[3][1];

	// Generate vector for the message
	for (int i = 0; i < 3; i++)
		messageVector[i][0] = (message.charAt(i)) % 65;

	int [][]cipherMatrix = new int[3][1];

	/* Given function generates
	 the encrypted vector*/
	encrypt(cipherMatrix, keyMatrix, messageVector);

	String CipherText="";

	for (int i = 0; i < 3; i++)
		CipherText += (char)(cipherMatrix[i][0] + 65);

	// Finally print the ciphertext
	System.out.print(" Ciphertext:" + CipherText);
}

public static void main(String[] args)
{
	// The message to be encrypted 
	String message = "FLY";

	// The cipher key
	String key = "CODINGANU";

	HillCipher(message, key);
	}
}

Output

There are two complications while encrypting the matrix:

• The matrix will form an inverse matrix when its determinant is not zero and not be divisible by 2 or 13. Hence, not all matrices have an inverse. 
• The determinant of the encrypting matrix should not have zero and any common factors with the modular base.

So this was all about Hill Cipher. Now it’s time for some frequently asked questions.

Frequently Asked Questions

Name some cryptography algorithms.

These are some of the cryptography algorithms - AES(Advanced Encryption Standard), DES(Data Encryption Standard), Blowfish, and RSA(Rivest-Shamir-Adleman).

Can someone hack encrypted data?

Yes, attackers can hack encrypted data. However, depending on the encryption level applied, the difficulty level increased.

What are the goals of Cryptography?

Confidentiality, Integrity, Availability, and Non-Repudiation of IT systems are the goals of cryptography. 

What are plain text and ciphertext?

The plaintext can refer to anything humans can understand, whereas ciphertext is a series of randomized letters, symbols, and numbers humans cannot understand.

What are encryption and decryption?

Encryption is the conversion of plain text into ciphertext. In contrast, decryption is the process that converts ciphertext into plaintext.

Conclusion

In this article, we have extensively discussed cipher and a type of polygraphic cipher called hill cipher with their examples. To learn more about cipher, check the link below:

• Substitution Cipher
• Caesar Cipher
• Keyword Cipher
• Monte Carlo Simulation

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Keep Coding!