Теория псевдослучайных генераторов

2023/2024

Учебный год

RUS

Обучение ведется на русском языке

3

Кредиты

Кто читает:

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

Статус:

Курс по выбору

Когда читается:

4-й курс, 3, 4 модуль

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

Фомин Денис Бониславович

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

Аннотация

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

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

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

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

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

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

• Линейные рекуррентные последовательности (ЛРП) над конечным полем. Характеристический, минимальный и аннулирующий многочлены, сопровождающая матрица. Линейная сложность. Условия совпадения минимального многочлена с характеристическим
• Представление ЛРП через функцию след. Генераторы Фибоначчи и Галуа
• Оценки минимального периода. ЛРП максимального периода
• Суммирование и произведение рекуррентных последовательностей. Семейства ЛРП, соответствующие заданному характеристическому многочлену. Свойства их сумм и пересечения. Вычисление минимальных многочленов и периодов
• Фильтрующие и комбинирующие генераторы. Оценки длины периода, линейной сложности, вероятностей выходных s-грамм
• Вероятностные свойства фильтрующей схемы. Классификация фильтрующих схем по вероятностям выходных s-грамм
• Нелинейные рекуррентные последовательности. Методы построения нелинейных регистров сдвига максимального периода («склейка-расклейка» циклов, изоморфизм автоматов, экспериментальные методы)
• Суммирование в конечной абелевой группе как способ улучшения характеристик исходных случайных последовательностей

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

• Реферат
  Реферат на заданную тему
• Контрольная работа

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

• 2023/2024 учебный год 4 модуль
  0.5 * Контрольная работа + 0.5 * Реферат

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

Рекомендуемая основная литература

• Demeester, T., Deleu, J., Godin, F., & Develder, C. (2018). Predefined Sparseness in Recurrent Sequence Models.
• Основы криптографии : учеб. пособие, Алферов, А. П., 2005

Рекомендуемая дополнительная литература

• Rosen, J. (2018). Terms in prime position in a recurrent sequence.
• Алгебра : Основы теории конечных групп,колец,полей: учебное пособие, Рожков, М. И., 2009