Хи-квадрат тест: статистическая проверка справедливости RNG

Тест хи-квадрат (χ²) Пирсона является базовым инструментом для проверки соответствия наблюдаемых частот ожидаемым в рамках заданного теоретического распределения. Статистика теста вычисляется как χ² = Σᵢ(Oᵢ − Eᵢ)² / Eᵢ, где Oᵢ — наблюдаемая частота в i-й категории, а Eᵢ — ожидаемая частота при нулевой гипотезе. Для оценки генераторов псевдослучайных чисел нулевая гипотеза H₀ предполагает равномерное распределение выходных значений по всем возможным категориям. Асимптотически при n → ∞ и выполнении условия Eᵢ ≥ 5 для всех категорий данная статистика подчиняется распределению χ² с (k − 1) степенями свободы, где k — число категорий.

Количество степеней свободы (degrees of freedom, df) определяет форму распределения χ² и критические значения для принятия решения. При тестировании k-категориального генератора df = k − 1, поскольку одна степень свободы расходуется на ограничение общей суммы частот. Критическое значение χ²_α при уровне значимости α = 0.05 и df = 255 (типичное для 8-битного генератора с 256 возможными исходами) составляет 293.25. Превышение наблюдаемой статистикой этого порога влечёт отклонение H₀ и вывод о неравномерности распределения генератора. Мощность теста (power) возрастает с увеличением объёма выборки n и величины реального отклонения от равномерности, что формализуется через параметр нецентральности δ = n · Σᵢ(pᵢ − 1/k)²/(1/k).

Корректная интерпретация результатов χ²-теста требует учёта эффекта множественного тестирования и размера выборки. При последовательном применении теста к тысячам генерируемых блоков данных необходимо применять поправку Бонферрони или метод контроля ложных открытий (FDR) по Бенджамини–Хохбергу для предотвращения инфляции ошибок первого рода. Чрезмерно большие выборки создают обратную проблему: тест становится сверхчувствительным и отклоняет H₀ при статистически значимых, но практически несущественных отклонениях. Для контроля этого эффекта рассчитывается мера размера эффекта Крамера V = √(χ²/(n·(k−1))), позволяющая отличить содержательные отклонения от статистических артефактов.

В практике аудита криптографических генераторов χ²-тест применяется в составе батарей статистических тестов наряду с тестами серий, тестом пробелов и спектральным тестом. Автоматизированный конвейер валидации PRNG выполняет χ²-тест на множественных уровнях агрегации: побайтовом, поблочном (блоки по 16, 32 и 64 бита) и на уровне составных паттернов. Совокупный p-value, вычисленный методом Фишера для объединения независимых тестов, предоставляет итоговую метрику качества генератора. Значение p-value ниже 10⁻⁶ однозначно указывает на системную неравномерность и влечёт немедленную ротацию серверного сида с полной реинициализацией энтропийного пула. Данный протокол обеспечивает соответствие выходных последовательностей стандартам NIST SP 800-22 и гарантирует криптографическую стойкость анализируемого генератора.