TestU01: библиотека С для эмпирического тестирования генераторов случайных чисел

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

Введение
Для тестирования последовательностей на случайность существует большое количество алгоритмов, а для удобства проверки последовательностей уже реализованы программные продукты, содержащие в себе некоторые наборы тестов. Среди них наиболее распространены тесты DieHard, NIST STS, TestU01, PractRand, gjrand, Стопка книг и другие.

Введение
В данном исследовании проведено применять практически пакет ТеstU01 к тестированию генератор в С++ и исследование эффективности тестов Стопка книг, TestU01 и тестов PractRand для проверки генераторов случайных чисел. На основе проведенного исследования был сделан вывод о том, какой из тестов находит отклонения на большем количестве генераторов и при меньшей длине последовательности.
Протестированы 14 различных генераторы случайных чисел, среди которых можно выделить линейные конгруэнтные генераторы, потоковый криптографический генератор RC4, функцию rand в ОС Linux, Mersenne Twister и AES+Feistel+Reverie.
Н.Н.Токарева к.ф.-м.н., с.н.с. ИМ СО РАН
Криптосистемы с открытым ключом и вероятностное шифрование

Тесты
Существуют различные тесты, которые оценивают, насколько исследуемая последовательность бит «похожа» или «не похожа» на действительно случайную. Методы оценки качества генераторов случайных и псевдослучайных последовательностей можно разделить на две группы:
Графические тесты
Статистические тесты

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

В отличие от графических тестов, статистические тесты выдают численную характеристику последовательности и позволяют однозначно сказать, пройден тест или нет.
Наиболее известны следующие программные пакеты статистических тестов:
Тесты NIST
TEST-U01
CRYPT-X
DIEHARD
ENT
PractRand
Стопка книг
Статистические тесты

Описание теста “TestU01”
TestU01 — это пакет статистических эмпирических тестов, реализованный на языке ANSI C, который предлагает набор утилит для тестирования генераторов случайных чисел.
Он предлагает четыре группы модулей для работы с генераторами:
реализация заранее запрограммированного генератора (модуль u)
реализация специальных статистических тестов (модуль s);
реализация батарей статистических тестов (модуль b);
применение тестов на целых семействах генераторов (модуль f).

Описание теста “TestU01”
В пакете TestU01 содержится шесть батарей статистических тестов.
SmallCrush (состоит из 10 тестов)
Crush (состоит из 96 тестов)
BigCrush (состоит из 106 тестов)
Alphabit (состоит из 17 тестов)
Rabbit (состоит из 38 тестов)
BlockAlphabit(состоит из 17 тестов)

PractRand - самый простой в использовании и удобный для измерения «эффективности». Он принимает на вход поток байт, может тестировать 32 и 64 битные генераторы. Способен справляться с очень большими объемами данных.
Описание теста “PractRand”

Основная идея метода а упарядочивании элементов как в стопке книг. Книга вынимается из стопки и кладётся наверх. Её номер становится первым; книги, которые до этого были над ней двигаются вниз, а остальные остаются на месте. Пусть некоторый источник порождает буквы из алфавита
и требуется по выборке
проверить гипотезу:
Против альтернативной гипотезы являющейся отрицанием
Описание теста “Стопка книг”

При тестировании по предлагаемому методу буквы алфавита А упорядочены ( и занумерованы в соответствии с этим порядком от 1 до S), причём этот порядок меняется после анализа каждого выборочного значения как в стопке книг.
Обозначим через номер буквы
При применении описываемого теста множество всех номеров
заранее, до анализа выборки, разбивается на r>1 непересекающихся частей
Затем по выборке подсчитывается количество
номеров , принадлежащих подмножеству которое мы обозначим через
Описание теста “Стопка книг”

При выполнении гипотезы вероятность того, что номер принадлежит множеству пропорциональна количеству элементов а этом подмножестве, т.е. равно . Затем по критерию проверяется гипотеза
против альтернативной гипотезы . Очевидно, при выполнении исходной гипотезы выполняет и наоборот, при выполнении гипотезы выполняется .
Описание теста “Стопка книг”

LCG(224 ,16598013,12820163), этот генератор используется в Microsoft VisualBasic 6.0.
LCG(231,65539,0), RANDU долгое время использовался во многих компьютерах в 1960-х – 1970-х годах,
LCG(232 ,1099087573,0), этот генератор предложил Fishman.
LCG(232 ,69069,1), этот генератор предложил Marsaglia.
LCG(232 ,69069,5), использовался в компиляторах GNU.
LCG(232 ,1664525,1013904223), предложен в Numerical Recipes.
LCG(232 , 214013, 2531011), используется в Microsoft Visual/Quick C/C++.
LCG(246 ,513,0), использовался для аэродинамического моделирования в НАСА в исследовательском центре Аmes.
LCG(263,519 ,1), LGG ( 263, 9219741426499971445, 1) рекомендовано использовать на будущее а Национальной лаборатории США Los Alamos.
Описание генераторов

10. LCG(263,921974142649997144
11. RC4
12. rand (C++ gcc 4.3.2)
13. Mersenne twister
14. AES+Feistel+Reverie
Описание генераторов

Каждый генератор выдавал 100 последовательностей одинаковой длины. В среднем 1 последовательность из 100 может быть забракована при уровне значимости a= 0.01.
Доверительный интервал, вычисленный с помощью критерия
равен [0;4]. Если количество забракованных последовательностей не попадает а этот интервал, то это говорит о том, что генератор выдаёт последовательности, при данной длине выборки, статистически отличимые от случайных. В этом случае будет говорить, что генератор не прошёл испытания, то есть забракован.
Тестирования проводились для последовательностей, выдаваемых генераторами, от до бит. Для некоторых генераторов тестирование было проведено при больших длинах последовательности и только некоторыми тестами.
Описание экспериментов

Тестом "Стопка книг" последовательность разбивалась на блоки длины и при тестировании рассматривалась как выборка из алфавита размера . Множество всех позиций а "Стопке книг" развивалось на два подмножества
Второе подмножества не хранилось в памяти компьютера.
При исследовании тестами TestU01, PracRand, выбирались рекомендуемые параметры.
Описание экспериментов

В данной работе приведены результаты тестирования, перечисленных выше генераторов случайных чисел и представлены длины последовательностей в битах, выдаваемые генератором, с которых начинаются первые отклонения от случайности, определяемые данным тестом. Если отклонения обнаружены, то с увеличением длины входной последовательности отклонения возрастают.
В результате было показано, что тестом
1. PractRand (стандартный, 1 терабайт) на 10 генераторах
2. TestU01(SmallCrush, Crush, BigCrush, Alphabit, Rabbit) на 9 генераторах
3. Стопка книг на 9 генераторах найдены отклонения от случайности
Результаты

f
Результаты

Заключение
Н.Н.Токарева к.ф.-м.н., с.н.с. ИМ СО РАН
Криптосистемы с открытым ключом и вероятностное шифрование

3) Рекомендуемые параметры для "Стопки книг" l длину блока рекомендуется выбирать из ряда 8, 16, 20, 32, 40 и так далее; размер одного или нескольких подмножеств где b число из ряда 2, 4, 5, 8, 10, 16, 20, 32, 40, 64, 80, 128, 160 и так далее.
4) С помощью PractRand и TestU01, как правило, легче всего интерпретировать результат.
5) PractRand требовал больше битов ввода для тестирования, чем другие наборы тестов - это может быть проблемой, если ваш RNG очень медленный или иным образом ограничен по объему производимых данных.
Заключение