Кодирование и защита информации
Название спецкурса на английском языке
Coding and information security
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
Подразделение
[Кафедра МаТИС]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Кодирование, криптография, стеганография. Исторический очерк развития.
Введение в теорию кодирования. Алфавитное кодирование. Префиксные коды. Теорема Маркова. Неравенство МакМиллана.
Коды с минимальной избыточностью (коды Хаффмана).
Самокорректирующиеся коды (коды Хэмминга). Геометрические приложения.
Математическая модель шифра замены. Классификация шифров замены.
Шифры перестановки. Элементы анализа.
Анализ шифра Виженера: нахождение длины ключа с использованием индекса совпадения; нахождение ключа с использованием взаимного индекса совпадения.
Статистические характеристики открытых текстов. Пример вскрытия шифра простой замены.
Блочные шифры. Стандарты шифрования данных. Режимы использования блочных шифров.
Введение в теорию сложности вычислений. Скорость роста функций. Сложностные классы. Труднорешаемые задачи и их применение в криптографии.
Шифрование с открытым ключом: принципы и примеры протоколов.
Задача о рюкзаке и рюкзачные системы.
Задача дискретного логарифмирования. Алгоритм Сильвера-Полига-Хеллмана, индексный алгоритм.
Проверка чисел на простоту. Вероятностные тесты на простоту. Тест Соловея-Штрассена. Тест Миллера-Рабина.
Факторизация больших составных чисел. Алгоритм Полларда. Факторизация Ферма. Алгоритм факторных баз.
Эллиптические кривые и их применение в криптографии. Обобщение известных криптосистем на эллиптические кривые.
Совершенные шифры. Латинские квадраты и их свойства. Построение параметрических классов латинских квадратов.
Клеточные автоматы и их использование в криптографии.
Системы шифрования, основанные на сложностных задачах комбинаторной теории групп.
Введение в теорию кодирования. Алфавитное кодирование. Префиксные коды. Теорема Маркова. Неравенство МакМиллана.
Коды с минимальной избыточностью (коды Хаффмана).
Самокорректирующиеся коды (коды Хэмминга). Геометрические приложения.
Математическая модель шифра замены. Классификация шифров замены.
Шифры перестановки. Элементы анализа.
Анализ шифра Виженера: нахождение длины ключа с использованием индекса совпадения; нахождение ключа с использованием взаимного индекса совпадения.
Статистические характеристики открытых текстов. Пример вскрытия шифра простой замены.
Блочные шифры. Стандарты шифрования данных. Режимы использования блочных шифров.
Введение в теорию сложности вычислений. Скорость роста функций. Сложностные классы. Труднорешаемые задачи и их применение в криптографии.
Шифрование с открытым ключом: принципы и примеры протоколов.
Задача о рюкзаке и рюкзачные системы.
Задача дискретного логарифмирования. Алгоритм Сильвера-Полига-Хеллмана, индексный алгоритм.
Проверка чисел на простоту. Вероятностные тесты на простоту. Тест Соловея-Штрассена. Тест Миллера-Рабина.
Факторизация больших составных чисел. Алгоритм Полларда. Факторизация Ферма. Алгоритм факторных баз.
Эллиптические кривые и их применение в криптографии. Обобщение известных криптосистем на эллиптические кривые.
Совершенные шифры. Латинские квадраты и их свойства. Построение параметрических классов латинских квадратов.
Клеточные автоматы и их использование в криптографии.
Системы шифрования, основанные на сложностных задачах комбинаторной теории групп.
Список источников
А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин, «Основы криптографии», Москва: Гелиос АРВ, 2001.
Н. Коблиц, «Курс теории чисел и криптографии», Москва: ТВП, 2001.
К. Шеннон, «Теория связи в секретных системах», в сб. «Работы по теории информации и кибернетике», Москва: Иностранная Литература, 1963, сс. 333-369.
J. Denes and A.D. Keedwell, «Latin squares and their applications», New York: Academic Press, 1974
Т. Кормен, Ч. Лейзерсон, Р. Ривест, «Алгоритмы: построение и анализ», Москва: МЦНМО, 2000.
В.А. Носов, «основы теории алгоритмов и анализа их сложности», Москва: 1992.
А. Саломаа, «Криптография с открытым ключом», Москва: Мир, 1995.
В.Б. Кудрявцев, А.С. Подколзин, А.А. Болотов, «Основы теории однородных структур», Москва: Наука, 1990.
A. Myasnikov, V. Shpilrain, A. Ushakov, «Group-based cryptography» Basel: Birkhauser, 2008.
Е.В. Панкратьев, «Элементы компьютерной алгебры», Москва: Бином, 2007.
Н. Коблиц, «Курс теории чисел и криптографии», Москва: ТВП, 2001.
К. Шеннон, «Теория связи в секретных системах», в сб. «Работы по теории информации и кибернетике», Москва: Иностранная Литература, 1963, сс. 333-369.
J. Denes and A.D. Keedwell, «Latin squares and their applications», New York: Academic Press, 1974
Т. Кормен, Ч. Лейзерсон, Р. Ривест, «Алгоритмы: построение и анализ», Москва: МЦНМО, 2000.
В.А. Носов, «основы теории алгоритмов и анализа их сложности», Москва: 1992.
А. Саломаа, «Криптография с открытым ключом», Москва: Мир, 1995.
В.Б. Кудрявцев, А.С. Подколзин, А.А. Болотов, «Основы теории однородных структур», Москва: Наука, 1990.
A. Myasnikov, V. Shpilrain, A. Ushakov, «Group-based cryptography» Basel: Birkhauser, 2008.
Е.В. Панкратьев, «Элементы компьютерной алгебры», Москва: Бином, 2007.
Дополнительная информация
В курсе освещаются следующие вопросы:
1) начальные сведения по теории кодирования и шифрования;
2) основные понятия теории сложности вычислений;
3) круг задач, решаемых с помощью криптографии;
4) симметричное и асимметричное шифрование;
5) криптографические протоколы, основанные на сложностных проблемах из различных областей алгебры и дискретной математики.
Нужные для понимания спецкурса сведения будут кратко напоминаться по ходу лекций.
День недели
пятница
Время
16:45-18:20
Аудитория
405
Дата первого занятия
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.