Hack Hill cipher? Easy

Target: Hack Hill Cipher

Good day, dear readers! Today I wanted to share a way that helped me open the text encrypted by the Hill method. I will not describe what Hill's method is: experienced craftsmen have already tried to convey to me the features of this method. Link to the post .

What do we have?

I will say right away that there was no plain text or key on hand. It was known that text with a length of 6286 characters was encrypted with a 7 x 7 matrix . Therefore, for our convenience, we will break the text into 898 lines of 7 characters. The text does not contain the letters 'e' and 'b' . For the sake of prudence, I will not cite the entire encrypted text, but only part of it:

тчгяцмекещэнлжсвтйджтчгсмнежздыщзяотьдрпюмимаадрх...

A seemingly senseless nonsense, for now ...

How will we break it?

Consider the brute force attack. It was stated above that two letters are excluded from the alphabet, therefore all linear combinations during encryption (as well as during decryption) are taken according to mod 31 (given that this is a prime number, the text becomes a little more secure).
If we consider enumeration of inverse matrix keys, then we will have to sort out$$combinations (this number fits approximately 75 characters). Therefore, this method is immediately excluded, though! If from this set one could sort out a subset of non-degenerate matrices in some more or less fast way , then perhaps the task would be easier. Unfortunately, I don’t know such a method and I’m not sure that this exists at all!

TOhow to be?

I propose to slightly “soften” our attack and take advantagesavvy. Imagine that we know the original matrix and take one of its lines. Let it be the first line . If we apply the multiplication of the first row of the key to the first block of size 7, then we will get the first letter of the plaintext. If we multiply by the second block, then we have the seventh letter of the plaintext, etc. In this way, we can get 898 characters of clear text and collect some statistics from it! Well, then we have to pick up seven lines of keys that satisfy a certain criterion. By this criterion I took the index of matchesRussian language. To do this, you need to collect all 898 letters, calculate the frequency for each letter and calculate their coincidence index (IP). recalculation of IP directly cast doubts for the following reason: the use of the double type prevents the rapid execution of the program. I was fortunate enough to find the most beautiful article on the PHI-test for mono-alphabeticity. Very briefly:

• The “critical” point is calculated $$where N is the length of the text;
• Random text is taken, calculated $$where F is the number of times a letter occurs in the text;
• Find out how much better $$ approximates $$.

Rather, you notice that there is nothing new here either. All the same can be done when breaking the Vizhener cipher. However, this will allow us to use only integer types in the program, due to which the conversion performance will only accelerate.

We begin to break ...

Immediately make a reservation: yes, I am a redneck coder. I have no doubt that C language professionals will find something to complain about here :). The program was parallelized into 8 threads.
I will say that for our text$$. I will give the code of one thread:

int chast[898]; /*Номера букв исходного текста*/
int mass[31];  /*Массив количества каждой буквы*/
int c1;
int c2;
int c3;
register __int32 PHI_O; /*PHI(O)*/
for (int k1 = 0; k1 < 4; k1++) {
     /*Здесь вложенные циклы for ...*/
     for (int k7 = 0; k7 < 31; k7++) {
/*При новой комбинации ключа очищаем массив и PHI(o) */
     memset(mass, 0, sizeof(mass));
     PHI_O = 0;
		      /*Сгенерированный ключ применяем к зашифрованном тексту*/
     for (int i = 0; i < 898; i++)
   {
       c1 = k1 * sym[7 * i] + k2 * sym[7 * i + 1];
       c2 = k3 * sym[7 * i + 2] + k4 * sym[7 * i + 3];
       c3 = k5 * sym[7 * i + 4] + k6 * sym[7 * i + 5] + k7* sym[7 * i + 6];
       chast[i] = (c1 + c2 + c3) % 31; /*Получаем какой-то текст*/
       mass[chast[i]]++; /*Сразу кладём в подсчет буквы*/
    }
     for (int i = 0; i < 31; i++) 
     PHI_O += mass[i] * (mass[i] - 1);
     if(PHI_O > 39000)
     { 
      cout << PHI_O << '\n';
      printf("%d %d %d %d %d %d %d\n", k1, k2, k3, k4, k5, k6, k7);
      }
						}
/*Куча закрывающихся скобок от вложенных циклов */
	}

So one thread iterates over $$lines of a matrix of a key and the fi test is made. As a result, I received quite a few candidates for “good” keys. Some were so elegant that their 898-character IP was 0.0529 ! Not all the gold that glitters . I was not too lazy to recalculate the frequency of letters obtained using the key string and noticed an amazing thing:

This series of letters fully met the fi-test criterion, but the frequency of letters was not plausible. In other words, the letter “c” could occur as often as the letter “o” occurs in a natural text, and “o” might not occur at all, but the IP property was preserved. I was not able to give a mathematical explanation for this. I exclude that this is a coincidence. So we had toSeparate flies from cutlets to choose the best candidates who combine well with the frequency of letters of our beloved and native Russian language. Surprisingly, such a tough selection was met by the candidates of several fighters:

• 3 16 5 24 17 20 25
• 6 30 5 1 13 12 3
• 7 11 18 12 17 27 15
• 12 17 0 15 5 16 1
• 15 19 27 14 21 10 2
• 25 14 27 20 22 21 22
• 29 3 1 10 30 28 26

All that's left is nothing ... Arrange them in the correct order. To do this, I had to create a key matrix, using the permutation function of the elements change the line indices between each other (i.e., the permutation went only between the indices) and apply the resulting matrix to the encrypted text, I put this whole thing into a text file (wonderful) and tried to cling to at least for some meaningful text. We are looking for ... we are looking for ... stop! Something seems to work out! Yes!



By the way find among 7! meaningful text lines are very easy, take no more than 2 minutes. That seems to be all!

conclusions

Computing on a CPU on 8 threads took me 10 hours. The computer puffed like a steam locomotive. Faced with difficulties more than once. Firstly, there were heaps of errors inside the code, which after 10 hours gave the wrong result. Secondly, it was difficult to choose an appropriate criterion. Thirdly, the program was not given good optimization (in this article I gave a piece of non-optimized code). Regarding the theoretical side of the issue: Divide and conquer .

This article ( at the specified link ) is required to read to everyone who is interested in classical cryptanalysis. The technique is great for smalltexts when you generously do not apply your skills of frequency analysis. The method is “rigidly” recursive in the sense that it depends heavily on all previous results. For this reason, it is impossible to parallelize it (by the way, it cannot be optimized if you wish), but the method is dynamic and should lead to the right result (in theory).

What in practice ? CUDA is without him! If I had my own titanium farm (at least 10), Hill’s cipher would be torn to shreds in less than a minute. The concept of parallel computing on CUDA, like a flock of hungry piranhas, does not give a chance to remain cryptographic to this encryption method, compressing time several thousand times. I’m not a huge specialist in this matter, but I have little doubt that this idea is easily implemented and I hope someone will implement it (if he really wants to).

It's all! I hope my article will be at least a little useful for you! Thanks for attention.