Тест на следующий бит

Тест на следующий бит (англ. next-bit test) — тест, служащий для проверки генераторов псевдо-случайных чисел на криптостойкость. Тест гласит, что не должно существовать полиномиального алгоритма, который, зная первые k битов случайной последовательности, сможет предказать k+1 бит с вероятностью большей ½.

Проблема определения случайности

В теории криптографии отдельной проблемой является определение того, насколько последовательность чисел или бит, сгенерированных генератором, является случайной. Как правило для этой цели используются различные статистические тесты, такие как например тесты DIEHARD или тесты NIST. Эндрю Яо доказал^[1] в 1982 году что генератор, прошедший «тест на следующий бит», пройдет и любые другие статистические тесты на случайность, выполнимые за полиномиальное время.

Формулировка

Двоичный генератор проходит тест на следующий бит, если:
Для любого i и любого вероятностного полиномиального по времени алгоритма A: $\{0,1\}^i$ -> {0,1} (Алгоритм, имеющий в качестве начальных данных последовательность битов длиной i, и выдающий на своём выходе бит), выполняется следующее неравенство:

$|P(A(s_1^{i-1}) = s_i) - 1/2| < O(v(n)),$

где $O(v(n))$ - обозначение функции, убывающей быстрее чем обратный полином степени n.

Стоит отметить, что определение теста на следующий бит не даёт никакого алгоритма для выполнения этого теста.

Расширенный тест на следующий бит

Бинарная последовательность $s_1^n$ полученная от источника S, считается прошедшей расширенный тест на следующий бит, если: для любого i и l: 1 < i, l < n и любого вероятностного полиномиального по времени алгоритма A: $\{0,1\}^{i-1}$ -> $\{0,1\}^l$ выполняется то, что при помощи A не может предсказать следующие l бит или, в случае предсказания, выполнимо неравенство:

$|P(A(s_1^{i-1}) = s_i^{1-i+l}) - (1/2)^l| < O(v(n))$

Доказано, что расширенный тест на следующий бит и тест на следующий бит — эквивалентны.^[2]

Тестирование несбалансированных последовательностей

Хоть тест на следующий бит и является универсальным методом проверки независимости выходных бит последовательности, он пригоден лишь для несмещенных последовательностей, то есть таких, в которых вероятность появления единицы эквивалентна вероятности появления нуля.
Если же выходная последовательность должна заведомо обладать некоторым смещением $b$, т.е. $P(s_i) = b$, то данный тест не пригоден. Поэтому для тестирования независимости выходных бит таких последовательностей приходится использовать другие тесты. В частности было предложено расширение теста на следующий бит - сравнительный тест на следующий бит.^[3] Идея теста заключается в том, что мы изначально полагаем, что распределение выходной последовательности описывается некоторой математической моделью, а тест служит для проверки соответствия генератора этой модели.

Сравнительный тест на следующий бит

Двоичный генератор проходит S сравнительный тест на следующий бит относительно модели M, если:
Для любого i и любого вероятностного полиномиального по времени алгоритма $A\colon\{0,1\}^i\rightarrow \{0,1\}$ (т.е. алгоритм, имеющий в качестве начальных данных последовательность битов длиной i и выдающий на своём выходе бит), выполняется следующее неравенство:

$|P_S(A(s_1^{i-1}) = s_i) - P_M(A(s_1^{i-1}) = s_i)| < O(v(n)),$

где $P_M(A(s_1^{i-1}) = s_i)$ - вероятность предсказания алгоритмом следующего бита для модельного генератора.

Очевидно, что задавшись моделью M, представляющей истинно случайную последовательность, мы получим $P_M(A(s_1^{i-1}) = s_i) = 1/2)$, т.е. классический тест на следующий бит. Задавшись же моделью с $P_M(A(s_1^{i-1}) = 1 ) = b$ и $P_M(A(s_1^{i-1}) = 0 ) = 1-b$, получим искомый случай теста для несбалансированной последовательности с заданным смещением $b$.

Практические реализации

Алгоритм Садегияна-Махаери (Sadeghiyan-Mohajeri test)

Данный тест использует преимущество древовидной структуры, способной сохранить всю информацию о подпоследовательностях в общей последовательности. Алгоритм вычисления m-битных последовательностей может быть представлен в виде двоичного дерева с взвешенными ребрами. В данном дереве каждый лист на глубине l хранит информацию о том, сколько раз встретилась данная l-битная последовательность. Т.к. дерево является взвешенным, то его каждому его ребру приписывается отношение количества, записанного в дочернем листе, к количеству записанному в родительском. Для достаточно большой случайной последовательности предполагается, что числа, соответствующие рёбрам, будут примерно равны 1/2.

Шаги алгоритма Садегияна-Махаери

1. Задаём уровень ошибки α = (1+sqrt((χ^2)/n)/2, соответствующий χ^2-распределению с одной степенью свободы и допущением ошибки 5%.
2. Вычисляем l = round($log_2$(n) - 1), n - длина исследуемой последовательности.
3. Приписываем к концу последовательности первые $(l-1)$ бит и разделяем последовательность на перекрывающиеся блоки длины $l$.
4. Вычисляем частоту встреч для всех листьев длины $l$.
5. Формируем $l$ и $(l-1)$ уровни дерева. Вычисляем соответствующие вероятности для всех рёбер.
6. Для каждого листа на уровне (l-1), если следующий бит(0 или 1) появляется с вероятностью меньшей, чем α, следующий бит предсказывается соответственно частоте этого появления. В противном случае предсказание невозможно.
7. Отбрасываем самый левый бит l-битной последовательности. Используя оставшиеся (l-1) бит снова переходим на шаг 6 и определяем следующий бит. Повторяем данную операцию до тех пор, пока это возможно. После того, как получаем невозможность предсказания следующего бита, подсчитываем количество предсказанных бит. Таким образом мы получим для каждой последовательности длины (l-1) количество следующих бит, предсказываемых при помощи предыдущего шага.
8. Вычисляем P-value равное отношению предсказанных бит ко всем попыткам предсказания.

Зададим величину r как вероятность того, что идеальный генератор сгенерировал последовательность менее случайную, чем исследуемый. Обычно r выбирают в пределах [0.001; 0.01]. Тогда если P-value больше r, то исследуемая последовательность считается случайной и наоборот в противном случае.

Тест Садегяна-Мохаери не дает ясного и точного критерия для определения случайности последовательности. Вместо этого создатели алгоритма предполагают возможность сделать некоторые выводы о общем поведении последовательности. Когда алгоритм успешно предсказывает (l+1) бит, то считается, что наступила локальная детерминированность.

Практический тест на следующий бит (PNB)

Цель данного теста - определение отклонений в статистике появления следующего бита для подпоследовательности. Если же такое отклонение имеется - тест пытается использовать его для предсказания следующего бита. Последовательность считается неслучайной, если она содержит слишком много подпоследовательностей, чей последний бит предсказуем. Практический тест показывает более разумные результаты в сравнении с оригинальным тестом Садегяна-Мохаери.

Шаги алгоритма PNB

1. Задаём уровень ошибки $a=\frac{1+\sqrt{X^2/n}}{2}$, соответствующий $X^2$-распределению с одной степенью свободы и допущением ошибки 5%, аналогично алгоритму Садегяна-Мохаери.
2. Вычисляем l = round($log_2$(n) - 2), n - длина исследуемой последовательности.
3. Перемещаем первые l бит в конец последовательности.
4. Составляем дерево, аналогичное дереву в алгоритме Садегяна-Мохаери, в конечных узлах устанавливаем счетчики, соответствующие количеству нулей и единиц в следующем бите.
5. "Сканируем" последовательность окном размером l бит. Начальное положение окна - первые l бит. С каждым тактом двигаем окно на 1 бит вперед и в зависимости от значения в следующем за окном бите, увеличиваем счетчик узла, соответствующего значениям битов в окне.
6. Для каждого из узлов вычисляем отношения $n_0/(n_0 + n_1)$ и $n_1/(n_0 + n_1)$, где $n_0$ и $n_1$ - значения счетчиков для данного узла. Если одно из этих отношений превышает α, то увеличиваем счетчик $Y_obs$.
7. Вычисляем P-value = (1/2)* erfc(($Y_obs$ - μ)/sqrt(2σ^2)

Стоит отметить, что нет^[4] известной теории, позволяющей вычислить точные значения μ и σ, используемые в последнем шаге алгоритма. Поэтому эти значения вычисляются приближенно.

См. также

• Тестирование псевдослучайных последовательностей
• Алгоритм Блюма — Микали

Примечания

1. ↑ Andrew Chi-Chih Yao. Theory and applications of trapdoor functions.
2. ↑ A. Lavasani and T. Eghlidos. Practical Next Bit Test for Evaluating Pseudorandom Sequence. Appendix A
3. ↑ A.W.Schrift, A. Shamir. On the Universality of the Next Bit Test. 1998
4. ↑ A. Lavasani and T. Eghlidos. Practical Next Bit Test for Evaluating Pseudorandom Sequence. Appendix B

Литература

• Andrew Chi-Chih Yao. Theory and applications of trapdoor functions.
• A. Lavasani and T. Eghlidos. Practical Next Bit Test for Evaluating Pseudorandom Sequence
• Rafael Pass. Cryptography. Lections.