Сдвиговые регистры с нелинейной обратной связью

Нетрудно представить более сложную, чем используемая в LFSR или FCSR, последовательность обратной связи. Проблема в том, что не существует математического аппарата, позволяющего провести анализ таких последовательностей. Что-то получится, но кто знает что? Вот некоторые из проблем, связанных со сдвиговыми регистрами с нелинейной обратной связью.

— В выходной последовательности могут быть смещения, например, единиц может быть больше, чем нулей.

— Максимальный период последовательности может быть меньше, чем ожидалось.

— Период последовательности для различных начальных значений может быть различным.

— Последовательность какое-то время может выглядеть как случайная, а потом "скатываться" к единственному значению. (Это можно легко устранить, выполняя XOR крайнего правого бита с нелинейной функцией.)

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

В сдвиговом регистре с нелинейной обратной связью функция обратной связи может быть произвольной (например, как на).

Рис. 17-8. Сдвиговый регистр с нелинейной обратной связью (возможно небезопасный).

Рис. 17-9. 3-битовый сдвиговый регистр с нелинейной обратной связью.

На Рис. 17-9 показан 3-битовый генератор со следующей обратной связью: новым битом является произведение первого и второго битов. Если его проинициализировать значением 110, то последовательность внутренних состояний будет следующей:

1 1 0

0 1 1

1 0 1

0 1 0

0 0 1

0 0 0

0 0 0

И так до бесконечности. Выходом является последовательность младших значащих битов:

0 1 1 0 1 0 0 0 0 0 0 0....

Это не слишком полезно.

Может быть и хуже. Если начальное значение 100, то следующими состояниями являются 010, 001, а затем всегда 000. Если начальным значением является 111, то оно будет повторяться всегда и с самого начала.

Была проделана определенная работа по вычислению линейной сложности произведения двух LFSR [1650, 726, 1364, 630, 658, 659]. Конструкция, включающая вычисление LFSR над полем нечетных характеристик [310] не является безопасной [842.].