[Из песочницы] Взломать шифр Хилла? Легко29.12.2017 23:48

Цель: взломать шифр Хилла

Доброго времени суток, уважаемые читатели! Сегодня я хотел поделиться способом, который помог мне вскрыть текст, зашифрованный методом Хилла. Что такое метод Хилла описывать не буду: до меня уже постарались опытные умельцы донести особенности данного способа. Ссылка на пост.

Что имеем?

Скажу сразу, что на руках не имелось ни открытого текста, ни ключа. Было известно, что текст длинной 6286 символов был зашифрован матрицей 7×7. Поэтому для нашего же удобства, мы разобьем текст на 898 строчек по 7 символов. В тексте не содержатся буквы 'ё' и 'ъ'. В целях благоразумства, я не буду приводить весь зашифрованный текст, а лишь его часть:

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

На вид бессмысленная ерунда, пока что…

Как будем ломать?

Рассмотрим атаку «грубой силой». Выше было оговорено, что из алфавита исключены две буквы, поэтому все линейные комбинации при шифровании (как и при дешифровке) берутся по mod 31 (учитывая, что это простое число, текст становится чуть более безопасным).
Если рассматривать перебор обратных матриц-ключей, то всего нам придется перебрать $inline$31^{49} $inline$ комбинаций (это число примерно умещается в 75 знаков). Поэтому такой способ исключается моментально, хотя! Если из этого множества можно было бы каким-нибудь более-менее быстрым способом перебрать подмножество невырожденных матриц, то возможно задача облегчилась бы. К сожалению я такого способа не знаю и не уверен, что такой вообще существует!

Как быть?

Предлагаю слегка «смягчить» нашу атаку и воспользоваться смекалкой. Представим, что мы знаем исходную матрицу и возьмем одну из ее строчек. Пускай это будет первая строчка. Если мы применим умножение первой строки ключа на первый блок размера 7, то мы получим первую букву открытого текста. Если умножим на второй блок, то имеем седьмую букву открытого текста и т.д. Таким вот образом мы можем получить 898 символов открытого текста и собрать с него какую-то статистику! Отлично, тогда нам придется подобрать такие семь строчек ключей, которые удовлетворяет некоторому критерию. Таким критерием я взял индекс совпадений русского языка. Для этого нужно собрать все 898 букв, посчитать частотность для каждой буквы и рассчитать их индекс совпадений (ИС). пересчёт ИС впрямую навеял сомнения по следующей причине: использование типа double препятствует быстрому выполнению программы. Мне посчастливилось найти прекраснейшую статью о ФИ-тесте для моноалфавитности. Очень кратко:

Рассчитывается «критическая» точка $inline$PHI (p) = 0,0529 * N * (N-1)$inline$, где N — длина текста;
Берется случайный текст, рассчитывается $inline$PHI (o) =\sum F (F- 1)$inline$, где F — сколько раз встречается буква в тексте;
Узнаем, насколько лучше $inline$PHI (O)$inline$ аппроксимирует $inline$PHI (P)$inline$.

Скорее вы подметите, что тут ничего нового-то и нет. Всё тоже самое можно проделать при взломе шифра Виженёра. Однако, это нам позволит в программе использовать только целочисленные типы, засчёт чего производительность пересчёта только ускорится.

Начинаем ломать…

Сразу оговорюсь: да, я быдло-кодер. Ни капли не сомневаюсь, что профессионалы языка С найдут здесь к чему придраться :). Программа была распараллелена на 8 потоков.
Скажу, что для нашего текста $inline$PHI (p)=0,0529×898*897=42611$inline$. Приведу код одного потока:

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);
      }
						}
/*Куча закрывающихся скобок от вложенных циклов */
	}

Таким образом один поток перебирает $inline$4×31^{6}$inline$ строчек матрицы ключа и производится фи-тест. Как следствие я получил достаточно много кандидатур на «хорошие» ключи. Некоторые были настолько изящны, что их ИС на 898 символов был равен 0,0529! Не всё золото, что блестит. Я не поленился пересчитать частотность букв, полученные с помощью строки-ключа и заметил удивительную вещь:

Данный ряд букв полностью удовлетворял критерию фи-теста, но частотность букв не являлась правдоподобной. Иными словами буква «в» могла встретиться так же часто, как в натуральном тексте встречается буква «о», а «о» могла и вовсе не встретиться, но при этом свойство ИС сохранялось. Мне не удалось дать этому математическое объяснение. Я исключаю, что это случайное совпадение. Итак, нам пришлось отделить мух от котлет выбрать самых лучших кандидатов, которые неплохо сочетаются с частотностью литер нашего любимого и родного русского языка. Удивительно, такому жёсткому отбору удовлетворяли кандидатуры нескольких бойцов:

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

Осталось-то всего ничего… Расположить их в нужной последовательности. Для этого мне пришлось создать матрицу-ключ, с помощью функции перестановки элементов менять между собой индексы строчек (т.е. перестановка шла только между индексами) и применять полученную матрицу к зашифрованному тексту, все это дело я выводил в текстовый файл (чудно) и пытался зацепиться хоть за какой-то осмысленный текст. Ищем… ищем… стоп! Кажется что-то получилось! Да!

Кстати найти среди 7! строк осмысленный текст очень легко, займет не больше 2 минут. Кажется, это всё!

Выводы

Вычисления на CPU на 8 потоках заняли у меня 10 часов. ЭВМ пыхтела как паровоз. Столкнулся с трудностями не раз. Во-первых, были кучи ошибок внутри кода, которые спустя 10 часов давали неверный результат. Во-вторых, было сложно подобрать подходящий критерий. В-третьих, программа не давалась хорошей оптимизации (в этой статье я привёл кусок неоптимизированного кода). Что касается теоретической стороны вопроса: Разделяй и властвуй.

Данная статья обязательна к прочтению всем, кто интересуется классическим криптоанализом. Техника отлично подходит для небольших текстов, когда широкодушно не применишь свои навыки частотного анализа. Метод «жестко» рекурсивен в том смысле, что сильно зависит от всех предыдущих результатов. По этой причине его невозможно распараллелить (кстати, его и не оптимизировать при всём желании), но метод динамичен и должен привести к верному результату (в теории).

Что же на практике? CUDAже без него! Будь у меня своя ферма титанов (хотя бы штучек 10), шифр Хилла был бы разорван в клочья менее, чем за минуту. Концепция параллельных вычислений на CUDA, как стая голодных пираний, не даёт шанса остаться криптостойким этому методу шифрования, сжимая время в несколько тысяч раз. Я не огромный специалист в этом деле, но я ни чуть не сомневаюсь, что это идея легко реализуема и надеюсь её кто-то осуществит (если очень захочет).

Это всё! Надеюсь моя статья будет хоть чуточку полезной для вас! Спасибо за внимание.