11. Применение линейных рекуррентных регистров для потокового шифрования

Однако использовать ЛРР непосредственно в качестве датчика гаммы (рис. 15) в потоковом шифраторе нельзя, поскольку ЛРР обладает следующим свойством: если известна выходная последовательность ЛРР длиной всего лишь 2n,то можно вычислить как начальное заполнение, так и полином обратной связи однозначно, причем сложность решения этой задачи имеет порядок

Рис. 15. К обсуждению применимости ЛРР для потокового шифрования

O(n³), т.е. требует примерноn³операций. Данное свойство является непосредственным следствием линейности ЛРР. Оно позволяет свести решение задачи криптоанализа к решению системы линейных уравнений.

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