НИС Методы и алгоритмы защиты информации 2022/2023

О семинаре

Цель семинара – познакомить участников с основными понятиями, методами и алгоритмами криптографии и теории кодирования. Параллельно мы обсуждаем необходимые сведения из алгебры, теории чисел и дискретной математики. Семинар проходит в форме докладов участников с их последующим обсуждением. Участие в семинаре позволит освоить современные методы защиты и передачи информации. Также будут даны многочисленные примеры практического использования материала, излагаемого в базовых математических курсах.

Семинар проводится для студентов 2 курса в 1-3 модулях.

Преподаватель

Аржанцев Иван Владимирович, arjantsev@hse.ru

Учебные ассистенты

Коннов Илья. t.me/iliago, vk.com/iliago, iakonnov@edu.hse.ru

Полезные ссылки

Таблица с оценками

Классрум для сдачи домашних заданий

План семинара

Криптография

№	Тема доклада	Литература
1	Простейшие криптосистемы. Сдвиг и аффинное преобразование. Частотный анализ. Биграммы. Ключ шифрования и ключ дешифрования. Классические криптосистемы и системы с открытым ключом	К, Гл. III, пар. 1 и Гл. IV, пар. 1
2	Необходимые факты из теории чисел: обратимость вычета по данному модулю, алгоритм нахождения обратного элемента, малая теорема Ферма, функция Эйлера и теорема Эйлера, китайская теорема об остатках, методы быстрого возведения в степень	K, Гл. I
3	Квадратичные вычеты и закон взаимности	K, Гл. II, пар. 2
4	Необходимые сведения из алгебры: группы и подгруппы, примеры конечных групп, порядок элемента, циклические группы и их порождающие	[любой нравящийся вам учебник по алгебре]
5	Строение конечных полей	ЛН
6	Задача дискретного логарифмирования и основанные на ней криптосистемы: система Диффи-Хеллмана обмена ключами, системы Мэсси-Омура и Эль-Гамаля	[K, Гл. IV, пар. 1, 3], [П, 1.3], [В,Гл. 5]
7	Алгоритмы решения задачи дискретного логарифмирования	K, Гл. IV, пар. 3
8	Криптосистема RSA	[K, Гл. IV, пар. 2], [П, 1.2]
9	Понятие электронной подписи. Электронная подпись в RSA и по Эль-Гамалю	[K, Гл. IV, пар. 1, 3], [П, 1.3], [В,Гл. 5]
10	Проверка чисел на простоту и задача факторизации. Решето Эратосфена. Псевдопростые числа и числа Кармайкла. Метод Поклингтона. (p-1)-метод Полларда	[K, Гл. V], [П, 2.4], [В, Гл. 1-2]
11	Задача о рюкзаке как задача комбинаторной оптимизации. Быстрорастущие наборы. Рюкзачная криптосистема	K, Гл. IV, пар. 4
12	Протоколы с нулевым разглашением. Три примера: раскраска карты в три цвета, поиск гамильтонова пути и извлечение корня в кольце вычетов	K, Гл. IV, пар. 5
13	Математика разделенного секрета. Пороговые (n,k)-схемы доступа. Схема Шамира и схема Блэкли.	Я, Гл. 5
14	Разделение секрета и теория матроидов	Я, Гл. 5
15	Математика эллиптических кривых: групповой закон, формулы сложения и удвоения точек, теорема Хассе о числе точек на эллиптической кривой	[K, Гл. VI, пар. 1], [П, гл. 4]
16	Нахождение точки на эллиптической кривой. Задача дискретного логарифмирования. Криптосистемы на эллиптических кривых: аналоги систем Диффи-Хеллмана и Эль-Гамаля	K, Гл. VI, пар. 2
17	Проверка чисел на простоту и разложение на множители при помощи эллиптических кривых. Аналог метода Поклингтона и метод Ленстры	[K, Гл. VI, пар. 3-4], [В, Гл. 4]

Литература

[В] О.Н.Василенко. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО, 2003, 325 стр.

[К] Н.Коблиц. Курс теории чисел и криптографии. М.: ТВП, 2001, 254 стр.

[ЛН] Р.Лидл и Г.Нидеррайтер. Конечные поля. М.: Мир, 1988

[П] Ю.Г.Прохоров. Эллиптические кривые и криптография. Семестр 1. М.: МГУ, 2007. 143 стр.

[Я] Введение в криптографию. Под редакцией В.В.Ященко. М.: МЦНМО, 2012, 352 стр.