НИС Методы и алгоритмы защиты информации 2022/2023 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Новая страница: «== О семинаре == Цель семинара – познакомить участников с основными понятиями, методами и…»)
 
(→‎Криптография)
Строка 25: Строка 25:
 
{| class="wikitable"
 
{| class="wikitable"
 
|-
 
|-
−
! № !! Тема доклада !! Литература
+
! № !! Тема доклада !! Литература !! Докладчик
 
|-
 
|-
 
| 1
 
| 1
 
|| Простейшие криптосистемы. Сдвиг и аффинное преобразование. Частотный анализ. Биграммы. Ключ шифрования и ключ дешифрования. Классические криптосистемы и системы с открытым ключом
 
|| Простейшие криптосистемы. Сдвиг и аффинное преобразование. Частотный анализ. Биграммы. Ключ шифрования и ключ дешифрования. Классические криптосистемы и системы с открытым ключом
 
|| К, Гл. III, пар. 1 и Гл. IV, пар. 1
 
|| К, Гл. III, пар. 1 и Гл. IV, пар. 1
 +
|| Гудошникова Юлия
 
|-
 
|-
 
   
 
   
Строка 35: Строка 36:
 
|| Необходимые факты из теории чисел: обратимость вычета по данному модулю, алгоритм нахождения обратного элемента, малая теорема Ферма, функция Эйлера и теорема Эйлера, китайская теорема об остатках, методы быстрого возведения в степень
 
|| Необходимые факты из теории чисел: обратимость вычета по данному модулю, алгоритм нахождения обратного элемента, малая теорема Ферма, функция Эйлера и теорема Эйлера, китайская теорема об остатках, методы быстрого возведения в степень
 
|| K, Гл. I
 
|| K, Гл. I
 +
|| Галкина Таисия
 
|-
 
|-
 
   
 
   
Строка 40: Строка 42:
 
|| Квадратичные вычеты и закон взаимности
 
|| Квадратичные вычеты и закон взаимности
 
|| K, Гл. II, пар. 2
 
|| K, Гл. II, пар. 2
 +
|| Порфирьев Антон
 
|-
 
|-
 
   
 
   
Строка 45: Строка 48:
 
|| Необходимые сведения из алгебры: группы и подгруппы, примеры конечных групп, порядок элемента, циклические группы и их порождающие
 
|| Необходимые сведения из алгебры: группы и подгруппы, примеры конечных групп, порядок элемента, циклические группы и их порождающие
 
|| [любой нравящийся вам учебник по алгебре]
 
|| [любой нравящийся вам учебник по алгебре]
 +
|| Степашкина Виталия
 
|-
 
|-
 
   
 
   
Строка 50: Строка 54:
 
|| Строение конечных полей
 
|| Строение конечных полей
 
|| ЛН
 
|| ЛН
 +
|| Цейтин Андрей
 
|-
 
|-
  
Строка 55: Строка 60:
 
|| Задача дискретного логарифмирования и основанные на ней криптосистемы: система Диффи-Хеллмана обмена ключами, системы Мэсси-Омура и Эль-Гамаля
 
|| Задача дискретного логарифмирования и основанные на ней криптосистемы: система Диффи-Хеллмана обмена ключами, системы Мэсси-Омура и Эль-Гамаля
 
|| [K, Гл. IV, пар. 1, 3], [П, 1.3], [В,Гл. 5]
 
|| [K, Гл. IV, пар. 1, 3], [П, 1.3], [В,Гл. 5]
 +
|| Волотова Анастасия
 
|-
 
|-
 
   
 
   
Строка 60: Строка 66:
 
|| Алгоритмы решения задачи дискретного логарифмирования
 
|| Алгоритмы решения задачи дискретного логарифмирования
 
|| K, Гл. IV, пар. 3
 
|| K, Гл. IV, пар. 3
 +
|| Шатравка Даниил
 
|-
 
|-
 
   
 
   
Строка 65: Строка 72:
 
|| Криптосистема RSA
 
|| Криптосистема RSA
 
|| [K, Гл. IV, пар. 2], [П, 1.2]
 
|| [K, Гл. IV, пар. 2], [П, 1.2]
 +
|| Вахитова Диана
 
|-
 
|-
  
Строка 70: Строка 78:
 
|| Понятие электронной подписи. Электронная подпись в RSA и по Эль-Гамалю
 
|| Понятие электронной подписи. Электронная подпись в RSA и по Эль-Гамалю
 
|| [K, Гл. IV, пар. 1, 3], [П, 1.3], [В,Гл. 5]
 
|| [K, Гл. IV, пар. 1, 3], [П, 1.3], [В,Гл. 5]
 +
|| Григорьева Василиса
 
|-
 
|-
 
   
 
   
Строка 75: Строка 84:
 
|| Проверка чисел на простоту и задача факторизации. Решето Эратосфена. Псевдопростые числа и числа Кармайкла. Метод Поклингтона. (p-1)-метод Полларда
 
|| Проверка чисел на простоту и задача факторизации. Решето Эратосфена. Псевдопростые числа и числа Кармайкла. Метод Поклингтона. (p-1)-метод Полларда
 
|| [K, Гл. V], [П, 2.4], [В, Гл. 1-2]
 
|| [K, Гл. V], [П, 2.4], [В, Гл. 1-2]
 +
|| Мельников Игорь
 
|-
 
|-
 
   
 
   
Строка 80: Строка 90:
 
|| Задача о рюкзаке как задача комбинаторной оптимизации. Быстрорастущие наборы. Рюкзачная криптосистема
 
|| Задача о рюкзаке как задача комбинаторной оптимизации. Быстрорастущие наборы. Рюкзачная криптосистема
 
|| K, Гл. IV, пар. 4
 
|| K, Гл. IV, пар. 4
 +
|| Мовшин Максим
 
|-
 
|-
 
   
 
   
Строка 85: Строка 96:
 
|| Протоколы с нулевым разглашением. Три примера: раскраска карты в три цвета, поиск гамильтонова пути и извлечение корня в кольце вычетов
 
|| Протоколы с нулевым разглашением. Три примера: раскраска карты в три цвета, поиск гамильтонова пути и извлечение корня в кольце вычетов
 
|| K, Гл. IV, пар. 5
 
|| K, Гл. IV, пар. 5
 +
|| Лаптева Анна
 
|-
 
|-
 
   
 
   
Строка 90: Строка 102:
 
|| Математика разделенного секрета. Пороговые (n,k)-схемы доступа. Схема Шамира и схема Блэкли.
 
|| Математика разделенного секрета. Пороговые (n,k)-схемы доступа. Схема Шамира и схема Блэкли.
 
|| Я, Гл. 5
 
|| Я, Гл. 5
 +
|| Новикова Юлия
 
|-
 
|-
 
   
 
   
Строка 95: Строка 108:
 
|| Разделение секрета и теория матроидов
 
|| Разделение секрета и теория матроидов
 
|| Я, Гл. 5
 
|| Я, Гл. 5
 +
|| Кислов Максим
 
|-
 
|-
 
   
 
   
Строка 100: Строка 114:
 
|| Математика эллиптических кривых: групповой закон, формулы сложения и удвоения точек, теорема Хассе о числе точек на эллиптической кривой
 
|| Математика эллиптических кривых: групповой закон, формулы сложения и удвоения точек, теорема Хассе о числе точек на эллиптической кривой
 
|| [K, Гл. VI, пар. 1], [П, гл. 4]
 
|| [K, Гл. VI, пар. 1], [П, гл. 4]
 +
|| Хворостяной Валерий
 
|-
 
|-
  
Строка 105: Строка 120:
 
|| Нахождение точки на эллиптической кривой. Задача дискретного логарифмирования. Криптосистемы на эллиптических кривых: аналоги систем Диффи-Хеллмана и Эль-Гамаля
 
|| Нахождение точки на эллиптической кривой. Задача дискретного логарифмирования. Криптосистемы на эллиптических кривых: аналоги систем Диффи-Хеллмана и Эль-Гамаля
 
|| K, Гл. VI, пар. 2
 
|| K, Гл. VI, пар. 2
 +
|| Нечесов Андрей
 
|-
 
|-
 
   
 
   
Строка 110: Строка 126:
 
|| Проверка чисел на простоту и разложение на множители при помощи эллиптических кривых. Аналог метода Поклингтона и метод Ленстры
 
|| Проверка чисел на простоту и разложение на множители при помощи эллиптических кривых. Аналог метода Поклингтона и метод Ленстры
 
|| [K, Гл. VI, пар. 3-4],  [В, Гл. 4]
 
|| [K, Гл. VI, пар. 3-4],  [В, Гл. 4]
 +
|| Сайфутдинов Рафаэль
 
|-
 
|-
 
|}
 
|}

Версия 11:21, 14 сентября 2022

О семинаре

Цель семинара – познакомить участников с основными понятиями, методами и алгоритмами криптографии и теории кодирования. Параллельно мы обсуждаем необходимые сведения из алгебры, теории чисел и дискретной математики. Семинар проходит в форме докладов участников с их последующим обсуждением. Участие в семинаре позволит освоить современные методы защиты и передачи информации. Также будут даны многочисленные примеры практического использования материала, излагаемого в базовых математических курсах.

Семинар проводится для студентов 2 курса в 1-3 модулях.

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

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

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

Коннов Илья. t.me/iliago, vk.com/iliago, iakonnov@edu.hse.ru

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

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

Классрум для сдачи домашних заданий

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

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

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

Литература

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

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

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

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

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

Источник — «http://wiki.cs.hse.ru/index.php?title=НИС_Методы_и_алгоритмы_защиты_информации_2022/2023&oldid=72252»