Программа курса
Математические методы защиты информации
(3 семестр магистратуры, уч. год ),
Автор программы ,
д. ф.-м. н., профессор ММФ НГУ, в. н.с. ИМ СО РАН
Отдельные главы теории кодирования
- Скорость кода, пропускная способность. Теорема Шеннона для двоичного симметричного канала связи с шумом (с доказательством). Вероятность ошибки декодирования.
- Декодирование циклических кодов.
- Каскадные методы построения кодов. Коды Зиновьева.
- Свитчинговые методы построения кодов. Коды Моллара.
- Матрица Адамара. Коды Адамара. Связь кодов Адамара с кодами Хэмминга и блок-схемами.
- Коды Рида-Маллера, группа автоморфизмов. Код Голея, его свойства. Код Нордстрома-Робинсона.
- Двойственные коды. Весовой энумератор. Дискретное преобразование Фурье. Тождества Мак-Вильямс.
2. Введение в криптологию
- Введение в криптологию. Секретность и имитостойкость. Основные идеи. Криптография и криптоанализ.
- Криптографические системы с секретными ключами. Подстановки. Перестановки. Полиалфавитные шифры. Шифр с бегущим ключом. Криптографические системы коды. Стандарты шифрования данных DES, AES, GOST. S-блоки.
- Теорема Шеннона о существовании совершенно секретных шифров.
- Криптографические системы с открытыми ключами. Односторонняя функция с лазейкой. “Шарады” Меркля.
- Криптосистема Диффи и Хэллмана и проблема вычисления дискретного логарифма.
- Криптосистема RSA и проблема разложения числа на простые сомножители.
- Криптосистема Меркля-Хэллмана, основанная на задаче об укладке ранца. Криптоанализ системы Меркля-Хэллмана.
- Криптосистема Шамира.
- Кодирующая система МакЭлиса. Криптосистема МакЭлиса, построенная на коде Рида-Маллера.
- Цифровая подпись, применение различных криптосистем для создания цифровой подписи.
- Криптосистемы на эллиптических кривых.
- Применение теории кодирования в криптографии. Проблема аутентификации. Распределение секретов.
- APN-функции, их свойства.
3. Сжатие информации
- Разделимые и префиксные коды. Стоимость кодирования. Неравенство Крафта-Макмиллана. Теорема Крафта, теорема Макмиллана.
- Оптимальное кодирование. Метод Хаффмена. Метод Фано.
- Энтропия, ее свойства. Метод Шеннона для бернуллиевских источников. Теорема Шеннона.
- Критерий разделимости побуквенного кодирования. Теоремы Маркова. Алгоритм распознавания разделимости.
- Универсальное кодирование, теорема Фитингофа.
- Код Левенштейна. Код “стопка книг”.
- Адаптивные методы сжатия данных. Методы Лемпела-Зива и их модификации. Адаптивный метод Хаффмена.
- Арифметический код.
Основная литература:
, , Основы современной криптографии для специалистов в информационных технологиях, Изд-во “Научный Мир”, М. 2004. , , "Криптографические методы защиты информации", Изд-во «Телеком. Горячая линия, М., 2005. Кричевский и поиск информации. Наука, 1986. Нечаев криптографии. Основы теории защиты информации. – М.: Высшая школа. 1999. – 109 с. Шоломов теории дискретных логических и вычислительных устройств. – М.: Наука. 1980. – 399 с. Потапов информации. Кодирование дискретных вероятностных источников. Новосибирск: Изд. центр НГУ. 19с.7. Баричев С, Основы современной криптографии, Москва, 20с.
Криптография с открытым ключом. Пер. с англ. – М.: Мир. 1996. – 318 с.Дополнительная литература:
Шеннон по теории информации и кибернетике. М.: ИЛ. 1963. Введение в криптографию. Под ред. . Москва, МЦНМО – ЧеРо, 1999. , Введение в теорию кодирования, учебное пособие для студентов ММФ и ФИТ НГУ., Изд. НГУ, 2006г., 123 с., под грифом УМО.Интернет-ресурсы:
1. http://www. codingtheory. *****
2. Потапов в теорию информации / 102 c., см. http://www. math. *****
