Фильтрующий и комбинирующий генераторы

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

Фильтрующие генераторы

Математической моделью фильтрующего генератора является автономный автомат А = (F", F_q, 6, f), вырабатывающий выходную гамму по закону:

где.

• • 5: F" —> F" - преобразование линейного регистра сдвига,
• • х — начальное состояние линейного регистра сдвига,
• • /: F" —> F_(/ — выходная функция (фильтр).

В качестве ключевых элементов фильтрующего генератора могут использоваться: начальное состояние линейного регистра сдвига, характеристический многочлен линейного регистра сдвига, выходная функция /.

Если используется линейный регистр сдвига максимального периода <7^Л — 1 и сбалансированная функция выхода /, то период выходной гаммы фильтрующего генератора будет также равен qⁿ — 1.

Кроме гарантированного периода выходная функция (фильтр) должна обеспечивать хорошие статистические качества выходных s-грамм, а также высокую линейную сложность. Напомним, что линейной сложностью периодической последовательности называется степень ее минимального многочлена.

Для двоичного случая (д — 2) известно, что верхней границей линейной сложности выходной последовательности фильтрующего генератора является величина.

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

Утверждение 6.12. Линейная сложность совпадает с размерностью векторного пространства, порожденного множеством всех функций на выходе фильтруюущего генератора.

'См. Bemasconi J., Gunther C.G. Analysis of a nonlinear feedforward logic for binary sequence generators // BBC Tech. Rep. — 19 859Rueppel R.A. Analysis and Design of Stream Ciphers. — Berlin: Springer. — 1986.

Доказательство. Если к — линейная сложность, то любая функция 7j = 7j (x) — /(<�Р^_1(ж)) при j > к над полем ?_q линейно выражается через начальные к функций 7i,…, 7fc. То есть размерность пространства на выходе фильтрующего генератора не более, чем к. С другой стороны, линейная сложность не может быть больше размерности пространства функций па выходе фильтрующего генератора. ?

Замечание. Из хода доказательства утверждения следует, что размерность пространства функций на выходе фильтрующего генератора равняется наибольшему натуральному числу к, при котором начальные к функций 71,…, 7& линейно независимы, а функция jk+i является их линейной комбинацией.

Пример 6.7. Найдем линейную сложность выходной последовательности двоичного фильтрующего генератора на основе линейного регистра сдвига длины п = 3 с обратной связью L (x) = xi+x₂ И фиЛЬТрОМ /(ж) — Х1Х2 + XX’t + Х2Х3.

Так как характеристический многочлен линейного регистра сдвига равен ж³ 4- x + 1 и является примитивным над F2, то период линейной рекуррентной последовательности максимален и равен 2³ — 1 = 7. В силу простоты числа 7 период фильтрующего генератора также равен 7.

Вычислим все функции.

на периоде фильтрующего генератора:

Примечание. При выводе указанных равенств мы пользуемся соотношением 7*(ж) = f (8‘~¹(x)) = 7j_i (<$(x)). Докажите это соотношение. Кроме того, убедитесь, что 78 = 77(8(х)) — 71.

Найдем максимальную линейно независимую подсистему (71,…, 7^) во множестве {71,…, 77}. Будем использовать следующий общий вид квадратичной функции от трех переменных (с условием </?(0) = 0):

Найдем ранг матрицы В, строки которой есть коэффициенты многочлена Жсгалкина соответствующих функций 71,…, 7е, поэтапно приводя ее к треугольному виду эквивалентными преобразованиями строк, сохраняющими ранг:

Таким образом, ранг матрицы В равен б и равен искомой линейной сложности, гак как следующая функция 77 будет линейно зависима от функций 71,76;

Упражнение 6.2.1. В условиях рассмотренного примера найти представление функции 77 через линейную комбинацию функций.

7i 1 • • •, 7б;