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

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

Один из самых наглядных тестов — тест на равномерное распределение частот появления каждого символа. Пусть ${\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].

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

• гистограмма распределения элементов последовательности;

  позволяет оценить равномерность распределения символов в последовательности и определить частоту повторения каждого символа;

• распределение на плоскости;

  предназначено для определения зависимости между элементами последовательности;

• проверка серий;

  позволяет определить равномерность отдельных символов в последовательности, а также равномерность распределения серий из k бит;

• проверка на монотонность;

  служит для определения равномерности исходя из анализа невозрастающих и неубывающих подпоследовательностей;

• автокорреляционная функция;

  предназначена для оценки корреляции между сдвинутыми копиями последовательностей и отдельных подпоследовательностей;

• профиль линейной сложности;

  тест оценивает зависимость линейной сложности последовательности от её длины;

• графический спектральный тест;

  позволяет оценить равномерность распределения бит последовательности на основании анализа высоты выбросов преобразования Фурье.

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

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

Тесты 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].

• Тест на следующий бит

• Дональд Э. Кнут. Глава 3. Случайные числа // Искусство программирования = The Art of Computer Programming. — 3-е изд.. — М.: Вильямс, 2000. — Т. 2. Получисленные алгоритмы. — 832 с. — ISBN 5-8459-0081-6.
• М. А. Иванов, И. В. Чугунков. Глава 4. Методика оценки качества генераторов ПСП // Теория, применение и оценка качества генераторов псевдослучайных последовательностей. — М.: КУДИЦ-ОБРАЗ, 2003. — 240 с. — ISBN 5-93378-056-1.

• Recommendation for Random Number Generation Using Deterministic Random Bit Generators (англ.) NIST SP 800-90
• Statistical Testing of Random Number Generators (англ.) Proceedings of the 22nd National Information Systems Security Conference, 10/99
• A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications (англ.) NIST SP 800-22
• РАЗРАБОТКА МЕТОДОВ ИССЛЕДОВАНИЯ СТАТИСТИЧЕСКИХ ХАРАКТЕРИСТИК ПРОМЕЖУТОЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ БЛОЧНОГО ШИФРА ГОСТ 28147-89 Н. А. Семенова
• Статистический анализ поточных шифров Е. В. Игоничкина (недоступная ссылка)