СТАТИСТИЧЕСКИЕ ТЕСТЫ ГЕНЕРАТОРА ПСЕВДОСЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ

АННОТАЦИЯ

В статье автор пытается проанализировать актуальность и востребованность статистических тестов.

Ключевые слова: генератор; статистика; криптоанализ.

Статистические тесты – это эмпирические тесты для оценки качества ГПСП и выявления их «уязвимых мест» за счёт статистических характеристик ПСП и сравнения их с аналогичными характеристиками ИСП. Решение данных задач базируется на проверке гипотез относительно свойств ПСП. В качестве статистической гипотезы может использоваться произвольное предположение о характере распределения и свойствах случайной величины. Истинность или ложность такого предположения подтверждается или отклоняется с помощью методов математической статистики. Общая схема проверки статистических гипотез состоит в следующем. Производятся две гипотезы: нулевая () и альтернативная (). Допустим, нулевая гипотеза заключается в том, что тестируемая ПСП истинно случайная (с точки зрения конкретного теста), а альтернативная – что ПСП не случайна. Для каждого теста выбирается какая-либо вычислимая функция (статистика), которая сводит свойство случайности тестируемых данных к одному числовому значению (наблюдаемой статистике). Статистика теста представляется как реализация случайной величины. Для того чтобы выполнить оценку прохождения теста, необходимо знать распределение тестовой статистики в предположении, что нулевая гипотеза верна. Часто эту роль играют нормальное распределение и распределение χ2 (Пирсона). Статистические тесты соединяют в себе вычислительные действия для получения статистики рассматриваемой последовательности и решающее правило проверки, с помощью которого по значениям статистики определяют, принять или отвергнуть нулевую гипотезу:

- если выборочное значение статистики принадлежит критической области, то нулевая гипотеза  отвергается, так как при однократном испытании произошло событие, вероятность которого мала и равна α;

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

Таким образом, алгоритм проверки статистических гипотез состоит из следующих шагов: формулировка гипотез   и  задание уровня значимости Авыбор тестовой функции (статистики)определение критической области и ее граничных точеквычисление выборочной статистикирешение о принятии гипотезы.

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

- Пороговое значение. Величина вычисленной статистики сравнивается с некоторым пороговым значением, и, если статистика, например, превосходит его, тест считается пройденным.

- Доверительный интервал. Тест считается пройденным, если величина статистики теста попадает в определенный доверительный интервал.

- Вероятностный подход. Набор значений статистики теста считается набором значений случайной величины с заданным законом распределения.

Крайний тип показал себя наиболее эффективным и надежным. Именно он используется во многих пакетах статистических тестов. При принятии решения о том, был ли пройден тест, возможны два типа ошибок. Возникновение ошибки первого рода означает, что тестируемая псевдослучайная последовательность на самом деле является случайной, но верная нулевая гипотеза  отклоняется. Вероятность такой ошибки равна уровню значимости α, который задается до начала тестирования. Уровень значимости α – это вероятность того, что тестирование покажет неслучайность последовательности, тогда как фактически она является случайной. Соответственно, вероятность принятия правильного решения составляет (1–α). Обычно в практических задачах приемлемым считается значение уровня значимости 0,05. Однако для целей криптографии используют более строгие значения α (как правило, из интервала [0,001; 0,01]). Ошибка второго рода (β) означает принятие гипотезы о случайности рассматриваемой последовательности, когда последовательность в действительности неслучайна. С точки зрения криптографии такая ошибка более критична. Величина ошибки второго рода определяет мощность критерия – вероятность того, что нулевая гипотеза будет отклонена при верной альтернативной гипотезе. Между двумя этими видами ошибок существует взаимозависимость: чем меньше α, тем больше β, и наоборот. Статистика теста построена так, что ее меньшие значения соответствуют дефектам псевдослучайной последовательности – отклонениям от истинной случайности. Обычно для удобства восприятия результатов тестирования вычисленная с помощью эталонного распределения вероятностей тестовая статистика преобразуется в так называемое значение p-value. Это значение трактуется как вероятность того, при заданном уровне значимости идеальный генератор случайных последовательностей может произвести последовательность, менее случайную, чем исследуемая. Такое событие тем менее вероятно, чем меньше значение p-value. Выполнение условия p-value>=α означает успешное прохождение теста. Важным является тот факт, что для любых статистических тестов, удовлетворяющих нулевой гипотезе, значения p-value равномерно распределены на интервале [0; 1). Это означает, что тестируемая произвольным тестом последовательность должна быть равномерно распределена на интервале [0; 1). Помимо пакетов, содержащих наборы тестов для многостороннего исследования статистических свойств ГПСП, существуют отдельные тесты, которые направлены на более точный и полный анализ ПСП. Следует понимать, что тестирование не может заменить криптоанализ. Тем не менее, оно является обязательным этапом анализа стойкости криптографического генератора. В условиях существования большого числа различных статистических тестов, как широко и давно распространенных, так и новых, важен обоснованный выбор, связанный со спецификой решаемых задач защиты информации.

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

1. Будько М.Б., Будько М.Ю., Гирик А.В., Грозов В.А. Методы генерации и тестирования случайных последовательностей – СПб: Университет ИТМО, 2019. – 70 с.