Теоретико-числовые методы в криптографии

Специалитет 2024/2025

Статус: Курс по выбору (Компьютерная безопасность)

Кто читает: Кафедра компьютерной безопасности

Где читается: Московский институт электроники и математики им. А.Н. Тихонова

Когда читается: 4-й курс, 3, 4 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для своего кампуса

Преподаватели: Малыгина Екатерина Сергеевна

Специальность: 10.05.01. Компьютерная безопасность

Язык: русский

Кредиты: 4

Полная версия программы учебной дисциплины Задать вопрос

Аннотация

Данная дисциплина относится к базовой части Профессионального цикла (Major), проводится на 4 курсе обучения и является обязательной. Для освоения учебной дисциплины студенты должны владеть базовыми знаниями и компетенциями, полученными при изучении следующих дисциплин: основными понятиями алгебры, теории конечных групп, колец и полей, основными понятиями элементарной теории чисел. Результаты освоения дисциплины используются в дальнейшем при прохождении производственной и преддипломной практик, при выполнении выпускной квалификационной работы, а также при изучении таких дисциплин, как криптографические методы защиты информации, криптографические протоколы, методы алгебраической геометрии в криптографии. Дисциплина реализуется в он-лайн формате

Цель освоения дисциплины

Формирование у студентов навыков, необходимых для разработки математических моделей защищаемых процессов и средств защиты информации и систем, обеспечивающих информационную безопасность
Формирование у студентов навыков, необходимых для обоснования и выбора рационального решения по уровню обеспечения защищенности компьютерной системы с учетом заданных требований
Формирование у студентов навыков, необходимых для подготовки научно-технических отчетов, обзоров, публикаций по результатам выполненных исследований
Формирование у студентов навыков, необходимых для выполнения экспериментально-исследовательских работ при проведении сертификации средств защиты и анализ результатов
Формирование у студентов навыков, необходимых для проведения аттестации технических средств, программ, алгоритмов на предмет соответствия требованиям защиты информации по соответствующим классам безопасности или профилям защиты

Планируемые результаты обучения

Владеть навыками вычисления символа Лежандра
Владеть навыками нахождения корней многочленов над конечным простым полем
Владеть навыками построения простых чисел заданного размера
Владеть навыками разложения чисел на множители и вычисления дискретных логарифмов в мультипликативной группе конечного простого поля
Знать алгоритмы построения простых чисел
Знать алгоритмы проверки больших целых чисел на простоту
Знать алгоритмы факторизации больших целых чисел
Знать методы дискретного логарифмирования в циклических группах
Знать методы нахождения корней многочленов над конечными полями
Уметь доказывать простоту больших целых чисел
Уметь решать задачу дискретного логарифмирования
Уметь решать задачу разложения больших целых чисел на множители
Уметь строить простые числа заданного размера

Содержание учебной дисциплины

Сведения из элементарной теории чисел: наибольший общий делитель, алгоритм Эвклида вычисления НОД и его модификации, бесконечность множества простых чисел, основная теорема арифметики
Сравнения первой степени. Китайская теорема об остатках. Функция Эйлера. Показатели и первообразные корни. Теоремы о существовании и количестве первообразных корней. Алгоритмы построения первообразных корней.
Теория и свойства многочленов от одной переменной, лемма Безу, основная теорема арифметики для многочленов. Дифференцирование многочленов. Решение полиномиальных сравнений по составному модулю -- сведение решений в конечных кольцах к случаю конечного простого поля. Метод подъема решения
Сравнения старших степеней по простому модулю. Квадратичные вычеты. Символы Лежандра и Якоби. Алгоритмы вычисления символа Лежандра
Вычисление корней второй степени. Алгоритм Тонелли-Шенкса вычисления квадратных корней по простому модулю. Алгоритм, основанный на квадратичных расширениях конечного простого поля
Методы вычисления корней третьей степени. Элементы теории двучленных сравнений. Вероятностный алгоритм вычисления корней многочленов старших степеней
Простые числа. Бесконечность множества простых чисел. Методы построения таблиц простых чисел
Вероятностные тесты проверки на простоту: числа Кармайкла, тест Соловея-Штрассена и тест Милера-Рабина
Алгоритмы доказательства простоты чисел с использованием разложения n-1 на простые множители (теоремы Лемера и Поклингтона)
Алгоритмы доказательства простоты чисел с использованием разложения n+1 на простые множители (теорема Морисона)
Рассмотрение обобщения указанных алгоритмов. Алгоритмы построения строго простых чисел
Полиномиальный алгоритм доказательства простоты
Цепные дроби. Понятие подходящей дроби. Квадратичные иррациональности и их разложения в цепные дроби. Наилучшие приближения действительных чисел
Экспоненциальные методы факторизации целых чисел. Метод Ферма, методы Полларда-Флойда и Брента. p-1 метод Полларада, p+1 метод Вильямса. Методы оптимизации рассмотренных алгоритмов
Решето Крайчика. Метод непрерывных дробей (Лемера), метод Моррисона-Бриллхарда, метод квадратичного решета и его дальнейшие модификации
Алгоритмы вычисления индексов (решения задачи дискретного логарифмирования): метод согласования, методы Нечаева и Поллига-Хеллмана. Методы, основанные на поиске длин циклов в последовательностях: методы Полларда, Госпера, а также параллельный метод Винера
Индекс методы решения задачи дискретного логарифмирования. Решение систем линейных уравнений в кольцах вычетов. Индекс-метод Адлемана и его модификации

Элементы контроля

Показатели и первообразные корни
Oral interview

Промежуточная аттестация

2024/2025 4th module
0.5 * Oral interview + 0.5 * Показатели и первообразные корни

Список литературы

Авторы

Нестеренко Алексей Юрьевич
Лось Алексей Борисович

Программа дисциплины