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

Это означает "динамический генератор случайной последовательности" ("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 равна

tn л \k-1

n(2 - 1)

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

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

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

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

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

го, он работает в два раза медленнее .

Хотя самопрореживаемый генератор также кажется безопасным, он может вести себя непредсказуемым о б-разом и обладать неизвестными свойствами . Это очень новый генератор, дайте ему немного времени .

16.5 A5

A5 - это потоковый шифр, используемый для шифрования GSM (Group Special Mobile). Это европейский стандарт для цифровых сотовых мобильных телефонов. Он используется для шифрования канала "телефон-базовая станция". Оставшаяся часть канала не шифруется, телефонная компания может легко сделать что-нибудь с вашими разговорами.

Вокруг этого протокола ведутся странные политические игры. Первоначально предполагалось, что крипт о-графия GSM позволит запретить экспорт телефонов в некоторые страны . Теперь ряд чиновников обсуждает, не повредит ли A5 экспортным продажам несмотря на то, что он так слаб, что вряд ли сможет служить препятс т-вием. По слухам в середине 80-х различные секретные службы НАТО сцепились по вопросу, должно ли шифр о-вание GSM быть сильным или слабым. Немцам была нужна сильная криптография, так как рядом с ними нах о-дился Советский Союз. Взяла верх другая точка зрения, и A5 представляет собой французскую разработку.

Большинство деталей нам известно. Британская телефонная компания передала всю документацию Брэ д-фордскому университету (Bradford University), не заставив подписать соглашение о неразглашении. Информация где-то просочилась и наконец была опубликована в Internet. A5 описывается в [1622], также в конце этой книги приведен код этого протокола.

A5 состоит из трех LFSR длиной 19, 22 и 23, все многочлены обратной связи - прорежены. Выходом является XOR трех LFSR. В A5 используется изменяемое управление тактированием . Каждый регистр тактируется в зависимости от своего среднего бита, затем выполняется XOR с обратной пороговой функцией средних битов всех трех регистров. Обычно на каждом этапе тактируется два LFSR.

Существует тривиальное вскрытие, требующее 2 40 шифрований: предположите содержание первых двух LFSR и попытайтесь определить третий LFSR по потоку ключей. (Действительно ли такой способ вскрытия возможен, остается под вопросом, который скоро будет разрешен разрабатываемой машиной для аппаратного поиска ключей [45].)

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

16.6 Hughes XPD/KPD

Этот алгоритм был предложен Hughes Aircraft Corp. Эта фирма встроила его в армейские тактические рации и оборудование поиска направления для продажи за границу. Алгоритм был разработан в 1986 году и получил название XPD, сокращение от Exportable Protection Device - Экспортируемое устройство защиты. Позднее он был переименован в KPD - Устройство кинетической защиты - и рассекречен [1037, 1036].

Алгоритм использует 61-битовый LFSR. Существует 210 различных примитивных многочлена обратной связи, одобренных NSA. Ключ выбирает один из этих многочленов (хранящихся где-то в ПЗУ), а также начальное состояние LFSR.

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

Этот алгоритм выглядит очень привлекательно, но у меня есть определенные сомнения . NSA разрешило его экспорт, следовательно должен быть способ вскрытия порядка, не большего чем 2 40. Но какой?

16.7 Nanoteq

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

Более или менее этот алгоритм описан в [902, 903]. Он использует 127-битовый LFSR с фиксированным многочленом обратной связи, ключ представляет собой начальное состояние регистра . При помощи 25 элементарных ячеек 127 битов регистра превращаются в один бит потока ключей . У каждой ячейки 5 входов и один выход:

f(xl, x2, x3, x4, x5) = xl + x2 + (xl + x3) (x2+ x4 + x5) + (xl + x4) (x2 + x3) + x5

Каждый выход функции подвергается операции XOR с некоторым битом ключа. Кроме того, существует секретная перестановка, зависящая от конкретной реализации и не описанная в статьях подробно . Этот алгоритм доступен только в аппаратном виде .

Безопасен ли он? Я не уверен. Ряд интересных факсов, передаваемых между полицейскими участками, ин о-гда появлялся в либеральных газетах. Это вполне могло быть результатом американской, английской или сове т-ской разведывательной деятельности. Росс Андерсон (Ross Anderson) предпринял ряд первых шагов, крипто анализируя этот алгоритм в [46], я думаю, что скоро появятся новые результаты.

16.8 Rambutan

Rambutan - это английский алгоритм, разработанный Communications Electronics Security Croup (Группа по безопасности электронных коммуникаций, одно из объединений, использованное CCHQ). Он продается только в виде аппаратного модуля и одобрен для защиты документов вплоть до грифа "Конфиденциально" . Сам алгоритм засекречен, и микросхема не предназначена для широкой коммерческой продажи .

Rambutan использует 112-битовый ключ (плюс биты четности) и может работать трех режимах: ECB, CBC, и 8-битовый CFB. Это сильный аргумент в пользу того, что этот алгоритм - блочный, но слухи утверждают иное. Предположительно это потоковый шифр с LFSR. У него пять приблизительно 80-битовых сдвиговых р е-гистров различной длины. Полиномы обратной связи значительно прорежены, в каждом из них всего лишь 10 отводов. Каждый сдвиговый регистр обеспечивает четыре входа для очень большой и сложной нелинейной функции, которая и выдает единственный бит.

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

16.9 Аддитивные генераторы

Аддитивные генераторы (иногда называемые запаздывающими генераторами Фиббоначи) очень эффективны, так как их результатом являются случайные слова, а не случайные биты [863]. Сами по себе они не безопасны, но их можно использовать в качестве составных блоков для безопасных генераторов .

Начальное состояние генератора представляет собой массив n-битовых слов: 8-битовых слов, 16-битовых слов, 32-битовых слов, и т.д.: Xb X2, X3, Xm. Это первоначальное состояние и является ключом. i-ое слово генератора получается как

X = (X,-a + Xi-ь + X,,c + + X-m) mod 2n

При правильном выборе коэффициентов a, b, c, . . . , m период этого генератора не меньше 2n-1. Одним из требований к коэффициентам является то, что младший значащий бит образует LFSR максимальной длины.

Например, (55,24,0) - это примитивный многочлен mod 2 из 14-й. Это означает, что длина следующего аддитивного генератора максимальна.

X = (X-55 +XW mod 2n

Это работает, так как у примитивного многочлена три коэффициента . Если бы их было больше, для получения максимальной длины потребовались бы дополнительные условия . Подробности можно найти в [249].

Fish - это аддитивный генератор, основанный на методах, используемых в прореживаемом генераторе [190]. Он выдает поток 32-битовых слов, которые могут быть использованы (с помощью XOR) с потоком открытого текста для получения шифротекста или с потоком шифротекста для получения открытого текста . Название алгоритма представляет собой сокращение от Fibonacci shrinking generator - прореживаемый генератор Фиббоначи .

Во первых используйте два следующих аддитивных генератора . Ключом является начальные состояния этих генераторов.

Ai = (X-55 +Х-24) mod 232

Bi = (Bi-52 +Bi-19) mod 232

Эти последовательности прореживаются попарно в зависимости от младшего значащего бита Bi: если его значение равно 1, то пара используется, если 0 - игнорируется . Cj - это последовательность используемых слов Ai, а Dj - это последовательность используемых слов Bi. Для генерации двух 32-битовых слов-результатов K2j и K2j+1 эти слова используются парами - C2j, C2j+1, D2j-, D2j+1.

Ej = C2j © (D2j, Л D2j+1)