Регистр-1

Регистр-2

Регистр-3

Регистр-п

Объединяющая функция

Рис. 17-5. Комбинированные генераторы.

Каскад LFSR/FCSR с суммированием/четностью

По теории сложение с переносом разрушает алгебраические свойства LFSR, а XOR разрушает алгебраические свойства FCSR. Данный генератор объединяет эти идеи, используемые в перечисленных суммирующем генераторе LFSR/FCSR и генераторе четности LFSR/FCSR, с каскадом Голлманна.

Генератор представляет собой последовательность массивов регистров , тактирование каждого массива определяется выходом предыдущего массива. На 11-й показан один этап такого генератора. Тактируется первый массив LFSR, и результаты объединяются сложением с переносом . Если выход функции объединения равен 1, то тактируется следующий массив (из FCSR), и выход этих FCSR объединяется с выходом предыдущей функции объединения с помощью XOR. Если выход первой функции объединения равен 0, то массив FCSR не тактируется, и выход просто складывается с переносом, полученным на предыдущем этапе Если выход этой второй функции объединения равен 1, то тактируется третий массив (из LFSR), и т.д.

Рис. 17-6. Придуманный генератор.

Генератор использует много регистров: п*от, где n - количество этапов, а m - количество регистров на этапе. Я рекомендую n = 10 и m = 5.

Чередующиеся генераторы "стоп-пошел"

Эти генераторы использую FCSR вместо некоторых LFSR. Кроме того, операция XOR может быть заменена сложением с переносом (см. 10-й).

- Генератор "стоп-пошел" FCSR. Регистр-1, Регистр-2 и Регистр-3 - это FCSR. Объединяющая функция -

XOR.

- Генератор "стоп-пошел" FCSR/LFSR. Регистр-1 - FCSR, а Регистр-2 и Регистр-3 - LFSR. Объединяющая функция - сложение с переносом.

- Генератор "стоп-пошел" LFSR/FCSR. Регистр-1 - LFSR, а Регистр-2 и Регистр-3 - FCSR. Объединяющая функция - XOR.

Регистр-1

Регистр-2

Объединяющая функция

Регистр-3

Рис. 17-7. Чередующийся генератор "стоп-пошел"

Прореживаемые генераторы

Существует четыре основных типа генераторов, использующих FCSR:

- Прореживаемый генератор FCSR. Прореживаемый генератор с FCSR вместо LFSR.

- Прореживаемый генератор FCSR/LFSR. Прореживаемый генератор с LFSR, прореживающим FCSR.

- Прореживаемый генератор LFSR/FCSR. Прореживаемый генератор с FCSR, прореживающим LFSR.

- Самопрореживаемый генератор FCSR. Самопрореживаемый генератор с FCSR вместо LFSR.

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

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

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

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

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

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

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

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

I-<v>

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

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

На 8-й показан 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.].

17.7 Другие потоковые шифры

В литературе описывались и другие потоковые шифры . Вот некоторые из них. Генератор Плесса (Pless)

Этот генератор использует свойства J-K триггеров [1250]. Восемь LFSR управляют четырьмя J-K триггерами; каждый триггер нелинейно объединяет два LFSR. Чтобы избежать проблемы, что выход триггера определяет и источник, и значение следующего выходного бита, после тактирования четырех триггеров их в ы-ходы перемешиваются для получения окончательного потока ключей .

Этот алгоритм был криптоаналитически взломан с помощью вскрытия каждого триггера в отдельности