НИС Методы и алгоритмы защиты информации — различия между версиями
м |
м |
||
Строка 31: | Строка 31: | ||
| 1 || Простейшие криптосистемы. Сдвиг и аффинное преобразование.<br/> Частотный анализ. Биграммы. Ключ шифрования и ключ дешифрования.<br/> Классические криптосистемы и системы с открытым ключом || К, Гл. III, пар. 1<br/> К, Гл. IV, пар. 1 || <center>Кунин Илья</center> || <center>21.09.2021</center> || <center>completed</center> || <center>05.10.2021</center> || <center>completed</center> | | 1 || Простейшие криптосистемы. Сдвиг и аффинное преобразование.<br/> Частотный анализ. Биграммы. Ключ шифрования и ключ дешифрования.<br/> Классические криптосистемы и системы с открытым ключом || К, Гл. III, пар. 1<br/> К, Гл. IV, пар. 1 || <center>Кунин Илья</center> || <center>21.09.2021</center> || <center>completed</center> || <center>05.10.2021</center> || <center>completed</center> | ||
|- | |- | ||
− | | 2 || Необходимые факты из теории чисел: обратимость вычета по данному модулю,<br/> алгоритм нахождения обратного элемента, малая теорема Ферма,<br/> функция Эйлера и теорема Эйлера, китайская теорема об остатках,<br/> возведение в степень методом повторного возведения в квадрат|| K, Гл. I || <center>Красковский Дмитрий</center> || <center>05.10.2021</center> || <center>completed</center> || <center>21.10.2021</center> || | + | | 2 || Необходимые факты из теории чисел: обратимость вычета по данному модулю,<br/> алгоритм нахождения обратного элемента, малая теорема Ферма,<br/> функция Эйлера и теорема Эйлера, китайская теорема об остатках,<br/> возведение в степень методом повторного возведения в квадрат|| K, Гл. I || <center>Красковский Дмитрий</center> || <center>05.10.2021</center> || <center>completed</center> || <center>21.10.2021</center> || <center>completed</center> |
|- | |- | ||
| 3 || Строение конечных полей || ЛН || <center>-</center> || <center>-</center> || <center>-</center> || <center>-</center> || <center>-</center> | | 3 || Строение конечных полей || ЛН || <center>-</center> || <center>-</center> || <center>-</center> || <center>-</center> || <center>-</center> | ||
Строка 41: | Строка 41: | ||
| 6 || Криптосистема RSA|| K, Гл. IV, пар. 2<br/> П, 1.2 || <center>Куликов Богдан</center> || <center>26.10.2021</center> || <center>completed</center> || <center>09.11.2021</center> || <center>completed</center> | | 6 || Криптосистема RSA|| K, Гл. IV, пар. 2<br/> П, 1.2 || <center>Куликов Богдан</center> || <center>26.10.2021</center> || <center>completed</center> || <center>09.11.2021</center> || <center>completed</center> | ||
|- | |- | ||
− | | 7 || Задача дискретного логарифмирования и основанные на ней криптосистемы:<br/> система Диффи-Хеллмана обмена ключами, системы Мэсси-Омура и Эль-Гамаля. Понятие электронной подписи. Электронная подпись в RSA и по Эль-Гамалю || K, Гл. IV, пар. 1, 3<br/> П, 1.3<br/> В, Гл. 5 || <center>Каменский Андрей</center> || <center>09.11.2021</center> || <center>completed</center> || <center> | + | | 7 || Задача дискретного логарифмирования и основанные на ней криптосистемы:<br/> система Диффи-Хеллмана обмена ключами, системы Мэсси-Омура и Эль-Гамаля. Понятие электронной подписи. Электронная подпись в RSA и по Эль-Гамалю || K, Гл. IV, пар. 1, 3<br/> П, 1.3<br/> В, Гл. 5 || <center>Каменский Андрей</center> || <center>09.11.2021</center> || <center>completed</center> || <center>10.01.2022</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> || | + | | 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>Соколов Александр</center> || <center> | + | | 9 || Задача о рюкзаке как задача комбинаторной оптимизации.<br/> Быстрорастущие наборы. Рюкзачная криптосистема || K, Гл. IV, пар. 4 || <center>Соколов Александр</center> || <center>11.01.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> | + | | 11 || Математика разделенного секрета. Пороговые (n,k)-схемы доступа.<br/> Схема Шамира и схема Блэкли. Связь с теорией матроидов || Я, Гл. 5 || <center>Коннов Илья</center> || <center>23.11.2021</center> || <center>completed</center> || <center>10.01.2022</center> || |
|- | |- | ||
− | | 12 || Криптосистема Рабина. McEliece || - || <center>Егоров Михаил</center> || <center> | + | | 12 || Криптосистема Рабина. McEliece || - || <center>Егоров Михаил</center> || <center>11.01.2022</center> || || <center>TBA</center> || |
|- | |- | ||
− | | 13 || Математика эллиптических кривых: групповой закон, формулы сложения и<br/> удвоения точек, теорема Хассе о числе точек на эллиптической кривой || K, Гл. VI, пар. 1<br/> П, гл. 4 || <center>Капустин Егор</center> || <center> | + | | 13 || Математика эллиптических кривых: групповой закон, формулы сложения и<br/> удвоения точек, теорема Хассе о числе точек на эллиптической кривой || K, Гл. VI, пар. 1<br/> П, гл. 4 || <center>Капустин Егор</center> || <center>11.01.2022</center> || || <center>TBA</center> || |
|- | |- | ||
− | | 14 || Нахождение точки на эллиптической кривой. Задача дискретного логарифмирования. Криптосистемы на эллиптических кривых: аналоги систем Диффи-Хеллмана <br/>и Эль-Гамаля || K, Гл. VI, пар. 2 || <center>Верзаков Ефим</center> || <center> | + | | 14 || Нахождение точки на эллиптической кривой. Задача дискретного логарифмирования. Криптосистемы на эллиптических кривых: аналоги систем Диффи-Хеллмана <br/>и Эль-Гамаля || K, Гл. VI, пар. 2 || <center>Верзаков Ефим</center> || <center>11.01.2022</center> || || <center>TBA</center> || |
|- | |- | ||
| 15 || Проверка чисел на простоту и разложение на множители при помощи<br/> эллиптических кривых. Аналог метода Поклингтона и метод Ленстры || K, Гл. VI, пар. 3-4 <br/>В, Гл. 4 || <center>Порохнин Даниил</center> || <center>TBA</center> || || <center>TBA</center> || | | 15 || Проверка чисел на простоту и разложение на множители при помощи<br/> эллиптических кривых. Аналог метода Поклингтона и метод Ленстры || K, Гл. VI, пар. 3-4 <br/>В, Гл. 4 || <center>Порохнин Даниил</center> || <center>TBA</center> || || <center>TBA</center> || |
Версия 22:13, 9 января 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, Сурова София