Параллельные алгоритмы для решения задач защиты информации

Москва
Горячая линия – Телеком
2014

2-е издание, стереотипное

УДК 004.056.5:519.688 
ББК 32.973.2-018.2 
      Б12 

Рецензенты: зав. кафедрой Защиты информации МФТИ, доктор техн. наук, 

профессор В. А. Конявский;  научный руководитель ЮР РУНЦ ИБ 
Южного федерального университета, доктор техн. наук, профессор 
О. Б. Макаревич 

Бабенко Л. К., Ищукова Е. А., Сидоров И. Д.
Б12   Параллельные алгоритмы для решения задач защиты информации. – 2-е изд., стереотип. – М.: Горячая линия–Телеком, 
2014. – 304 с., ил. 
ISBN 978-5-9912-0439-2. 

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

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

ББК 32.973.2-018.2 
Адрес издательства в Интернет WWW.TECHBOOK.RU 
Научное издание 

Бабенко Людмила Климентьевна, Ищукова Евгения Александровна, 

Сидоров Игорь Дмитриевич 

Параллельные алгоритмы для решения задач защиты информации 

Монография 
2-е издание, стереотипное 

Редактор  Ю. Н. Чернышов 
Компьютерная верстка  Ю. Н. Чернышова 
Обложка художника  О. В. Карповой 

Подписано  в  печать  24.06.14. Формат 6090/16. Усл. печ. л. 19.  Тираж 300 экз. (1-й завод 100 экз.)  

ISBN 978-5-9912-0439-2         Л. К. Бабенко, Е. А. Ищукова, И. Д. Сидоров, 2014 
©  Научно-техническое издательство «Горячая линия–Телеком», 2014 

Введение

Ключевой задачей защиты информации является создание стойких алгоритмов шифрования. В современной криптографии шифры
по принципу построения и использования секретного ключа разделяют на симметричные и асимметричные. Любой разрабатываемый
алгоритм шифрования подвергается тщательному анализу с целью
выявления его слабых мест и возможности взлома. Для того чтобы
иметь возможность оценить стойкость используемого шифра, необходимо наличие эффективных алгоритмов анализа.
На сегодняшний день существует довольно много различных методов анализа симметричных блочных шифров, основанных на различных подходах. Среди них можно выделить несколько основных
направлений. Метод линейного анализа основан на построении системы эффективных статистических аналогов. Накопление статистики с использованием данной системы аналогов позволяет предположить значения битов секретного ключа. Метод дифференциального
анализа и его производные — метод невозможных дифференциалов,
бумеранг-атака — основаны на прослеживании изменения несходства
между двумя текстами при их прохождении через раунды шифрования. Алгебраические методы анализа основаны на построении и
решении системы линейных уравнений от многих переменных, полностью описывающих схему шифрования. Метод слайдовой атаки
предназначен для анализа гомогенных шифров или шифров с некоторой степенью самоподобия. Для таких шифров рассматривается
возможность сопоставления двух процессов шифрования с запаздыванием на один или несколько раундов.
Для асимметричных криптосистем также существует достаточно большое разнообразие методов.
Среди них наиболее известны
такие методы, как метод Гельфонда, «giant step-baby step», метод
встречи на случайном дереве, метод базы разложения, метод решета числового поля, метод Ферма, метод непрерывных дробей, метод
квадратичного решета и др. Однако, если при анализе симметричных криптосистем различные методы используют различные приемы, такие как линеаризация, рассмотрение пар текстов, составление систем переопределенных уравнений, то при анализе асимметричных криптосистем все методы сводятся к решению двух задач
различными способами — задачи дискретного логарифмирования и

Введение

задачи факторизации больших чисел.
С появлением мощных вычислительных ресурсов задача анализа асимметричных криптосистем превратилась из чисто теоретической в практическую. При этом
многие из вышеуказанных методов поддаются распараллеливанию,
а значит, могут работать в несколько раз быстрее при использовании
соответствующих вычислительных средств.
Одним из способов повышения производительности при анализе различных криптосистем является использование распределенных многопроцессорных вычислений (РМВ) для ускорения процесса
анализа и скорейшего получения результата. Применение РМВ возможно как при криптоанализе симметричных блочных шифров, так
и при использовании методов анализа современных асимметричных
криптосистем.
В монографии освещаются основные проблемы современной системы защиты информации в области криптоанализа. При этом отдельное внимание уделяется вопросом возможности применения высокопроизводительных распределенных вычислений для ускорения
вычислительного процесса. Книга организована следующим образом. В первом разделе рассматриваются основные алгоритмы симметричного и ассиметричного шифрования, современные функции
хэширования, а также основные методы анализа, связанные с оценкой уязвимостей рассматриваемых криптосхем. При рассмотрении
криптоалгоритмов и методов их анализа отдельный упор делается
на возможность применения РМВ для сокращения времени анализа. Во втором разделе рассматриваются основные современные типы параллельных вычислительных архитектур.
Особое внимание
уделяется вопросам распределения данных для распределенных вычислений, а также вопросам оценки эффективности разработанных
параллельных алгоритмов. В третьем разделе приводятся краткие
сведения об интерфейсе передаче данных MPI, его основных функциях и способах межпроцессного взаимодействия. В четвертом разделе описывается архитектура CUDA и возможность ее использования для распределенных многопроцессных вычислений. Наконец, в
пятом разделе рабобраны подробные решения основных задач современной защиты информации, описаны детальные алгоритмы и приведены листинги программ с подробными комментариями. В приложениях даны подробные инструкции по установке, настройке и работе с пакетом программ MPICH 1.2.5, а также подробное описание
библиотечных функций MPI.

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

1.1. Введение в криптографию

Не секрет, что стремление защитить свои интересы было присуще человеку с давних пор. Еще в древности человек использовал
различные варианты кодирования информации, изобретал устройства, которые бы способствовали созданию более стойких шифров и
при этом обеспечивали легкость шифрования.
Основной целью криптографической защиты информации является защита ее от утечки, что обеспечивается обратимым однозначным преобразованием данных, которые необходимо скрыть, в форму,
непонятную для посторонних или неавторизованных лиц.
Можно
сказать, что теория информации в современном понимании начало свое развитие с работы Огюста Кергоффса «Военная криптография», опубликованной в 1883 году. Все современные криптоалгоритмы базируются на принципе Кирхгофа, согласно которому секретность шифра обеспечивается секретностью ключа, а не секретностью
алгоритма шифрования. При этом стойкость криптосистемы зависит от нескольких параметров, а именно: от сложности алгоритмов
преобразования, от длины ключа, а точнее, от объема ключевого
пространства, от метода реализации. Позднее Клод Шеннон в своей
работе «Теория связи в секретных системах» [1], опубликованной в
1949 году, сформулировал необходимые и достаточные условия недешифруемости системы шифрования.
Долгое время криптография оставалась секретной наукой, в
тайны которой был посвящен лишь узкий круг лиц. Это было естественно, так как в первую очередь она была направлена на сохранение государственных секретов. Ситуация стала меняться во второй
половине ХХ века с появлением персональных компьютеров. Когда практически каждый человек получил возможность оперировать

Р а з д е л 1

электронной информацией, возникла естественная потребность както защищать эту информацию от посторонних глаз. На сегодняшний
день наука криптография развивается очень стремительно. Связано это с тем, что в последние годы данная область знаний стала
открытой. Если раньше созданием и анализом шифров занимались
лишь секретные государственные структуры, то в наши дни любой
желающий может беспрепятственно овладеть азами данной науки.
Кроме того, быстрое развитие современных информационных технологий также делает криптографию востребованной. Как следствие, появляются все новые и новые шифры, предлагаемые авторами
из разных стран, направленные на усиление секретности данных,
шифруемых с их помощью.
Широкое распространение получило использование симметричной криптографии, а несколько позднее и ассиметричной. В 1976 году в США был утвержден стандарт шифрования данных DES (Data
Encryption Standard) [2], который использовался довольно длительное время (более 20 лет). Естественно, что у людей возникло желание проверить: а действительно ли предлагаемые алгоритмы для
шифрования конфиденциальных данных обеспечивают сохранность
информации? Для того чтобы ответить на этот вопрос, необходимо
было провести ряд достаточно сложных исследований. Так, исследования в области анализа стойкости шифров постепенно стали причиной того, что в криптологии выделилось два родственных направления, теснейшим образом связанных между собой: криптография
и криптоанализ.
Прослеживая историю развития этих направлений, можно сказать, что одним из блочных алгоритмов, наиболее
часто подвергавшийся различного рода атакам, является алгоритм
шифрования DES. Именно для анализа этого алгоритма шифрования были разработаны такие мощные атаки, как линейный и дифференциальный криптоанализ, которые в дальнейшем стали применяться к целому классу блочных шифров. Более того, проведенные
исследования показали, что метод дифференциального криптоанализа применим не только к блочным алгоритмам шифрования, но
также к поточным шифрам и даже к анализу надежности функций
хэширования.
Прежде чем перейти к рассмотрению возможных сценариев анализа систем защиты информации, необходимо рассмотреть основные
принципы построения этих систем. В данном разделе мы рассмотрим некоторые основные алгоритмы симметричного шифрования,
ассиметричного шифрования, функции хэширования, а также основные подходы к их анализу. При этом особое внимание уделим
вопросу о возможности выполнения параллельных вычислений.

Задачи защиты информации
7

1.2. Симметричные алгоритмы шифрования
1.2.1. Алгоритм шифрования DES
Несмотря на то что с мая 2002 года в США в силу вступил
новый стандарт шифрования данных AES, предыдущий стандарт
шифрования данных DES (Data Encryption Standard), который ANSI
называет Алгоритмом шифрования данных DEA (Data Encryption
Algorithm), а ISO — DEA-1, остается одним из самых известных алгоритмов. Можно даже сказать, что в настоящий момент алгоритм
шифрования DES используется в основном для обучения специалистов по защите информации, являясь открытым и в то же время
стойким алгоритмом шифрования. За годы своего существования
он выдержал натиск различных атак и для многих применений все
еще является криптостойким.
DES представляет собой блочный симметричный шифр, построенный по схеме Фейстеля, он преобразует 64-битовый блок исходных
данных в блок шифрованных данных такой же длины под воздействием секретного ключа шифрования.
Так как DES является симметричным алгоритмом, то для шифрования и дешифрования используются одинаковые алгоритмы с
той лишь разницей, что при дешифровании раундовые подключи
используются в обратном порядке. То есть, если при шифровании
использовались раундовые подключи K1, K2, K3,. . . , K16, то подключами дешифрования соответственно будут K16, K15, K14,. . . , K1.
Алгоритм использует только стандартную арифметику 64-битовых
чисел и логические операции, поэтому легко реализуется на аппаратном уровне.
Длина секретного ключа равна 56 битам. Ключ обычно представляется 64-битовым числом, но каждый восьмой бит используется
для проверки четности и игнорируется.
Биты четности являются
наименьшими значащими битами байтов ключа.
Криптостойкость алгоритма полностью определяется ключом.
Фундаментальным строительным блоком DES является комбинация
подстановок и перестановок. DES работает с 64-битовыми блоками
открытого текста и состоит из 16 раундов. Работа алгоритма начинается с первоначальной перестановки, выполняемой до начала
работы раундов шифра в соответствии с табл. 1.1.

Таблица 1.1
Начальная перестановка

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

Р а з д е л 1

Эту и все последующие таблицы для алгоритма DES следует
читать слева направо и сверху вниз. Например, начальная перестановка перемещает бит 58 в позицию 1, бит 50 — в позицию 2, бит
42 — в позицию 3 и так далее.

Рис. 1.1. Общий вид работы
алгоритма шифрования DES

После этого блок данных разбивается на правую и левую половины
длиной по 32 бита. Затем выполняется 16 раундов, в которых данные
перемешиваются и объединяются с
ключом.
После шестнадцатого раунда правая и левая половины объединяются и алгоритм завершается
заключительной перестановкой (обратной по отношению к первоначальной). Общий вид работы алгоритма представлен на рис. 1.1.
В каждом раунде правая половина данных увеличивается с 32 до
48 битов дублированием некоторых
битов с помощью перестановки с расширением в соответствии с табл. 1.2.
Расширенные данные объединяются с 48-битовым раундовым подключом посредством сложения по модулю 2 (операция XOR), после чего
проходит через восемь S-блоков замены. На вход каждого S-блока поступает 6-битовый вход, и в результате замены образуется 4-битовый выход. Всего используется восемь различных S-блоков.
Каждый S-блок
представляет собой таблицу из четырех строк и шестнадцати столбцов.
Каждый элемент в блоке является 4битовым столбцом. По шести входным битам S-блока определяется,
под какими номерами столбцов и строк следует искать выходное
значение.
Первый из восьми S-блоков показан в табл. 1.3.
Остальные блоки замены легко можно найти в книгах и справочниках по
криптографии, например в [2–6].
Входные биты особым образом определяют элементы S-блока.
Рассмотрим 6-битовый вход S-блока: b1, b2, b3, b4, b5 и b6. Биты b1 и

Задачи защиты информации
9

Таблица 1.2
Перестановка с расширением

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

Таблица 1.3
Блок S1

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

00
14
4
13
1
2
15
11
8
3
10
6
12
5
9
0
7

01
0
15
7
4
14
2
13
1
10
6
12
11
9
5
3
8

10
4
1
14
8
13
6
2
11
15
12
9
7
3
10
5
0

11
15
12
8
2
4
9
1
7
5
11
3
14
10
0
6
13

Рис. 1.2. Пример работы S-блока замены

b6 объединяются, образуя 2-битовое число от 0
до 3, соответствующее строке таблицы. Средние четыре бита, с b2 по b5, объединяются, образуя 4-битовое число от 0 до 15, соответствующее столбцу таблицы. Необходимо учитывать,
что строки и столбцы нумеруются с нуля, а не
с единицы. Например, пусть на вход блока S1
попадает значение 110011. Первый и последний
биты, объединяясь, образуют 11, что соответствует строке три блока S1. Средние четыре бита
образуют 1001, что соответствует 9-му столбцу
того же S-блока. Элемент блока S1, находящийся на пересечении строки три и столбца девять,
равен 11, т. е. на выходе будет образовано значение 1011 (рис. 1.2).
В результате подстановки с помощью восьми блоков замены получается восемь 4-битовых блоков, которые вновь объединяются в
единый 32-битовый блок. Этот блок поступает на вход следующего этапа — перемешивания с использованием Р-перестановки. Эта
перестановка перемещает каждый входной бит в другую позицию,
ни один бит не используется дважды, и ни один бит не игнорируется. Этот процесс называется прямой перестановкой или просто перестановкой. Перестановка выполняется в соответствии с табл. 1.4.
Например, двадцать первый бит перемещается в позицию четыре, а
четвертый бит — в позицию тридцать один.

Таблица 1.4
Перестановка Р

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

Р а з д е л 1

Рис. 1.3. Функция F

Операции расширения данных, сложения с раундовым подключом, замены с помощью S-блоков и перемешивания с помощью Рперестановки образуют функцию F, выполняемую в каждом раунде шифрования. Схема работы функции F наглядно показана на
рис. 1.3.
Результат функции F объединяется с левой половиной с помощью операции сложения по модулю два (XOR). В итоге этих действий появляется новая правая половина, а старая правая становится
новой левой половиной. Эти действия повторяются 15 раз, образуя
15 циклов DES. В последнем, шестнадцатом раунде выполняются
все те же действия за тем исключением, что правая и левая части
местами не меняются.
После 16 раундов преобразования выполняется заключительная
перестановка, которая является обратной по отношению к первоначальной и преобразует данные в соответствии с табл. 1.5.
Остается рассмотреть процедуру выработки шестнадцати 48-битовых раундовых подключей из секретного 56-битового ключа шиф
Таблица 1.5
Заключительная перестановка

40
8
48
16
56
24
64
32
39
7
47
15
55
23
63
31

38
6
46
14
54
22
62
30
37
5
45
13
53
21
61
29

36
4
44
12
52
20
60
28
35
3
43
11
51
19
59
27

34
2
42
10
50
18
58
26
33
1
41
9
49
17
57
25