2.2 Частотный тест в пределах блока

2.2.1 Назначение теста

Данный тест рассматривает пропорциональность единиц в пределах М-битных блоков. Назначение данного теста заключается в определении того, является ли частота единиц в М-битном блоке приблизительно равной М/2, как это должно быть согласно предположению о случайности. Для блоков с размером М=1, этот тест вырождается в тест № 1 (Частотный тест (на монотонность бит).

2.2.2 Исходные данные

• М- длина каждого блока

• n — длина последовательности бит.

•  = 1, 2, ..., n - последовательность битов, сгенерированная RNG или PRNG

2.2.3 Тестовая статистика

2(obs): мера, показывающая на сколько хорошо исследованная пропорция единиц в данном М-битном блоке соответствует ожидаемой пропорции (½).

Исходное распределение для тестовой статистики - распределение 2.

2.2.4 Описание теста

1. 1. Разбить входную последовательность на N = [n / М] не пересекающихся блоков. Отбросить все неиспользуемые биты.

2. 2. Определить пропорцию i; единиц в каждом М-битном блоке, используя выражение:

3. 3. Рассчитать статистику 2(obs)

4. 4. Рассчитать P-value = igamc(N/2, 2(obs)/2), где igamc - неполная гамма-функция для Q(a, x):

2.2.5 Правило принятия решения (на 1%-ом уровне)

Если вычисленное значение P-value < 0.01, то следует сделать заключение, что последовательность не является случайной. В противном случае, следует сделать заключение, что последовательность случайная.

2.2.6 Заключение и интерпретация результатов теста

В случае, когда P-value мало (<0.01), это указывает на большое отклонение от равных пропорций единиц и нулей, по крайней мере, в одном из блоков.

2.2.7 Рекомендуемый размер входной последовательности

Рекомендуется, чтобы каждая тестируемая последовательность состояла как минимум из 100 битов (то есть, n  100). Учитывая, что nMN, размер блока М должен быть выбран таким образом, чтобы выполнялись следующие условия: М20, М 20,M>0.01n и N < 100.

2.2.8 Пример

(вход)  =11001001000011111101101010100010001000010110100011

000010001101001100010011000110011000101000101110 00

(вход) n = 100

(вход) М=10

(обработка) N=10

(обработка) 2 = 7.2

(результат) P-value = 0.706438

(заключение) Поскольку P-value  0.01, последовательность следует принять как случайную.

3.2 Техническое описание

Тест стремится определить локализованные отклонения от идеальной частоты 5% единиц путём декомпозиции тестовой последовательности на некоторое количес1 непересекающихся участков последовательности и применения 2 -теста на гомогенное совпадение эмпирических частот с идеалом ½. Малые значение P-value говорят о больших отклонениях от равных пропорций единиц и нулей как минимум в одном из блоков. Строка, состоящая из 0 и 1 (или, что тоже самое, из -1 и 1) разбита на некотог количество непересекающихся подстрок. Для каждой подстроки рассчитывав пропорция единиц. Статистика хи-квадрат сравнивает эти пропорции для подстрок идеалом ½. Статистика относится к распределению хи-квадрат с количеством степен свободы равным количеству подстрок.

Параметрами теста являются М и N, такие что n = MN, то есть исходная стро разбивается на N подстрок, длины М каждая. Для каждой из этих подстрок, вероятноcть единиц оценивается по наблюдаемой относительной частоте единиц, _i, i = I, ...,N. Сумма:

при гипотезе о случайности, имеет распределение хи-квадрат с количеством степеней свободы N. Соответствующее значение P-value:

Ссылки для теста

[1] Nick Maclaren, \Cryptographic Pseudo-random Numbers in Simulation," Cambridge Security Workshop on Fast Software Encryption. Dec. 1993. Cambridge, U.K.: R. Anderson, pp. 185-190.

[2] Donald E. Knuth, The Art of Computer Programming. Vol 2: Seminumerical Algorithms. 3rd ed. Reading, Mass: Addison-Wesley, 1998 (especially

pp. 42-47).

[3] Milton Abramowitz and Irene Stegun, Handbook of Mathematical Functions:

NBS Applied Mathematics Series 55. Washington, D.C.: U.S. Government Printing 0_ce, 1967.