цифических условиях [597, 595, 596, 1333]. Обобщение понятия линейной сложности выполнено в [776]. Существую также понятия сферической и квадратичной сложности [844].

В любом случае помните, что высокая линейная сложность не обязательно гарантирует безопасность генер а-тора, но низкая линейная сложность указывает на недостаточную безопасность генератора [1357, 12.49].

Корреляционная независимость

Криптографы пытаются получить высокую линейную сложность, нелинейно объединяя результаты некот о-рых выходных последовательностей . При этом опасность состоит в том, что одна или несколько внутренних выходных последовательностей - часто просто выходы отдельных LFSR - могут быть связаны общим ключевым потоком и вскрыты при помощи линейной алгебры. Часто такое вскрытие называют корреляционным вскрытием или вскрытием разделяй-и-властвуй. Томас Сигенталер (Thomas Siegenthaler) показал, что можно точно определить корреляционную независимость, и что существует компромисс между корреляционной независ и-мостью и линейной сложностью [1450].

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

Против многих генераторов потоков ключей на базе LFSR успешно использовались корреляционные вскр ы-тия и их вариации, такие как быстрые корреляционные вскрытия, предлагающие компромисс между вычисл и-тельной сложностью и эффективностью [1451, 278, 1452, 572, 1636, 1051, 1090, 350, 633, 1054, 1089, 995]. Ряд интересных новых идей в этой области можно найти в [46, 1641].

Другие вскрытия

Существуют и другие способы вскрытия генераторов потоков ключей . Тест на линейную корректность (linear consistency) пытается найти некоторое подмножество ключа шифрования с помощью матричной техники [1638]. Существует и вскрытие корректности "встречей посередине" (meet-in-the-middle consistency attack) [39, 41]. Алгоритм линейного синдрома (linear syndrome algorithm) основан на возможности записать фрагмент выходной последовательности в виде линейного уравнения [1636, 1637]. Существует вскрытие лучшим аффинным приближением (best afflne approximation attack) [502] и вскрытие выведенным предложением (derived sequence attack) [42]. К потоковым шифрам можно применить также методы дифференциального [501] и линейного [631] криптоанализа.

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

Основной подход при проектировании генератора потока ключей на базе LFSR прост. Сначала берется один или несколько LFSR, обычно с различными длинами и различными многочленами обратной связи . (Если длины взаимно просты, а все многочлены обратной связи примитивны, то у образованного генератора будет макс и-мальная длина.) Ключ является начальным состоянием регистров LFSR. Каждый раз, когда необходим новый бит, сдвиньте на бит регистры LFSR (это иногда называют тактированием (clocking)). Бит выхода представляет собой функцию, желательно нелинейную, некоторых битов регистров LFSR. Эта функция называется комбинирующей функцией, а генератор в целом - комбинационным генератором. (Если бит выхода является функцией единственного LFSR, то генератор называется фильтрующим генератором.) Большая часть теории подобного рода устройств разработана Селмером (Selmer) и Нилом Цирлером (Neal Zierler) [1647].

Можно ввести ряд усложнений. В некоторых генераторах для различных LFSR используется различная тактовая частота, иногда частота одного генератора зависит от выхода другого . Все это электронные версии идей шифровальных машин, появившихся до Второй мировой войны, которые называются генераторами с управлением тактовой частотой (clock-controlled genelators) [641]. Управление тактовой частотой может быть с прямой связью, когда выход одного LFSR управляет тактовой частотой другого LFSR, или с обратной связью, когда выход одного LFSR управляет его собственной тактовой частотой.

Хотя все эти генераторы чувствительны, по крайней мере теоретически, к вскрытиям вложением и вероятной корреляцией [634, 632], многие из них безопасны до сих пор. Дополнительную теорию сдвиговых регистров с управляемой тактовой частотой можно найти в [89].

Ян Касселлс (Ian Cassells), ранее возглавлявший кафедру чистой математики в Кембридже и работавший криптоаналитиком в Bletchly Park, сказал, что "криптография - это смесь математики и путаницы, и без путаницы математика может быть использована против вас." Он имел в виду, что в потоковых шифрах для обеспеч е-ния максимальной длины и других свойств необходимы определенные математические структуры, такие как LFSR, но, чтобы помешать кому-то получить содержание регистра и вскрыть алгоритм, необходимо внести н е-который сложный нелинейный беспорядок . Этот совет справедлив и для блочных алгоритмов .

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

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

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

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

b = (a1 л a2) ©((-a1) л a3)

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

-+ b(t)

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

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

(П1 + 1) П2 + П1П3,

Период генератора равен наименьшему общему делителю периодов трех генераторов . При условии, что степени трех примитивных многочленов обратной связи взаимно просты, период этого генератора будет равен произведению периодов трех 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

> b(t)

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

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

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

В этой схеме мультиплексор исльзутся для объединения двух LFSR [778, 779, 780]. Мультиплексор,

ного выходного бита. Кроме того, используется

функцияТ котор

управляемый LFSR<-I. вы дбирает 1 бит LFSR-2 в качестве оторая отображает выход LF

ает выход LFSR-2 на вхо

Тактирован

.сора (см. 8tb).

> 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.