Программная реализация генетического алгоритма для дешифрования гомофонического шифра

АННОТАЦИЯ

Разработан и программно реализован генетический алгоритм для дешифрования гомофонического шифра. Задачами алгоритма является выявление ключа для зашифрованного текста и дешифрование текста. Процесс дешифрования автоматизирован с помощью реализованной программы.

ABSTRACT

Genetic algorithm for decrypting the homophonic cipher is developed and implemented. Objectives of the algorithm are to find an identification key for ciphered text and recover decrypting the text. Process of decrypting is automated with implemented program.

Введение

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

Многообразие существующих алгоритмов шифрования порождает в свою очередь различные способы расшифровки (криптоанализа) зашифрованных данных. Самым распространенным способом дешифрования шифра замены является частотный анализ, основанный на различной частоте использования букв в тексте.

Однако частотный анализ затруднен, если шифрование было осуществлено с помощью гомофонического шифра, которые «сглаживает» частотный профиль зашифрованного текста. Тем не менее можно попытаться провести криптоанализ данного шифра с помощью генетического алгоритма. Аналогичные попытки для других методов шифрования уже предпринимались и показали свою эффективность.

Постановка задачи

Гомофонический шифр относится к шифрам простой замены. Алгоритм шифрования заключается в замене символа исходного алфавита одним из предложенных в ключе символов шифрующего алфавита.  Пусть шифруемым текстом будет некоторая последовательность символов . Текст состоит из символов исходного алфавита . Также задан некоторый шифрующий алфавит , состоящий из заменяющих символов. Для каждого символа алфавита A предусмотрено несколько заменяющих символов алфавита B. Количество заменяющих символов зависит от частоты употребления символов исходного алфавита в шифруемом тексте. Набор символов алфавита A и заменяющих символов для каждого символа алфавита образуют ключ K шифруемого текста

}.

При этом алфавиты A и B могут пересекаться как множества, но наборы заменяющих символов для двух различных букв исходного алфавита пересекаться не должны.

Далее каждый символ исходного текста а_j заменяется случайным символом из соответствующего набора заменяющих символов  .

Взлом такого шифра при помощи классического частотного анализа по сути сводится к перебору всех возможных ключей [1, c. 17, 3, с. 176].

Генетический алгоритм

Рассмотрим основные шаги генетического алгоритма для дешифрования гомофонического шифра [4, с. 53-55].

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

Рисунок 1. Пример ключей для шифрования

На этапе скрещивания все особи будут скрещены между собой. Для этого из первой особи выбираются исходные символы с нечетными номерами, а из второй – исходные символы с четными номерами. Строка с заменяющими символами остается неизменной.

На этапе селекции отсеиваются особи, которые имеют не полный набор символов исходного алфавита в первой строке. Далее на этапе формирования нового поколения необходимо расшифровать зашифрованный текст каждым ключом и подсчитать частоту двухсимвольных сочетаний в расшифрованном тексте. Эти частоты необходимо сравнить с «эталонными» значениями частоты двухсимвольных сочетаний в тексте. Эти данные могут быть получены из таблиц [2, с. 8-59]. Более приспособленными особями будут считаться те, у которых меньше сумма отклонений частот от идеальных значений. Работа алгоритма будет закончена через определенное количество поколений, указанных пользователем. Фитнес-функция данного алгоритма будет выглядеть следующим образом:

,

где  – «эталонная» частота двухсимвольного сочетания,  - частота аналогичного сочетания символов в тексте, расшифрованном с помощью ключа x.

Реализация алгоритма

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

Разрабатываемая программа представляет собой desktop-приложение и имеет достаточно простой интерфейс, который будет рассмотрен далее в статье.

Основная форма приложения разделена на две части (рис. 2). В левой части формы расположено окно для ввода зашифрованного текста. Зашифрованный текст может быть введен как вручную пользователем, так и загружен из файла. Под окном ввода расположено поле для выбора пользователем числа итераций генетического алгоритма.

Рисунок 2. Внешний вид основной формы приложения

Также для удобства тестирования необходима разработка программы шифрования с помощью гомофонического шифра. Программа также представляет собой desktop-приложение. В процессе шифрования удаляются все пробелы и знаки пунктуации, также все буквы приводится к нижнему регистру.

Результаты работы алгоритма

Разработанные программы позволяют оценить точность работы алгоритма дешифрования опытным путем. Для проверки качества работы алгоритма было подготовлено несколько тестов, в которых различались количество итераций алгоритма и количество символов в дешифруемом тексте. Результаты тестирования можно отобразить в виде графика (рис. 3).

Рисунок 3. Результаты тестирования

На графике видно, что высокая точность работы алгоритма достигается при количестве итераций (поколений) более 500. Однако в словах расшифрованного текста могут присутствовать небольшие ошибки, которые не мешают пониманию текста в целом.

Заключение

В ходе исследования был разработан алгоритм дешифрования гомофонического шифра. Алгоритм был протестирован с использованием специально разработанных программ шифрования и дешифрования гомофонического шифра.

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

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