Потоковые шифры на базе LFSR

Основной подход при проектировании генератора потока ключей на базе LFSR прост. Сначала берется один или несколько LFSR, обычно с различными длинами и различными многочленами обратной связи . (Если длины взаимно просты, а все многочлены обратной связи примитивны, то у образованного генератора будет макс и-мальная длина.) Ключ является начальным состоянием регистров LFSR. Каждый раз, когда необходим новый бит, сдвиньте на бит регистры LFSR (это иногда называют тактированием (clocking)). Бит выхода представляет собой функцию, желательно нелинейную, некоторых битов регистров LFSR. Эта функция называется комбинирующей функцией, а генератор в целом - комбинационным генератором (Если бит выхода является функцией единственного LFSR, то генератор называется фильтрующим генератором) Большая часть теории подобного рода устройств разработана Селмером (Selmer) и Нилом Цирлером (Neal Zierler) .
Можно ввести ряд усложнений. В некоторых генераторах для различных LFSR используется различная тактовая частота, иногда частота одного генератора зависит от выхода другого . Все это электронные версии идей шифровальных машин, появившихся до Второй мировой войны, которые называются генераторами с управлением тактовой частотой (clock-controlled genelators) . Управление тактовой частотой может быть с прямой связью, когда выход одного LFSR управляет тактовой частотой другого LFSR, или с обратной связью, когда выход одного LFSR управляет его собственной тактовой частотой.
Хотя все эти генераторы чувствительны, по крайней мере теоретически, к вскрытиям вложением и вероятной корреляцией, многие из них безопасны до сих пор. 
Ян Касселлс (Ian Cassells), ранее возглавлявший кафедру чистой математики в Кембридже и работавший криптоаналитиком в Bletchly Park, сказал, что "криптография - это смесь математики и путаницы, и без путаницы математика может быть использована против вас." Он имел в виду, что в потоковых шифрах для обеспеч е-ния максимальной длины и других свойств необходимы определенные математические структуры, такие как LFSR, но, чтобы помешать кому-то получить содержание регистра и вскрыть алгоритм, необходимо внести некоторый сложный нелинейный беспорядок. Этот совет справедлив и для блочных алгоритмов.
Поэтому не стоит серьезно увлекаться генераторами потока ключей на базе LFSR, описания которых появились в литературе. Я не знаю, используется ли хоть один из них в реальных криптографических продуктах. Большей частью они представляют лишь теоретический интерес . Некоторые были взломаны, некоторые могли остаться безопасными.
Так как шифры на базе LFSR обычно реализуются аппаратно, на рисунках используются символы электронной логики. 
Генератор Геффа
В этом генераторе потока ключей используются три LFSR, объединенные нелинейным образом. Два LFSR являются входами мультиплексора, а третий LFSR управляет выходом мультиплексора. Если а\, U2 и аз - выходы трех LFSR, выход генератора Геффа (Geffe) можно описать как:

Рис. 16-6. Генератор Геффа.
Если длины LFSR равны n1, n2 и n3, соответственно, то линейная сложность генератора равна

Период генератора равен наименьшему общему делителю периодов трех генераторов. При условии, что степени трех примитивных многочленов обратной связи взаимно просты, период этого генератора будет равен произведению периодов трех LFSR.
Хотя этот генератор неплохо выглядит на бумаге, он криптографически слаб и не может устоять против корреляционного вскрытия . В 75 процентах времени выход генератора равен выходу LFSR-2. Поэтому, если известны отводные последовательности обратной связи, можно догадаться о начальном значении LFSR-2 и сгенерировать выходную последовательность этого регистра. Тогда можно подсчитать, сколько раз выход LFSR совпадает с выходом генератора. Если начальное значение определено неверно, две последовательности будут согласовываться в 50 процентах времени, а если правильно, то в 75 процентах времени.
Аналогично, выход генератора равен выходу LFSR в 75 процентах времени. С такими корреляциями генератор потока ключей может быть легко взломан. Например, если примитивные многочлены состоят только из трех членов, и длина самого большого LFSR равна n, для восстановления внутренних состояний всех трех LFSR нужен фрагмент выходной последовательности длиной 37n битов.
Обобщенный генератор Геффа
Вместо выбора между двумя LFSR в этой схеме выбирается один из k LFSR, где k является степенью 2. Всего используется k + 1 LFSR. Тактовая частота LFSR-1 должна быть в Iog2 k раз выше, чем у остальных k LFSR.

Рис. 16-7. Обобщенный генератор Геффа.
Несмотря на то, что эта схема сложнее генератора Геффа, для взлома можно использовать то же корреляционное вскрытие. Не рекомендую этот генератор.
Генератор Дженнингса

Рис. 16-8. Генератор Дженнингса.
Ключом является начальное состояние двух LFSR и функции отображения. Хотя у этого генератора замечательные статистические свойства, он пал перед выполненным Россом Андерсоном (Ross Anderson) вскрытием корректности встречей посередине и вскрытием линейной корректности. Не используйте этот генератор.
Генератор "стоп-пошел " (Stop-and-Go) Both-Piper
Этот генератор, использует выход одного LFSR для управления тактовой частотой другого LFSR [151]. Тактовый вход LFSR-2 управляется выходом LFSR-1, так что LFSR-2 может изменять свое состояние в момент времени t только, если выход LFSR-1 в момент времени t - 1 был равен 1.

Рис. 16-9. Генератор "стоп-пошел" Beth-Piper.
Никому не удалось привести для общего случая достоверные данные о линейной сложности этого генератора. Однако он не устоял перед корреляционным вскрытием .
Чередующийся генератор "стоп-пошел "
В этом генераторе используются три LFSR различной длины. LFSR-2 тактируется, когда выход LFSR-1 равен 1, LFSR-3 тактируется, когда выход LFSR-1 равен 0. Выходом генератора является XOR LFSR-2 и LFSR-3.

Рис. 16-10. Чередующийся генератор "стоп-пошел"
У этого генератора большой период и большая линейная сложность. Авторы показали способ корреляциюнного вскрытия LFSR-1, но это не сильно ослабляет генератор. Были предложены и другие генераторы такого типа .
Двусторонний генератор "стоп-пошел "
В этом генераторе используется два LFSR с одинаковой длиной n. Выходом генератора является XOR выходов каждого LFSR. Если выход LFSR-1 в момент времени t-1 равен 0, а в момент времени t-2 - 1, то LFSR-2 не тактируется в момент времени t. Наоборот, если выход LFSR-2 в момент времени t-1 равен О, а в момент времени t-2 - 1, и если LFSR-2 тактируется в момент времени t, то LFSR-1 не тактируется в момент времени t.

Рис. 16-11. Двусторонний генератор "стоп-пошел".
Линейная сложность такой системы примерно равна ее периоду  "в такой системе не очевидная избыточность ключа не наблюдается".
Пороговый генератор
Этот генератор пытается обойти проблемы безопасности, характерные для предыдущих генераторов, с помощью переменного числа LFSR [277]. По теории при использовании большего количества LFSR вскрыть шифр сложнее.
 Возьмите выход большого числа LFSR (используя нечетное число регистров). Для получения максимального периода убедитесь, что длины всех LFSR взаимно просты, а многочлены обратной связи - примитивны.. Если более половины выходных битов LFSR - 1, то выходом генератора является 1. Если более половины выходных битов LFSR - 0, то выходом генератора является 0.

Рис. 16-12. Пороговый генератор.
Для трех LFSR выход генератора можно представить как:

Это очень похоже на генератор Геффа за исключением того, что пороговый генератор обладает большей линейной сложностью

Этот генератор не слишком хорош. Каждый выходной бит дает некоторую информацию о состоянии LFSR -точнее 0.189 бита - и генератор в целом не может устоять перед корреляционным вскрытием . Я не советую использовать такой генератор.
Самопрореживающие (Self-Decimated) генераторы
Самопрореживающими называются генераторы, которые управляют собственной тактовой частотой . Было предложено два типа таких генераторов, один Рэйнером Рюппелом (Ranier Rueppel) другой Биллом Чамберсом (Bill Chambers) и Дитером Коллманом (Dieter Collmann) [308]. В генераторе Рюп-пела если выход LFSR равен О, LFSR тактируется d раз. Если выход LFSR равен О, LFSR тактируется k раз. Генератор Чамберса и Коллмана сложнее, но идея остается той же. К сожалению оба генератора не безопасны, хотя был предложен ряд модификаций, которые могут исправить встречающиеся проблемы.

Рис. 16-14. Самопрореживающий генератор Чамберса и Голлмана.
Многоскоростной генератор с внутренним произведением (inner-product)
Этот генератор, предложенный Массеем (Massey) и Рюппелом , использует два LFSR с разными тактовыми частотами . Тактовая частота LFSR-2 в d раз больше, чем у LFSR-1. Отдельные биты этих LFSR объединяются операцией AND, а затем для получения выходного бита генератора они объединяются посредством XOR.

Рис. 16-15. Многоскоростной генератор с внутренним произведением.
Хотя этот генератор обладает высокой линейной сложностью и великолепными статистическими характеристиками, он все же не может устоять перед вскрытием линейной согласованности [1639]. Если n1 - длина LFSR-1, n2 - длина LFSR-2, a d - отношение тактовых частот, то внутреннее состояние генератора может быть получено по выходной последовательности длиной

Суммирующий генератор
Еще одно предложение Рэйнер Рюппела, этот генератор суммирует выходы двух LFSR (с переносом). Это в высокой степени нелинейная операция. В конце 80-х этот генератор был лидером в отношении безопасности, но он пал перед корреляционным вскрытием . Кроме того, было показано, что этот генератор является частным случаем обратной связи, использующей сдвиговый регистр с переносом, и может быть взломан.
DNRSG
Это означает "динамический генератор случайной последовательности" ("dynamic random-sequence generator"). Идея состоит в том, чтобы взять два различных фильтруемых генератора - пороговых, суммирующих, и т.п. - использующих один набор LFSR, а управляемых другим LFSR.
Сначала тактируются все LFSR. Если выходом LFSR-0 является 1, то вычисляется выход первого фильтрующего генератора. Если выходом LFSR-0 является 0, то вычисляется выход второго фильтрующего генератора. Окончательным результатом является XOR выходов первого и второго генераторов.
Каскад Голлманна
Каскад Голлманна, представляет собой усиленную версию генератора "стоп-пошел". Он состоит из последовательности LFSR, тактирование каждого из которых управляется предыдущим LFSR. Если выходом LFSR-1 в момент времени t является 1, то тактируется LFSR-2. Если выходом LFSR-2 в момент времени t является 1, то 

Рис. 16-16. Каскад Голлманна.

тактируется LFSR-3, и так далее. Выход последнего LFSR и является выходом генератора. Если длина всех LFSR одинакова и равна n, линейная сложность системы из k LFSR равна
Это дерзкая идея: концептуально они очень просты и могут быть использованы для генерации последовательностей с огромными периодами, огромными линейными сложностями и хорошими статистическими свойствами. Они чувствительны к вскрытию, называемому запиранием (lock-in)] и представляющему метод, с помощью которого сначала криптоаналитик восстанавливает вход последнего сдвигового регистра в каскаде , а затем взламывает весь каскад, регистр за регистром. В некоторых случаях это представляет собой серьезную проблему и уменьшает эффективную длину ключа алгоритма, но для минимизации возможности такого вскрытия можно предпринять ряд определенных мер.
Дальнейший анализ показал, что с ростом k последовательность приближается к случайной. На основании недавних вскрытий коротких каскадов Голлманна, я советую использовать k не меньше 15. Лучше использовать больше коротких LFSR, чем меньше длинных LFSR.
Прореживаемый генератор
Прореживаемый (shrinking) генератор использует другую форму управления тактированием. Возьмем два LFSR: LFSR-1 и LFSR -2. Подадим тактовый импульс на оба регистра. Если выходом LFSR-1 является 1, то выходом генератора является выход LFSR-2. Если выход LFSR-1 равен 0, оба бита сбрасываются, LFSR тактируются заново и все повторяется.
Идея проста, достаточно эффективна и кажется безопасной. Если многочлены обратной связи прорежены, генератор чувствителен к вскрытию, но других проблем обнаружено не было . Хотя этот тип генератора достаточно нов. Одна из проблем реализации состоит в том, что скорость выдачи результата не постоянна, если LFSR-1 генерирует длинную последовательность нулей, то на выходе генератора ничего нет . Для решения этой проблемы авторы предлагают использовать буферизацию
Самопрореживаемый генератор
Самопрореживаемый (self-shrinking) генератор является вариантом прореживаемого генератора. Вместо двух LFSR используется пара битов одного LFSR. Протактируйте LFSR дважды. Если первым битом пары будет 1, то второй бит будет выходом генератора. Если первый бит - 0, сбросьте оба бита и попробуйте снова. Хотя для самопрореживаемого генератора нужно примерно в два раза меньше памяти, чем для прореживаемого, он работает в два раза медленнее.
Хотя самопрореживаемый генератор также кажется безопасным, он может вести себя непредсказуемым образом и обладать неизвестными свойствами. Это очень новый генератор, дайте ему немного времени.