Генерация сильных ключей шифрования изображений

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

Данная работа состоит из четырех глав, содержит три таблицы, 17 изображений и три приложения.

Оглавление

1.2 Требования к разрабатываемому программному обеспечению

При разработке Системы необходимо учесть необходимость сравнения различных методов шифрования. В качестве примеров могут выступать как стандартизированные алгоритмы AES [2] и DES, так и алгоритмы, разработанные энтузиастами - шифрование на основе эллиптических кривых или шифрование с использованием генетических алгоритмов.

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

Оригинальное изображение (необходима поддержка форматов JPEG, PNG).

Параметры работы алгоритма шифрования.

Параметры работы генетического алгоритма (количество эпох, размер популяции и т.д.).

Также необходима индикация работы алгоритма, в том числе отображение для пользователя промежуточных результатов. Пример интерфейса представлен на рисунке ниже (рис. 1.1):

Рисунок 1.1. Пример интерфейса главного окна системы

1.3 Экономическое обоснование решения

В качестве методики для определения стоимости разрабатываемой системы используется модель COCOMO (Constructive Cost Model) [3]. Данная модель использует простую формулу регрессии для определения трудоемкости, длительности и количества персонала, необходимого для разработки проекта.

Модель COCOMO выделяет следующие базовые уравнения:

Трудоемкость - a * (KLOC)b. Измеряется в человеко-месяцах

Длительность разработки - с * (Трудоемкость)d. Измеряется в месяцах.

Число разработчиков - Трудоемкость / длительность разработки.

Коэффициенты a, b, c, d определяются согласно таблице коэффициентов модели базового уровня (табл. 1.1).

Таблица 1.1. Коэффициенты для базовой модели COCOMO

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

Для данной работы выбрана органическая модель проекта, поскольку для проекта не выдвигаются жесткие требования, а команда разработки достаточно небольшая. Соответственно, выбраны следующие коэффициенты: a=2.4, b=1.05, c=2.5, d=0.38.

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

Таблица 1.2. Результаты анкетирования по оценке количества строк кода

Исходя из результатов анкетирования, определим KLOC = 1.54. После определения количества строк кода можно приступать к оценке трудозатрат по разработке данного программного обеспечения. Согласно формуле определения трудоемкости, сложность данного проекта составляет

2.4*1.541.05 = 3.78 человека-месяца.

Длительность разработки составляет

2.5*3.780.38 = 4.14 месяцев.

Количество разработчиков, необходимое для разработки данной системы составляет

3.78 / 4.14 = 1 (округленное вверх до целого) человек.

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

генерация шифрование изображение криптографический

2. Теоретическое обоснование решения для генерации сильных ключей шифрования изображений

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

2.1 Анализ существующих методов шифрования

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

Абсолютно стойкая система обладает рядом свойств, выведенных Клодом Шенноном [4]. Во-первых, ключ шифрования уникален и не может быть использован дважды. Это предотвращает расшифровку данных злоумышленником, если ранее какой-либо ключ был скомпрометирован. Кроме того, даже если ключ шифрования не был скомпрометирован, перехват нескольких сообщений, зашифрованных одним ключом, дает теоретическую возможность определения ключа шифрования, особенно если в качестве исходных данных используется текст на естественном языке, который, как известно, обладает избыточностью.

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

.

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

),

и определенного ранее свойства

следует .

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

В качестве ключа шифрования будет использоваться следующая строка: «Во-первых, ключ шифрования уникален и не может быть использован дважды». Для упрощения, из ключа будут убраны все пробелы и знаки препинания, все символы будут приведены к нижнему регистру и транслитерированы. Таким образом, итоговый ключ будет представлять следующую строку из 62 символов латинского алфавита «vopervyhkluchshifrovanyaunikaleninemozhetbytispolzovandvyazhедdy». Ниже представлен код для транслитерации данного ключа на языке Python:

TRANSLITERATION_MAP = {

'а': 'a', 'б': 'b', 'в': 'v', 'г': 'g', 'д': 'd', 'е': 'e', 'ё': 'e',

'ж': 'zh', 'з': 'z', 'и': 'i', 'й': 'i', 'к': 'k', 'л': 'l', 'м': 'm',

'н': 'n', 'о': 'o', 'п': 'p', 'р': 'r', 'с': 's', 'т': 't', 'у': 'u',

'ф': 'f', 'х': 'h', 'ц': 'ts', 'ч': 'ch', 'ш': 'sh', 'щ': 'sh',

'ъ': '', 'ы': 'i', 'ь': '', 'э': 'e', 'ю': 'u', 'я': 'ya'

}

def transliterate(s: str):

return ''.join(TRANSLITERATION_MAP.get(x, '') for x in s.lower())

Длина данного ключа 62 символа, поэтому все сообщения также будут содержать в себе 62 символа. Если сообщение оказывается длиннее, оно будет обрезано до 62 символов. В качестве шифруемых сообщений будут использоваться следующие предложения:

В шифровании, криптографическая стойкость - это мера способности криптографической (vshifrovaniikriptograficheskayastoikostetomerasposobnostikript).

Абсолютно стойкая система обладает рядом свойств, выведенных Клодом Шенноном

(absolutnostoikayasistemaobladaetryadomsvoistvvivedennihklodoms).

В качестве примера, попробуем зашифровать несколько предложений из данной работы

(vkachestveprimerapoprobuemzashifrovatneskolkopredlozheniiizdan).

Несмотря на отсутствие стандартизованных алгоритмов проверки сгенерированных

(nesmotryanaotsutstviestandartizovannihalgoritmovproverkisgener).

Существуют определенные наработки в сфере выявления стойкости сгенерированного

(sushestvuutopredelennienarabotkivsfereviyavleniyastoikostisgen).

Также стоит отметить, что алгоритмы проектируются таким образом, чтобы

(takzhestoitotmetitchtoalgoritmiproektiruutsyatakimobrazomchtob).

Шифрование непосредственно изображений осложняется тем, что изображениям

(shifrovanieneposredstvennoizobrazheniioslozhnyaetsyatemchtoizo).

Проецируя данный подход на шифрование изображений можно выделить следующую

(proetsiruyadanniipodhodnashifrovanieizobrazheniimozhnovidelits).

Таким образом, предлагается реализация Системы для определения стойкости

takimobrazompredlagaetsyarealizatsiyasistemidlyaopredeleniyast.

Кроме того, даже если ключ шифрования не был скомпрометирован, перехват

krometogodazheeslikluchshifrovaniyanebilskomprometirovanperehv.

Исходный код программы для проведения данного анализа представлен в приложении B.

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

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

Сообщения №3 (В качестве примера…) и №6 (Также стоит отметить…) содержат 12 одинаковых символов. В исходных сообщениях это символы h, e, s, t, m, e, o, i, r, o, t, o.

Сообщения №1 (В шифровании…) и №9 (Таким образом…) содержат 11 одинаковых символов. В исходных сообщениях это символы i, a, r, g, t, i, s, t, m, o, t.

Сообщения №5 (Существуют определенные наработки…) и №8 (Проецируя данный подход…) содержат девять одинаковых символов. В исходных сообщениях это символы s, u, n, a, e, a, e, n, i.

Существуют специальные частотные словари для различных языков, содержащие в себе информацию о статистическом распределении символов. Согласно информации Национального корпуса русского языка, частотность букв в русском языке распределяется следующим образом (табл. 2.1) [5].

Таблица 2.1. Частота распределения букв в русском языке

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

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

Для зашифрованных сообщений получилась следующая статистика по максимальной длине одинаковой подпоследовательности:

Сообщения №3 (В качестве примера…) и №6 (Также стоит отметить…) содержит подпоследовательность длиной четыре символа (hest). Необходимо уточнить, что данная строка не является подпоследовательностью в строгом смысле, поскольку из сообщений были убраны пробелы и некоторые символы после замены стали занимать две позиции. Данная строка образована словом «качестве» (kachestve) и словосочетанием «также стоит» (takzhestoit). Для того, чтобы корректно обрабатывать подобные случаи, необходимо собирать статистику по n-граммам с учетом склейки слов и транслитерации (в данном случае).

Сообщения №5 (Существуют определенные наработки…) и №9 (Таким образом…) содержит подпоследовательность длиной четыре символа (pred).

Сообщения №5 (Существуют определенные наработки…) и №8 (Проецируя данный подход…) содержат подпоследовательность длиной три символа (eni).

Даже согласно частотной статистике для символов русского языка, подпоследовательность eni достаточно хороша, потому что все ее буквы попадают в топ-5 частотной таблицы. Если же собрать статистику для n-грамм и отобрать наиболее вероятные n-граммы согласно частотной статистике для символов, можно сделать предположение о возможном содержании подстроки «eni» (вновь отмечаем тот факт, что злоумышленнику неизвестно значение подстроки, и все что он может делать - подбирать возможные варианты на основе частотного словаря или других статистических показателей).

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

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

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

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

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

Все алгоритмы шифрования, рассматриваемые в данной работе, относятся к системам шифрования с достаточной криптографической стойкостью.

Существует также разделение криптографических систем на симметричные и ассиметричные системы [6]. В симметричных криптографических системах используется один и тот же ключ для шифрования и дешифрования сообщения. Это накладывает определенные ограничения на коммуникацию участников, поскольку они должны заранее определиться не только с алгоритмом шифрования, но и убедиться, что ключ шифрования был передан по безопасному каналу, для предотвращения компрометации ключа. В качестве примера такой криптосистемы может выступать шифрование по принципу магического квадрата [7]. Магический квадрат - это квадрат со стороной N, в каждой из ячеек которого записано число от единицы до N*N. Все числа в магическом квадрате различны, а сумма чисел по строкам, столбцам и полным диагоналям равна одному и тому же числу. При шифровании символ на позиции i записывается в ячейку, содержащую в себе номер i. После записи всех символов в квадрат, все строки последовательно склеивались, в результате чего получалась перестановка исходного текста (если все ячейки квадрата оказались заполнены, в противном случае, пустые ячейки заменялись точками). Для расшифровки сообщения получатель должен знать расположение чисел в магическом квадрате.

Симметричные шифры, в свою очередь, подразделяются на блочные и поточные алгоритмы шифрования [8]. Блочный шифр подразумевает обработку блока исходного текста фиксированного размера за один раз. Если размер оставшегося сообщения меньше размера блока, данный блок дополняют данными. Примерами блочных алгоритмов шифрования выступают DES, AES, ГОСТ 28147-89 . Поточные шифры, в отличие от блочных, шифруют данные потоком, побайтово или побитово. Простейшая реализация представляет собой поток данных, генератор гаммы и шифратор. Пример работы поточного шифра представлен на рисунке ниже (рис. 2.1).

Рисунок 2.1. Блок-схема работы поточного шифра

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

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

Рисунок 2.2. Схема передачи сообщения с использованием асимметричного алгоритма шифрования

На данной схеме представлены три основных этапа шифрования с использованием публичного ключа. Боб (справа) генерирует пару ключей - публичный e и приватный d, после чего передает публичный ключ по открытому каналу Алисе (слева). Алиса шифрует сообщение m с использованием переданного публичного ключа и передает зашифрованное сообщение c по открытому каналу связи. Боб расшифровывает сообщение c, используя значение приватного ключа d.

Идея асимметричных криптографических систем заключается в сложности вычисления обратной функции. Допустим, нам известно значение x, которое мы хотим зашифровать при помощи вычисления функции f(x). Значение функции f(x) можно достаточно быстро вычислить, но узнать x только на основе f(x) невозможно за приемлемое время. Для того, чтобы сделать возможным расшифровку значения f(x) применяются специальные функции шифрования, поддерживающие, так называемую, лазейку. Зная значение y, можно восстановить значение x на основе значения f(x). На сегодняшний день, криптосистемы на основе асимметричного шифрования широко используются, в том числе в сетевых протоколах, таких как TLS, SSL, и SSH.

Преимущество ассиметричных систем шифрования заключается в том, что собеседникам достаточно обменяться публичными ключами, поскольку без приватных ключей зашифрованное сообщение невозможно будет расшифровать. Недостатком, по сравнению с симметричными шифрами является низкая скорость шифрования. Широко распространенным асимметричным алгоритмом шифрования является RSA, названный так в честь его авторов Rivest, Shamir и Adleman, базирующийся на невозможности факторизации больших чисел за разумное время. Данный алгоритм не накладывает ограничений на длину ключа, однако стоит отметить, что с увеличением вычислительной мощности, ужесточаются требования к длине ключа, который может быть использован для безопасной передачи данных. Так, начиная с 31 декабря 2013 года, Mozilla перестала поддерживать сертификаты с длиной ключа менее 2048 бит [9].

2.2 Анализ методов шифрования в контексте шифрования изображений

Поскольку блочные шифры оперируют блоками фиксированного размера, возникает проблема при обработке сообщений, длина которых превышает длину блока. Существует несколько подходов, решающих данную проблему. Самый простой из них - разбить все сообщение на блоки фиксированного размера и зашифровать каждый из них независимо от других. Данный метод называется ECB (Electronic Codebook) и обладает существенным недостатком, несмотря на возможность распараллеливания процессов шифрования и дешифрования, а также возможность чтения определенного блока зашифрованного сообщения без необходимости расшифровки всего сообщения. Поскольку каждый блок шифруется независимо от других, все одинаковые блоки после шифрования также будут совпадать. Особенно явно это проявляется при шифровании изображений.

В качестве примера попробуем зашифровать некоторое изображение с использованием метода ECB. Для упрощения, исходное изображение будет в формате Netpbm. Это достаточно простой формат изображения, который состоит из двух основных частей: заголовка и самого изображения. Заголовок описывает тип изображения, размеры в пикселях и максимальное значение каждого пикселя. В зависимости от типа изображения, некоторые поля заголовка могут быть опущены. Тело изображения последовательно описывает каждый пиксель изображения. Таким образом, можно достаточно просто закодировать тело изображения, не изменяя его заголовок, чтобы зашифрованное изображение было корректно распознано программой просмотра изображений.

Рисунок 2.3. Исходное изображение

Изображение выше (рис. 2.3) содержит достаточно большое количество повторяющихся частей, поэтому ожидается, что после шифрования данного изображения надпись «TOP SECRET» останется видимой. Для начала переведем данное изображение в формат ppm. Сделать это можно следующей командой при помощи пакета ImageMagic:

convert top_secret.jpg top_secret.ppm.

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

head -n 3 top_secret.ppm > header.txt

tail -n +4 top_secret.ppm > body.bin

Первая команда копирует первые три строки заголовка из файла top_secret.ppm в файл header.txt. Вторая команда копирует все строки, начиная с четвертой в файл body.bin.

После разделения изображения на заголовок и на тело, можно зашифровать тело изображения при помощи библиотеки openssl. Следующая команда шифрует файл body.bin, при помощи алгоритма AES-128, используя ECB, помещая тело зашифрованного изображения в файл body.ecb.bin:

openssl enc -aes-128-ecb -nosalt -pass pass:»TOP SECRET» -in body.bin -out body.ecb.bin

После того, как тело изображения было зашифровано, необходимо добавить к нему заголовок и преобразовать данное изображение обратно в jpg:

cat header.txt body.ecb.bin > top_secret.ecb.ppm

convert top_secret.ecb.ppm top_secret.ecb.jpg

В итоге, после выполнения всех команд, зашифрованное изображение, расположенное в файле top_secret.ecb.jpg выглядит следующим образом (рис. 2.4). На данном изображении достаточно отчетливо видны границы исходного изображения. Надпись, присутствующая на исходном изображении все еще может быть прочитана.

Рисунок 2.4. Изображение, зашифрованное при помощи метода ECB

Проблема с ECB проявляет себя не только при работе с изображениями. В 2013 году, корпорация Adobe сообщила об утечке пользовательских данных для 38 миллионов аккаунтов. Пароли пользовательских аккаунтов были зашифрованы с использованием ECB [10], что позволило злоумышленникам собрать статистику по зашифрованным паролям, после чего соотнести эту информацию со статистикой по самым распространенным паролям. Эта информация, вкупе с подсказками к паролю, которые хранились в открытом виде, позволила злоумышленникам получить незашифрованный пароль с хорошей долей вероятности, несмотря на то, что ключ шифрования не был скомпрометирован.

Поэтому вместо ECB чаще используются другие режимы шифрования, к примеру, режим сцепления блоков шифротекста (Cipher block chaining, CBC). На диаграмме ниже представлена схема работы режима CBC (рис. 2.5)

Рисунок 2.5. Блок-схема работы режима CBC

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

Для того, чтобы на примере показать различия между режимами ECB и CBC, вновь зашифруем ранее представленное изображение с фразой «Top secret». Для этого изменим параметр шифрования для команды openssl на -aes-128-cbc. На рисунке ниже представлено изображение, зашифрованное в режиме CBC (рис. 2.6).

Рисунок 2.6. Изображение, зашифрованное в режиме CBC

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

2.3 Анализ работы генетического алгоритма

Эволюционные алгоритмы - семейство алгоритмов, реализующих принципы естественного отбора. Данные алгоритмы часто применяются для решения оптимизационных задач или для решения NP-полных задач (задача коммивояжера). Генетический алгоритм - один из примеров эволюционных алгоритмов. Данный подход внедряет несколько новых определений:

Генотип (особь) - вектор, описывающий решение оптимизируемой задачи. Не требуется, чтобы данное решение было самым оптимальным.

Популяция - набор генотипов.

Фитнес-функция - функция от генотипа, вычисляющая выживаемость (приспособляемость) данного генотипа.

Схема работы генетического алгоритма состоит из нескольких простых этапов:

Генерация начальной популяции.

Вычисление значения фитнес функции для каждого генотипа в популяции.

Разделение популяции на две группы - выжившие и умершие генотипы. Все умершие генотипы исключаются из популяции.

Генерация новых генотипов для популяции:

Случайная генерация генотипа.

Скрещивание нескольких выживших генотипов.

Мутация выжившего или нового генотипа.

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

Результатом работы алгоритма является наиболее приспособленный генотип (на основе фитнес-функции) из текущей популяции.

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

Помимо выбора родителей, также играет роль очередность процесса скрещивания. Если скрещивание происходит после селекции, т.е. когда из популяции уже удалены все «умершие» особи, то в качестве родителей для данной особи будут выбраны только выжившие генотипы. Это может отрицательно сказаться на всей работе алгоритма, поскольку вся популяция может скатиться в локальный максимум (или минимум), после чего все новые особи будут проигрывать наилучшему решению (которое, на самом деле, не является решением всей задачи), в результате чего вся популяция будет забиваться копиями локального оптимума. Существуют различные подходы, позволяющие избежать данной ситуации. Самый простой - проводить скрещивание не только из выживших особей, но и из умерших. Это позволит разнообразить популяцию и позволит избежать локальных решений. Также можно проводить мутацию новой особи, внося, таким образом, разнообразие в генетический фонд.

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

3. Проектирование системы для генерации сильных ключей шифрования изображений

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

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

На изображении ниже (рис. 3.1) представлена диаграмма прецедентов для данной Системы.

Рисунок 3.1. Диаграмма прецедентов разрабатываемой Системы

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

После разработки диаграммы прецедентов были построены диаграммы последовательности для основных действий в Системе. На изображении ниже (рис. 3.2) представлена диаграмма последовательности для запуска процесса шифрования изображения:

Рисунок 3.2. Диаграмма последовательности для шифрования изображения

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

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

Рисунок 3.3. Диаграмма последовательности для запуска процесса дешифрования изображения

На изображении ниже (рис. 3.4) представлена диаграмма классов для реализации генетического алгоритма. Выделяются интерфейсы GeneticSolver, Population Phenotype. Для каждого интерфейса приводится реализация: ImageDecryptionGeneticSolver, ImagePopulation, ImagePhenotype. Кроме того, представлен интерфейс EpochCompletedListener для уведомления клиента о завершении эпохи генетического алгоритма и класс GaParams, содержащий в себе параметры работы генетического алгоритма.

Рисунок 3.4. Диаграмма классов для реализации генетического алгоритма

3.1 Выбор технологий, используемых для разработки Системы

Поскольку система будет реализована как Web-приложение, будет разумным выбрать в качестве инструмента разработки язык, который уже продолжительное время используется для разработки Web-приложений. Это не только сократит сроки разработки, но и упростит дальнейшую поддержку проекта.

3.1.1 Язык разработки Java

В качестве основного языка для разработки серверной части приложения используется язык программирования Java. Это объектно-ориентированный язык программирования общего назначения, изначально разработанный компанией Sun Microsystems в 1995 году. В настоящее время принадлежит компании Oracle Corporation. Согласно рейтингу TIOBE за апрель 2017 г, язык Java занимает первое место по популярности.

3.1.2 Spring Framework

В качестве фреймворка для разработки серверных приложений используется набор библиотек Spring Framework. Это фреймворк с открытым исходным кодом для разработки приложений на платформе Java, впервые представленный в 2002 году. Данный фреймворк включает в себя множество модулей для разработки Web-ориентированных приложений, таких как:

Spring Core Container - модуль, обеспечивающий реализацию модели разработки с использованием инверсии зависимостей (Inversion of Control. IoC)

Messaging - модуль, обеспечивающий работу с очередями сообщений и взаимодействие с клиентом при помощи технологии WebSocket.

MVC - модуль, обеспечивающий реализацию традиционного подхода разработки Web приложений - Model_View_Controller. Также облегчает создание RESTful приложений.

Поскольку в данной работе не используются модули для работы с базой данных, AOP, в списке выше они были опущены.

3.1.3 Сервер приложений Tomcat

Для запуска приложения используется контейнер сервлетов Apache Tomcat 8. Это Web_сервер, реализованный с помощью языка программирования Java. Первая версия контенера была выпущена в 1999 году и с тех пор находится в активной разработке. Tomcat предоставляет следующие компоненты: Catalina - контейнер сервлетов, Coyote - компонент, обеспечивающий поддержку протокола HTTP и Jasper - движок для обработки JavaServer Pages (JSP).

3.1.4 Язык разработки JavaScript

Для разработки клиентской части Web-приложения используется язык программирования JavaScript, стандартизованный в спецификации ECMAScript. Первая версия этого языка была выпущена в 1995 году. В отличие от ряда других языков программирования, ни одна компания не владеет правами на язык JavaScript.

3.1.5 jQuery

Также для разработки клиентской части Web-приложения используется библиотека с открытым исходным кодом jQuery. Первая версия данной библиотеки выпущена в 2006 году. Библиотека jQuery позволяет упростить разработку за счет предоставления легковесного интерфейса для управления DOM деревом. Кроме того библиотека предоставляет широкие возможности для работы с сервером с использованием подхода AJAX (Asynchronous Javascript and XML).

3.1.6 REST API

REST (Representational State Transfer, передача состояния представления) - архитектурный стиль взаимодействия компонентов приложения. Не существует официального стандарта для протоколов построенных на базе REST, поскольку, в отличие от SOAP, REST является архитектурным стилем, но не протоколом. За счет этого, приложения, построенные на базе архитектуры REST, могут достаточно гибко эволюционировать, подстраиваясь под новые требования. REST архитектура требует соблюдения следующих условий:

Модель клиент-сервер. Поскольку Система реализована в качестве Web приложения, данное условие автоматически выполняется.

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

Кэширование. Система может кэшировать результат для ускорения расчетов. В данной работе указанное условие не является релевантным.

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

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

Код по требованию. Позволяет расширять функциональность клиента Системы за счет загрузки с сервера ресурсов в виде апплетов или скриптовых сценариев. Данное условие выполняется, функциональность клиента будет расширена путем выполнения сценариев на языке JavaScript, загружаемых с сервера.

3.1.7 WebSocket

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

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

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

Для реализации данного приложения предлагается использовать стандартную архитектуру, используемую для разработки Web-приложений с использованием фреймворка Spring Boot. Для этого вынесем все компоненты в отдельные пакеты:

Пакет config. Содержит классы для настройки конфигурации приложения.

Пакет domain. Содержит классы, описывающие сущности данной предметной области.

Пакет encrypter. Содержит классы, реализующие интерфейс шифратора.

Пакет ga. Содержит классы для работы с генетическим алгоритмом.

Пакет service. Содержит все сервисы приложения.

Пакет util. Содержит вспомогательные классы.

Пакет web. Содержит классы, реализующие логику взаимодействия с клиентом.

4.1 Реализация генетического алгоритма

Общая диаграмма работы генетического алгоритма представлена на рисунке ниже (рис. 4.1).

Рисунок 4.1. Схема работы генетического алгоритма

Для реализации генетического алгоритма выделим общий интерфейс GaSolver, содержащий в себе следующие методы:

solve(params) - запускает генетический алгоритм с указанными параметрами.

onEpochCompleted(listener) - добавляет обработчик события завершения эпохи генетического алгоритма.

interrupt() - прерывает выполнение текущего алгоритма.

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

Рисунок 4.2. Диаграмма классов для паттерна Наблюдатель

Для реализации текущей задачи нет необходимости хранить информацию обо всех подписчиках на событие, поэтому метод onEpochCompleted позволит регистрировать только одного подписчика. Это избавляет от необходимости реализовывать логику для удаления подписчиков. Пример использования метода onEpochCompleted представлен ниже:

ImageDecryptionGeneticSolver solver = new ImageDecryptionGeneticSolver();

solver.onEpochCompleted((currentEpoch, population) -> {

ImagePhenotype bestSolution = population.getBestSolution();

byte[] encryptedImageData = ImageUtils.toByteArray(bestSolution.getImage());

TemporaryFile encryptedImageFile = fileService.putFile(

new TemporaryFile(encryptedImageData, bestSolution.getImage()));

ImageDto imageDto = new ImageDto(encryptedImageFile.getUuid());

imageDto.setFitness(bestSolution.getFitness())

.setEpoch(currentEpoch)

.setKey(bestSolution.getEncryptionKey());

webSocketResource.updateEncryptedImage(imageDto);

});

В данном примере после завершения каждой эпохи сервер уведомит клиента по протоколу WebSocket об измененном изображении.

Также, для передачи параметров необходимо добавить класс GaParam, содержащий следующие методы:

initialPopulation - начальная популяция.

epochsNum - количество эпох.

encryptedImage - зашифрованное изображение.

encrypter - класс шифратора.

encryptionType - тип шифрования.

Дополнительно, необходимо описать интерфейс Phenotype с методом getFitness, чтобы иметь возможность определять значение фитнес функции для конкретного генотипа. Чтобы объединить несколько особей в популяцию, необходимо описать интерфейс Population со следующими методами:

getPhenotypes - возвращает список особей в популяции.

addPhenotypes - добавляет новых особей в популяцию.

replaceWorstPhenotypes - убирает из популяции N худших особей и добавляет в нее новых особей.

getBestSolution - возвращает лучшую особь из популяции.

getSize - возвращает количество особей в популяции.

Реализация представленного ранее класса GeneticSolver располагается в файле ImageDecryptionGeneticSolver. Базовая реализация каждой эпохи состоит из двух шагов:

Вычисление значения фитнес-функции для каждой необработанной ранее особи.

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

Для упрощения, предполагаем, что нам известна длина ключа, а сам ключ представляет собой перестановку длины N. Таким образом, мутация ключа происходит следующими способами:

Ключ циклически сдвигается на определенное значение. К примеру, если текущая перестановка [1,2,5,9,8,6,0,7,3,4], то после сдвига перестановки вправо на два элемента получится перестановка [3,4,1,2,5,9,8,6,0,7].

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

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

Сдвигается блок заданного размера внутри ключа. К примеру, если текущая перестановка [1,2,5,9,8,6,0,7,3,4], то после сдвига блока ключа [5, 9] вправо на два элемента получится перестановка [1,2,8,6,5,9,0,7,3,4].

Скрещивание двух ключей работает по следующему алгоритму:

Каждый ключ разбивается на две части в одном и том же месте.

В итоговый ключ переходит первая часть из первого ключа и вторая часть из второго ключа.

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

4.2 Реализация модуля шифрования изображений

Для реализации модуля шифрования изображений необходимо описать интерфейс Encrypter с двумя методами: