НИС Методы и алгоритмы защиты информации — различия между версиями
Материал из Wiki - Факультет компьютерных наук
м |
м |
||
| Строка 45: | Строка 45: | ||
| 8 || Проверка чисел на простоту и задача факторизации. Решето Эратосфена. Псевдопростые числа и числа Кармайкла. Метод Поклингтона.<br/> (p-1)-метод Полларда. || K, Гл. V <br/>П, 2.4 <br/>В, Гл. 1-2 || <center>Абаев Фёдор</center> || <center>09.11.2021</center> || <center>completed</center> || <center>23.11.2021</center> || <center>completed</center> | | 8 || Проверка чисел на простоту и задача факторизации. Решето Эратосфена. Псевдопростые числа и числа Кармайкла. Метод Поклингтона.<br/> (p-1)-метод Полларда. || K, Гл. V <br/>П, 2.4 <br/>В, Гл. 1-2 || <center>Абаев Фёдор</center> || <center>09.11.2021</center> || <center>completed</center> || <center>23.11.2021</center> || <center>completed</center> | ||
|- | |- | ||
| − | | 9 || Задача о рюкзаке как задача комбинаторной оптимизации.<br/> Быстрорастущие наборы. Рюкзачная криптосистема || K, Гл. IV, пар. 4 || <center> | + | | 9 || Задача о рюкзаке как задача комбинаторной оптимизации.<br/> Быстрорастущие наборы. Рюкзачная криптосистема || K, Гл. IV, пар. 4 || <center>Ломакин Павел</center> || <center>08.02.2022</center> || || <center>TBA</center> || |
|- | |- | ||
| 10 || Протоколы с нулевым разглашением. Три примера: раскраска карты в три цвета,<br/> поиск гамильтонова пути и извлечение корня в кольце вычетов || K, Гл. IV, пар. 5 || <center>Гайсин Ислам</center> || <center>09.11.2021</center> || <center>completed</center> || <center>-</center> || <center>-</center> | | 10 || Протоколы с нулевым разглашением. Три примера: раскраска карты в три цвета,<br/> поиск гамильтонова пути и извлечение корня в кольце вычетов || K, Гл. IV, пар. 5 || <center>Гайсин Ислам</center> || <center>09.11.2021</center> || <center>completed</center> || <center>-</center> || <center>-</center> | ||
|- | |- | ||
| − | | 11 || Математика разделенного секрета. Пороговые (n,k)-схемы доступа.<br/> Схема Шамира и схема Блэкли. Связь с теорией матроидов || Я, Гл. 5 || <center>Коннов Илья</center> || <center>23.11.2021</center> || <center>completed</center> || <center>10.01.2022</center> || | + | | 11 || Математика разделенного секрета. Пороговые (n,k)-схемы доступа.<br/> Схема Шамира и схема Блэкли. Связь с теорией матроидов || Я, Гл. 5 || <center>Коннов Илья</center> || <center>23.11.2021</center> || <center>completed</center> || <center>10.01.2022</center> || <center>completed</center> |
|- | |- | ||
| 12 || Криптосистема Рабина. McEliece || - || <center>Егоров Михаил</center> || <center>11.01.2022</center> || <center>completed</center> || <center>24.01.2022</center> || | | 12 || Криптосистема Рабина. McEliece || - || <center>Егоров Михаил</center> || <center>11.01.2022</center> || <center>completed</center> || <center>24.01.2022</center> || | ||
| Строка 57: | Строка 57: | ||
| 14 || Нахождение точки на эллиптической кривой. Задача дискретного логарифмирования. Криптосистемы на эллиптических кривых: аналоги систем Диффи-Хеллмана <br/>и Эль-Гамаля || K, Гл. VI, пар. 2 || <center>Верзаков Ефим</center> || <center>11.01.2022</center> || <center>completed</center> || <center>24.01.2022</center> || | | 14 || Нахождение точки на эллиптической кривой. Задача дискретного логарифмирования. Криптосистемы на эллиптических кривых: аналоги систем Диффи-Хеллмана <br/>и Эль-Гамаля || K, Гл. VI, пар. 2 || <center>Верзаков Ефим</center> || <center>11.01.2022</center> || <center>completed</center> || <center>24.01.2022</center> || | ||
|- | |- | ||
| − | | 15 || Проверка чисел на простоту и разложение на множители при помощи<br/> эллиптических кривых. Аналог метода Поклингтона и метод Ленстры || K, Гл. VI, пар. 3-4 <br/>В, Гл. 4 || <center>Порохнин Даниил</center> || <center> | + | | 15 || Проверка чисел на простоту и разложение на множители при помощи<br/> эллиптических кривых. Аналог метода Поклингтона и метод Ленстры || K, Гл. VI, пар. 3-4 <br/>В, Гл. 4 || <center>Порохнин Даниил</center> || <center>08.02.2022</center> || || <center>TBA</center> || |
|- | |- | ||
|} | |} | ||
| Строка 67: | Строка 67: | ||
! № !! Тема доклада !! Литература !! Отвечающий доклад !! Дата выступления || Отметка о выполнении || Дедлайн ДЗ || Отметка о проверке | ! № !! Тема доклада !! Литература !! Отвечающий доклад !! Дата выступления || Отметка о выполнении || Дедлайн ДЗ || Отметка о проверке | ||
|- | |- | ||
| − | | 1 || Основные понятия теории кодирования. Коды, исправляющие ошибки. Расстояние Хемминга и неравенство треугольника. [7,4,3]_2-код Хэмминга и его синдром || РРШ, раздел 1 <br/> КвЛ, разд. 7 <br/>ЛН || <center>Ломакин Павел</center> || <center>25.01.2022</center> || || <center> | + | | 1 || Основные понятия теории кодирования. Коды, исправляющие ошибки. Расстояние Хемминга и неравенство треугольника. [7,4,3]_2-код Хэмминга и его синдром || РРШ, раздел 1 <br/> КвЛ, разд. 7 <br/>ЛН || <center>Ломакин Павел</center> || <center>25.01.2022</center> || <center>completed</center> || <center>08.02.2022</center> || |
|- | |- | ||
| − | | 2 || Линейная алгебра над конечными полями: число прямых, число k-мерных<br/> подпространств и число невырожденных матриц в n-мерном пространстве над<br/> полем из q элементов. || - || <center>Ищенко Алексей</center> || <center> | + | | 2 || Линейная алгебра над конечными полями: число прямых, число k-мерных<br/> подпространств и число невырожденных матриц в n-мерном пространстве над<br/> полем из q элементов. || - || <center>Ищенко Алексей</center> || <center>08.02.2022</center> || || <center>TBA</center> || |
|- | |- | ||
| − | | 3 || Линейные коды и их характеристики. Порождающая и проверочная матрицы. <br/>Двойственный код и тождество Мак-Вильямса. Эквивалентность кодов.<br/> Методы вычисления минимального расстояния для подпространства || РРШ, разд. 4 <br/>ЛН || <center>Адамян Эдвард</center> || <center> | + | | 3 || Линейные коды и их характеристики. Порождающая и проверочная матрицы. <br/>Двойственный код и тождество Мак-Вильямса. Эквивалентность кодов.<br/> Методы вычисления минимального расстояния для подпространства || РРШ, разд. 4 <br/>ЛН || <center>Адамян Эдвард</center> || <center>08.02.2022</center> || || <center>TBA</center> || |
|- | |- | ||
| − | | 4 || Неравенство Синглтона. Граница Хэмминга и граница Гилберта. Оценка Плоткина || РРШ,_разд.2,7,15 <br/>ЛН, ВНЦ || <center>Дмитрин Платон</center> || <center> | + | | 4 || Неравенство Синглтона. Граница Хэмминга и граница Гилберта. Оценка Плоткина || РРШ,_разд.2,7,15 <br/>ЛН, ВНЦ || <center>Дмитрин Платон</center> || <center>08.02.2022</center> || || <center>TBA</center> || |
|- | |- | ||
| 5 || Совершенные коды, их классификация. Обобщенные коды Хэмминга.<br/> Проверка совершенности || РРШ, разд. 6 <br/>ВНЦ || <center>Андрющенко Михаил</center> || <center>TBA</center> || || <center>TBA</center> || | | 5 || Совершенные коды, их классификация. Обобщенные коды Хэмминга.<br/> Проверка совершенности || РРШ, разд. 6 <br/>ВНЦ || <center>Андрющенко Михаил</center> || <center>TBA</center> || || <center>TBA</center> || | ||
Версия 16:21, 27 января 2022
Содержание
О семинаре
Цель семинара – познакомить участников с основными понятиями, методами и алгоритмами криптографии и теории кодирования. Параллельно мы обсуждаем необходимые сведения из алгебры, теории чисел и дискретной математики. Семинар проходит в форме докладов участников с их последующим обсуждением. Участие в семинаре позволит освоить современные методы защиты и передачи информации. Также будут даны многочисленные примеры практического использования материала, излагаемого в базовых математических курсах.
Семинар проводится для студентов 2 курса в 1-3 модулях.
Преподаватель
Аржанцев Иван Владимирович, arjantsev@hse.ru
Учебные ассистенты
Минец Максим, mvminets@edu.hse.ru
Сурова София, svsurova@edu.hse.ru
Полезные ссылки
Классрум для сдачи домашних заданий
План семинара
Криптография
| № | Тема доклада | Литература | Отвечающий доклад | Дата выступления | Отметка о выполнении | Дедлайн ДЗ | Отметка о проверке |
|---|---|---|---|---|---|---|---|
| 1 | Простейшие криптосистемы. Сдвиг и аффинное преобразование. Частотный анализ. Биграммы. Ключ шифрования и ключ дешифрования. Классические криптосистемы и системы с открытым ключом |
К, Гл. III, пар. 1 К, Гл. IV, пар. 1 |
|
|
|
|
|
| 2 | Необходимые факты из теории чисел: обратимость вычета по данному модулю, алгоритм нахождения обратного элемента, малая теорема Ферма, функция Эйлера и теорема Эйлера, китайская теорема об остатках, возведение в степень методом повторного возведения в квадрат |
K, Гл. I | |
|
|
|
|
| 3 | Строение конечных полей | ЛН | |
|
|
|
|
| 4 | Квадратичные вычеты и закон взаимности | K, Гл. II, пар. 2 | |
|
|
|
|
| 5 | Необходимые сведения из алгебры: группы и подгруппы, примеры конечных групп, порядок элемента, циклические группы и их порождающие |
любой учебник по алгебре | |
|
|
|
|
| 6 | Криптосистема RSA | K, Гл. IV, пар. 2 П, 1.2 |
|
|
|
|
|
| 7 | Задача дискретного логарифмирования и основанные на ней криптосистемы: система Диффи-Хеллмана обмена ключами, системы Мэсси-Омура и Эль-Гамаля. Понятие электронной подписи. Электронная подпись в RSA и по Эль-Гамалю |
K, Гл. IV, пар. 1, 3 П, 1.3 В, Гл. 5 |
|
|
|
|
|
| 8 | Проверка чисел на простоту и задача факторизации. Решето Эратосфена. Псевдопростые числа и числа Кармайкла. Метод Поклингтона. (p-1)-метод Полларда. |
K, Гл. V П, 2.4 В, Гл. 1-2 |
|
|
|
|
|
| 9 | Задача о рюкзаке как задача комбинаторной оптимизации. Быстрорастущие наборы. Рюкзачная криптосистема |
K, Гл. IV, пар. 4 | |
|
|
||
| 10 | Протоколы с нулевым разглашением. Три примера: раскраска карты в три цвета, поиск гамильтонова пути и извлечение корня в кольце вычетов |
K, Гл. IV, пар. 5 | |
|
|
|
|
| 11 | Математика разделенного секрета. Пороговые (n,k)-схемы доступа. Схема Шамира и схема Блэкли. Связь с теорией матроидов |
Я, Гл. 5 | |
|
|
|
|
| 12 | Криптосистема Рабина. McEliece | - | |
|
|
|
|
| 13 | Математика эллиптических кривых: групповой закон, формулы сложения и удвоения точек, теорема Хассе о числе точек на эллиптической кривой |
K, Гл. VI, пар. 1 П, гл. 4 |
|
|
|
|
|
| 14 | Нахождение точки на эллиптической кривой. Задача дискретного логарифмирования. Криптосистемы на эллиптических кривых: аналоги систем Диффи-Хеллмана и Эль-Гамаля |
K, Гл. VI, пар. 2 | |
|
|
|
|
| 15 | Проверка чисел на простоту и разложение на множители при помощи эллиптических кривых. Аналог метода Поклингтона и метод Ленстры |
K, Гл. VI, пар. 3-4 В, Гл. 4 |
|
|
|
Теория кодирования
| № | Тема доклада | Литература | Отвечающий доклад | Дата выступления | Отметка о выполнении | Дедлайн ДЗ | Отметка о проверке |
|---|---|---|---|---|---|---|---|
| 1 | Основные понятия теории кодирования. Коды, исправляющие ошибки. Расстояние Хемминга и неравенство треугольника. [7,4,3]_2-код Хэмминга и его синдром | РРШ, раздел 1 КвЛ, разд. 7 ЛН |
|
|
|
|
|
| 2 | Линейная алгебра над конечными полями: число прямых, число k-мерных подпространств и число невырожденных матриц в n-мерном пространстве над полем из q элементов. |
- | |
|
|
||
| 3 | Линейные коды и их характеристики. Порождающая и проверочная матрицы. Двойственный код и тождество Мак-Вильямса. Эквивалентность кодов. Методы вычисления минимального расстояния для подпространства |
РРШ, разд. 4 ЛН |
|
|
|
||
| 4 | Неравенство Синглтона. Граница Хэмминга и граница Гилберта. Оценка Плоткина | РРШ,_разд.2,7,15 ЛН, ВНЦ |
|
|
|
||
| 5 | Совершенные коды, их классификация. Обобщенные коды Хэмминга. Проверка совершенности |
РРШ, разд. 6 ВНЦ |
|
|
|
||
| 6 | CRC-коды | - | |
|
|
||
| 7 | Коды Рида-Соломона и их декодирование. | РРШ, разд. 8-9 | |
|
|
||
| 8 | Циклические коды и главные идеалы. Бинарный и тернарный коды Голея. Проверка совершенности |
КвЛ, раздел 8 ЛН |
|
|
|
||
| 9 | БЧХ коды | РРШ, разд. 20 ЛН |
|
|
|
||
| 10 | Коды Рида-Маллера | - | |
|
|
||
| 11 | Декодирование линейных кодов. Синдромы. Алгоритм декодирования по лидеру смежного класса | ЛН | |
|
|
||
| 12 | Линейные рекуррентные последовательности и их свойства | ЛН | |
|
|
||
| 13 | Конечные геометрии и системы Штейнера | ЛН | |
|
|
Литература
[В] - О.Н.Василенко. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО, 2003, 325 стр.
[К] - Н.Коблиц. Курс теории чисел и криптографии. М.: ТВП, 2001, 254 стр.
[ЛН] - Р.Лидл и Г.Нидеррайтер. Конечные поля. М.: Мир, 1988
[П] - Ю.Г.Прохоров. Эллиптические кривые и криптография. Семестр 1. М.: МГУ, 2007. 143 стр.
[Я] - Введение в криптографию. Под редакцией В.В.Ященко. М.: МЦНМО, 2012, 352 стр.
[ВНЦ] - С.Г.Влэдуц, Д.Ю.Ногин и М.А.Цфасман. Алгеброгеометрические коды. М.: МЦНМО, 2003
[КвЛ] - П.Камерон и Дж.ван Линт. Теория графов, теория кодирования и блок-схемы. М.: Наука, 1980
[РРШ] - А.Ромащенко, А.Румянцев и А.Шень. Заметки по теории кодирования. М.: МЦНМО, 2011
Оценивание
Участие в семинаре без доклада
K = 0,2 КП + 0,3 АУ + 0,5 ИК
КП - контроль посещаемости
АУ - активность участника (домашние задания)
ИК - итоговый контроль в конце 3-го модуля в виде устного экзамена по криптографии и теории кодирования
Участие в семинаре с одним докладом по одной из частей семинара (или по криптографии, или по теории кодирования)
K = 0,2 КП + 0,2 АУ + 0,3 ДП + 0,3 ИК
КП - контроль посещаемости
АУ - активность участника (домашние задания)
ДП - доклад с презентацией по одной из тем семинара
ИК - итоговый контроль в конце 3-го муделя в виде устного экзамена по темам той части семинара, по которой не было доклада
Участие в семинаре с двумя докладами по обеим частям семинара (и по криптографии, и по теории кодирования)
K = 0,2 КП + 0,2 АУ + 0,3 ДП1 + 0,3 ДП2
КП - контроль посещаемости
АУ - активность участника (домашние задания)
ДП1 - доклад с презентацией по одной из тем из криптографии
ДП2 - доклад с презентацией по одной из тем из теории кодирования
Контакты
Если вы нашли ошибку, то напишите мне - svsurova@edu.hse.ru, Сурова София
