Криптографический алгоритм “методом перестановок”

Перестановка  строк 
 

      Рис. 3. Таблицы  шифрования двойной перестановкой 

      Получается  шифровка АЗЮЖЕ СШГГООИПЕР. Ключом к этому шифру служат номера столбцов 2413 и номера строк 4123 исходной таблицы. Число вариантов двойной перестановки тоже велико: для таблицы 3 х 3 их 36, для 4 х 4 их 576, а для 5x5 их уже 14400. Однако двойная перестановка очень слабый вид шифра, легко читаемый при любом размере таблицы шифрования.

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

      Ключ  – столбцы 2413, строки 4123. Переставляя  столбы и строки в порядке, записанном в ключе, получаем исходное сообщение  «ПРИЕЗЖАЮ ШЕСТОГО».

      Вскрытие  шифров перестановки

      Криптоанализ  – раздел криптологии, изучающий  методы «вскрытия» (определения ключа или сообщения). При этом криптологи считают, что алгоритм шифрования известен, а ключ нет. Необходимо определить текст перехваченной шифровки.

      Была  перехвачена радиограмма противника АЗЮЖЕ СШГТООИПЕР. Известно (разведчики взяли «языка»), что противник использует для шифрования  метод двойной перестановки в таблице 4х4. Ключи шифрования после взятия «языка» были изменены, и дешифровать шифровку не удалось. Поэтому криптоаналитику необходимо вскрыть шифровку.

      Сообщение АЗЮЖЕ СШГТООИПЕР укладывается в таблицу 4х4 (Рис.4). 

 

      Рис. 4.Исходная таблица для «вскрытия» сообщения 

      Метод «вскрытия» шифров двойной  перестановки основан  на определении маловероятных  сочетаний букв и  нахождении на их основе истинной  последовательности столбцов в шифровальной таблице.

      Для расшифровки перехваченного сообщения  необходимо определить вероятности  следования двух букв разных столбцов и выбрать наиболее вероятную  последовательность. Вероятность следования одного столбца за другим Р_{столбца} равна произведению вероятностей двухбуквенных комбинаций во всех n строках этих двух столбцов:

      Р_{столбца} = Р_{строки 1} · Р_{строки 2} · … · Р_{строки i} · … · Р_{строки  n}.

      Для упрощения счета используют формулу:

      log Р_{столбца} = log Р_{строки 1} + log Р_{строки 2} + … + log Р_{строки n}.

      Более того, как и в статических алгоритмах эффективного кодирования, чаще используются не вероятности появления в текстах  комбинаций из двух букв, не частоты  встречаемости, а количество встретившихся  двухбуквенных комбинаций в текстах.

      Таким образом, для «вскрытия» сообщений, зашифрованных методом двойной  перестановки принято [5] использовать логарифмы числа встретившихся  в текстах двухбуквенных комбинаций F(), которые приведены в таблице  №1.

      Для таблицы, приведенной на рис.4, получим следующие значения.

      При следовании за первым столбцом второго, получим:

      F(1®2) =F(A3) + F(Е  ) + F(ГТ) + F(ИП)=7+9+0+5=21.

      При следовании за первым столбцом третьего получим:

      F(1®3) =F(АЮ) + F(ЕС) + F(ГО) + F(ИЕ) =6+8+8+8=30.

      При следовании за первым столбцом четвертого получим:

      F(1®4) =F(АЖ) + F(ЕШ) + F(ГО) + F(ИР) =7+5+8+7=27.

      Рассматривая  все возможные варианты следования столбцов получим:

      F(2®1) = F(ЗА) + F(_Е ) + F(ТГ) + F(ПИ) =8+7+1+7=23;

      F(2®3) = F(ЗЮ) + F(_С) + F(ТО) + F(ПЕ) =0+9+9+8=26;

      F(2®4) = F(ЗЖ) + F(_Ш) + F(ТО) + F(ПР) =1+5+9+9=24; 

      F(3®1) = F(ЮА) + F(СЕ) + F(ОГ) + F(ЕИ) =0+7+8+8=23;

      F(3®2) = F(ЮЗ) + F(С_) + F(ОТ) + F(ЕП) =2+7+8+8=25;

      F(3®4) = F(ЮЖ) + F(СШ) + F(ОО) + F(ЕР) =1+5+6+8=20; 

      F(4®1) = F(ЖA) + F(ШЕ) + F(ОГ) + F(РИ) =6+6+8+8=28;

      F(4®2) = F(ЖЗ) + F(Ш_) + F(ОТ) + F(РП) =1+5+8+4=18;

      F(4®3) = F(ЖЮ) + F(ШС) + F(ОО) + F(РЕ) =0+0+6+8=14. 

      На  рис.5 приведен граф логарифмов частот следования столбцов друг за другом. 
 

      Таблица 1

      Логарифмы числа встретившихся двухбуквенных  комбинаций

      

      Рис. 5. Граф логарифмов частот следования столбцов. 

      Для дешифровки перехваченного сообщения  необходимо найти такой порядок  следования столбцов, чтобы получить максимальную сумму логарифмов (наиболее вероятное следование столбцов в исходном сообщении). Существует множество методов решения этой задачи (задачи коммивояжера) [6]. Самый простой – полный перебор вариантов. Самый быстрый был предложен в 1965 году Литтлом под названием «Метод ветвей и границ». Для простых случаев, как в данной лабораторной работе, целесообразно применить полный перебор. Результат решения приведен на рис.6. 

      

      Рис. 6. Подграф максимального пути.

      Для полученного графа составляем возможные  варианты таблиц (Рис.7). 

 
 
 
 
 

Рис. 7. Варианты таблиц, составленных на основе подграфа максимального пути. 

      Текст в одной из них уже читается и, расставив строки в порядке (4123), получим расшифровку ПРИЕЗЖАЮ ШЕСТОГО (Рис.8). 

 

      Рис. 8. Расшифрованный текст. 
 
 

      ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ

1. Зашифровать предложение из 16 символов методом двойной перестановки и показать преподавателю.
2. Произвести криптоанализ перехваченного сообщения (выдает преподаватель).
3. Сравнить полученный и исходные ключи.
4. Разработать программы, позволяющие максимально автоматизировать процесс криптоанализа (автоматизированное рабочее место криптоаналитика).

      СОДЕРЖАНИЕ  ОТЧЕТА

1. Цель работы.
2. Результаты выполнения пунктов задания на лабораторную работу.
3. Схемы алгоритмов для автоматизированного рабочего места   криптоаналитика, листинги разработанных программ.
4. Выводы по работе.