Применение пакета NIST STS для решения учебных задач дисциплины "Теория псевдослучайных генераторов"

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Применение пакета NIST STS для решения учебных задач дисциплины «Теория псевдослучайных генераторов»

Одной из задач освоения дисциплины «Теория псевдослучайных генераторов» является приобретение навыков решения задач оценки качества генераторов псевдослучайных последовательностей [1]. Оценить качество генераторов псевдослучайных последовательностей с точки зрения случайности позволяют статистические тесты, использующие методы статистического анализа для определения близости генерируемой последовательности к истинно случайной.

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

Статистические тесты обычно объединяются в пакеты, представляющие собой подборку различных статистических методик по оценке качества псевдослучайных последовательностей. Наиболее распространенными и известными являются пакеты Diehard, TestU01, NIST, CRYPT-X, тесты Д. Кнута. В работе [2] нами проанализированы достоинства и недостатки пакетов тестов Diehard, TestU01, NIST STS. Установлено преимущество пакета NIST как наиболее разработанного стандарта, предназначенного для сертификации генераторов псевдослучайных последовательностей и отвечающего различным областям применения псевдослучайных чисел. Именно NIST STS выбран нами и реализован для проведения учебных занятий по исследованию генераторов псевдослучайных последовательностей. В работе [3] описано программное средство, реализующее статистический пакет NIST. Отличительной особенностью данной реализации является ориентированность программного средства на пользователя. Дружественный, интуитивно понятный интерфейс позволяет использовать программу в учебном процессе.

Продемонстририуем применение статистического пакета NIST для решения учебных задач дициплины «Теория псевдослучайных генераторов» на примере исследования фильтрующих и комбинирующих генераторов.

Формулировка задания. Реализовать фильтрующие и комбинирующие генераторы. Исследовать характеристики фильтрующих и комбинирующих генераторов, вырабатывающих последовательности, в зависимости от прохождения статистических тестов.

Для выполнения задания сначала необходимо реализовать фильтрующие и комбинирующие генераторы, затем получить последовательности, вырабатываемые генераторами с различными характеристиками, исследовать полученные последовательности с помощью пакета NIST, а затем сделать выводы о прохождении статистических тестов в зависимости от харакеристик генераторов.

Фильтрующие и комбинирующие генераторы являются структурными компонентами некоторых классических поточных шифров [4]. Они строятся на основе линейных регистров сдвига и булевой функции f, которая является функцией усложнения.

Схема фильтрующего генератора представлена на рисунке 1. На вход регистра сдвига подаётся последовательность, являющаяся ключом для криптосистемы. На выходе из регистра сдвига последовательность поступает в фильтр, где усложняется булевой функцией.

Рисунок 1 - Схема фильтрующего генератора

Схема комбинирующего генератора представлена на рисунке 2. Комбинирующие генераторы можно рассматривать как усложнение фильтрующих генераторов. На вход усложняющей булевой функции поступают элементы линейных рекуррентных последовательностей, вырабатываемые линейными регистрами.

Рисунок 2 - Схема комбинирующего генератора

Работу линейных регистров сдвига можно описать линейными рекуррентными уравнениями вида:

:,

где.

С линейным рекуррентным уравнением можно связать многочлен над полем , называемый характеристическим многочленом линейной рекуррентной последовательности.

В качестве функций усложнения в генераторах используется булева функция. Булевы функции будем представлять в алгебраической нормальной форме [4].

Приведем пример реализованного при выполнении задания программного средства. Интерфейс программного средства представлен на рисунке 3.

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

Рисунок 3. Программное средство «Генераторы псевдослучайных последовательностей»

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

Функции усложнения применяются к линейным рекуррентным последовательностям, построенным на основе уравнений рекурсии, характеристические многочлены которых являются неприводимыми.

На основе выбранных булевых функций осуществляется усложнение линейной рекуррентной последовательности. Усложнённая последовательность является результатом работы фильтрующего или комбинирующего генератора.

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

Таблица 1 - Примеры характеристик исследуемых генераторов и результаты тестирования соответствующих им последовательностей

В процессе анализа результатов тестирования необходимо сформулировать выводы о связи характеристик генераторов и статистических тестов, которые проходят последовательности, вырабатываемые данными генераторами.

В качестве примера рассмотрим выводы, полученные в результате решения рассматриваемой задачи:

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

- последовательности фильтрующих генераторов проходят некоторые из тестов, начиная с длины регистра сдвига, равной 4. Прохождение тестов последовательностями в данном случае больше зависит от длины регистра сдвига, чем от свойств функции усложнения. В основном последовательности проходят частотный побитовый, частотный блочный тесты и тест кумулятивных сумм;

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

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

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

1. Рабочая программа дисциплины «Б.1.В.ДВ.7.1 Теория псевдослучайных генераторов» / сост. А.Н. Благовисная. - Оренбург: ОГУ, 2018.

2. Самойлов, Е. И. О программных реализациях тестов псевдослучайных последовательностей / Е. И. Самойлов, А. Н. Благовисная // Университетский комплекс как региональный центр образования, науки и культуры [Электронный ресурс]: материалы Всероссийской научно-методической конференции; Оренбург. гос. ун-т. - Оренбург: ОГУ, 2018. - С. 1751-1754.

3. Самойлов, Е.И. Учебное программное средство тестирования псевдослучайных последовательностей / Е. И. Самойлов, А. Н. Благовисная // Вестник современных исследований. - 2018. - № 5-1 (20). - С. 510-513.

4. Логачев, О.А. Булевы функции в теории кодирования и криптологии / О.А. Логачев, А.А. Сальников, В.В. Ященко. - М.: МЦНМО, 2012. - 583 с.

Размещено на Allbest.ru