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

О семинаре

Научный семинар знакомит участников с методами представления, передачи и защиты информации, включая изучение предварительных сведений из алгебры, теории чисел и дискретной математики. Рассматриваются основные направления современной криптографии, включая анализ конкретных криптосистем и протоколов, и теории кодирования. Семинар включает доклады участников с их последующим обсуждением. Участие в семинаре позволит участникам, среди прочего, освоить практические приложения материала, изученного на базовых математических дисциплинах на первом году обучения, и поможет закрепить этот материал. Большое внимание уделяется качеству подготовки презентации и умению доступно изложить изученный материал.

Семинар проводится для студентов 2 курса ОП «Программная инженерия» в 1-3 модулях.

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

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

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

Шустрова Юлия, t.me/jshustrik, yupshustrova_1@edu.hse.ru

Пичугин Владислав, t.me/temporary_nickname, vipichugin_1@edu.hse.ru

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

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

[Форма для сдачи домашек]

[Форма для загрузки презентаций]

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

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

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

Литература

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

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

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

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

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

[ВНЦ] С.Г.Влэдуц, Д.Ю.Ногин и М.А.Цфасман. Алгеброгеометрические коды. М.: МЦНМО, 2003

[КвЛ] П.Камерон и Дж.ван Линт. Теория графов, теория кодирования и блок-схемы. М.: Наука, 1980

[РРШ] А.Ромащенко, А.Румянцев и А.Шень. Заметки по теории кодирования. М.: МЦНМО, 2011

Оценивание

Итоговая оценка ИО по 10-балльной шкале формируется как взвешенная сумма, в зависимости от количества докладов.

Участие в семинаре без доклада:

• контроль посещаемости научного семинара (КП, 10-балльная оценка);
• решение домашних заданий (ДЗ, 10-балльная оценка);
• устный экзамен в конце 3-го модуля в форме собеседования (УЭ, 10-балльная оценка);
• ИО = 0,2 КП + 0,3 ДЗ + 0,5 УЭ

Участие в семинаре с докладом по одной из частей курса:

• контроль посещаемости научного семинара (КП, 10-балльная оценка);
• решение домашних заданий (ДЗ, 10-балльная оценка);
• доклад с презентацией (ДП, 10-балльная оценка);
• устный экзамен в конце 3-го модуля в форме собеседования той части курса, по которой доклада не было (УЭ, 10-балльная оценка);
• ИО = 0,2 КП + 0,2 ДЗ + 0,3 ДП + 0.3 УЭ

Участие в семинаре с докладами по обеим частям курса:

• контроль посещаемости научного семинара (КП, 10-балльная оценка);
• решение домашних заданий (ДЗ, 10-балльная оценка);
• доклад с презентацией по первой (ДП1, 10-балльная оценка) и по второй (ДП2, 10-балльная оценка) части курса;
• ИО = 0,2 КП + 0,2 ДЗ + 0,3 ДП1 + 0.3 ДП2

Округление производится для итоговой оценки. Способ округления — арифметический.