# Hill Cipher in Cryptography

This article is about the **Hill Cipher**. In this article, we will briefly study the basic **Hill Cipher and its examples aim to capture**. We will cover the types of message in Hill Cipher.

Submitted by Monika Sharma, on January 08, 2020

It is a polygraphic substitution cipher that depends on linear algebra. Every letter from the alphabet is represented by several modulo 26. Simply, we write as **A = 0, B = 1, ..., Z = 25** is used, but this is not a correct feature of the cipher.

To encrypt a message, each block of **n** letters is multiplied by an invertible **n × n** matrix, against modulus 26 or we can say the multiple inverses of **n**.

To decrypt the message, every block is multiplied by the inverse of the matrix or inversed matrix used for encryption.

The matrix used for encryption is the plain text and one matrix is formed is cipher key when we combine or multiple them we get the new matrix called ciphertext, and the key should be chosen randomly from the set of invertible **n × n** matrices (modulo 26).

### Encryption

We have to do encryption on the message **'ACT' (n=3)**. The key is **'GYBNQKURP'** which can be written as the **n x n** matrix that is **3 x 3** matrix,

The message for encryption **'ACT'** is written as a vector,

The enciphered vector is given as,

In this, we just do the multiple matrices we just multiple the **1** row with **1** column as we can say **6*0+24*2+1*19=67** same as **13*0+16*2+10*19=222** and **20*0+17*2+15*19=319**.

And that matrix does the **mod 26** with particular column and made again the **3*1** matrix and we alphabetically write them with called ciphertext i.e **"POH"**.

### Decryption

To decrypt the message, we turn the ciphertext back into a plain text, then simply multiply by the inverse matrix of the key matrix as **"IFKVIVVMI"** in letters. The inverse of the matrix used in the encryption is,

For ciphertext which we already find we decrypt that and make plain text,

Now, we just find the inverse matrix then multiple it by key then it will give us back **"ACT"**.

**Let, K is DDCF**

be the key and suppose the plaintext is **"HELP"**. Then this plaintext is represented by two pairs because **n** is **2**.

Firstly we do encryption, then we will compute

and continue encryption as follows and written as,

The matrix **K** is invertible, hence **K ^{-1}** exists such that

**KK**The inverse of

^{-1}= K^{-1}K = I_{2}**K**can be computed by using the formula,

This formula still holds after a modular reduction if a modular multiplicative inverse is used to compute.

Now, we have to do decryption,

Then we compute,

And we get,

**Security**

The basic **Hill Cipher** is vulnerable to a known-plaintext attack that attacks by key because it is completely linear algebra. An opposite site that intercepts n plaintext/ciphertext character pairs can set up a linear system that can be easily solved; if this will happen then this system is undefined, it is the only way is to add a few more plaintexts/ciphertext pairs. While when **n x n** matrix multiplication is a useful step when it will be combined with other non-linear operations because matrix multiplication can provide diffusion. For example, a unique chosen matrix can give security that minor differences before the matrix multiplication will give the answer in huge differences after the matrix multiplication. Otherwise, some new ciphers use a matrix multiplication step to gave diffusion. For example, the MixColumns matrix step in AES cipher is matrix multiplication. The function g in Twofish is a combination of non-linear algebra S-boxes i.e substitution boxes with a carefully chosen matrix multiplication (MDS) is used this.

**Reference:** Hill Cipher

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.