Фомичев В.М. Дискретная математика и криптология. Курс лекций. - М., 2003. - 400 с.
Книга написана ведущим специалистом в области криптологии, имеющим многолетний опыт преподавания в МИФИ. Изложены базовые вопросы криптологии и необходимые для их изучения основы математического аппарата. С целью закрепления материала даны задачи и упражнения.Рекомендуется для студентов, аспирантов, изучающих дисциплины по криптологии и компьютерной безопасности, преподавателей, а также практических работников, имеющих дело с криптографическими методами защиты информации. Книга хорошо дополняет учебник Алферова и др. "Основы криптографии".
СОДЕРЖАНИЕ
ВСТУПИТЕЛЬНОЕ СЛОВО..................................................................3
ПРЕДИСЛОВИЕ.....................................................................................4
Часть I ИЗБРАННЫЕ ГЛАВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ
Глава 1. МНОЖЕСТВА И ОТОБРАЖЕНИЯ..................................8
1.1. Понятие множества.....................................................................8
1.2. Подмножества и операции над множествами...........................9
1.3. Системы подмножеств множества...........................................10
1.4. Частично упорядоченные множества...................................... 14
1.5. Свойства некоторых решеток...................................................17
1.5.1. Решетка двоичных п-мерных векторов..........................................17
1.5.2. Решетка делителей целого числа....................................................19
1.6. Графы.........................................................................................20
1.6.1. Основные понятия............................................................................20
1.6.2. Пути в графе......................................................................................21
1.6.3. Отношения между графами.............................................................24
1.6.4. Способы задания графов.................................................................24
1.7. Отображения множеств............................................................25
1.8. Задачи и упражнения................................................................29
Глава 2. АЛГЕБРАИЧЕСКИЕ ОСНОВЫ......................................32
2.1. Операции, полугруппы, группы...............................................32
2.2. Кольца и поля............................................................................37
2.3. Некоторые свойства матриц..................................................... 39
2.4. Векторные пространства...........................................................41
2.5. Конечные расширения полей...................................................43
2.6. Задачи и упражнения................................................................46
Глава 3. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ....................................49
3.1. Элементарные булевы функции..............................................49
3.2. Реализация функций формулами.............................................51
3.3. Разложение булевых функций по переменным......................52
3.4. Полнота и замкнутость системы функций..............................54
3.5. Важнейшие замкнутые классы................................................. 56
3.6. Критерий полноты системы булевых функций......................61
3.7. Основные способы задания булевых функций.......................65
3.7.1. Табличное задание...........................................................................65
3.7.2. Геометрическое и графическое задание........................................66
3.7.3. Многочлен Жегалкина и действительный многочлен.................67
3.7.4. Спектральное представление..........................................................68
3.8. Связь различных представлений функций..............................72
3.9. Понятие о классификации двоичных функций.......................77
3.10. Задачи и упражнения..............................................................84
Глава 4. ФУНКЦИИ k-ЗНАЧНОЙ ЛОГИКИ................................90
4.1. Начальные понятия и элементарные функции........................90
4.2. Важные классы функций k-значной логики.............................93
4.3. Примеры полных систем в Р^...................................................95
4.4. Распознавание полноты и критерии полноты в Р^.................97
4.5. Особенности k-значных логик................................................100
4.6. Задачи и упражнения..............................................................102
Глава 5. СБАЛАНСИРОВАННОСТЬ ОТОБРАЖЕНИЙ..........105
5.1. О связи отображений с системами функций.........................105
5.2. Критерии сбалансированности отображений........................106
5.3. Критерии биективности преобразований..............................109
5.4. Некоторые классы отображений............................................110
5.4.1. Аффинные отображения................................................................110
5.4.2. Отображения регистров сдвига.....................................................111
5.4.3. «Треугольные» преобразования...................................................114
5.5. Задачи и упражнения..............................................................116
Глава 6. СТРУКТУРА И ПЕРИОДЫ ПРЕОБРАЗОВАНИЙ.....120
6.1. Периоды последовательностей..............................................120
6.2. Граф отображения...................................................................122
6.3. Характеристики периодичности преобразования.................124
6.4. Полноцикловые преобразования............................................126
6.5. Линейные регистры сдвига.....................................................131
6.6. Аффинные преобразования максимального периода...........133
6.7. Задачи и упражнения..............................................................136
Глава 7. ПСЕВДОСЛУЧАЙНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ.................................138
7.1. Подходы к анализу последовательностей.............................138
7.2. Линейные рекуррентные последовательности......................139
7.3. Линейная сложность последовательностей...........................140
7.4. Статистические требования к последовательностям............145
7.5. Статистическое тестирование последовательностей............148
7.5.1. Частотный тест...............................................................................150
7.5.2. Автокорреляционный тест............................................................150
7.5.3. Последовательный тест.................................................................150
7.5.4. Тест серий.......................................................................................151
7.6. Задачи и упражнения..............................................................153
Глава 8. КРИПТОГРАФИЧЕСКИЕ СВОЙСТВА НЕЛИНЕЙНЫХ ОТОБРАЖЕНИЙ...............................................155
8.1. Перемешивающие свойства отображений............................155
8.2. Совершенность композиции преобразований.......................157
8.3. Усиление свойства совершенности........................................160
8.3.1. Строгий лавинный критерий.........................................................161
8.3.2. Критерии распространения и бент-отображения........................162
8.4. Алгебраические характеристики нелинейности...................163
8.5. Линейный синдром при итерациях........................................166
8.6. Приближения нелинейных отображений..............................169
8.7. Задачи и упражнения..............................................................172
Глава 9. КОНЕЧНЫЕ АВТОМАТЫ МИЛИ................................176
9.1. Функционирование автомата, виды автоматов.....................176
9.2. Способы задания автоматов Мили.........................................178
9.3. Отношения и операции с автоматами....................................181
9.4. Различимость состояний и входов......................................... 183
9.5. Периодичность в конечных автоматах.................................. 187
9.6. Задачи и упражнения..............................................................190
Часть II ОСНОВЫ КРИПТОЛОГИИ
Глава 10. ОСНОВНЫЕ ПОНЯТИЯ
И ЗАДАЧИ КРИПТОЛОГИИ.........................................................194
10.1. Задачи криптографии............................................................194
10.2. Основные понятия криптологии..........................................195
10.3. Симметричные и асимметричные шифросистемы............... 197
10.4. Понятие о криптографических протоколах.........................198
10.5. Организация секретной связи, задачи криптоаналитика... 199
10.6. Обеспечение целостности сообщений.................................205
10.7. Цифровая подпись.................................................................206
Глава 11. КЛЮЧЕВАЯ СИСТЕМА ШИФРА..............................211
11.1. Строение и порядок ключевого множества.........................211
11.2. Вероятностная модель ключевого множества....................212
11.3. Генерация ключей.................................................................213
11.4. Обеспечение секретности ключей.......................................214
11.4.1. Схемы разделения секрета..........................................................214
11.4.2. Рассылка ключей..........................................................................216
11.4.3. Хранение ключей..........................................................................217
11.4.4. Смена ключей...............................................................................218
11.5. Протоколы обмена ключами................................................219
11.5.1. Передача ключей с использованием симметричного шифрования...............................................................................................219
11.5. 1.1. Двусторонние протоколы................................................................219
11.5.1.2. Трехсторонний протокол.................................................................223
11.5.2. Управление ключами в системах с открытым ключом............224
11.5.2.1. Алгоритм Диффи - Хеллмана..........................................................224
11.5.2.2. Протокол «станция-станция»........................................................225
11.5.3. Предварительное распределение ключей..................................226
11.5.4. Зависимость протоколов от архитектуры сети........................227
Глава 12. ИСТОЧНИКИ ОТКРЫТЫХ ТЕКСТОВ.....................229
12.1. Характеристики открытых текстов......................................229
12.2. Детерминированные модели................................................230
12.3. Вероятностные модели.........................................................231
12.3.1. Стационарный источник независимых символов алфавита ....232
12.3.2. Стационарный источник независимых биграмм......................233
12.3.3. Стационарный источник марковски зависимых букв..............234
12.3.4. Усложнение стационарных моделей..........................................235
12.3.5. Нестационарные источники сообщений....................................236
Глава 13. КРИПТОГРАФИЧЕСКАЯ
СТОЙКОСТЬ ШИФРОВ.................................................................238
13.1. Вероятностные модели шифра.............................................238
13.2. Совершенно стойкие шифры................................................239
13.3. Системный подход к оценке практической стойкости шифров............................................................................................242
13.4. Другие подходы к оценке практической
стойкости шифров..........................................................................246
13.4.1. Асимптотический анализ стойкости..........................................246
13.4.2. Оценка количества необходимого шифрматериала.................246
13.4.3. Стоимостный подход...................................................................247
Глава 14. ШИФРЫ ПЕРЕСТАНОВКИ И ЗАМЕНЫ..................249
14.1. Шифры перестановки...........................................................249
14.1.1. Шифрование с помощью скиталя...............................................250
14.1.2. Маршругные шифры....................................................................250
14.1.3. Решетка Кардано..........................................................................251
14.2. Шифры замены......................................................................252
14.2.1. Шифр Цезаря................................................................................253
14.2.2. Таблица Вижинера.......................................................................253
14.2.3. Шифры пропорциональной замены...........................................255
14.2.4. Замена биграмм............................................................................255
14.2.5. Замена к-грамм.............................................................................257
Глава 15. ШИФРУЮЩИЕ АВТОМАТЫ.....................................259
15.1. Математические модели шифра...........................................259
15.2. Автоматная модель симметричного шифра........................260
15.3. Отношения и операции с шифрующими автоматами........263
15.4. Моноключевые шифрующие автоматы...............................265
15.5. Криптографические генераторы...........................................266
15.6. Эквивалентность ключей и шифрующих автоматов.........268
15.7. Различимость входов............................................................272
15.8. Задачи и упражнения............................................................273
Глава 16. ПОТОЧНЫЕ ШИФРЫ..................................................275
16.1. Различия между поточными и блочными шифрами..........275
16.2. Синхронные поточные шифры.............................................276
16.3. Самосинхронизирующиеся поточные шифры....................280
16.4. Шифры гаммирования..........................................................282
16.5. Криптографические свойства поточных шифров...............282
16.5.1. Повторное использование гаммы...............................................283
16.5.2. Выход гаммы в линию связи.......................................................284
16.5.3. Восстановление текста, зашифрованного
неравновероятной гаммой.......................................................................285
16.5.4. Критерии оценки криптографических свойств управляющего и шифрующего блоков..................................................287
16.6. Задачи и упражнения............................................................289
Глава 17. СИММЕТРИЧНЫЕ БЛОЧНЫЕ ШИФРЫ ................291
17.1. Сравнение характеристик асимметричных
и симметричных блочных шифров...............................................291
17.2. Принципы построения блочных шифров............................291
17.2.1. Немного истории..........................................................................292
17.2.2. Итеративные блочные шифры....................................................294
17.2.3. Шифры Фейстеля.........................................................................296
17.2.4. Построение цикловой функции..................................................298
17.2.5. Входное и выходное отображения.............................................301
17.2.6. Построение ключевого расписания............................................302
17.3. Слабые ключи итеративного шифра....................................304
17.4. Режимы шифрования............................................................306
17.4.1. ЕСВ (простая замена)...................................................................307
17.4.2. СВС (сцепление блоков шифртекста)........................................308
17.4.3. СРВ (обратная связь по шифртексту
или гаммирование с обратной связью)..................................................310
17.4.4. OFB (обратная связь по выходу, гаммирование
или внутренняя обратная связь)..............................................................311
17.4.5. Другие режимы шифрования......................................................312
17.4.6. Чередование..................................................................................314
17.5. Усложнение симметричных блочных шифров...................314
17.6. Задачи и упражнения............................................................316
Глава 18. КРИПТОГРАФИЧЕСКИЕ ГЕНЕРАТОРЫ................318
18.1. Элементная база криптосхем................................................318
18.2. Фильтрующие генераторы....................................................319
18.3. Комбинирующие генераторы...............................................321
18.4. Корреляционные атаки.........................................................326
18.5. Генераторы гаммы с неравномерным движением..............327
18.5.1. Схемы с внешним управлением..................................................328
18.5.1.1. Генераторы «З-тшагов»..................................................................328
18.5.1.2. Генераторы с перемежающимся шагом........................................330
18.5.L3. Каскадные генераторы Гольмана...................................................331
18.5.1.4. Сжимающие генераторы................................................................331
18.5.1.5. Аддитивные генераторы.................................................................332
18.5.2. Схемы с самоуправлением..........................................................334
18.5.2.1. Генераторы (6,т)-самоусечения...................................................... 334
18.5.2.2. Самосжимающий генератор...........................................................335
18.6. Генераторы с дополнительной памятью..............................335
18.6.1. Генераторы Макларена - Марсальи...........................................335
18.6.2. Регистр сдвига с обратной связью с переносом........................337
18.7. Задачи и упражнения............................................................339
ПРИЛОЖЕНИЯ................................................................................341
1. Алгоритм шифрования DES......................................................341
2. Алгоритм ГОСТ 28147-89.........................................................345
3. Блочный шифр IDEA..................................................................347
4. RUNDAEL..................................................................................350
Математические операции алгоритма....................................................351
Описание алгоритма.................................................................................352
Состояния, ключи и число циклов шифрования............................................353
Цикловое преобразование................................................................................354
Ключевое расписание.......................................................................................355
5. Стандарт генерации ключей ANSI Х9.17................................357
6. Алгоритм А5/1...........................................................................358
7. Американский стандарт хеш-функции (SHS)..........................359
8. Криптосистема RSА....................................................................361
9. Шифрсистема Эль Гамаля.........................................................363
10. Схема цифровой подписи Эль Гамаля....................................364
Ответы и решения.............................................................................365
Словарь...............................................................................................372
Литература.........................................................................................386
