Hil's cipher. Detailed analysis

In this publication, I will try to describe the encryption and decryption using the Hill algorithm in as much detail as possible. So, without further ado, immediately to the point.

Encryption

In order to encrypt any text using the Hill algorithm, the following steps must be taken:

1. Create a coded alphabet. Suppose we want to encrypt Russian text. Then the length of the alphabet will be 33 letters. It is advisable to add 4 more characters to the alphabet to choose from, I will add the following: "?", ".", ",", "". This is done so that the length of the alphabet is a prime, i.e. a number that is completely divided only by itself and by 1. This, of course, is not necessary, but very convenient, because for decryption it is necessary that the determinant of the key and the length of the alphabet are mutually simple, i.e. did not have common divisors except 1. If the length of the alphabet is a prime, then there are much more keys for which this condition is satisfied. Each character of our alphabet is assigned an integer code. It’s most convenient to just use letter numbers. Thus we obtain the encoded alphabet:
   
   
   
   
2. Now we take the text that we want to encrypt and encode it using our alphabet. Take for example the word "Cipher" , its code will be like this: 25 9 21 17 .
   
   
3. Now we select a keyword, or just a set of letters, which we will use as a key. It is important here that the length of this keyword is equal to the square of the integer, i.e. 4, 9, 16, 25 , etc. Only then can we make it the square matrix needed for encryption. I have chosen the word "ALPINISM" . We encode it using our alphabet. We get: 0 12 29 16 9 14 9 8 13 . We write the key in the form of a 3x3 matrix: The
   
   
   
   key can be set immediately with the matrix, if it is more convenient for you. I used the keyword.
   
   
4. Now we need to break the text into blocks of n characters each, where the n-dimension of the matrix, in my case is 3. Let's start breaking up:
   
   The first block: (25 9 21)
   
   We only have one number left on the second block - 17. The simplest solution in this case: add as many characters as possible to form an entire block. I decided to add spaces.
   
   Then the second block: (17 35 35)
   
   
5. Now we encrypt our text. For text encryption, it is required to carry out matrix multiplication of each block by a key matrix. It is worth noting that the blocks could be written not in rows, but in columns. Then we would multiply the key by the column, this is not a significant difference.
   
   Another important factor for this cipher is the key matrix determinant: it must be different from zero, otherwise it will be impossible to decrypt the encrypted text.
   
   So, we multiply the first block by the key:
   
   
   
   Multiply the second block by the key:
   
   
   
   Matrix multiplication is not a complicated operation, so I did not paint it in detail.
   Now we need to divide the resulting matrix modulo by 37, i.e. take the remainder of division by 37.
   
   Divide the first matrix:
   
   
   
   Divide the second matrix:
   
   
   
   Why divide by 37? Because this is the length of our alphabet, if you had an alphabet of a different length, you would divide by a different number. For example, for the English alphabet, divide by 26, or 29 if you added any characters.
   
   
6. Now we decode the resulting matrices using our alphabet.
   
   The first matrix: AYUN
   The second matrix: CHYA Glue
   
   two matrices and get the encrypted text: AYUNCHYA
   

Decryption

Now move on to decryption. Decryption is performed according to the following algorithm:

1. We reverse-code the ciphertext into numbers and break it into blocks.
   
   
2. We find the key matrix determinant:
   
   
   
   Finding the determinant is also a very simple operation, so I did not paint it.
   
   
3. Now, using the extended Euclidean algorithm, we find d , x , y .
   
   I will not describe the description and the algorithm itself. Information about this algorithm can easily be found on the Internet. At the input of the algorithm, we give det K and the length of our alphabet. At the output, we get d = 1 , x = -4 , y = 41 . We are only interested in x .
   
   
4. Now a complex and important thing. We need to find the inverse determinant of the element in the ring modulo 37 . To do this, do the following:
   
   • If the determinant is negative and x is positive, then the inverse of the determinant will be x .
   • If the determinant is positive and x is negative, then the inverse of the determinant will be 37 + x .
   • If the determinant is positive and x is positive, then the inverse of the determinant will be x .
   • If the determinant and x are negative, then the inverse will be -x .
   
   I selected this algorithm for searching the inverse element experimentally, because I couldn’t find anything useful on this topic. In any case, even if this algorithm is primitive, it works.
   
   So, our determinant is 379 , it is positive, and x is -4 - negative. Then we find the element inverse to the determinant by the formula 37 + x = 37 + (- 4) = 37-4 = 33 .
   
   
5. Now there’s another moment with which I suffered for a long time, because I could not find any useful information on the Internet. It is necessary to find the matrix inverse to the key matrix modulo 37 . In order to find this matrix, we need to find the matrix of algebraic complements of the key and the inverse determinant of the key matrix (already found in the previous paragraph). The matrix of algebraic complements is also very simple to find, I will not paint it. In our case, it looks like this:
   
   
   
   Now we divide this matrix modulo by 37 , I already painted this in encryption. We get such a matrix, it is important here not to lose the signs of the elements (some perform modulo division with loss of minuses, this is unacceptable in this algorithm):
   
   
   
   We multiply the matrix of algebraic complements by the inverse determinant of the element. We
   
   
   
   get the following matrix: Divide this matrix modulo by 37 :
   
   
   
   Transpose it (swap rows and columns in places):
   
   
   
   Now if the matrix element is negative, change it to another, calculated by the formula 37+ <element> :
   
   
   
   The last matrix obtained is inverse modulo to key matrix. If we multiply the matrix of the key and this matrix, and then divide the result modulo by 37, we get the identity matrix, i.e. matrix of the form:
   
   
   
   
6. To decrypt the ciphertext, we multiply the ciphertext lines by the matrix inverse to the key.
   Multiply the first line:
   
   
   
   Multiply the second line:
   
   
   
   Divide the resulting lines by 37 modulo:
   
   
   
   Glue the matrices (25 9 21 13 35 35) and decode using our alphabet: Cipher.
   
   As a result, we got the source text with two extra spaces at the end, which do not play any role.
   

Thanks for attention!