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

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

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

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

Абсолютно стойкая система обладает рядом свойств, выведенных Клодом Шенноном [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, ГОСТ 28 147–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].