НИС Методы и алгоритмы защиты информации
Содержание
О семинаре
Цель семинара – познакомить участников с основными понятиями, методами и алгоритмами криптографии и теории кодирования. Параллельно мы обсуждаем необходимые сведения из алгебры, теории чисел и дискретной математики. Семинар проходит в форме докладов участников с их последующим обсуждением. Участие в семинаре позволит освоить современные методы защиты и передачи информации. Также будут даны многочисленные примеры практического использования материала, излагаемого в базовых математических курсах.
Семинар проводится для студентов 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, Сурова София
