1.3.4 Покерный тест

В покерном тесте проверяемая псевдослучайная последовательность разбивается на блоки длиной бит. Этот тест, как и однобитный и двубитный, основан на том, что в идеальной случайной последовательности вероятность всех блоков одинакова. Пусть – число -битных пар блоков, двоичным представлением которых является число . Для подсчета в покерном тесте используется формула (1.5):

, (1.6)

где – суммарное число -битных блоков в исследуемой последовательности. Из соображений эффективности выберем равным степени двойки (в случае когда покерный тест переходит в монобитный). Поскольку имеет распределение с степенями свободы, нужно выбирать порог, равный 30,6. Эффективный алгоритм подсчета встречаемости различных блоков основан на использовании таблицы (использование таблицы целесообразно лишь при небольшом размере блоков, т.е. при ).

1.4 Основные свойства ЛРР и ЛРПМ (на периоде)

1. Функционирование ЛРР однозначно определяется используемым образующим полиномом f (t) :

f (t) = c _m  t ^m + c _m – 1  t ^m ‑ 1 + . . . + c ₂  t ² + c ₁  t ₁ + 1 ,     f (t)  Z ₂ [t ] . (1.7)

Здесь m  степень полинома (deg(f (t)));

c_i   коэффициенты c_i {0, 1}, c₀ = 1.

2. Период ЛРПМ (линейной рекуррентной последовательности максимального периода) T = 2 ^m – 1.

ЛРПМ может быть получена только при использовании примитивного образующего полинома f (t) . В противном случае период формируемой последовательности будет заведомо меньшим.

3. Расстояние единственности l ₀ = 2  m .

То есть закон функционирования ЛРР (вид образующего полинома) может быть однозначно восстановлен по 2m безошибочно полученным подряд расположенным битам ЛРПМ. Это и следующее (связанное с ним) свойство являются основными недостатками ЛРР, из – за которых они не могут использоваться в изолированном виде в качестве ГКП.

4. Структурная скрытность S_c = l ₀ / T = 2m / (2 ^m – 1 ) .

То есть структурная скрытность для ЛРР достаточно низкая  закон функционирования ЛРР легко раскрываем.

5. Количество нулей (на периоде ЛРПМ) на один меньше количества единиц: N₀ = 2 ^m – 1 – 1 и N₁ = 2 ^m – 1 соответственно.

6. Длина максимальной серии из единиц  m, из нулей  (m ‑ 1).

7. Свойства псевдослучайности:  из общего количества серий на периоде ЛРПМ

1 / 2 всех длин имеют длину 1;

1 / 4  длину 2;

     . . . 

1 / 2 ^k  длину k.

8. На периоде ЛРПМ по одному разу встречаются все m – разрядные комбинации от 1 до 2 ^m – 1  (свойство “окна”).

9. Количество изоморфизмов ЛРПМ N _И =  (T ) / m  (здесь  (T )  значение функции Эйлера) .

То есть для данной степени m существует N _И примитивных полиномов и, соответственно, N _И ЛРПМ, отличающихся тонкой структурой и не являющихся циклическими сдвигами друг относительно друга.

10. Сумма двух ЛРПМ, отличающихся только циклическим сдвигом, также является ЛРПМ, отличающейся от двух исходных только циклическим сдвигом.

То есть комбинирование (линейное) нескольких отрезков одной и той же ЛРПМ не дает увеличения структурной скрытности.

В качестве начального содержимого регистра  битов (S _m ‑ 1 , S _m ‑ 2 , …, S ₁ , S ₀ ) ₂  задается случайный (псевдослучайный) двоичный m ‑ разрядный вектор (запрещенной является только нулевая комбинация).

Бит обратной связи ЛРР (в соответствии с (1.7)) формируется согласно следующему соотношению:

_(1.8)

где S_j  содержимое ячеек регистра;

c_i  коэффициенты образующего полинома (причем c ₀ = 1).

При реализации программной модели комбинированного генератора с переменным шагом рекомендуется использовать образующие полиномы со степенями не менее m_i = 128. Причем степени образующих полиномов должны быть попарно взаимно простыми и выбираются близких размерностей.

При реализации программной модели генератора со сжатием рекомендуется использовать образующие полиномы со степенями не менее m_i = 64. Причем степени образующих полиномов должны быть взаимно простыми и выбираются близких размерностей.