29.12.2017 15:27
A1mas 10 7800 Источник

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


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

Что имеем?


Скажу сразу, что на руках не имелось ни открытого текста, ни ключа. Было известно, что текст длинной 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

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

image

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

Выводы


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

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

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

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

Комментарии (10)


  1. Pochemuk
    29.12.2017 21:15
    #10593608

    Чисто из любопытства…

    Возьмем полный русский алфавит (33 буквы) и пробел.

    В качестве статистики будем применять не статистику частоты букв, а статистику буквосочетаний. Чтобы сразу отсеивать невозможные буквосочетания, хотя бы.

    Удастся ли за счет этого существенно снизить число финалистов?


    1. datacompboy
      29.12.2017 22:37
      #10593682

      буквосочетания можно использовать только вместо просмотра глазами полученного массива перестановок.
      проверка же сделана для каждой строки матрицы независимо — а потому мы при переборе получаем буквы с интервалом в 7 между ними.

      разумеется, таблицы сочетаний в тексте с интервалом в 7 букв посчитать можно, но смысла я большого в этом не вижу.


  1. ser-mk
    30.12.2017 00:11
    #10593764

    … По этой причине его невозможно распараллелить (кстати, его и не оптимизировать при всём желании), но метод динамичен и должен привести к верному результату (в теории). 

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


    1. A1mas Автор
      30.12.2017 12:29
      #10594028
      +1

      Имелось в виду не про мой метод, а про метод разделяй и властвуй. Способ который привел я на КУДА оптимизируем


  1. maxzhurkin
    30.12.2017 16:16
    #10594176

    Доля вырожденных матриц, IMHO, слишком мала, чтобы их исключение как-то серьёзно повлияло на трудоёмкость полного перебора


  1. lgorSL
    31.12.2017 01:53
    #10594518
    +1

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

    Фишка в том, что умножение по модулю 31 на любое число является перестановкой. И вообще, для любого числа кроме 0, найдётся обратный элемент. Например, 2*16 = 1 mod 31, т.е 2^{-1} = 16 mod 31.
    Если есть решение типа a*b = c, то так же есть решения (a*2) * (b * 2^{-1}) = c, (a * 3) * (b * 3^{-1}) = c и т.д.


    Так что можно ускорить поиск — если нашёлся вектор "a", проходящий фи-тест, можно попробовать ещё 29 векторов: 2a, 3a,… 30a. Возможно, в каком-нибудь из них частоты букв совпадут с реальными


    1. A1mas Автор
      31.12.2017 02:38
      #10594536
      +1

      Хорошая идея. Нужно запомнить…


    1. datacompboy
      31.12.2017 13:49
      #10594714

      Не уверен, что это имеет смысл при полном переборе. Стоимость проверки позже, «а не рассматривали ли мы его уже» может оказаться дороже.


      1. lgorSL
        31.12.2017 17:21
        #10594820
        +1

        Имеет. Среди векторов, а, 2а,… 30а найдётся один, у которого первый элемент — единица (ну или хотя бы ноль). Это значит, что можно ограничить первый элемент в массиве (0 или 1), перебрать все варианты, найди кандидатов по ИС и уже только среди них пробовать вектора 2а, 3а и т.п.


        1. datacompboy
          31.12.2017 17:26
          #10594822

          хм. а вот о таком подходе не подумал, да. Получается, можно на 1 число сузить по сути перебор… интересно.