Бакалавриат
2022/2023
Теория чисел и криптография
Лучший по критерию «Полезность курса для Вашей будущей карьеры»
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
3-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Преподаватели:
Устинов Алексей Владимирович
Язык:
русский
Кредиты:
5
Контактные часы:
60
Программа дисциплины
Аннотация
Первоначально криптографические протоколы строились в конечных полях и кольцах вычетов. Простейшие примеры — это криптосистемы RSA, Эль-Гамаля и Диффи — Хеллмана. Потом стали появляться новые, конкурирующие направления такие как криптография на эллиптических кривых и криптография на решётках. Во всех случаях стойкость криптосистем опирается на алгоритмическую сложность некоторых задач. Для эллиптических кривых эти задачи кажутся более сложными, что позволяет использовать более короткие ключи, несмотря на бОльшую сложность базовых арифметических операций. На решётках, наоборот, базовая операция очень проста — это сложение векторов, и стойкость криптосистем достигается за счёт использования решёток высокихразмерностей. В курсе планируется познакомится со всеми тремя
направлениями и частично коснуться новых направлений, возникших благодаря эллиптическим кривым и решёткам. Например, наличие наэллиптических кривых нетривиальной операции спаривания привело кпоявлению протоколов, не существующих в традиционной криптографии над конечными полями (pairing-based cryptography). Благодаря использованию решёток удалось построить системы шифрования, позволяющие проводить вычисления с зашифрованными данными (homomorphic encryption).
Цель освоения дисциплины
- Цель курса ¬– познакомиться с криптографией на эллиптических кривых и на решётках. Курс, соответственно будет состоять из двух частей. В первой части будут изложены основы теории эллиптических кривых. Затем будут рассмотрены различные приложения эллиптических кривых в криптографии. Во второй части курса будут изложены основы геометрии чисел. Основное внимание будет уделено LLL-алгоритму. В качестве приложений будут рассмотрены криптографические протоколы на решётках. По мере необходимости будут рассказаны стандартные сведения из криптографии над кольцами вычетов.
Планируемые результаты обучения
- Построить системы шифрования, позволяющие проводить вычисления с зашифрованными данными
- Познакомиться с криптографией на эллиптических кривых и криптографией на решётках, а также частично коснуться новых направлений, возникших благодаря эллиптическим кривым и решёткам
Элементы контроля
- Домашнее задание
- Коллоквиум
- ЭкзаменЭкзамен проводится в устной форме, в аудитории, пользоваться материалами не разрешается. Студент получает билет, который включает в себя два вопроса из программы экзамена – один вопрос по материалу первой части (эллиптические кривые) и один вопрос по второй части (решётки). После ответа студенту могут быть заданы дополнительные вопросы по программе курса, а также предложены задачи на понимание теоретического материала. Такие задачи не требуют проведения обширных вычислений.
- Работа на семинарах
- Контрольная работа
Промежуточная аттестация
- 2022/2023 учебный год 2 модульИтог = min(10,Округление(0.3 * ДЗ + 0.3 * Кол + 0.4 * Экз + 0.1 Сем)), где ДЗ — средняя оценка за все домашние задания, Кол — оценка за коллоквиум, Экз — оценка за экзамен, Сем – работа на семинарах.
