1.3.1 Монобитный тест

Монобитный тест – самый простой тест из FIPS-140-3. Он основан на определении соотношения между нулями и единицами во всей двоичной последовательности. Его используют для того, чтобы выяснить, действительно ли число нулей и единиц в последовательности приблизительно одинаковы, как это должно быть в случае истинно случайной последовательности. Тест оценивает, насколько доля единиц близка к 0,5. Таким образом, для успешного прохождения теста, нужно чтобы в сгенерированной последовательности количество нулей и единиц было примерно одинаковым. Если вычисленное в ходе теста значение вероятности p < 0,01, то данная двоичная последовательность не является истинно случайной. В противном случае, последовательность носит случайный характер. Все последующие тесты проводятся при условии, что пройден монобитный тест.

Алгоритм монобитного теста следующий:

Пусть число битов в проверяемой последовательности равно l, число единиц – , число нулей – n0 .В данном тесте вычисляется следующее значение: (1.1)

Если значение Х_l превысит некото­рый порог (который зависит от p), то генератор не проходит тест. Поскольку Х_l имеет приблизительно х распределение с одной степенью свободы, то в качестве порога было взято число 6,63 (так как ).

Единственной сложностью здесь является эффективный подсчет числа различных би­тов, так как в большинстве современных вычислительных архитектур нет команд для работы с отдельными битами. Число мысленно разбивается на ячейки, равной длины и биты в старшей и младшей половинах ячейки рассматривается как число битов в соответствующей части ячейки. Затем параллельно для всех ячеек число битов в обеих половинах ячейки суммиру­ются и результат записывается в младшую часть. Вначале суммирование производится для ячеек размером 2 бита, потом 4 и так далее до 32. В результате мы получаем полное число би­тов за логарифмическое (от длины машинного слова) время.

1.3.2 Блочный тест

Пусть m положительное целое число, такое, что и пусть Разобьем последовательность x на k непересекающихся подпоследовательностей, каждая длиной m, и пусть n_i будет числом появлений i-го типа последовательности длиной m,. Блочный тест определяет, действительно ли последовательности длиной m, появляются приблизительно столько же раз в последовательности x, столько же раз, сколько ожидается для случайной последовательности. Для применения критерия используется расчет параметра

(1.2)

который согласуется с распределением χ2 с 2m – 1 степенями свободы. Статистический параметр, задаваемый уравнением, вычисляется для m = 4. Статистика должна удовлетворять условию 1,03 < X3 < 57,4.

1.3.3 Серийный тест

Данный тест определяет число вхождений серий одинаковых битов различной длины. В идеальной случайной последовательности среднее число серий длиной равняется

(1.3)

Пусть число единичных и нулевых серий в проверяемой последовательности равняется и соответственно. Статистика данного теста вычисляется по формуле (1.4):

(1.4)

Данная статистика имеет распределение с степенями свободы. Для произвольного числа , содержащего серию нулевых битов длиной в младших разрядах, содержит серию из единичных битов в младших разрядах (все остальные биты нулевые). Длину выделенной таким образом канонической серии единичных битов можно считать бинарным поиском.