Cipher Hila. Detailed analysis

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

Encryption

In order to encrypt any text using Hill’s algorithm, it is necessary to do the following steps:

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 to the alphabet 4 more characters to choose from, I will add the following: "?", ".", ",", "". This is done so that the length of the alphabet is a prime number, i.e. a number that is divisible entirely 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 be mutually simple, that is, did not have common divisors except 1. If the length of the alphabet is a prime number, then there are more keys for which this condition is satisfied. We assign an integer code to each symbol of our alphabet. The most convenient way is to use numbers of letters. Thus we receive the coded alphabet:
   
   
   ')
   
2. Now we take the text that we want to encrypt and encode it using our alphabet. Take for example the word "NUMBER" , its code will be: 25 9 21 17 .
   
   
3. Now we select a keyword, or simply 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 a square matrix of it necessary for encryption. I chose 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 by the matrix, if you so convenient. I used the keyword.
   
   
4. Now we need to break the text into blocks of n characters in each, where the n-dimension of the matrix, in my case, is 3. We will begin to break:
   
   The first block: (25 9 21)
   
   On the second block, we have only one number left - 17. The simplest solution in this case is to add as many characters to form a whole block. I decided to add spaces.
   
   Then the second block: (17 35 35)
   
   
5. Now encrypt our text. To encrypt text, matrix multiplication of each block by the key matrix is ​​required. It is worth noting that the blocks could be written not into rows, but into columns. Then we would multiply the key by the column, this is not a significant difference.
   
   Also an important factor for this cipher is the key matrix determiner: it must be non-zero, otherwise the decryption of the cipher text will be impossible.
   
   So, multiply the first block with the key:
   
   
   
   Multiply the second block with the key:
   
   
   
   Matrix multiplication is not a complicated operation, so I did not describe it in detail.
   Now we need to divide the resulting matrix modulo 37, i.e. take the remainder of the division by 37.
   
   We divide the first matrix:
   
   
   
   We 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 another number. For example, for the English alphabet we divide by 26, or 29, if you added some characters.
   
   
6. Now we decode the resulting matrix using our alphabet.
   
   First Matrix: AYN
   The second matrix: CEA
   
   We stick together two matrices and we get the encrypted text: AUNCHYYA
   

Decryption

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

1. Back encode ciphertext into numbers and break into blocks.
   
   
2. Find the determinant of the matrix key:
   
   
   
   Finding a determinant is also a very simple operation, so I did not paint it.
   
   
3. Now, using the advanced Euclidean algorithm, we find d , x , y .
   
   I will not describe the description and the algorithm itself. Information about this algorithm can be easily found on the Internet. To the input of the algorithm we submit 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 difficult and important thing. We need to find the reciprocal of the determinant element in the ring modulo 37 . To do this, do the following:
   
   • If the determinant is negative and x is positive, then the inverse element of the determinant will be x .
   • If the determinant is positive and x is negative, then the inverse element of the determinant will be 37 + x .
   • If the determinant is positive, and x is positive, then the inverse to the determinant element will be equal to x .
   • If the determinant and x are negative, then the inverse element will be equal to -x .
   
   I selected this algorithm for searching for the inverse element experimentally, since could not find absolutely nothing 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 the inverse determinant element is found by the formula 37 + x = 37 + (- 4) = 37-4 = 33 .
   
   
5. Now one more thing that I have been tormented for a long time, because no useful information was found on the Internet. It is necessary to find the matrix inverse of 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 matrix of the key (already found in the previous paragraph). The matrix of algebraic complements is also sought very simply, I will not paint it. In our case, it looks like this:
   
   
   
   Now we divide this matrix modulo 37 , which I have already described in encryption. We get such a matrix, it is important not to lose signs on the elements (some do divide by module with loss of minuses, in this algorithm it is unacceptable):
   
   
   
   Multiply the matrix of algebraic complements by the inverse determinant element. We get the following matrix:
   
   
   
   Divide this matrix modulo 37 :
   
   
   
   Transpose it (change the rows and columns in some places):
   
   
   
   Now, if the matrix element is negative, change it to another one, calculated using the formula 37+ <element> :
   
   
   
   The last matrix obtained is the inverse of the modulus of the key matrix. If we multiply the matrix of the key and this matrix, and then divide the result modulo 37, we get the identity matrix, i.e. view matrix:
   
   
   
   
6. To decrypt the ciphertext, multiply the ciphertext rows by the matrix inverse of the key.
   Multiply the first line:
   
   
   
   Multiply the second line:
   
   
   
   We divide the lines by 37 modulo:
   
   
   
   We glue the matrices (25 9 21 13 35 35) and decode with our alphabet: Cipher.
   
   As a result, we got the source code with two extra spaces at the end, which do not play any role.
   

Thanks for attention!