0(t)

0A(t)

п-этапный LFSR-2

п-этапный LFSR-1

fe(t+n-1) I fe(t+n-2)

0(t)

0B(t)

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

Линейная сложность такой системы примерно равна ее периоду. Согласно [1638], "в такой системе не очевидная избыточность ключа не наблюдается".

Пороговый генератор

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

Этот генератор показан на 4-й. Возьмите выход большого числа LFSR (используя нечетное число регистров). Для получения максимального периода убедитесь, что длины всех LFSR взаимно просты, а многочлены обратной связи - примитивны.. Если более половины выходных битов LFSR - 1, то выходом генератора является 1. Если более половины выходных битов LFSR - 0, то выходом генератора является 0.

b(t)

Рис. 16-12. Пороговый генератор.

Для трех LFSR выход генератора можно представить как: b = (a1 л © (a1 л ® (a2 л

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

n1 n2 + n1 n3 + n2n3

где n1, n2 и n3 - длины первого, второго и третьего LFSR.

Этот генератор не слишком хорош. Каждый выходной бит дает некоторую информацию о состоянии LFSR -точнее 0.189 бита - и генератор в целом не может устоять перед корреляционным вскрытием . Я не советую использовать такой генератор.

Самопрореживающие (Self-Decimated) генераторы

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

0: Тактирование d раз 1: Тактирование k раз

V LFSR

b t)

Рис. 16-13. Самопрореживающий генератор Рюппела.

0: Тактирование d раз 1: Тактирование k раз

V LFSR

b t)

Рис. 16-14. Самопрореживающий генератор Чамберса и Голлмана.

Многоскоростной генератор с внутренним произведением (inner-product)

Этот генератор, предложенный Массеем (Massey) и Рюппелом [1014], использует два LFSR с разными тактовыми частотами (см. 1st). Тактовая частота LFSR-2 в d раз больше, чем у LFSR-l. Отдельные биты этих LFSR объединяются операцией AND, а затем для получения выходного бита генератора они объединяются посредс т-

вом XOR.

Ь /-этапный LFSR-1

1-Г\

b t)

*Ь n-этапный LFSR-2

Рис. 16-15. Многоскоростной генератор с внутренним произведением.

Хотя этот генератор обладает высокой линейной сложностью и великолепными статистическими характер и-стиками, он все же не может устоять перед вскрытием линейной согласованности [1639]. Если ni - длина LFSR-l, n2 - длина LFSR-2, а d - отношение тактовых частот, то внутреннее состояние генератора может быть получено по выходной последовательности длиной

n2+ n2 + log2d

Суммирующий генератор

Еще одно предложение Рэйнер Рюппела , этот генератор суммирует выходы двух LFSR (с переносом) [1358, 1357]. Это в высокой степени нелинейная операция. В конце 80-х этот генератор был лидером в отношении безопасности, но он пал перед корреляционным вскрытием [1053, 1054, 1091]. Кроме того, было показано, что этот генератор является частным случаем обратной связи, использующей сдвиговый регистр с переносом (см.

раздел 17.4), и может быть взломан [844].

DNRSG

Это означает "динамический генератор случайной последовательности" ("dynamic random-sequence generator") [1117]. Идея состоит в том, чтобы взять два различных фильтруемых генератора - пороговых, суммиру ю-щих, и т.п. - использующих один набор LFSR, а управляемых другим LFSR.

Сначала тактируются все LFSR. Если выходом LFSR-0 является 1, то вычисляется выход первого фильтрующего генератора. Если выходом LFSR-0 является 0, то вычисляется выход второго фильтрующего генератора. Окончательным результатом является XOR выходов первого и второго генераторов.

Каскад Голлманна

Каскад Голлманна (см. 0-й), описанный в [636, 309], представляет собой усиленную версию генератора "стоп-пошел". Он состоит из последовательности LFSR, тактирование каждого из которых управляется предыдущим LFSR. Если выходом LFSR-l в момент времени t является 1, то тактируется LFSR-2. Если выходом LFSR-2 в момент времени t является 1, то тактируется LFSR-3, и так далее. Выход последнего LFSR и является выходом генератора. Если длина всех LFSR одинакова и равна n, линейная сложность системы из k LFSR равна

/n 1 \k-1

n(2 - 1)

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

Это дерзкая идея: концептуально они очень просты и могут быть использованы для генерации последов а-тельностей с огромными периодами, огромными линейными сложностями и хорошими статистическими сво й-ствами. Они чувствительны к вскрытию, называемому запиранием (lock-in) [640] и представляющему метод, с помощью которого сначала криптоаналитик восстанавливает вход последнего сдвигового регистра в каскаде , а затем взламывает весь каскад, регистр за регистром . В некоторых случаях это представляет собой серьезную проблему и уменьшает эффективную длину ключа алгоритма, но для минимизации возможности такого вскрытия можно предпринять ряд определенных мер.

Дальнейший анализ показал, что с ростом k последовательность приближается к случайной 639]. На основании недавних вскрытий коротких каскадов Голлманна [1063], я советую меньше 15. Лучше использовать больше коротких LFSR, чем меньше длинных LFSR.

[637, 638, 642, k

использовать

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

Прореживаемый (shrinking) генератор [378] использует другую форму управления тактированием. Возьмем два LFSR: LFSR-l и LFSR -2. Подадим тактовый импульс на оба регистра. Если выходом LFSR-l является 1, то выходом генератора является выход LFSR-2. Если выход LFSR-l равен 0, оба бита сбрасываются, LFSR тактируются заново и все повторяется.

Идея проста, достаточно эффективна и кажется безопасной . Если многочлены обратной связи прорежены, генератор чувствителен к вскрытию, но других проблем обнаружено не было . Хотя этот тип генератора достаточно нов. Одна из проблем реализации состоит в том, что скорость выдачи результата не постоянна, если LFSR-l генерирует длинную последовательность нулей, то на выходе генератора ничего нет . Для решения этой проблемы авторы предлагают использовать буферизацию [378]. Практическая реализация прореживаемого генератора рассматривается в [901].

Самопрореживаемый генератор

Самопрореживаемый (self-shrinking) генератор [1050] является вариантом прореживаемого генератора. Вместо двух LFSR используется пара битов одного LFSR. Протактируйте LFSR дважды. Если первым битом пары будет 1, то второй бит будет выходом генератора . Если первый бит - 0, сбросьте оба бита и попробуйте снова. Хотя для самопрореживаемого генератора нужно примерно в два раза меньше памяти, чем для прореживаем о-