• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Специалитет 2018/2019

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

Статус: Курс обязательный (Компьютерная безопасность)
Когда читается: 4-й курс, 3, 4 модуль
Формат изучения: Full time
Специальность: 10.05.01. Компьютерная безопасность
Язык: русский
Кредиты: 3

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

Аннотация

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

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

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

Результаты освоения дисциплины

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

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

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

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

  • неблокирующий Created with Sketch. Контрольная работа 1
  • неблокирующий Created with Sketch. Контрольная работа 2
  • неблокирующий Created with Sketch. Экзамен
Промежуточная аттестация

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

  • Промежуточная аттестация (4 модуль)
    0.25 * Контрольная работа 1 + 0.25 * Контрольная работа 2 + 0.5 * Экзамен