Надежность двухуровневого подхода к тестированию в наборе тестов NIST SP 800-22

Аннотация

Рассматривается предложенный в наборе тестов NIST SP 800-22 двухуровневый подход к тестированию генераторов случайных чисел, который состоит в подсчете количества последовательностей, прошедших основной тест, и проверке распределения p-значений с помощью хи-квадрат-теста. Данный подход может повысить надежность статистического теста, однако он чувствителен к погрешностям аппроксимации, возникающим при вычислении p-значений. Показано, что для последовательностей, порождаемых с помощью симметричного алгоритма блочного шифрования (AES), двухуровневый подход к тестированию не является надежным. Систематическая погрешность при вычислении p-значений зависит только от погрешности аппроксимации точного распределения статистики эквивалентным ему теоретическим распределением и от числа бит n в тестируемых последовательностях. Для надежного двухуровневого тестирования такая погрешность не должна превосходить $\frac{\sigma}{N} = \frac{1}{k}\sqrt {\frac{{k\; - \;1}}{N}}$, где  $\sigma = \sqrt {\frac{1}{k}\left( {1\; - \;\frac{1}{k}} \right)N}$ – стандартное отклонение от среднего числа частиц в ячейке в равновероятной схеме размещения N частиц по k ячейкам. Подобные эвристические соображения и проведенные эксперименты позволяют предположить, что, например, при n = 2²⁰ в двухуровневом частотном тесте (Frequency test) из набора тестов NIST SP 800-22 количество тестируемых последовательностей N не должно превышать 26 000. Для полного исключения систематической погрешности, возникающей при проведении частотного теста и определении номера ячейки из k возможных ячеек (непересекающихся подынтервалов отрезка [0, 1]), которому принадлежит p-значение, предложены двусторонние оценки квантилей биномиального закона.