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

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

16.5 A5

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

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

Большинство деталей нам известно. Британская телефонная компания передала всю документацию Брэ д-фордскому университету (Bradford University), не заставив подписать соглашение о неразглашении. Информация где-то просочилась и наконец б1ла опубликована в 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-битовых слов, и т.д.: X1, X2, X3, Xm. Это первоначальное состояние и является ключом. г-ое слово генератора получается как

X- = (X-a + X-b + X-c + + X-m) mod 2n

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

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

X,- = (X,-55 +X,-2) mod 2n

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

Fish

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

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

А,- = (A,-55 +A,-24,) mod 232

В,- = (B,-52 +B,-19,) mod 232

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

E2j = C2j © (D2j, л D2j+1)

F2j = D2j+1 л (Ej, л C2j+1) K2j = E2j е E2j K2j+1 = C2j+1 е E2j

Этот алгоритм быстр. на процессоре i486/33 реализация Fish на языке C шифрует данные со скоростью 15-Мбит/с. К сожалению он также не безопасен, порядок вскрытия составляет около 240 [45].

Pike

Pike - это обедненная и урезанная версия Fish, предложенная Россом Андерсоном, тем, кто взломал Fish [45]. Он использует три аддитивных генератора. Например:

Ai = (A,-55 +A,-24) mod 232

Bi = (Bi-57 +Bi-7; mod 232

Ci = (Ci-58 +Ci-1) mod 232

Для генерации слова потока ключей взгляните на биты переноса при сложении . Если все три одинаковы (все нули или все единицы), то тактируются все три генератора. Если нет, то тактируются только два совпадающих генератора. Сохраните биты переноса для следующего раза. Окончательным выходом является XOR выходов трех генераторов.

Pike быстрее Fish, так как в среднем для получения результата нужно 2.75 действия, а не 3. Он также слишком нов, чтобы ему доверять, но выглядит очень неплохо.

Mush

Mush представляет собой взаимно прореживающий генератор . Его работу объяснить легко [1590]. Возьмем два аддитивных генератора: A и B. Если бит переноса A установлен, тактируется B. Если бит переноса B установлен, тактируется A. Тактируем A и при переполнении устанавливаем бит переноса. Тактируем B и при переполнении устанавливаем бит переноса. Окончательным выходом является XOR выходов A и B. Проще всего использовать те же генераторы, что и в Fish:

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

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

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

16.10 Gifford

Дэвид Джиффорд (David Gifford) изобрел потоковый шифр и использовал его для шифрования сводок нов остей в районе Бостона с 1984 по 1988 год [608, 607, 609]. Алгоритм использует единственный 8-байтовый регистр: b0, b1, . . . , b7. Ключом является начальное состояние регистра. Алгоритм работает в режиме OFB, открытый текст абсолютно не влияет на работу алгоритма. (См. -1-й).