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

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

Теоретическая основа

Принципы построения

Один из самых наглядных тестов — тест на равномерное распределение частот появления каждого символа. Пусть $\xi _{1},\xi _{2}...\xi _{n}$ — последовательность длиной n и размерности m. Тогда частоты ν_i должны принадлежать отрезку ${\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$\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 бит;

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

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

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

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

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

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

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

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

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

Статистические тесты

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

№	Название	Автор	Организация
1	Тесты NIST	Andrew Rukhin, et. al.	NIST ITL
2	TEST-U01	P.L’Ecuyer и др.	Universit´e de Montr´eal
3	CRYPT-X	Helen Gustafson и др.	Queensland University of Technology
4	The pLab Project	Peter Hellekalek	University of Salzburg
5	DIEHARD	George Marsaglia	Florida State University
6	Dieharder	Robert G. Brown	Duke University
7	ENT	John Walker	Autodesk, Inc.
8	The Art Of Computer Programming Vol. 2 Seminumerical Algorithms	Дональд Кнут	Stanford University
9	Handbook of Applied Cryptography	Alfred Menezes и др.	CRC Press, Inc.

Тесты DIEHARD

Основная статья: Тесты DIEHARD

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

Тесты Д. Кнута

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

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

Тесты NIST

Основная статья: Статистические тесты NIST

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

№	Название теста	Определяемый дефект
1	Частотный тест	Слишком много нулей или единиц
2	Проверка кумулятивных сумм	Слишком много нулей или единиц в начале последовательности
3	Проверка «дырок» в подпоследовательностях	Отклонение в распределении последовательностей единиц
4	Проверка «дырок»	Большое (малое) число подпоследовательностей нулей и единиц свидетельствует, что колебание потока бит слишком быстрое (медленное)
5	Проверка рангов матриц	Отклонение распределения рангов матриц от соответствующего распределения для истинно случайной последовательности, связанное с периодичностью последовательностей
6	Спектральный тест	Периодические свойства последовательности
7	Проверка непересекающихся шаблонов	Непериодические шаблоны встречаются слишком часто
8	Проверка пересекающихся шаблонов	Слишком часто встречаются m-битные последовательности единиц
9	Универсальный статистический тест Маурера	Сжимаемость (регулярность) последовательности
10	Проверка случайных отклонений	Отклонение от распределения числа появлений подпоследовательностей определённого вида
11	Разновидность проверки случайных отклонений	Отклонение от распределения числа появлений подпоследовательностей определённого вида
12	Проверка аппроксимированной энтропии	Неравномерность распределения m-битных слов. Малые значения означают высокую повторяемость
13	Проверка серий	Неравномерность распределения m-битных слов
14	Сжатие при помощи алгоритма Лемпела-Зива	Большая сжимаемость, чем истинно случайная последовательность
15	Линейная сложность	Отклонение от распределения линейной сложности для конечной длины подстроки

Практические приложения

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

Конкурс AES

Основная статья: AES (конкурс)

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

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

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

См. также

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

Литература

• Дональд Э. Кнут. Глава 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 Н. А. Семенова
• Статистический анализ поточных шифров Е. В. Игоничкина (недоступная ссылка)