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

Так как шифры на базе LFSR обычно реализуются аппаратно, на рисунках используются символы электронной логики. В тексте, е означает XOR, л - AND, v - OR, и - - NOT.

Генератор Геффа

В этом генераторе потока ключей используются три LFSR, объединенные нелинейным образом (см. 10th) [606]. Два LFSR являются входами мультиплексора, а третий LFSR управляет выходом мультиплексора. Если a1, a2 и a3 - выходы трех LFSR, выход генератора Геффа (Geffe) можно описать как:

b = (a1 л е((-«1) л аз)

Мультиплексор 2 в 1

LFSR-2

LFSR-3

Выбор

-•► bit)

LFSR-1

Рис. 16-6. Генератор Геффа.

Если длины LFSR равны n1, n2 и n3, соответственно, то линейная сложность генератора равна

(n1 + 1) n2 + n1n3,

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

Хотя этот генератор неплохо выглядит на бумаге , он криптографически слаб и не может устоять против ко р-реляционного вскрытия [829, 1638]. В 75 процентах времени выход генератора равен выходу LFSR-2. Поэтому, если известны отводные последовательности обратной связи , можно догадаться о начальном значении LFSR-2 и сгенерировать выходную последовательность этого регистра . Тогда можно подсчитать, сколько раз выход LFSR совпадает с выходом генератора. Если начальное значение определено неверно, две последовательности будут согласовываться в 50 процентах времени, а если правильно, то в 75 процентах времени .

Аналогично, выход генератора равен выходу LFSR в 75 процентах времени. С такими корреляциями генератор потока ключей может быть легко взломан . Например, если примитивные многочлены состоят только из трех членов, и длина самого большого LFSR равна n, для восстановления внутренних состояний всех трех LFSR нужен фрагмент выходной последовательности длиной 37n битов [1639].

Обобщенный генератор Геффа

Вместо выбора между двумя LFSR в этой схеме выбирается один из k LFSR, где k является степенью 2. Всего используется k + 1 LFSR (см. 9th). Тактовая частота LFSR-l должна быть в log2 k раз выше, чем у остальных k LFSR.

LFSR-n+1

LFSR-3

LFSR-2

LFSR-1

> b(t)

Рис. 16-7. Обобщенный генератор Геффа.

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

Генератор Дженнингса

IравлFеSfЫ-й1

функция, которая отображает выход L

В этой схеме мультиплексор иCПOSЬЗуTся объединения двух LFSR [778, 779, 780]. Мультиплексор, FSR. выбирает 1 бит LFSR-2 в качестве>лчередного выходного бита. Кроме того, используется

SR-2 на вход мультиплексора (см. 8th).

Тактирован

LFSR-1

LFSR-3

LFSR-2

> b(t)

Рис. 16-8. Генератор Дженнингса.

Ключом является начальное состояние двух LFSR и функции отображения. Хотя у этого генератора замечательные статистические свойства, он пал перед выполненным Россом Андерсоном (Ross Anderson) вскрытием корректности встречей посередине [39] и вскрытием линейной корректности [1638,442]. Не используйте этот генератор.

Генератор "стоп-пошел" (Stop-and-Go) Both-Piper

Этот генератор, показанный на 7th, использует выход одного LFSR для управления тактовой частотой другого LFSR [151]. Тактовый вход LFSR-2 управляется выходом LFSR-l, так что LFSR-2 может изменять свое состояние в момент времени t только, если выход LFSR-l в момент времени t - 1 был равен 1.

LFSR-1

Тактирование

LFSR-2

a2(t)

LFSR-3

Рис. 16-9. Генератор "стоп-пошел" Beth-Piper.

Никому не удалось привести для общего случая достоверные данные о линейной сложности этого генератора. Однако он не устоял перед корреляционным вскрытием [1639].

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

В этом генераторе используются три LFSR различной длины. LFSR-2 тактируется, когда выход LFSR-l равен 1, LFSR-3 тактируется, когда выход LFSR-l равен 0. Выходом генератора является XOR LFSR-2 и LFSR-3 (см. Рис. 16.10) [673].

LFSR-1

,aiit) Г\

LFSR-2

LFSR-3

bit)

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

У этого генератора большой период и большая линейная сложность . Авторы показали способ корреляцио н-ного вскрытия LFSR-1, но это не сильно ослабляет генератор. Были предложены и другие генераторы такого типа [1534, 1574, 1477].

Двусторонний генератор "стоп-пошел"

В этом генераторе используется два LFSR с одинаковой длиной n (см. Рис. 16.11) [1638]. Выходом генератора является XOR выходов каждого LFSR. Если выход LFSR-l в момент времени t-1 равен 0, а в момент времени t-2 - 1, то LFSR-2 не тактируется в момент времени t. Наоборот, если выход LFSR-2 в момент времени t-1 равен 0, а в момент времени t-2 - 1, и если LFSR-2 тактируется в момент времени t, то LFSR-l не тактируется в момент времени t.