Максимизация пропускной способности симметричных алгоритмов шифрования ГОСТ и DES
Автор работы: Пользователь скрыл имя, 30 Апреля 2013 в 15:52, дипломная работа
Краткое описание
Рассматриваемые в работе алгоритмы шифрования основаны на работе сети
Фейстеля. Рассмотрим конструкцию блочного шифра, действующего по схеме
Фейстеля (см. Рис. 1). Информация, которую необходимо зашифровать, представлена
в двоичном виде как последовательность нулей и единиц:
Рис. 1: Схема сети Фейстеля
− Вся информация разбивается на блоки фиксированной длины. (В случае если
длина входного блока меньше, чем размер, который шифруется заданным
алгоритмом, то блок удлиняется каким-либо способом). Как правило, длина
блока является степенью двойки, например 64 бита (ГОСТ и DES). Далее
будем рассматривать операции происходящие только с одним блоком, так как
с другими в процессе шифрования выполняются те же самые операции.
Содержание
1 Введение
4
Сеть Фейстеля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
Алгоритм ГОСТ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
Алгоритм DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2 Основные понятия и результаты
7
Определения и постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . .
7
Алгоритм оптимизированного перебора . . . . . . . . . . . . . . . . . . . . . .
8
Алгоритм выноса за скобки . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Глубина и площадь схем . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Схема ГОСТ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Пропускная способность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Схема DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 Доказательства утверждений
15
Список литературы
16
Вложенные файлы: 1 файл
Московский Государственный Университет
им. М.В.Ломоносова
Механико-математический факультет
Кафедра математической теории интеллектуальных систем
Дипломная работа
Максимизация пропускной способности симметричных
алгоритмов шифрования ГОСТ и DES
Выполнила: Верховская А.П.
Научный руководитель: Галатенко А.В.
Рецензент: Гасанов Э.Э.
Москва
2010
Аннотация
В связи с увеличением скорости передачи данных по сети появилась
проблема увеличения скорости шифрования данных. В данной работе рассмотрены
алгоритмы симметричного шифрования, основанные на сети Фейстеля, такие
как ГОСТ 28147-89 и Data Encryption Standard (DES). Ставится задача
максимизации пропускной способности аппаратной реализации данных алгоритмов.
Схемы оптимизируются по глубине, что влечет и уменьшение площади.
Сложность составляет нахождение оптимальных схем для S-блоков, участвующих
в алгоритмах шифрования. Схемы для них строятся на основе минимальной
ДНФ булевой функции. Реализован алгоритм оптимизированного перебора
для нахождения минимальной ДНФ функции. Также реализован алгоритм
дальнейшего упрощения сложности схемы, построенной по минимальной ДНФ,
вынос за скобки общих частей элементарных конъюнкций. Посчитано численное
значение пропускной способности алгоритмов и представлена схема их реализации.
Для сравнения посчитана пропускная способность программной реализации
изучаемых алгоритмов.
2
Содержание
1 Введение
4
Сеть Фейстеля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
Алгоритм ГОСТ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
Алгоритм DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2 Основные понятия и результаты
7
Определения и постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . .
7
Алгоритм оптимизированного перебора . . . . . . . . . . . . . . . . . . . . . .
8
Алгоритм выноса за скобки . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Глубина и площадь схем . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Схема ГОСТ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Пропускная способность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Схема DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 Доказательства утверждений
15
Список литературы
16
Приложение
17
3
1 Введение
Рассматриваемые в работе алгоритмы шифрования основаны на работе сети
Фейстеля. Рассмотрим конструкцию блочного шифра, действующего по схеме
Фейстеля (см. Рис. 1). Информация, которую необходимо зашифровать, представлена
в двоичном виде как последовательность нулей и единиц:
Рис. 1: Схема сети Фейстеля
− Вся информация разбивается на блоки фиксированной длины. (В случае если
длина входного блока меньше, чем размер, который шифруется заданным
алгоритмом, то блок удлиняется каким-либо способом). Как правило, длина
блока является степенью двойки, например 64 бита (ГОСТ и DES). Далее
будем рассматривать операции происходящие только с одним блоком, так как
с другими в процессе шифрования выполняются те же самые операции.
− Выбранный блок делится на два равных подблока - левый L
i
и правый R
i
.
− Левый подблок L
i
видоизменяется функцией f(L
i
,K
i
) в зависимости от
раундового ключа K
i
, после чего он складывается по модулю 2 с правым
подблоком R
i
.
− Результат сложения присваивается новому правому подблоку R
i+1
, который
будет половиной входных данных для следующего раунда, а правый подблок
R
i
присваивается без изменений новому левому подблоку L
i+1
, который будет
другой половиной.
− После чего операция повторяется N − 1 раз, при этом при переходе от одного
этапа к другому меняются раундовые ключи (K
0
на K
1
и т. д.) по какому-либо
математическому правилу, где N
количество раундов в заданном алгоритме.
4
Отечественный алгоритм шифрования ГОСТ 28147-89 [1] шифрует данные 64-
битными блоками с использованием 256-битного ключа шифрования. Выполняется
32 раунда преобразований, в каждом из которых предусмотрены следующие
операции:
1. Один из 32-битных подблоков данных складывается с 32-битным значением
ключа раунда K
i
по модулю 2
32
.
2. Результат предыдущей операции разбивается на 8 фрагментов по 4 бита,
которые параллельно прогоняются через 8 таблиц замен S
1
...S
8
. Пример
возможных таблиц замен (используются Центральным банком РФ):
№ S-блока
Значение
1
4
10 9
2 13 8 0
14 6
11 1
12 7
15 5
3
2
14 11 4
12 6
13 15 10 2
3 8
1 0
7 5
9
3
5
8 1
13 10 3 4
2 14 15 12 7 6
0 9
11
4
7
13 10 1 0
8 9
15 14 4 6
12 11 2 5
3
5
6
12 7
1 5
15 13 8 4
10 9
14 0
3 11 2
6
4
11 10 0 7
2 1
13 3
6 8
5 9
12 15 14
7
13 11 4
1 3
15 5
9 0
10 14 7 6
8 2
12
8
1
15 13 0 5
7 10 4 9
2 3
14 6
11 8
12
3. 4-битные фрагменты (после замен) объединяются обратно в 32-битный подблок,
значение которого циклически сдвигается влево на 11 бит.
4. Обработанный предыдущими операциями подблок накладывается на необработанный
с помощью побитовой логической операции исключающее или (XOR).
5. Подблоки меняются местами.
Процедура расширения ключа в алгоритме ГОСТ 28147-89, фактически,
отсутствует: в раундах шифрования последовательно используются 32-битные
фрагменты K
1
...K
8
исходного 256-битного ключа шифрования в следующем
порядке: K
1
,K
2
,K
3
,K
4
,K
5
,K
6
,K
7
,K
8
, –– за исключением последних 8 раундов ––
в раундах с 25-го по 31-й фрагменты используются в обратном порядке.
Расшифрование полностью аналогично зашифрованию, но с другим порядком
использования фрагментов ключа:
• в прямом порядке
в первых 8 раундах;
• в остальных раундах
в обратном порядке.
В алгоритме DES [2] используются прямое преобразование сетью Фейстеля в
шифровании (см. Рис. 1) и обратное преобразование сетью Фейстеля в расшифровании.
Исходный текст
блок 64 бит. Процесс шифрования состоит в начальной
перестановке, 16 циклах шифрования и конечной перестановке. Шифрованный
текст
блок 64 бит. Рассмотрим подробную схему алгоритма DES:
5
1. Исходный текст T (блок 64 бит) преобразуется c помощью начальной перестановки
IP(Initial Permutation), которая определяется таблицей:
58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7
2. Полученный после начальной перестановки 64-битовый блок IP(T) участвует в
16-циклах преобразования Фейстеля, них функция f играет роль шифрования.
Рассмотрим подробно функцию f. Аргументами функции f являются 32-
битовый вектор R
i
и 48-битовый ключ K
i
. Для вычисления функции f
используются функция расширения , преобразование S, состоящее из 8
преобразований S-блоков, и перестановка P.
3. Функция расширяет 32-битовый вектор R
i
до 48-битового вектора E(R
i
) путём
дублирования некоторых битов из R
i
. Порядок битов вектора E(R
i
) указан в
таблице:
32 1
2 3
4 5
4 5
6 7
8 9
8 9
10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
4. Полученный после перестановки блок E(R
i
) складывается по модулю 2 с
ключами K
i
и затем представляется в виде восьми последовательных блоков
B
1
,B
2
,...,B
8
. E(R
i
) = B
1
B
2
...B
8
5. Каждый B
j
является 6-битовым блоком. Далее каждый из блоков B
j
трансформируется
в 4-битовый блок B
j
с помощью преобразований S
j
. Преобразования S
j
определяются таблицей:
S
1
14 4 13 1 2
15 11 8 3
10 6
12 5
9 0 7
0
15 7
4 14 2 13 1 10 6 12 11 9
5 3 8
4
1 14 8 13 6 2
11 15 12 9
7 3
10 5 0
15 12 8
2 4
9 1
7 5
11 3
14 10 0 6 13
S
2
15 1 8
14 6
11 3
4 9
7 2
13 12 0 5
10
3
13 4
7 15 2 8
14 12 0 1
10 6
9 11 5
0
14 7
11 10 4 13 1 5
8 12 6 9
3 2
15
13 8 10 1 3
15 4
2 11 6 7
12 0
5 14 9
S
3
10 0 9
14 6 3 15 5 1
13 12 7 11 4 2
8
13 7 0
9 3 4 6
10 2
8 5
14 12 11 15 1
13 6 4
9 8 15 3
0 11 1 2
12 5
10 14 7
1
10 13 0 6 9 8
7 4
15 14 3 11 5 2
12
6
S
4
7
13 14 3 0
6 9
10 1
2 8 5 11 12 4
15
13 8 11 5 6
15 0
3 4
7 2 12 1
10 14 9
10 6 9
0 12 11 7
13 15 1 3 14 5
2 8
4
3
15 0
6 10 1 13 8 9
4 5 11 12 7 2
14
S
5
2
12 4
1 7
10 11 6 8
5 3
15 13 0 14 9
14 11 2
12 4
7 13 1 5
0 15 10 3
9 8
6
4
2 1
11 10 13 7
8 15 9 12 5 6
3 0
14
11 8 12 7 1
14 2
13 6
15 0
9 10 4 5
3
S
6
12 1 10 15 9 2 6
8 0
13 3
4 14 7 5
11
10 15 4
2 7 12 9
5 6
1 13 14 0
11 3
8
9
14 15 5 2 8 12 3 7
0 4
10 1
13 11 6
4
3 2
12 9 5 15 10 11 14 1
7 6
0 8
13
S
7
4
11 2
14 15 0 8
13 3
12 9 7 5
10 6 1
13 0 11 7 4
9 1
10 14 3 5 12 2
15 8 6
1
4 11 13 12 3 7
14 10 15 6 8 0
5 9 2
6
11 13 8 1
4 10 7 9
5 0 15 14 2 3 12
S
8
13 2 8
4 6
15 11 1 10 9 3
14 5
0 12 7
1
15 13 8 10 3 7
4 12 5 6
11 0
14 9
2
7
11 4
1 9
12 14 2 0
6 10 13 15 3 5
8
2
1 14 7 4
10 8
13 15 12 9
0 3
5 6
11
6. Значение функции f(R
i
,K
i
) (32 бит) получается перестановкой , применяемой
к 32-битовому блоку B
1
B
2
...B
8
. Перестановка задана таблицей:
16 7
20 21 29 12 28 17
1 15 23 26 5 18 31 10
2 8
24 14 32 27 3 9
19 13 30 6
22 11 4 25
При расшифровании данных все действия выполняются в обратном порядке.
В 16 циклах расшифрования, в отличие от шифрования c помощью прямого
преобразования сетью Фейстеля, используется обратное преобразование сетью
Фейстеля.
В настоящее время скорость передачи данных по сети выше скорости шифрования.
Встает задача увеличения скорости шифрования. Достаточно быстрых реализаций в
интернете найти не удалось, поэтому в работе предлагаются собственные методы.
А именно, составляется аппаратная реализация алгоритмов и оценивается ее
пропускная способность.
2 Основные понятия и результаты
Определение. Глубина вершины в схеме
это максимальная длина пути из
входов в эту вершину. Глубиной схемы назовем максимальную из глубин ее
выходных вершин.
Определение. Сложность (площадь) схемы
это число функциональных элементов
в схеме.
7
Задача состоит в синтезе схем для алгоритмов ГОСТ и DES, т.е. построении
схем минимальной глубины. Рассмотрим функции, участвующие в формировании
этих алгоритмов:
− Сумма по mod 2
32
. Существующая оценка глубины сумматора
11 [7].
− XOR (исключающее ИЛИ). Это сумма по mod 2, глубина ее схемы равна 2.
− Перестановки и сдвиги битов не влияют на глубину схемы, это просто
переключения контактов.
− S-блоки. Здесь и возникает сложность аппаратной реализации.
Рассмотрим работу S-блоков подробнее. S-блоки ГОСТа и DES
это 4
булевых функции от 4 и, соотвественно, 6 переменных. Для базиса, состоящего из
стандартных элементов отрицания, конъюнкции и дизъюнкции, можно рассматривать
задачу оптимального синтеза как задачу о синтезе функциональной схемы, соот-
ветствующей минимальной аналитической записи функции. Решение этой задачи
сводится к нахождению минимальной ДНФ или минимального скобочного выражения
для данной функции. После этого осуществляется синтез функциональной схемы по
найденной записи собственной функции [6].
Определение. [4] ДНФ, реализующая функцию и имеющая минимальное число
букв переменных в записи, называется минимальной.
Определение. [5] ДНФ, являющаяся дизъюнкцией всех простых импликант
функции, называется сокращенной ДНФ.
Определение. [4] Простой импликантой функции называется элементарная
конъюнкция, соответствующая максимальному интервалу.
Определение. [5] Интервал называется максимальным, если он содержится во
множестве единиц функции и не существует интервала большей размерности,
который бы его содержал.
Определение. [5] ДНФ функции называется тупиковой, если ей соответствует
неприводимое покрытие подмножества единиц функции. Покрытие подмножества
единиц функции максимальными интервалами называется неприводимым, если
после удаления из него любого интервала оно перестает быть покрытием.
Процесс построение минимальных ДНФ [5]:
1. Выделяются все максимальные интервалы и строится сокращенная ДНФ.
2. Строятся все тупиковые ДНФ.
3. Среди всех тупиковых ДНФ выделяются все минимальные ДНФ.
На этом процессе и основан реализованный перебор. Итак, задана булева
функция от n переменных в виде столбца значений. Требуется найти минимальную
ДНФ этой функции. Способ решения поставленной задачи
оптимизированный
полный перебор:
8
1. Генерируем все элементарные конъюнкции от n переменных.
2. Сортируем элементарные конъюнкции в порядке возрастания их сложности в
список.
3. Оставляем в списке элементарных конъюнкций только простые импликанты
функции. Для этого отбрасываем элементарные конъюнкции, принимающие
значение 1 на нулях функции, и те, что не соответствуют максимальным
интервалам функции, т.е. если K
i
⊂ K
j
, то удаляем из списка конъюнкцию
K
j
.
4. Перебираем ДНФ, реализующие функцию, и выбираем минимальную:
• Генерируем ДНФ как цепочку конъюнктов.
Работаем одновременно с тремя стэками: в первом находятся порядковые
номера из списка элементарных конъюнкций, во втором
столбец длиной
2
n
, в котором отмечены покрытые единицы функции данным набором
элементарных конъюнкций, и в третьем хранится число покрытых единиц.
На нулевом шаге в цепочке нет ни одной элементарной конъюнкции и
сложность минимальной ДНФ равна ∞. Рассмотрим ситуацию, что мы
находимся в i-том положении, т.е. мы набрали цепочку из i элементарных
конъюнкций, которые покрыли m
i
единиц функции. Чтобы добавить
следущий член цепочки мы должны проверить 3 условия:
– Добавляем элементарные конъюнкции только в порядке возрастания
их порядковых номеров в списке. Элементарную конъюнкцию можно
добавить, только если при её добавлении сложность цепочки не станет
больше сложности минимальной ДНФ, имеющейся на данном шаге. В
противном случае мы делаем откат назад к (i−1) шагу, т.к. проверять
дальнейшие элементарные конъюнкции бессмысленно, их сложность
заведомо больше.
– Если сложность нам позволяет добавить еще один член, то рассматриваем
множество единиц, которые он покрывает. Если он добавляет новые,
то добавляем его в цепочку, иначе рассматриваем следующую в списке
элементарную конъюнкцию и начинаем проверку заново.
– Если мы добавили новый член в цепочку, то смотрим число единиц,
которые она покрывает, если оно совпадает с числом единиц функции,
то мы получили минимальную ДНФ i-го шага. Она получилась лучше
имеющейся на данный момент минимальной ДНФ, значит теперь
рассматриваем ее в качестве минимальной ДНФ. Делаем откат назад
к (i − 1) шагу.
• По окончании перебора мы получим минимальную ДНФ функции.
Теорема. Описанный алгоритм корректен.
Для дальнейшего упрощения схемы можно реализовать вынос за скобки общих
частей элементарных конъюнкций, это съэкономит нам число фукнцинальных
элементов, т.е. уменьшит площадь схемы, следовательно и ее глубину. Для
решения этой задачи используется так называемый жадный алгоритм. Функция
9
реализована рекурсивно, на вход к ней поступает ДНФ в виде цепочки элементарных
конъюнкций, на выходе она дает строку
скобочное выражение функции. Итак:
char f(ДНФ)
{
Найти пару конъюнктов с максимальным пересечением T, длина пересечения T
l
;
if(T
l
==0)
{
Превратить ДНФ в строку;
Вернуть строку;
}
else
{
Составить список L
1
из тех конъюнкций, у которых можно вынести
конъюнкт T;
Вынести конъюнкт T из конъюнкций из списка L
1
;
Составить список L
2
из тех конъюнкций, у которых нельзя вынести
конъюнкт T;
Составить строку следующего вида:
T(в строковом представлении)"("f(L
1
)")V"f(L
2
);
Вернуть строку;
}
}
Далее следует учесть, что S-блок
это булев оператор. Значит среди четырех
булевых функций возможно использование в схемах одинаковых функциональных
элементов. Следовательно организуем поиск общих подстрок по четырем строкам
(скобочная запись функции).
Применяя данные алгоритмы к S-блокам ГОСТа, получим глубину схем
равную 5. Площадь же получилась равной:
S
1
S
2
S
3
S
4
S
5
S
6
S
7
S
8
32 30 39 30 33 35 29 33
Полученные схемы реализованы на языке Verilog (см. Приложение). Для сравнения,
если построить схему этих S-блоков по СДНФ соответствующих функций, то
площадь схем будет равной 124.
Применяя же данные алгоритмы к S-блокам DES, получим глубину схем
равную 7. Площадь:
S
1
S
2
S
3
S
4
S
5
S
6
S
7
S
8
219 216 220 218 224 237 233 211
Схемы этих S-блоков, построенные на основе СДНФ имеют площадь равную 764.
Построим схему для ГОСТа (см. Рис. 2), исходя из ограничений в 40 уровней
логики. Глубина базового цикла равна 17 (сумматор 11, S-блоки 5 и XOR 2).
Следовательно за один такт алгоритм просчитает два цикла. На вход пользователь
подает сообщение, 64 бита открытого текста и управляющий бит, который указывает
алгоритму откуда брать данные: со входа или с задержки (предыдущего такта). Если
управляющий бит равен 1, то на вход схемы подаются заданные пользователем 64
бита, и обнуляется счетчик тактов. По окончании двух циклов счетчик увеличивается
10
Рис. 2: Схема ГОСТ
11
на единицу, его 4-ый бит определяет готовность шифр-текста. Как только бит
станет равным 1, т.е. пройдет 16 парных циклов (32 раунда ГОСТа), на выход
подастся готовое зашифрованное сообщение, 64 бита шифр-текста. Из соображений
безопасности, пока шифр-текст не готов, на выход подается 0. Таким образом после
каждого такта на выход подается бит, сообщающий о готовности шифр-текста, и само
зашифрованное сообщение. Выдавать 0 в промежуточных тактах целесообразно, т.к.
это предотвратит успех двух наиболее значительных атак на симметричное блочное
шифрование
линейного и дифференциального криптоанализа [3].
Линейный криптоанализ происходит в два шага. Первый построение соотношений
между открытым текстом, шифр-текстом и ключом, которые справедливы с высокой
вероятностью. Второй
использование этих соотношений вместе с известными
парами открытый текст
шифр-текст для получения битов ключа. Смысл
алгоритма состоит в получении соотношений следующего вида:
P
i1
⊕ P
i2
⊕ ... ⊕ P
i
a
⊕ C
j1
⊕ C
j2
⊕ ... ⊕ C
j
b
= K
k1
⊕ K
k2
⊕ ... ⊕ K
k
c
где P
n
, C
n
, K
n
n-ые биты текста, шифр-текста и ключа. Данные соотношения
называются линейными аппроксимациями. Для произвольно выбранных бит открытого
текста, шифротекста и ключа вероятность справедливости такого соотношения
P примерно равна 1/2. Такими соотношениями, вероятность которых заметно
отличается от 1/2 можно пользоваться для вскрытия алгоритма. Криптоаналитик
находит некое однораундовое соотношение, затем пытается распространить его на
весь алгоритм. В блочных шифрах анализ преимущественно концентрируется на
S-блоках, так как они являются нелинейной частью шифра. Построим например
таблицу линейной аппроксимации для первого S-блока ГОСТа:
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
0 +8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1 0
−2 +4
0
−2 −2 0
0
+4 +2 0
+2 −2
0
+2
0
2 0
0
−2 +2 −2 +2 0
0
−2 +2 0
0
−4 −4 +2 −2
3 0
+2 −2
0
−4 −2 −2
0
+2
0
−4 +2 +2
0
0
−2
4 0
+2 0
−2 +2 −4 −2 −4 0
+2 0
−2 −2
0
+2
0
5 0
0
0
0
0
−4 +4
0
0
0
0
0
0
−4 −4
0
6 0
+2 −2
0
0
−2 −2 +4 +2
0
+4 +2 −2
0
0
+2
7 0
+4 +2 +2 −2 +2 0
0
+2 +2 0
−4 0
0
−2 +2
8 0
+4 +2 −2 +2 +2 0
0
−2 +2 0
+4 0
0
−2 −2
9 0
−2 +2 +4 0
−2 −2
0
−2 +4 0
+2 +2
0
0
+2
A 0
0
+4
0
0
0
−4
0
0
−4 0
0
0
−4 0
0
B 0
−2 0
−4 −2
0
−2
0
0
+2 +4 −2 +2
0
−2 −4
C 0
−2 −2
0
0
+2 −2 −4 +2
0
0
+2 −2
0
−4 +2
D 0
0
+2 +2 −2 −2 0
0
−2 −2 0
0
−4 +4 −2 −2
E 0
+2 0
+2 −2
0
+2 −4 0
−2 +4 +2 +2
0
+2
0
F 0
0
0
+4 +4
0
0
0
+4
0
0
0
0
0
0
−4
Это означает, что мы, к примеру, можем использовать такую аппроксимацию S-
блока:
X
3
⊕ X
4
= Y
2
с вероятностью 4/16 и отклонением −1/4
или X
4
= Y
1
с вероятностью 12/16 и отклонением +1/4.
Аппроксимацию с наибольшим отклонением от 1/2 найти не сложно, но
возникает ряд проблем при экстраполировании метода на полнораундовый шифр.
12
Первая из них
вычисление вероятности линейной аппроксимации. Эта проблема
решается при помощи ряда предположений и приближением вероятности. Эта задача
становится сложной только при большом количестве раундов. Так что если бы
злоумышленник имел межтактовые значения работы схемы, т.е. шифр-текст после 2
раундов ГОСТа, то применяя линейный криптоанализ он легко бы взломал алгоритм.
Следовательно требование выдавать 0 на промежуточных тактах обеспечивает
устойчивость к таким атакам.
Дифференциальный криптоанализ основан на изучении преобразования разнос-
тей между шифруемыми значениями на различных раундах шифрования. Идея
дифференциального криптоанализа базируется на вероятностных отношениях между
входными разностями и разностями выхода. Выбирается пара открытых текстов
с фиксированной разностью. Затем анализируются разности, получившиеся после
шифрования одним раундом алгоритма, и определяются вероятности различных
ключей. Если для многих пар входных значений, имеющих одну и ту же разность
∆X, при использовании одного и того же подключа одинаковыми оказывается
и разность ∆Y соответствующих выходных значений, то можно говорить, что
∆X влечет ∆Y с определенной вероятностью. Если эта вероятность близка к
единице, то можно считать, что подключ раунда найден с данной вероятностью.
Результаты дифференциального криптоанализа используются при разработке S-
блоков (стремятся, чтобы появление разностей выходных значений было равноверо-
ятным), и при определении оптимального числа раундов. Следовательно, чтобы
обеспечить устойчивость к атакам такого рода, в схеме в качестве промежуточных
шифр-текстов выдается 0.
Аналогично будем строить схему для DES (см. Рис. 3, Рис. 4). Глубина базового
цикла равна 11 (XOR с ключом 2, S-блоки 7 и XOR с подблоком 2). Следовательно
за один такт алгоритм просчитает три цикла. Также как в случае ГОСТа на
вход пользователь подает управляющий бит и отрытый текст (64 бита).Если
управляющий бит равен 1, то на схему подается сообщение, введенное пользователем,
и обнуляется счетчик. После каждого цикла счетчик увеличивается на 1. После
первого цикла проверяется 4-ый бит счетчика (16 раундов DES), который и сообщит
нам о готовности шифр-текста. Каждый такта на выход поступает бит готовности
и шифр-текст данного такта. Аналогично ГОСТу в целях безопасности, пока шифр-
текст не готов, на выход подается 0.
Ограничение в 40 уровней логики соответствует тактовой частоте 500 Mhz.
Таким образом пропускная способность алгоритма ГОСТ равна:
64 бит
16 тактов
500Mhz(тактов/секунду) = 2Gbps(бит/секунду).
А пропускная способность алгоритма DES получается равной:
64 бит
16/3 тактов
500Mhz(тактов/секунду) = 6Gbps(бит/секунду).
Для сравнения приведем значение пропускной способности программной реализации
данных алгоритмов. В качестве открытого текста было взято сообщение размером
8800160 байт. Оценочное время работы алгоритмов на процессоре с тактовой
частотой 2,5 Ghz оказалось 252546 микросекунд для ГОСТа и 425378 микросекунд
для DES. Соответственно пропускная способность ГОСТа равна:
8800160·8 бит
252546·10
−6
секунд
= 278,766 Mbps(бит/секунду).
И пропускная способность для DES:
8800160·8 бит
425378·10
−6
секунд
= 165,5 Mbps(бит/секунду).
Легко заметить, что аппаратная реализация оказалась в несколько раз быстрее.
13
Рис. 3: Схема DES
14
Рис. 4: Функция f в схеме DES
3 Доказательства утверждений
Лемма. Описанный в работе алгоритм (на стр. 8) без отсечения строит все
тупиковые ДНФ функции.
Доказательство. Рассмотрим алгоритм без 1-го условия добавления элементарной
конъюнкции в цепочку (ограничения на сложность). В списке элементарных
конъюнкций, из которых строятся ДНФ, находятся простые импликанты функции.
Таким образом единицы функции покрываются максимальными интервалами. Ни
один интервал отбросить из набранной ДНФ нельзя, т.к. он добавлялся при
условии покрытия новых единиц функции. Следовательно, в процессе перебора
мы получаем тупиковые ДНФ. Докажем, что алгоритм строит все тупиковые ДНФ.
Набор цепочек можно представить следующим образом:
• Строится корневое дерево. В корне расположен пустой конъюнкт.
• В узлах первого яруса расположены элементарные конъюнкции из списка слева
направо в порядке возрастания.
• Каждый следующий ярус строится так: узел i-го яруса, содержащего элементарную
конъюнкцию K, соединен ребрами с узлами (i + 1)-го яруса, содержащими
элементарные конъюнкции следующие за конъюнкцией K в списке простых
импликант, также упорядоченные слева направо по возрастанию сложности.
Например, у первой элементарной конъюнкции первого яруса будут ребра,
ведущие в узлы второго яруса, которые содержат все конъюнкции списка
начиная со второй, а у последней элементарной конъюнкции первого яруса не
будет никаких ребер.
• Цепочки набираются путем обхода данного дерева в глубину.
15
Обход позволяет перебрать все возможные комбинации составления ДНФ из
простых импликант функции. Следовательно, алгоритм строит все тупиковые ДНФ.
■
Лемма. Отсекаются только тупиковые ДНФ, не являющиеся минимальными.
Доказательство. Процесс отбрасывания некоторых цепочек, по сложности превыща-
ющих имеющийся минимум, не ведет к потере из рассмотрения минимальной
ДНФ. Как только сложность набранной цепочки становится больше имеющегося
минимума, то отрубается вся ветка, т.к. следующие простые импликанты имеют
заведомо большую сложность (благодаря упорядочению списка) и при их добавлении
суммарная сложность цепочки может стать только больше.
■
Теорема. Описанный алгоритм находит минимальную ДНФ.
Доказательство. Доказательство теоремы непосредственно следует из двух лемм.
■
Список литературы
[1] ГОСТ 28147-89
[2] Data Encryption Standard (DES)
[3] Howard M.Heys A Tutorial on Linear and Differential Cryptanalysis
[4] С.В.Яблонский Введение в дискретную математику
[5] С.В.Яблонский, О.Б.Лупанов Дискретная математика и математические
вопросы кибернетики
[6] Д.А.Поспелов Логические методы анализа и синтеза схем
[7] М.И.Гринчук Уточнение верхней оценки глубины сумматора и компаратора,
Дискретный анализ и исследование операций, 15:2 (2008), 12–22
[8] С.Б.Гашков, М.И.Гринчук, И.С.Сергеев О построении схем сумматоров
малой глубины, Дискретный анализ и исследование операций, 14:1 (2007), 27–44
16
Приложение
17
module S-box_1(X1,X2,X3,X4,Y1,Y2,Y3,Y4);
input X1,X2,X3,X4;
output Y1,Y2,Y3,Y4;
wire w1_1,w1_2,w1_3,w1_4,w1_5,w1_6,w1_7,w1_8,w1_9;
wire w2_1,w2_2,w2_3,w2_4,w2_5,w2_6,w2_7,w2_8,w2_9,w2_10;
wire w3_1,w3_2,w3_3,w3_4,w3_5;
wire w4_1,w4_2,w4_3,w4_4,w4_5,w4_6,w4_7;
assign w1_1 = X1 |X2;
assign w1_2 = X3 & w1_1;
assign w1_3 = X2 &X3;
assign w1_4 =X1 & w1_3;
assign w1_5 = w1_2 | w1_4;
assign w1_6 =X4 & w1_5;
assign w1_7 =X3 & X4;
assign w1_8 =X2 | w1_7;
assign w1_9 = X1 & w1_8;
assign Y1 = w1_6 | w1_9;
assign w2_1 = X1 & X2;
assign w2_2 = X3 &X4;
assign w2_3 = w1_7;
assign w2_4 = w2_2 | w2_3;
assign w2_5 = w2_1 & w2_4;
assign w2_6 =w2_1;
assign w2_7 = X3 & X4;
assign w2_8 = w2_7 & w2_6;
assign w2_9 =X1 &X2;
assign w2_10 = w2_8 | w2_9;
assign Y2 = w2_5 | w2_10;
assign w3_1 = X2 & X3;
assign w3_2 =X3 &X4;
assign w3_3 = w3_1 | w3_2;
assign w3_4 = X1 & w3_3;
assign w3_5 =X2 & X4;
assign Y3 = w3_4 | w3_5;
assign w4_1 =X2 & X3;
assign w4_2 = w1_3;
assign w4_3 = w4_1 | w4_2;
assign w4_4 =X1 & w4_3;
assign w4_5 = X1 &X2;
assign w4_6 = X3 | w4_5;
assign w4_7 = X4 & w4_6;
assign Y4 = w4_4 | w4_7;
Приложение
18
endmodule
module S-box_2(X1,X2,X3,X4,Y1,Y2,Y3,Y4);
input X1,X2,X3,X4;
output Y1,Y2,Y3,Y4;
wire w1_1,w1_2,w1_3,w1_4,w1_5,w1_6,w1_7,w1_8,w1_9,w1_10;
wire w2_1,w2_2,w2_3,w2_4,w2_5,w2_6,w2_7,w2_8;
wire w3_1,w3_2,w3_3,w3_4,w3_5,w3_6;
wire w4_1,w4_2,w4_3,w4_4;
assign w1_1 =X2 &X4;
assign w1_2 =X1 & X2;
assign w1_3 = w1_2 & X4;
assign w1_4 = w1_1 | w1_3;
assign w1_5 =X3 & w1_4;
assign w1_6 = X2 & X3;
assign w1_7 = X1 |X4;
assign w1_8 = w1_6 & w1_7;
assign w1_9 = X1 &X4;
assign w1_10 = w1_8 | w1_9;
assign Y1 = w1_5 | w1_10;
assign w2_1 =X1 & X3;
assign w2_2 =X3 &X4;
assign w2_3 = w2_1 | w2_2;
assign w2_4 = X2 & w2_3;
assign w2_5 =X1 &X4;
assign w2_6 = X1 &X2;
assign w2_7 = w2_6 & X3;
assign w2_8 = w2_5 | w2_7;
assign Y2 = w2_4 | w2_8;
assign w3_1 = X3 &X4;
assign w3_2 =w2_6;
assign w3_3 = w3_1 & w3_2;
assign w3_4 = X1 & X4;
assign w3_5 =X3 | w3_4;
assign w3_6 =X2 & w3_5
assign Y3 = w3_3 | w3_6;
assign w4_1 = X4 |X2;
assign w4_2 = X1 & w4_1;
assign w4_3 = w1_2;
assign w4_4 = w4_3 & X3;
Приложение
19
assign Y4 = w4_2 | w4_4;
endmodule
module S-box_3(X1,X2,X3,X4,Y1,Y2,Y3,Y4);
input X1,X2,X3,X4;
output Y1,Y2,Y3,Y4;
wire w1_1,w1_2,w1_3,w1_4,w1_5,w1_6,w1_7,w1_8,w1_9,w1_10;
wire w2_1,w2_2,w2_3,w2_4,w2_5,w2_6,w2_7,w2_8,w2_9;
wire w3_1,w3_2,w3_3,w3_4,w3_5,w3_6,w3_7,w3_8;
wire w4_1,w4_2,w4_3,w4_4,w4_5,w4_6,w4_7,w4_8,w4_9,w4_10,w4_11;
assign w1_1 = X1 &X3;
assign w1_2 =X1 &X2;
assign w1_3 = w1_2 & X3;
assign w1_4 = w1_1 | w1_3;
assign w1_5 =X4 & w1_4;
assign w1_6 = X3 |X1;
assign w1_7 = X2 & w1_6;
assign w1_8 =X2 &X3;
assign w1_9 = w1_7 | w1_8;
assign w1_10 = X4 & w1_9
assign Y1 = w1_5 | w1_10;
assign w2_1 = X4 |X3;
assign w2_2 =X2 & w2_1;
assign w2_3 = X2 & X3;
assign w2_4 = w2_3 &X4;
assign w2_5 = w2_2 | w2_4;
assign w2_6 =X1 & w2_5;
assign w2_7 = X1 & X2;
assign w2_8 = X4 | w2_7;
assign w2_9 =X3 & w2_8;
assign Y2 = w2_6 | w2_9;
assign w3_1 =X1 & X4;
assign w3_2 =w2_1;
assign w3_3 = w3_1 | w3_2;
assign w3_4 =X2 & w3_3;
assign w3_5 = w2_3;
assign w3_6 =X3 & X4;
assign w3_7 = w3_5 | w3_6;
assign w3_8 = X1 & w3_7;
assign Y3 = w3_4 | w3_8;
Приложение
20
assign w4_1 =X1 &X3;
assign w4_2 = X1 &X2;
assign w4_3 = w4_2 & X3;
assign w4_4 = w4_1 | w4_3;
assign w4_5 =X4 & w4_4;
assign w4_6 = w1_1;
assign w4_7 = X2 | X4;
assign w4_8 = w4_6 & w4_7;
assign w4_9 = X2 & X3;
assign w4_10 = w4_9 & X4;
assign w4_11 = w4_8 | w4_10;
assign Y4 = w4_5 | w4_11;
endmodule
module S-box_4(X1,X2,X3,X4,Y1,Y2,Y3,Y4);
input X1,X2,X3,X4;
output Y1,Y2,Y3,Y4;
wire w1_1,w1_2,w1_3,w1_4,w1_5,w1_6,w1_7,w1_8,w1_9,w1_10,w1_11,w1_12;
wire w2_1,w2_2,w2_3,w2_4,w2_5,w2_6,w2_7;
wire w3_1,w3_2,w3_3,w3_4,w3_5;
wire w4_1,w4_2,w4_3,w4_4,w4_5,w4_6,w4_7;
assign w1_1 =X2 &X4;
assign w1_2 = X2 &X3;
assign w1_3 = w1_2 & X4;
assign w1_4 = w1_1 | w1_3;
assign w1_5 = X1 & w1_4;
assign w1_6 =X2 & X4;
assign w1_7 = X2 &X4;
assign w1_8 = w1_6 | w1_7;
assign w1_9 =X1 & w1_8;
assign w1_10 = X3 &X4;
assign w1_11 = w1_10 & X2;
assign w1_12 = w1_9 | w1_11;
assign Y1 = w1_5 | w1_12;
assign w2_1 =X1 & X4;
assign w2_2 = w1_10;
assign w2_3 = w2_2 & X1;
assign w2_4 = w2_1 | w2_3;
assign w2_5 = X2 & w2_4;
assign w2_6 =w1_7;
assign w2_7 =X3 & w2_6;
assign Y2 = w2_5 | w2_7;
Приложение
21
assign w3_1 = X1 & X2;
assign w3_2 = w1_6;
assign w3_3 = w3_1 | w3_2;
assign w3_4 = X3 & w3_3;
assign w3_5 =X1 &X3;
assign Y3 = w3_4 | w3_5;
assign w4_1 = w3_1;
assign w4_2 =X2 &X3;
assign w4_3 = w4_1 | w4_2;
assign w4_4 =X4 & w4_3;
assign w4_5 = w2_1;
assign w4_6 = X2 | w4_5;
assign w4_7 = X3 & w4_6;
assign Y4 = w4_4 | w4_7;
endmodule
module S-box_5(X1,X2,X3,X4,Y1,Y2,Y3,Y4);
input X1,X2,X3,X4;
output Y1,Y2,Y3,Y4;
wire w1_1,w1_2,w1_3,w1_4,w1_5,w1_6,w1_7,w1_8;
wire w2_1,w2_2,w2_3,w2_4,w2_5,w2_6,w2_7;
wire w3_1,w3_2,w3_3,w3_4,w3_5,w3_6,w3_7,w3_8;
wire w4_1,w4_2,w4_3,w4_4,w4_5,w4_6,w4_7,w4_8;
assign w1_1 =X3 & X4;
assign w1_2 =X2 &X4;
assign w1_3 = w1_1 | w1_2;
assign w1_4 = X1 & w1_3;
assign w1_5 =X1 & X4;
assign w1_6 = X3 &X4;
assign w1_7 = w1_5 | w1_6;
assign w1_8 = X2 & w1_7;
assign Y1 = w1_4 | w1_8;
assign w2_1 =X1 &X2;
assign w2_2 = X2 & X4;
assign w2_3 = w2_2 & X1;
assign w2_4 = w2_1 | w2_3;
assign w2_5 =X3 & w2_4;
assign w2_6 =X2 |X1;
assign w2_7 =X4 & w2_6;
assign Y2 = w2_5 | w2_7;
Приложение
22
assign w3_1 = w2_2;
assign w3_2 = X1 &X2;
assign w3_3 = w3_1 | w3_2;
assign w3_4 = X3 & w3_3;
assign w3_5 = X1 & X4;
assign w3_6 =X1 &X3;
assign w3_7 = w3_6 &X4;
assign w3_8 = w3_5 | w3_7
assign Y3 = w3_4 | w3_8;
assign w4_1 =X1 & X3;
assign w4_2 = X2 &X3;
assign w4_3 = w4_1 | w4_2;
assign w4_4 =X4 & w4_3;
assign w4_5 =X1 & X2;
assign w4_6 = w3_2;
assign w4_7 = w4_6 & X3;
assign w4_8 = w4_5 | w4_7;
assign Y4 = w4_4 | w4_8;
endmodule
module S-box_6(X1,X2,X3,X4,Y1,Y2,Y3,Y4);
input X1,X2,X3,X4;
output Y1,Y2,Y3,Y4;
wire w1_1,w1_2,w1_3,w1_4,w1_5,w1_6,w1_7,w1_8;
wire w2_1,w2_2,w2_3,w2_4,w2_5,w2_6,w2_7;
wire w3_1,w3_2,w3_3,w3_4,w3_5,w3_6,w3_7,w3_8,w3_9,w3_10;
wire w4_1,w4_2,w4_3,w4_4,w4_5,w4_6,w4_7,w4_8,w4_9,w4_10,w4_11;
assign w1_1 =X1 & X2;
assign w1_2 =X2 &X4;
assign w1_3 = w1_2 & X1;
assign w1_4 = w1_1 | w1_3;
assign w1_5 =X3 & w1_4;
assign w1_6 = X1 & X2;
assign w1_7 = X4 | w1_6;
assign w1_8 = X3 & w1_7;
assign Y1 = w1_5 | w1_8;
assign w2_1 = X2 & X3;
assign w2_2 = X1 | X4;
assign w2_3 = w2_1 & w2_2;
assign w2_4 = X1 & X4;
Приложение
23
assign w2_5 = w2_3 | w2_4;
assign w2_6 =w2_2;
assign w2_7 = w2_6 &X2;
assign Y2 = w2_5 | w2_7;
assign w3_1 = X1 | X3;
assign w3_2 =X2 & w3_1;
assign w3_3 = w1_1;
assign w3_4 = w3_3 &X3;
assign w3_5 = w3_2 | w3_4;
assign w3_6 =X4 & w3_5;
assign w3_7 = w2_1;
assign w3_8 =X2 &X3;
assign w3_9 = w3_7 | w3_8;
assign w3_10 = X4 & w3_9;
assign Y3 = w3_6 | w3_10;
assign w4_1 = X1 &X3;
assign w4_2 = X2 & X4;
assign w4_3 = w1_2;
assign w4_4 = w4_2 | w4_3;
assign w4_5 = w4_1 & w4_4;
assign w4_6 =X2 & X4;
assign w4_7 = X3 | w4_6;
assign w4_8 =X1 & w4_7;
assign w4_9 = w4_5 | w4_8;
assign w4_10 = w2_1;
assign w4_11 = w4_10 &X4;
assign Y4 = w4_9 | w4_11;
endmodule
module S-box_7(X1,X2,X3,X4,Y1,Y2,Y3,Y4);
input X1,X2,X3,X4;
output Y1,Y2,Y3,Y4;
wire w1_1,w1_2,w1_3,w1_4,w1_5,w1_6,w1_7;
wire w2_1,w2_2,w2_3,w2_4,w2_5,w2_6,w2_7,w2_8,w2_9,w2_10,w2_11,w2_12;
wire w3_1,w3_2,w3_3,w3_4,w3_5,w3_6,w3_7,w3_8;
wire w4_1,w4_2,w4_3,w4_4;
assign w1_1 =X2 &X4;
assign w1_2 =X1 & X2;
assign w1_3 = w1_2 & X4;
assign w1_4 = w1_1 | w1_3;
assign w1_5 =X3 & w1_4;
Приложение
24
assign w1_6 = X3 |X2;
assign w1_7 = X1 & w1_6;
assign Y1 = w1_5 | w1_7;
assign w2_1 =X2 & X3;
assign w2_2 =X1 & X4;
assign w2_3 = X1 &X4;
assign w2_4 = w2_2 | w2_3;
assign w2_5 = w2_1 & w2_4;
assign w2_6 =X1 &X4;
assign w2_7 =w2_1;
assign w2_8 = w2_6 & w2_7;
assign w2_9 = w2_5 | w2_8;
assign w2_10 = X2 & X4;
assign w2_11 = X1 |X3;
assign w2_12 = w2_10 & w2_11;
assign Y2 = w2_9 | w2_12;
assign w3_1 =w2_11;
assign w3_2 = w2_3;
assign w3_3 = w3_1 | w3_2;
assign w3_4 =X2 & w3_3;
assign w3_5 = w1_2;
assign w3_6 = X1 &X3;
assign w3_7 = w3_5 | w3_6;
assign w3_8 = X4 & w3_7;
assign Y3 = w3_4 | w3_8;
assign w4_1 = w1_6;
assign w4_2 =X4 & w4_1;
assign w4_3 = X2 &X3;
assign w4_4 = w4_3 & X1;
assign Y4 = w4_2 | w4_4;
endmodule
module S-box_8(X1,X2,X3,X4,Y1,Y2,Y3,Y4);
input X1,X2,X3,X4;
output Y1,Y2,Y3,Y4;
wire w1_1,w1_2,w1_3,w1_4,w1_5,w1_6,w1_7,w1_8,w1_9,w1_10;
wire w2_1,w2_2,w2_3,w2_4,w2_5,w2_6,w2_7,w2_8,w2_9,w2_10;
wire w3_1,w3_2,w3_3,w3_4,w3_5,w3_6,w3_7,w3_8;
wire w4_1,w4_2,w4_3;
assign w1_1 =X2 &X3;
Приложение
25
assign w1_2 = X1 &X4;
assign w1_3 =X1 & X4;
assign w1_4 = w1_2 | w1_3;
assign w1_5 = w1_1 & w1_4;
assign w1_6 = X1 | X3;
assign w1_7 = X4 & w1_6;
assign w1_8 =X1 &X4;
assign w1_9 = w1_7 | w1_8;
assign w1_10 = X2 & w1_9;
assign Y1 = w1_5 | w1_10;
assign w2_1 = X1 &X2;
assign w2_2 =w1_6;
assign w2_3 = w2_2 & X2;
assign w2_4 = w2_1 | w2_3;
assign w2_5 =X4 & w2_4;
assign w2_6 = X2 & X4;
assign w2_7 = X3 | w2_6;
assign w2_8 = X1 & w2_7;
assign w2_9 =X2 & X3;
assign w2_10 = w2_8 | w2_9;
assign Y2 = w2_5 | w2_10;
assign w3_1 =X3 & X4;
assign w3_2 = w1_8;
assign w3_3 = w3_2 & X3;
assign w3_4 = w3_1 | w3_3;
assign w3_5 = X2 & w3_4;
assign w3_6 = X3 & X4;
assign w3_7 = X1 | w3_6;
assign w3_8 =X2 & w3_7;
assign Y3 = w3_5 | w3_8;
assign w4_1 =X1 |X4;
assign w4_2 =X2 & w4_1;
assign w4_3 =X1 &X3;
assign Y4 = w4_2 | w4_3;
endmodule
Информация о работе Максимизация пропускной способности симметричных алгоритмов шифрования ГОСТ и DES