Схемы с динамическим изменением закона рекурсии

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

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

Один из путей построения подобных схем основан на динамическом изменении закона рекурсии линейного регистра сдвига.

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

Рассмотрим два многочлена А(х)=х^т + åа_jх^j, В(х) =х^т + å b_k х^k степени т и последовательность v, удовлетворяющую условиям:

Ясно, что в четных тактах закон рекурсии последовательности v определяется характеристическим многочленом А(х), а в нечетных тактах – характеристическим многочленом В(х).

Образуем многочлены A⁽⁰⁾(x), A⁽¹⁾(x), B⁽⁰⁾(x), B⁽¹⁾(x) следующим образом:

Несложно проверить, что получаемая в результате последовательность v является линейной рекуррентной последовательностью с характеристическим многочленом

Н(x)=A⁽¹⁾(x)B⁽¹⁾(х) – A⁽⁰⁾(x)B⁽⁰⁾(x).

К классу операторов с динамическим изменением закона рекурсии относятся также линейные регистры сдвига с неравномерным движением информации. Так называются регистры, для которых число тактов работы до получения (i+1)-го знака выходной последовательности зависит либо от значения числа i, либо от состояния регистра в такте i. Получаемая в результате последовательность будет некоторой выборкой с переменным шагом из исходной ЛРП, вырабатываемой линейным регистром сдвига.

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

Теорема 5. Пусть d₀,...,d_{t –1} – набор из t > 1 чисел множества 0,…,qⁿ – 2 и

Пусть при i= k×t + r элементы последовательности v задаются

формулой

где с – нулевой, а q — примитивный элементы поля GF(qⁿ). Пусть, кроме того, простые делители числа t делят , но не делят (qⁿ –1,D).

Пусть, наконец, qⁿ º 1(тоd 4), если t кратно четырем. Тогда минимальный многочлен М_v(х) последовательности v имеет вид М_v(х)=Р(х^t), где Р(х) –минимальный многочлен элемента q ^D.