Статистические тесты

Генерация псевдослучайных битов

Генератор псевдослучайных битов (ГПСБ) – это детерминированный алгоритм, преобразующий случайную двоичную последовательность длины k в двоичную последовательность длины l>k, выглядящую случайной.

Так как выходная последовательность полностью определяется входом, то она может принимать 2^k значений.

Требования к ГПСБ:

1. Длина k входа случайной последовательности должна обеспечивать достаточную для криптосистемы сложность перебора, 2^k должно быть достаточно большим.

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

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

Если первые l битов известны, то l+1 предсказать нельзя.

Есть некторая последовательность длины n. Существует гипотеза о том, что последовательность случайная.

Есть параметр L, который называется уровень доверия (значимости).

Если значение L велико, то можно откинуть истинную гипотезу «Последовательность случайная». В таком случае это будет ошибка первого рода.

Если значение L мало, то можно принять ложную гипотезу «Последовательность неслучайная». В этом случае будет ошибка второго рода.

Параметр L принадлежит интервалу [10^-3; 0,05].

В результате теста получается значение x*.

x_L – табличное значение для выбранного L.

Если x*> x_L, то x* не принимается.

Использование:

1. Нормальное распределение

N(0,1) – нормально

2. χ² - распределение

Имеет параметр v – степень свободы.

Рассмотрим 5 тестов:

1. частотный

Основан на положении, что в последовательности должно быть приблизительно одинаковое количество нулей и единиц.

n₀ – число нулей,

n₁ – число единиц.

Для случайной последовательности эта величина должна удовлетворять критерию χ² с

v=1 при n.

2. двухбитный тест

Эта величина должна удовлетворять критерию χ² с v=2 при n.

3. покер-тест

Пусть

| |

k

Делим последовательность на отрезки длины m, n_i - количество раз, которое встретился отрезок типа i,.

Статистика для случайной последовательности должна выглядеть следующим образом:

, k должно удовлетворять χ² с v=2^m – 1.

4. тест непрерывной серии

Серия состоит из последовательности только из нулей или только из единиц.

Количество этих серий сравнивается с нужным для случайной последовательности. Тест должен удовлетворять χ² с 2k-2, где k - длина серии.

5. тест автокорреляций

Рассматривается последовательность длины n. Сдвигаем ее и сравниваем совпадающие разряды.

Имеет смысл сдвигать на .

Пусть A(d) - количество битов, котоыре не совпали.

Должен удовлетворять нормальному распределению N(0,1)

Нас не устраиваются не очень большие A(d), не очень маленькие.