Фомичев В.М. Дискретная математика и криптология. Курс лекций ОНЛАЙН

Фомичев В.М. Дискретная математика и криптология. Курс лекций. -М., Диалог-МИФИ, 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

Поделиться ссылкой:
  • Добавить ВКонтакте заметку об этой странице
  • Мой Мир
  • Facebook
  • Twitter
  • LiveJournal
  • В закладки Google
  • Яндекс.Закладки
  • Сто закладок
  • Blogger
  • Блог Li.ру
  • Блог Я.ру
  • Одноклассники
  • RSS

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Наш сайт находят по фразам: