Криптография 2018 Лекция 2

Выход: зашифрованное сообщение (ciphertext).

Алгоритм расшифрования:
Вход: исходное зашифрованное сообщение (ciphertext)

и ключ.
Выход: незашифрованное сообщение (plaintext).

В обоих алгоритмах используется один и тот же ключ.

алгоритм должен быть достаточно сильным, чтобы передаваемое зашифрованное сообщение невозможно

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

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

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

диапазоне статистических особенностей зашифрованного текста. Это достигается тем, что значение

каждого элемента незашифрованного текста влияет на значения многих элементов зашифрованного текста или, что то же самое, любой элемент зашифрованного текста зависит от многих элементов незашифрованного текста.

Конфузия - это уничтожение статистической взаимосвязи между зашифрованным текстом и ключом.

Если Х - это исходное сообщение и K - криптографический ключ, то зашифрованный передаваемый текст можно записать в виде Y = EK[X]. Обратное преобразование в этом случае будет выглядеть так: X = DK[Y].

шифрование блоками или шифрование потоком.
Блок текста рассматривается как неотрицательное целое

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

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

Табличная подстановка, при которой группа бит отображается в другую группу бит. Это так называемые S-box.

Перемещение, с помощью которого биты сообщения переупорядочиваются.

Операция сложения по модулю 2, обозначаемая XOR.

Операция сложения по модулю 232 или по модулю 216.

Циклический сдвиг на некоторое число бит.

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

получен по определенному алгоритму из ключа шифрования K.

Ключ раунда называется

подключом.

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

блок зашифрованного текста.
Число блоков длины n равно 2n. Для того

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

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

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

с другой стороны, достаточно просты и компактны. Сеть Фейстеля имеет следующую структуру.

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

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

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

Функция F называется образующей.

и побитового выполнения операции XOR результата F с другой ветвью.

После этого ветви меняются местами.

Считается, что оптимальное число раундов - от 8 до 32.

Важно то, что увеличение количества раундов значительно увеличивает криптостойкость алгоритма.

Сеть Фейстеля является обратимой даже в том случае, если функция F не является таковой.

В настоящее время все чаще используются различные разновидности сети Фейстеля для 128-битного блока с четырьмя ветвями. Увеличение количества ветвей, а не размерности каждой ветви связано с тем, что наиболее популярными до сих пор остаются 32-разрядные процессоры.

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

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

64-битными блоками, используя 56-битный ключ.
Процесс шифрования состоит из четырех этапов.
На

первом из них выполняется начальная перестановка ( IP ) 64-битного исходного текста (забеливание), во время которой биты переупорядочиваются в соответствии со стандартной таблицей.

Следующий этап состоит из 16 раундов одной и той же функции, которая использует операции сдвига и подстановки.

На третьем этапе левая и правая половины выхода последней (16-й) итерации меняются местами.

Наконец, на четвертом этапе выполняется перестановка IP-1 результата, полученного на третьем этапе. Перестановка IP-1 инверсна начальной перестановке.

каждой итерации получается промежуточное 64-битное значение.

Левая и правая части каждого

промежуточного значения трактуются как отдельные 32-битные значения, обозначенные L и R.

это произвольные 64 бита, то
X = IP(M) - переставленные 64

бита.

Если применить обратную функцию перестановки Y = IP-1(X) = IP-1(IP(M)), то получится первоначальная последовательность бит.

Первоначально ключ подается на вход функции перестановки.

Затем для каждого из 16 раундов подключ Ki является комбинацией левого циклического сдвига и перестановки.

Функция перестановки одна и та же для каждого раунда, но подключи Ki для каждого раунда получаются разные вследствие повторяющегося сдвига битов ключа.

Ki получаются по следующему алгоритму:
Для 56-битного ключа, используемого на входе

алгоритма, вначале выполняется перестановка в соответствии с таблицей (РС-1).

Полученный 56-битный ключ разделяется на две 28-битные части, обозначаемые как C0 и D0 соответственно.

На каждом раунде Ci и Di независимо циклически сдвигаются влево на 1 или 2 бита, в зависимости от номера раунда.

Полученные значения являются входом следующего раунда. Они также представляют собой вход в табличную перестановку (РС-2), которая и создает 48-битное выходное значение, являющееся подключем раунда.

но ключи Ki используются в обратной последовательности. K16 используется на

первом раунде, K1 используется на последнем раунде.

Пусть выходом i-ого раунда шифрования будет Li||Ri. Тогда соответствующий вход (16-i)-ого раунда расшифрования будет Ri||Li.

После последнего раунда процесса расшифрования две половины выхода меняются местами так, чтобы вход заключительной перестановки IP-1 был R16||L16.

Выходом этой стадии является незашифрованный текст.

их в качестве входа в алгоритм.
Известно, что IP и IP-1

взаимно обратны.

Следовательно, Ld0||Rd0 = IP (ciphertext)

Ciphertext = IP-1(R16||L16) Ld0||Rd0 = IP(IP-1(R16||L16)) = R16||L16

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

IP-1(R0||L0) = IP-1(IP (plaintext)) = plaintext, что и демонстрирует возможность расшифрования DES.

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

DES с двумя разными ключами. Используя незашифрованное сообщение P и два ключа K1 и K2, зашифрованное сообщение С можно получить следующим образом:
C = Ek2 [Ek1 [P]]
Для расшифрования требуется, чтобы два ключа применялись в обратном порядке:
P = Dk1 [Dk2 [C]]
В этом случае длина ключа равна 56 * 2 = 112 бит.

называемая атака "встреча посередине". Она основана на следующем свойстве алгоритма.

Мы имеем
С = Ek2 [Ek1 [P]] Тогда X = Ek1 [P] = Dk2 [C].

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

В этом случае, во-первых, шифруется Р для всех возможных K1, и упорядочивается по значению Х.

Следующий шаг состоит в расшифровании С, с применением всех K2.

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

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

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

Очевидное противодействие атаке "встреча посередине" состоит в использовании третьей стадии шифрования с тремя различными ключами. Это поднимает стоимость лобовой атаки до 2168. Но при этом длина ключа равна 56 * 3 = 168 бит, что иногда бывает громоздко.

В качестве альтернативы предлагается метод тройного шифрования, использующий только два ключа. В этом случае выполняется последовательность зашифрование-расшифрование-зашифрование.
C = EK1 [DK2 [EK1 [P]]]

Не имеет большого значения, что используется на второй стадии: шифрование или расшифрование. В случае использования дешифрования существует только то преимущество, что можно тройной DES свести к обычному одиночному DES, используя K1 = K2:
C = EK1 [DK1 [EK1 [P]]] = EK1 [P]