В. М. Фомичёв дискретная математика и криптология курс лекций
Вид материала | Курс лекций |
- Курс лекций (28 часов) канд филос наук О. В. Аронсон Курс лекций «Математика и современная, 27.49kb.
- Джеймс А. Дискретная математика и комбинаторика [Текст] / Джеймс А. Андерсон, 42.79kb.
- Темы курсовой работы по дисциплине "дискретная математика" (Приложение к рабочей программе, 128.96kb.
- Рабочая программа дисциплины (модуля) Дискретная математика, 101.32kb.
- Рабочая программа учебной дисциплины «Дискретная математика» Направление подготовки, 139.29kb.
- Примерная программа наименование дисциплины «Дискретная математика» Рекомендуется для, 135.29kb.
- Календарный план учебных занятий по обязательной дисциплине «Дискретная математика, 109.62kb.
- Аннотация программы учебной дисциплины «Дискретная математика и математическая логика, 55.65kb.
- Методические указания к выполнению курсовой работы по дисциплине " Дискретная математика", 254.75kb.
- Программа лекций по курсу «Дискретная математика», 39.52kb.
В.М.Фомичёв
ДИСКРЕТНАЯ МАТЕМАТИКА И КРИПТОЛОГИЯ
(курс лекций)
Под общей редакцией
доктора физико-математических наук
Н.Д.Подуфалова
Москва «ДИАЛОГ-МИФИ» 2003
Книга задумана как учебное пособие по охватывающим 3 семестра курсам «Математические основы криптологии» и «Криптографические методы защиты информации», читавшимся автором в течение 10 лет на факультете «Информационной безопасности» МИФИ.
Книга содержит 18 глав и Приложение (см. Оглавление). Для закрепления материала в завершение большинства глав даны задачи и упражнения, в общей сложности около 300 задач. В конце учебника выборочно и по возможности лаконично даны ответы и решения.
Объём издания – 400 страниц.
ВСТУПИТЕЛЬНОЕ СЛОВО
Неуклонно возрастают многообразие и сложность проблем информационной безопасности, возникающих в ходе активного развития информационных технологий. Современные решения многих проблем защиты информации немыслимы без использования методов криптологии. Систематическому изложению теоретических основ криптологии и важнейших её приложений для решения задач защиты информации посвящена данная книга.
Учебник написан ведущим специалистом в области криптологии, доцентом кафедры криптологии и дискретной математики МИФИ, имеющим многолетний опыт преподавания. Содержание учебника полностью соответствует Государственному образовательному стандарту высшего профессионального образования по специальности «Комплексное обеспечение информационной безопасности автоматизированных систем» (шифр 075500). Десятки ВУЗов России, разворачивающих в настоящее время подготовку специалистов по защите информации, нуждаются в подобном учебнике, что повышает его актуальность и ценность.
Этот учебник выгодно отличается от немногих предшествующих изданий на русском языке высокой степенью полноты и самодостаточности материала. Автор добился цельности и логичности изложения, чёткости определения основных понятий, математической строгости. Для закрепления материала даны задачи и упражнения.
Книга может быть также полезна как преподавателям при подготовке лекций и семинарских занятий, так и практическим работникам.
Доктор физико-математических наук, профессор,
академик Российской Академии Образования (РАО)
Н.Д.Подуфалов май 2003 года
ОГЛАВЛЕНИЕ
Вступительное слово
Предисловие автора
Часть I. ИЗБРАННЫЕ ГЛАВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ
Глава 1. МНОЖЕСТВА И ОТОБРАЖЕНИЯ
1.1. Понятие множества
1.2. Подмножества и операции над множествами
1.3. Системы подмножеств множества
1.4. Частично упорядоченные множества
1.5. Свойства некоторых решёток
1.5.1. Решётка двоичных n-мерных векторов
1.5.2. Решётка делителей целого числа
- Графы
1.6.1. Основные понятия
1.6.2. Пути в графе
1.6.3. Отношения между графами
1.6.4. Способы задания графов
1.7. Отображения множеств
1.8. Задачи и упражнения
Глава 2. АЛГЕБРАИЧЕСКИЕ ОСНОВЫ
- Операции, полугруппы, группы
- Кольца и поля
- Некоторые свойства матриц
- Векторные пространства
- Конечные расширения полей
2.6. Задачи и упражнения
Глава 3. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ
- Элементарные булевы функции
- Реализация функций формулами
- Разложение булевых функций по переменным
- Полнота и замкнутость системы функций
- Важнейшие замкнутые классы
- Критерий полноты системы булевых функций
- Основные способы задания булевых функций
3.7.1. Табличное задание
3.7.2. Геометрическое и графическое задание
- Многочлен Жегалкина и действительный многочлен
3.7.4. Спектральное представление
- Связь различных представлений функций
- Понятие о классификации двоичных функций
3.10. Задачи и упражнения
Глава 4. ФУНКЦИИ k -ЗНАЧНОЙ ЛОГИКИ
- Начальные понятия и элементарные функции
- Важные классы функций k-значной логики
- Примеры полных систем в Pk
- Распознавание полноты и критерии полноты в Pk
- Особенности k-значных логик
4.6. Задачи и упражнения
Глава 5. СБАЛАНСИРОВАННОСТЬ ОТОБРАЖЕНИЙ
- О связи отображений с системами функций
- Критерии сбалансированности отображений
- Критерии биективности преобразований
- Некоторые классы отображений
5.4.1. Аффинные отображения
5.4.2. Отображения регистров сдвига
5.4.3. «Треугольные» преобразования
5.5. Задачи и упражнения
Глава 6. СТРУКТУРА И ПЕРИОДЫ ПРЕОБРАЗОВАНИЙ
6.1. Периоды последовательностей
- Граф отображения
- Характеристики периодичности преобразования
- Полноцикловые преобразования
- Линейные регистры сдвига
6.6. Аффинные преобразования максимального периода
6.7. Задачи и упражнения
Глава 7. ПСЕВДОСЛУЧАЙНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ
- Подходы к анализу последовательностей
- Линейные рекуррентные последовательности
- Линейная сложность последовательностей
- Статистические требования к последовательностям
- Статистическое тестирование последовательностей
7.5.1. Частотный тест
7.5.2. Автокорреляционный тест
7.5.3. Последовательный тест
7.5.4. Тест серий
7.6. Задачи и упражнения
Глава 8. КРИПТОГРАФИЧЕСКИЕ СВОЙСТВА НЕЛИНЕЙНЫХ ОТОБРАЖЕНИЙ
- Перемешивающие свойства отображений
- Совершенность композиции преобразований
- Усиление свойства совершенности
8.3.1. Строгий лавинный критерий
8.3.2. Критерии распространения и бент-отображения
8.4. Алгебраические характеристики нелинейности
8.5. Линейный синдром при итерациях
8.6. Приближения нелинейных отображений
8.7. Задачи и упражнения
Глава 9. КОНЕЧНЫЕ АВТОМАТЫ МИЛИ
- Функционирование автомата, виды автоматов
- Способы задания автоматов Мили
- Отношения и операции с автоматами
- Различимость состояний и входов
- Периодичность в конечных автоматах
- Задачи и упражнения