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

Один из самых наглядных тестов — тест на равномерное распределение частот появления каждого символа. Пусть ${\displaystyle \xi _{1},\xi _{2}...\xi _{n}}$ — последовательность длиной n и размерности m. Тогда частоты ν_i должны принадлежать отрезку ${\displaystyle {\Bigl [}{\tfrac {n-2,58{\sqrt {n(2^{m}-1)}}}{2^{m}}};{\tfrac {n+2,58{\sqrt {n(2^{m}-1)}}}{2^{m}}}{\Bigr ]}}$. Однако, большинство тестов используют другой метод — принятие или отклонение гипотезы о случайности последовательности, используя статистические распределения.

Зная вероятностные свойства истинно случайной последовательности, можно на их основе проверять гипотезу о том, насколько сгенерированная последовательность похожа на случайную. Для этого для каждого теста подбирается подходящая статистика, вычисляется её значения для идеальной и сгенерированной последовательности. Если разность этих значений превышает некоторое критическое значение, установленное заранее, то последовательность считается неслучайной. Для «хороших» последовательностей вероятность такого события крайне мала (допустим ~0,001 и обозначим её α). Однако, существует вероятность того, что «плохая» последовательность удовлетворит критерию и будет сделан вывод о её случайности (обозначим вероятность такого события β). На практике значения длины последовательности n, α и β связаны, задаётся α и подбирается n такое, чтобы минимизировать β.

Определим величину P-value как вероятность того, что идеальный генератор сгенерировал последовательность менее случайную, чем исследуемый. Тогда если P-value больше α, то исследуемая последовательность считается случайной и наоборот в противном случае.

Кратко шаги статистического тестирования можно изобразить в виде таблицы:

№ шага	Процесс	Комментарии
1	Постановка гипотезы	Предполагаем, что последовательность является случайной
2	Вычисление статистики исследуемой последовательности	Тестирование на битовом уровне
3	Вычисление P-value	P-value${\displaystyle \in }$[0; 1]
4	Сравнение P-value с α	Задаем α в пределах [0,001; 0,01]; если P-value<α, то тест пройден

Пусть дана двоичная последовательность s. Требуется установить, проходит ли данная последовательность статистический тест или нет. Для этого используются несколько различных подходов:

• пороговое значение
• фиксированный диапазон значений
• значение вероятности

Данный подход заключается в подсчёте какой-либо статистической величины двоичной последовательности с(s) и его сравнении с некоторым пороговым значением. Если полученное значение с(s) меньше порогового значения, то последовательность s не проходит данный тест.

Подход также заключается в подсчёте некоторой статистической величины двоичной последовательности с(s) как и в первом случае. Однако теперь мы говорим, что если с(s) выходит за пределы некоторого диапазона значений, то последовательность s не проходит данный тест.

Третий подход в определении того факта, что двоичная последовательность s проходит статистический тест, включает подсчёт не только статистической величины с(s), но и соответствующее ей значение вероятности p. Обычно подсчёт конкретной статистической величины производится таким образом, чтобы её большие значения предполагали неслучайный характер последовательности s. Тогда p есть вероятность получения значения с(s) большего либо равного значению с(s'), высчитанного для истинно случайной последовательности s'. Следовательно, малые значения вероятности p (обычно p < 0,05 или p < 0,01) могут быть интерпретированы как доказательство того, что s не является случайной. Таким образом, если для некоторого фиксированного значения a значение вероятности p < a, то двоичная последовательность s не проходит данный тест. Как правило, a принимает значения из интервала [0,001;0,01].

Тесты DIEHARD были разработаны Джорджем Марсальей в течение нескольких лет и впервые опубликованы на CD-ROM, посвящённом случайным числам. Они рассматриваются как один из наиболее строгих известных наборов тестов.

Тесты Кнута основаны на статистическом критерии ${\displaystyle \chi ^{2}}$. Вычисляемое значение статистики ${\displaystyle \chi ^{2}}$ сравнивается с табличными результатами, и в зависимости от вероятности появления такой статистики делается вывод о её качестве. Среди достоинств этих тестов — небольшое их количество и существование быстрых алгоритмов выполнения. Недостаток — неопределенность в трактовке результатов. Вот краткое описание этих тестов:

• Проверка несцепленных серий. Последовательность разбивается на m непересекающихся серий и строится распределение ${\displaystyle \chi ^{2}}$ для частот появления каждой возможной серии.
• Проверка интервалов. Данный тест проверяет равномерность распределения символов в исследуемой последовательности, анализируя длины подпоследовательностей, все элементы которых принадлежат определённому числовому интервалу.
• Проверка комбинаций. Последовательность разбивается на подпоследовательности определённой длины, и исследуются серии, состоящие из различных комбинаций чисел.
• Тест собирателя купонов. Пусть ${\displaystyle \xi _{1},\xi _{2},\dots ,\xi _{n}}$ — последовательность длины n и размерности m. Исследуются подпоследовательности определённой длины, содержащие каждое m-разрядное число.
• Проверка перестановок. Данный тест проверяет равномерность распределения символов в исследуемой последовательности, анализируя взаимное расположение чисел в подпоследовательностях.
• Проверка на монотонность. Служит для определения равномерности исходя из анализа невозрастающих и неубывающих подпоследовательностей.
• Проверка корреляции. Данный тест проверяет взаимонезависимость элементов последовательности.

Отличие этих тестов от других современных — открытость алгоритмов. Также среди достоинств — однозначная интерпретация результатов тестирования. Таблица общих характеристик:

С целью утверждения нового стандарта шифрования Advanced Encryption Standard Национальный институт стандартов и технологий при поддержке правительства США провёл конкурс, в ходе которого были протестированы 15 претендовавших алгоритмов. Один из критериев, используемых при оценке алгоритмов, заключался в их пригодности в качестве генераторов случайных чисел. Проверка таких генераторов на предмет формирования случайных двоичных последовательностей с хорошими статистическими свойствами осуществлялась с помощью набора статистических тестов NIST.

В течение первого раунда AES тестирование проводилось с 128-битными ключами. Лишь 9 алгоритмов из 15 алгоритмов смогли пройти статистические тесты[10].

По результатам первого раунда 5 алгоритмов шифрования были выбраны в качестве финалистов AES: MARS, RC6, Rijndael, Serpent и Twofish. Во втором раунде конкурса AES оценка пригодности этих 5 алгоритмов в качестве генераторов случайных чисел проводилась на основе 192-битных и 256-битных ключей. Продолжительность статистических тестов NIST составила несколько месяцев, причем вычисления производились на многочисленных рабочих станциях Sun Ultra. Все данные формировались и обрабатывались в режиме онлайн. В результате второго раунда было показано, что каждый из пяти финалистов формирует случайную бинарную последовательность с хорошими статистическими свойствами и поэтому может быть использован в качестве генератора псевдослучайных чисел, причем имеется возможность использования ключей размерами: 128, 192 и 256 бит[11].