НИС Методы и алгоритмы защиты информации 2024/2025 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
(добавлены оценки за 3 декабря) |
(поправлены темы 2 части) |
||
| Строка 170: | Строка 170: | ||
|| [K, Гл. VI, пар. 3-4], [В, Гл. 4] | || [K, Гл. VI, пар. 3-4], [В, Гл. 4] | ||
|| Тугов Евгений | || Тугов Евгений | ||
| − | || | + | || 14 января |
| − | || | + | || 10 |
|- | |- | ||
|} | |} | ||
| Строка 184: | Строка 184: | ||
|| Основные понятия теории кодирования. Коды, исправляющие ошибки. Расстояние Хемминга и неравенство треугольника. [7,4,3]_2-код Хэмминга и его синдром | || Основные понятия теории кодирования. Коды, исправляющие ошибки. Расстояние Хемминга и неравенство треугольника. [7,4,3]_2-код Хэмминга и его синдром | ||
|| [РРШ, раздел 1], [КвЛ, раздел 7], [ЛН, глава 9, раздел 1], [ВНЦ, 1.1.1] | || [РРШ, раздел 1], [КвЛ, раздел 7], [ЛН, глава 9, раздел 1], [ВНЦ, 1.1.1] | ||
| − | || | + | || Русидзе Анна |
| − | || | + | || 14 января |
|| | || | ||
|- | |- | ||
| 2 | | 2 | ||
| − | || Линейная алгебра над конечными полями: число прямых и число k-мерных подпространств в n-мерном пространстве над полем из q элементов; число невырожденных матриц порядка n и число матриц с определителем 1 порядка n над полем из q элементов | + | || Линейная алгебра над конечными полями: число прямых и число k-мерных подпространств в n-мерном пространстве над полем из q элементов; число невырожденных матриц порядка n и число матриц с определителем 1 порядка n над полем из q элементов |
|| [Разобраться самостоятельно] | || [Разобраться самостоятельно] | ||
| − | || | + | || Молонов Борис |
| − | || | + | || 14 января |
|| | || | ||
|- | |- | ||
| Строка 200: | Строка 200: | ||
|| Линейные коды и их характеристики. Порождающая и проверочная матрицы. Двойственный код и тождество Мак-Вильямс. Эквивалентность кодов. Методы вычисления минимального расстояния для подпространства | || Линейные коды и их характеристики. Порождающая и проверочная матрицы. Двойственный код и тождество Мак-Вильямс. Эквивалентность кодов. Методы вычисления минимального расстояния для подпространства | ||
|| [РРШ, раздел 4], [ЛН, глава 9, раздел 1], [КвЛ, раздел 7], [ВНЦ, 1.1.1 - 1.1.3] | || [РРШ, раздел 4], [ЛН, глава 9, раздел 1], [КвЛ, раздел 7], [ВНЦ, 1.1.1 - 1.1.3] | ||
| − | || | + | || Грузинцев Егор |
|| | || | ||
|| | || | ||
| Строка 208: | Строка 208: | ||
|| Неравенство Синглтона. Граница Хэмминга и граница Гилберта. Оценка Плоткина | || Неравенство Синглтона. Граница Хэмминга и граница Гилберта. Оценка Плоткина | ||
|| [РРШ, разделы 2,7,15], [ЛН, глава 9, раздел 1], [ВНЦ, 1.1.4] | || [РРШ, разделы 2,7,15], [ЛН, глава 9, раздел 1], [ВНЦ, 1.1.4] | ||
| − | || | + | || Овсянникова Александра |
|| | || | ||
|| | || | ||
| Строка 214: | Строка 214: | ||
| 5 | | 5 | ||
| − | || Совершенные коды, их классификация | + | || Обобщенные коды Хэмминга. Совершенные коды, их классификация. Проверка совершенности кодов Хэмминга. |
|| [РРШ, раздел 6], [ВНЦ, теорема 1.2.25 - обязательно включить!], [КвЛ, раздел 8] | || [РРШ, раздел 6], [ВНЦ, теорема 1.2.25 - обязательно включить!], [КвЛ, раздел 8] | ||
| − | || | + | || Лелекова Анастасия |
|| | || | ||
|| | || | ||
| Строка 224: | Строка 224: | ||
|| Коды Рида-Соломона и их декодирование | || Коды Рида-Соломона и их декодирование | ||
|| [РРШ, разделы 8-9] | || [РРШ, разделы 8-9] | ||
| − | || | + | || Анохин Антон |
|| | || | ||
|| | || | ||
| Строка 233: | Строка 233: | ||
|| Коды Адамара и коды Рида-Маллера | || Коды Адамара и коды Рида-Маллера | ||
|| [РРШ, разделы 17-19], [ВНЦ, 1.2.2] | || [РРШ, разделы 17-19], [ВНЦ, 1.2.2] | ||
| − | || | + | || Анненков Алексей |
|| | || | ||
|| | || | ||
| Строка 242: | Строка 242: | ||
|| Циклические коды и главные идеалы. Бинарный и тернарный коды Голея. Проверка совершенности | || Циклические коды и главные идеалы. Бинарный и тернарный коды Голея. Проверка совершенности | ||
|| [КвЛ, раздел 8], [ЛН, глава 9, раздел 2] | || [КвЛ, раздел 8], [ЛН, глава 9, раздел 2] | ||
| − | || | + | || Булгаков Тимофей |
|| | || | ||
|| | || | ||
| Строка 249: | Строка 249: | ||
| 9 | | 9 | ||
| − | || | + | || Коды Голея и футбольный тотализатор |
|| [РРШ, раздел 20], [ЛН, глава 9, раздел 2], [КвЛ, раздел 8] | || [РРШ, раздел 20], [ЛН, глава 9, раздел 2], [КвЛ, раздел 8] | ||
| − | || | + | || Амиров Агиль |
|| | || | ||
|| | || | ||
| Строка 257: | Строка 257: | ||
| 10 | | 10 | ||
| − | || | + | || БЧХ коды |
| − | || | + | || Максимов Тимофей |
|| | || | ||
|| | || | ||
| Строка 268: | Строка 268: | ||
|| Декодирование линейных кодов. Синдромы. Алгоритм декодирования по лидеру смежного класса | || Декодирование линейных кодов. Синдромы. Алгоритм декодирования по лидеру смежного класса | ||
|| [ЛН, глава 9, раздел 1] | || [ЛН, глава 9, раздел 1] | ||
| − | || | + | || Гулынин Платон |
|| | || | ||
|| | || | ||
| Строка 275: | Строка 275: | ||
| 12 | | 12 | ||
| − | || Линейные рекуррентные последовательности | + | || Линейные рекуррентные последовательности, их свойства и связь с теорией кодирования |
|| [ЛН, глава 8 + пример 9.39 – применение к кодированию] | || [ЛН, глава 8 + пример 9.39 – применение к кодированию] | ||
| − | || | + | || Владимиров Алексей |
|| | || | ||
|| | || | ||
| Строка 286: | Строка 286: | ||
|| Конечные геометрии, системы Штейнера и еще один подход к кодам Рида-Маллера | || Конечные геометрии, системы Штейнера и еще один подход к кодам Рида-Маллера | ||
|| [ЛН, глава 9, разделы 3-4], [КвЛ, раздел 10] | || [ЛН, глава 9, разделы 3-4], [КвЛ, раздел 10] | ||
| − | || | + | || Дик Кирилл |
|| | || | ||
|| | || | ||
Версия 15:14, 16 января 2025
Содержание
О семинаре
Научный семинар знакомит участников с методами представления, передачи и защиты информации, включая изучение предварительных сведений из алгебры, теории чисел и дискретной математики. Рассматриваются основные направления современной криптографии, включая анализ конкретных криптосистем и протоколов, и теории кодирования. Семинар включает доклады участников с их последующим обсуждением. Участие в семинаре позволит участникам, среди прочего, освоить практические приложения материала, изученного на базовых математических дисциплинах на первом году обучения, и поможет закрепить этот материал. Большое внимание уделяется качеству подготовки презентации и умению доступно изложить изученный материал.
Семинар проводится для студентов 2 курса ОП «Программная инженерия» в 1-3 модулях.
Преподаватель
Аржанцев Иван Владимирович, arjantsev@hse.ru
Учебные ассистенты
Шустрова Юлия, t.me/jshustrik, yupshustrova_1@edu.hse.ru
Арисова Елизавета, t.me/arisovaliza, eiarisova_1@edu.hse.ru
Полезные ссылки
Классрум для сдачи домашних заданий
План семинара
Криптография
| № | Тема доклада | Литература | Докладчик | Дата доклада | Оценка |
|---|---|---|---|---|---|
| 1 | Простейшие криптосистемы. Сдвиг и аффинное преобразование. Частотный анализ. Биграммы. Ключ шифрования и ключ дешифрования. Классические криптосистемы
и системы с открытым ключом |
[К, Гл. III, пар. 1 и Гл. IV, пар. 1] | Авраменко Денис | 24 сентября | 9 |
| 2 | Необходимые факты из теории чисел: обратимость вычета по данному модулю, алгоритм нахождения обратного элемента, малая теорема Ферма, функция Эйлера и теорема Эйлера, китайская теорема об остатках, методы быстрого возведения в степень | [K, Гл. I] | Дик Кирилл | 24 сентября | 10 |
| 3 | Квадратичные вычеты и закон взаимности | [K, Гл. II, пар. 2] | Леонов Вадим | 8 октября | 10 |
| 4 | Необходимые сведения из алгебры: группы и подгруппы, примеры конечных групп, порядок элемента, циклические группы и их порождающие | [любой нравящийся вам учебник по алгебре] | Голикова Василиса | 8 октября | 10 |
| 5 | Строение конечных полей | [ЛН, моя лекция на ПМИ] | Максимов Тимофей | 8 октября | 10 |
| 6 | Задача дискретного логарифмирования и основанные на ней криптосистемы: система Диффи-Хеллмана обмена ключами, системы Мэсси-Омура и Эль-Гамаля | [K, Гл. IV, пар. 1, 3], [П, 1.3], [В,Гл. 5] | Зенин Вадим | 22 октября | 9 |
| 7 | Алгоритмы решения задачи дискретного логарифмирования | [K, Гл. IV, пар. 3] | Хашпаков Астемир | 22 октября | 10 |
| 8 | Криптосистема RSA | [K, Гл. IV, пар. 2], [П, 1.2] | Яхьяев Тамирлан | 22 октября | 10 |
| 9 | Задача про систему RSA в августе 1977 года в колонке «Математические игры» Мартина Гарднера в журнале Scientific American | [открытые источники] | Зайцев Кирилл | 5 ноября | 10 |
| 10 | Понятие электронной подписи. Электронная подпись в RSA и по Эль-Гамалю | [K, Гл. IV, пар. 1, 3], [П, 1.3], [В,Гл. 5] | Лазаренко Александр | 5 ноября | 10 |
| 11 | Проверка чисел на простоту и задача факторизации. Решето Эратосфена. Псевдопростые числа и числа Кармайкла. Метод Поклингтона. (p-1)-метод Полларда [можно разделить на два доклада] | [K, Гл. V], [П, 2.4], [В, Гл. 1-2] | Булгаков Тимофей | 5 ноября | 10 |
| 12 | Задача о рюкзаке как задача комбинаторной оптимизации. Быстрорастущие наборы. Рюкзачная криптосистема | [K, Гл. IV, пар. 4] | Чанышева Диана | 26 ноября | 10 |
| 13 | Протоколы с нулевым разглашением. Три примера: раскраска карты в три цвета, поиск гамильтонова пути и извлечение корня в кольце вычетов | [K, Гл. IV, пар. 5] | Мягкова Анна | 26 ноября | 10 |
| 14 | Математика разделенного секрета. Пороговые (n,k)-схемы доступа. Схема Шамира и схема Блэкли. | [Я, Гл. 5] | Носов Андрей | 3 декабря | 10 |
| 15 | Разделение секрета и теория матроидов | [Я, Гл. 5] | Рогачков Антон | 3 декабря | 9 |
| 16 | Математика эллиптических кривых: групповой закон, формулы сложения и удвоения точек, теорема Хассе о числе точек на эллиптической кривой | [K, Гл. VI, пар. 1], [П, гл. 4] | Владимиров Алексей | 3 декабря | 10 |
| 17 | Нахождение точки на эллиптической кривой. Задача дискретного логарифмирования. Криптосистемы на эллиптических кривых: аналоги систем Диффи-Хеллмана и Эль-Гамаля | [K, Гл. VI, пар. 2] | Сокуров Идар | 3 декабря | 10 |
| 18 | Проверка чисел на простоту и разложение на множители при помощи эллиптических кривых. Аналог метода Поклингтона и метод Ленстры | [K, Гл. VI, пар. 3-4], [В, Гл. 4] | Тугов Евгений | 14 января | 10 |
Теория кодирования
| № | Тема доклада | Литература | Докладчик | Дата доклада | Оценка |
|---|---|---|---|---|---|
| 1 | Основные понятия теории кодирования. Коды, исправляющие ошибки. Расстояние Хемминга и неравенство треугольника. [7,4,3]_2-код Хэмминга и его синдром | [РРШ, раздел 1], [КвЛ, раздел 7], [ЛН, глава 9, раздел 1], [ВНЦ, 1.1.1] | Русидзе Анна | 14 января | |
| 2 | Линейная алгебра над конечными полями: число прямых и число k-мерных подпространств в n-мерном пространстве над полем из q элементов; число невырожденных матриц порядка n и число матриц с определителем 1 порядка n над полем из q элементов | [Разобраться самостоятельно] | Молонов Борис | 14 января | |
| 3 | Линейные коды и их характеристики. Порождающая и проверочная матрицы. Двойственный код и тождество Мак-Вильямс. Эквивалентность кодов. Методы вычисления минимального расстояния для подпространства | [РРШ, раздел 4], [ЛН, глава 9, раздел 1], [КвЛ, раздел 7], [ВНЦ, 1.1.1 - 1.1.3] | Грузинцев Егор | ||
| 4 | Неравенство Синглтона. Граница Хэмминга и граница Гилберта. Оценка Плоткина | [РРШ, разделы 2,7,15], [ЛН, глава 9, раздел 1], [ВНЦ, 1.1.4] | Овсянникова Александра | ||
| 5 | Обобщенные коды Хэмминга. Совершенные коды, их классификация. Проверка совершенности кодов Хэмминга. | [РРШ, раздел 6], [ВНЦ, теорема 1.2.25 - обязательно включить!], [КвЛ, раздел 8] | Лелекова Анастасия | ||
| 6 | Коды Рида-Соломона и их декодирование | [РРШ, разделы 8-9] | Анохин Антон | ||
| 7 | Коды Адамара и коды Рида-Маллера | [РРШ, разделы 17-19], [ВНЦ, 1.2.2] | Анненков Алексей | ||
| 8 | Циклические коды и главные идеалы. Бинарный и тернарный коды Голея. Проверка совершенности | [КвЛ, раздел 8], [ЛН, глава 9, раздел 2] | Булгаков Тимофей | ||
| 9 | Коды Голея и футбольный тотализатор | [РРШ, раздел 20], [ЛН, глава 9, раздел 2], [КвЛ, раздел 8] | Амиров Агиль | ||
| 10 | БЧХ коды | Максимов Тимофей | |||
| 11 | Декодирование линейных кодов. Синдромы. Алгоритм декодирования по лидеру смежного класса | [ЛН, глава 9, раздел 1] | Гулынин Платон | ||
| 12 | Линейные рекуррентные последовательности, их свойства и связь с теорией кодирования | [ЛН, глава 8 + пример 9.39 – применение к кодированию] | Владимиров Алексей | ||
| 13 | Конечные геометрии, системы Штейнера и еще один подход к кодам Рида-Маллера | [ЛН, глава 9, разделы 3-4], [КвЛ, раздел 10] | Дик Кирилл |
Литература
[В] О.Н.Василенко. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО, 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
Округление производится для итоговой оценки. Способ округления — арифметический.
