Иногда очень остро встает вопрос о случайности используемых данных. Во многих программах вы используете датчики случайных (точнее псевдослучайных) чисел. Зачастую это линейный конгруэнтный датчик случайных чисел. А на сколько хорош датчик случайных чисел используемый в вашей программе?
В этой заметке я хочу рассказать одном из статистических тестов входящих в пакет исследования NIST для датчиков случайных чисел. Это спектральный тест на основе дискретного преобразования Фурье. Заметка представляет собой «вольный» перевод оригинальной документации с некоторыми исправлениями. К материалу прилагается практическая реализация этого теста.
Известно, что проблема генерации случайной последовательности с произвольным законом распределения вероятностей сводится к проблеме генерации так называемой равномерно распределенной случайной последовательности (РРСП), или, как ее часто называют в криптографических приложениях, «чисто случайной» последовательности.
Проверка близости конкретной последовательности к модели РРСП осуществляется методами статистического тестирования и состоит в проверке гипотез выполнения базовых свойств РРСП.
Тест исследует последовательность бит с целью выявления периодических составляющих в псевдослучайной последовательности (ПСП).
Параметрами теста выступают:
$n$ - длина ПСП (бит), должна быть кратна $2^k$,
$x_i$ - биты ПСП, $i = 1 ,…, n$
Итак, давайте рассмотрим алгоритм выполнения теста.
1. ПСП преобразуется к виду: $x_i = 2x_i – 1$, для $i = 1,2,…,n$;
2. Определяются параметры:
$T = \sqrt{2.995732274 n}$ – верхняя граница значений спектральных компонент c’; Следует заметить, что в оригинальной документации NIST вместо числа 2.995… дано число 3, но оно было уточнено.
$N_0 = 0.95 n/2$ – ожидаемое число значений спектральных компонент c’ в интервале $[0; T);$
3. Вычисляется быстрое дискретное преобразование Фурье: c = БДПФ(x);
4. вычисляется модуль спектра: $c_i' = |c_i| = \sqrt{Re(ci)^2+Im(ci)^2}, i = 1,2, ..., n/2$.
5. определяется число N_1 значений спектральных компонент c’, принадлежащих диапазону: $c_i'$
6. определяется значение вероятности $Pv: Pv = 2 (1-Ф(|N_1 - N_0|/\sqrt{0.25 * 0.95 * 0.05 * n} ))
Заметим, что до проведения теста выбирается критическое значение $a$ и считается, что последовательность «хорошая», если вероятность значимости $Pv$ попала в интервал от $a$ до $1-a$. Как правило выбирают a довольно меленьким, например, 0.005.Математическая основа теста довольно проста. Т.к. последовательность спектральных компонент обладает свойством симметрии, то можно ограничится анализом первой половины спектра: ci, i = 1,2, ...,n/2 . В предположении о том, что последовательность случайна, ограничиваем амплитуды спектра ci уровнем $T = \sqrt{2.995732274 n}$. Для случайной последовательности более 95% компонент спектра должны быть ниже уровня T. Уровень Т здесь определен для биномиального распределения элементов последовательности.
Покажем наглядно, работу теста.
Гистограммы, представленные на рисунках 1 и 2, иллюстрируют чувствительность теста к периодическим составляющим в ПСП. Для эксперимента было сформировано две ПСП, размером 4096 бит каждая.
ПСП1 – сгенерирована «хорошим» генератором ПСП.
ПСП2 – сгенерирована генератором ПСП с дефектом, порождающим периодические подпоследовательности внутри ПСП.
На гистограммах проведена линия, обозначающая 95-процентный уровень T. Очевидно, что количество компонент спектра ПСП2, превышающих уровень T, явно превышает 5%.
Рисунок 1 – Спектр ПСП1 (не обнаружено периодических составляющих), результат тестирования – удовлетворительный, $Pv = 0.8077$.
Рисунок 2 – Спектр ПСП2 (периодические составляющие ярко выражены), результат тестирования – неудовлетворительный, $Pv = 0.0001$
На практике при исследовании ПСП статистический тест выполняют многократно.
При этом получают целый набор статистик $d = |N_1 - N_0|/\sqrt{0.25 * 0.95 * 0.05 * n}$ и вероятностей значимости Pv. Эти две последовательности дополнительно исследуются на соответствие распределению теста и на равномерность в [0,1] соответственно при помощи статистических критериев.
В завершение статьи $N_1$. Конечно, есть оригинальная реализация от NIST, но в моей проведены некоторые оптимизации, позволяющие немного сократить время счета. Модуль содержит 2 функции: fft – Выполняет быстрое преобразование Фурье, и DFT_Test – собственно сам тест Фурье. На вход последней функции подается массив из байт, каждый равен 0 или 1, и длинна этого массива.Теоретически данным модулем можно обрабатывать последовательности до $2^32$. Однако на практике я больше чем $2^20$ не использовал из-за увеличения времени вычислений.
