Learn all about Cryptography from this video.
Before we dive into the details of Hill Cipher, let’s first take a look at its history and how it came to be used in cryptography.
Hill Cipher History
Cryptography, the study, and practice of secure communication through unique methods and techniques prevents third parties or organizations from accessing sensitive information. In modern cryptography, concepts like confidentiality, data integrity, authentication, etc. play a crucial role.
The Hill Cipher method was invented and developed in 1929 by Lester S. Hill, a renowned American mathematician. Hill Cipher uses multiple mathematical methods thus, figuring several primary methods in classical cryptography.
What is Hill Cipher?
Hill Cipher, in the pretext of classical cryptography, follows a polygraphic substitution cipher, which means there is uniform substitution across multiple levels of blocks. This polygraphic substitution cipher makes it possible for Hill Cipher to work seamlessly with digraphs (two-letter blocks), trigraphs (three-letter blocks), or any multiple-sized blocks for the purpose of building a uniform cipher.
Hill Cipher is based on linear algebra, the sophisticated use of matrices in general (matrix multiplication and matrix inverses), as well as rules for modulo arithmetic. Evidently, it is a more mathematical cipher compared to others.
The Hill Cipher is also a block cipher. A block cipher is an encryption method that implements a deterministic algorithm with a symmetric key to encrypt a block of text. It doesn’t need to encrypt one bit at a time like in stream ciphers. Hill Cipher being a block cipher theoretically, means that it can work on arbitrary-sized blocks.
While Hill Cipher is digraphic in nature, it is capable of expanding to multiply any size of letters to add more complexity and reliability for better use. Since most of the problems and solutions for Hill Ciphers are mathematical in nature, it becomes easy to conceal letters with precision.
We will cover both Hill Cipher encryption and decryption procedures solving 3×3 matrices. However, it is possible to use Hill Cipher for higher matrices (4×4, 5×5, or 6×6) with a higher and advanced level of mathematics and complexity. Here, we will demonstrate simple examples that will provide more understanding of the Hill Cipher.
Hill Cipher Example
As an example of the Hill Cipher technique, let’s encrypt the text, ‘ACT’, and, later, decrypt the resulting ciphertext. This will help us understand how the Hill Cipher works.
To keep the example simple, here is a straightforward substitution scheme with the letter A mapped to 0, B mapped to 1, and so on and so forth.
Hill Cipher Encryption
We have to encrypt the message ‘ACT’ (n=3). The key is ‘GYBNQKURP’, which in the form of an nxn matrix looks like below:
‘ACT’ is written in the form of the following vector:
The resulting enciphered vector will be:
This results in the ciphertext of ‘POH’.
Hill Cipher Decryption
For the purpose of decryption, the ciphertext will have to be turned back into a vector. Simply, multiply it by the inverse matrix of the key matrix (IFKVIVVMI in letters). The inverse of the matrix will be:
For the previous Ciphertext ‘POH’, multiplying it with the inverse matrix gives:
The output vector gives back ‘ACT’.
Note:
Encryption and decryption both play a crucial role in understanding the use of Hill Ciphers in general. It is important to understand that any possible matrix in the system does not represent a key matrix. Cipher decryption instead requires an inverse key matrix.
The determinant method can determine whether the inverse exists or not. If the value of the determinant is 0 or shares a factor other than 1, it means that the matrix does not have an inverse. As a result, one will have to find or choose a different key matrix for decryption.
A usable or key matrix with non-zero determinants must have a coprime component directly to the overall length of the alphabet to be able to extract results from a cipher.
Advantages of Hill Cipher
Hill cipher offers several advantages as an encryption algorithm:
- Security: Hill cipher provides a higher level of security compared to traditional substitution ciphers as it operates on blocks of letters rather than individual letters. This makes it more resistant to frequency analysis attacks.
- Flexibility: Hill cipher allows encryption and decryption of messages containing both uppercase and lowercase letters, as well as punctuation marks and spaces. This flexibility makes it suitable for encrypting a wide range of text-based data.
- Complexity: The encryption process of Hill cipher involves matrix operations, making it more complex and harder to decipher without knowledge of the encryption key. This adds an additional layer of security to the algorithm.
- Key Strength: The security of Hill cipher is directly dependent on the size and randomness of the encryption key matrix. By using a larger key matrix, the encryption strength can be increased, making it more difficult for unauthorized individuals to decrypt the message.
- Mathematical Background: Hill cipher is based on linear algebra principles, providing a foundation for learning and understanding more advanced encryption techniques. It offers an opportunity to explore the relationship between matrices and encryption algorithms.
Security Aspects of Hill Cipher
When dealing with 2×2 matrices, Hill Cipher is easily solvable. But when it comes to modern cryptography solutions that have 256 combinations of numbers, Hill Ciphers can be fairly weak.
As mentioned earlier, Hill Cipher has a proven vulnerability when it comes to dealing with known-plaintext attacks due to its linear dependency. Any system having linear ciphertext pairs can easily break the Hill Cipher matrices as it follows only the standard algebraic algorithms for solutions.
Unfortunately, a higher level of matrix multiplications doesn’t do anything to add more security to the system. It can, however, complement diffusion on mixing with non-linear operations. Modern advanced encryption methods like AES use different diffusion to add further security to their system.
Lester S. Hill had built a unique machine for a 6×6 matrix cipher that had proven a higher level of security. However, its key settings were not configurable limiting its applications in practice.
CONCLUSION
Hill Cipher was among the first polygraphic cipher systems to be built on the practical system with more than three symbols or letters in one. In the modern era, Hill Cipher is rarely or almost never used. However, its existence is undeniable in the learning curve of cryptography.
Simple 2×2 Hill Cipher matrices are quite simple and decipherable, but as it expands in size, the calculations become a lot more complex, which requires an in-depth understanding of higher mathematics.