Специалитет
2023/2024
Теория псевдослучайных генераторов
Статус:
Курс по выбору (Компьютерная безопасность)
Кто читает:
Кафедра компьютерной безопасности
Когда читается:
4-й курс, 3, 4 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для всех кампусов НИУ ВШЭ
Преподаватели:
Фомин Денис Бониславович
Специальность:
10.05.01. Компьютерная безопасность
Язык:
русский
Кредиты:
3
Контактные часы:
42
Программа дисциплины
Аннотация
Данная дисциплина относится к вариативной профильной части Профессионального цикла (Major), проводится на 4 курсе обучения и является обязательной. Для освоения учебной дисциплины студенты должны владеть базовыми школьными знаниями и компетенциями, основными понятиями линейной алгебры, теории конечных групп, колец и полей. Результаты освоения дисциплины используются в дальнейшем при изучении таких дисциплин, как Криптографические методы защиты информации, Криптографические протоколы, Теоретико-числовые методы в криптографии. Дисциплина реализуется в он-лайн формате
Цель освоения дисциплины
- формирование у студентов навыков, необходимых для применения соответствующего математического аппарата для формализации, анализа и решения проблем, возникающих в ходе профессиональной деятельности
- формирование у студентов навыков, необходимых для разработки и анализа свойств выходных последовательностей, вырабатываемых псевдослучайными генераторами
- формирование у студентов навыков, необходимых для анализа свойств шифров, использующих псевдослучайные генераторы
Планируемые результаты обучения
- Владеть навыками нахождения периодов линейных рекуррентных последовательностей над конечным полем, а также генераторов над кольцами вычетов
- Владеть навыками проведения вычислений в числовых и конечных группах, кольцах вычетов и полях
- Знать методы нахождения ключа генератора по отрезку выхода и оценки их сложности
- Знать методы оценки длины периода
- Знать методы оценки статистических свойств выходной последовательности
- Уметь вычислять периоды линейных рекуррентных последовательностей над конечным полем
- Уметь проводить оценивание периода и статистических свойств фильтрующих и комбинирующих генераторов, а также генераторов над кольцами вычетов
Содержание учебной дисциплины
- Линейные рекуррентные последовательности (ЛРП) над конечным полем. Характеристический, минимальный и аннулирующий многочлены, сопровождающая матрица. Линейная сложность. Условия совпадения минимального многочлена с характеристическим
- Представление ЛРП через функцию след. Генераторы Фибоначчи и Галуа
- Оценки минимального периода. ЛРП максимального периода
- Суммирование и произведение рекуррентных последовательностей. Семейства ЛРП, соответствующие заданному характеристическому многочлену. Свойства их сумм и пересечения. Вычисление минимальных многочленов и периодов
- Фильтрующие и комбинирующие генераторы. Оценки длины периода, линейной сложности, вероятностей выходных s-грамм
- Вероятностные свойства фильтрующей схемы. Классификация фильтрующих схем по вероятностям выходных s-грамм
- Нелинейные рекуррентные последовательности. Методы построения нелинейных регистров сдвига максимального периода («склейка-расклейка» циклов, изоморфизм автоматов, экспериментальные методы)
- Суммирование в конечной абелевой группе как способ улучшения характеристик исходных случайных последовательностей
Список литературы
Рекомендуемая основная литература
- 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