Создание массива ключей более сложно, но также прямолинейно. Сначала, байты ключа копируются в ма с-сив L из c 32-битовых слов, дополняя при необходимости заключительное слово нулями. Затем массив S инициализируется при помощи линейного конгруэнтного генератора по модулю 2 32:

S0 = P

for i = 1 to 2(r + 1) - 1:

Si = + Q) mod 232

P = 0xb7e15163 и Q = 0x9e3779b9, эти константы основываются на двоичном представлении e и phi. Наконец, подставляем L в S:

i = j = 0

A = B = 0

выполнить n раз (где n - максимум 2(r + 1) и c):

A = Si = (Si + A + B) <<< 3

B = Li = (Li + A + B) <<< (A + B) i = (i + 1) mod 2(r + 1) j = (j + 1 ) mod c

По сути, RC5 представляет собой семейство алгоритмов. Только что мы определили RC5 с 32-битовым сл о-вом и 64-битовым блоком, не существуе причин, запрещающих использовать тот же алгоритм с 64-битовым словом и 128-битовым. Для w = 64, P и Q равны 0xb7e151628aed2a6b и 0x9e3779b97f4a7c15, соответственно. Ривест обозначил различные реализации RC5 как RC5- w/r/b, где w - это размер слова, r - число этапов, а b -длина ключа в байтах.

RC5 является новым алгоритмом, но RSA Laboratories потрптила достаточно много времени, анализируя его работу с 64-битовым блоком. После 5 этапов статистика выглядит очень хорошо. После 8 этапов каждый бит открытого текста влияет по крайней мере на один циклический сдвиг. Дифференциальное вскрытие требует 2 24 выбранных открытых текстов для 5 этапов, 2 45 для 10 этапов, 253 для 12 этапов и 268 для 15 этапов. Конечно же, существует только 264 возможных открытых текстов, поэтому такое вскрытие неприменимо против алгоритма с 15 и более этапами. 0ценка для линейного криптоанализа показывает, что алгоритм безопасен после 6 этапов. Ривест рекомендует использовать не меньше 12 этапов, а лучше 16 [1325]. Это число может меняться.

RSADSI в настоящее время патентует RC5, а это названия заявлено, как торговая марка. Компания утве р-ждает, что плата за лицензирование будет очень мала, но это лучше проверить.

14.9 Другие блочные алгоритмы

Существует алгоритм, называемый в литературе CRYPTO-MECCANO [301], но он не является безопасным. Четыре японских криптографа на Eurocrypt 91 представили алгоритм, основанный на хаотичных отображениях [687, 688], Бихам выполнил криптоанализ этого алгоритма на той же конференции [157]. Другой алгоритм оп и-рается на подмножества некоторого множества случайных кодов [693]. Существует множество алгоритмов, о снованных на теории кодов, исправляющих ошибки: вариант алгоритма МакЭлайса (McEliece) (см. раздел 19.7) [786, 1290], алгоритм Rao-Nam [1292, 733, 1504, 1291, 1056, 1057, 1058, 1293], варианты алгоритма Rao-Nam [464, 749, 1503] и алгоритм Li-Wang [964, 1561] - все они небезопасны. CALC также небезопасен [1109]. Алг о-ритм TEA (Tiny Encryption Algorithm, Крошечный алгоритм шифрования) слишком нов, чтобы его коммент и-ровать [1592]. Другим алгоритмом является Vino [503]. MacGuffin, блочный алгоритм, предложенный Мэттом Блэйзом и мной, также небезопасен [189], он был взломан на той же конференции, на которой он был предл о-жен. BaseKing, похожий по философии на 3-way, но использующий 192-битовый блок [385], слишком нов, чт о-бы его комментировать.

Кроме того, существует множество блочных алгоритмов, разработанных вне криптографического сообщес т-ва. Некоторые из них используются различными военными и правительственными организациями. У меня нет данных о таких алгоритмах. Существуют также десятки частных коммерческих алгоритмов. Некоторые из них могут быть хороши, некоторые нет. Если компания предполагает, что опубликование ее алгоритмов не будет служить интересам компании, то лучше согласиться с ней и не использовать эти алгоритмы.

14.10 Теория проектирования блочного шифра

В раздел 11.1 я описывал принципы Шеннона для смешения и рассеяния. Спустя пятьдесят лет после того, как эти принципы были впервые сформулированы, они остаются краеугольным камнем проектирования хор о-

шего блочного шифра.

Смешение служит для маскировки взаимосвязей между открытым текстом, шифротекстом и ключом. По мните, как даже незначительная зависимость между этими тремя вещами может быть использована при дифф е-ренциальном и линейном криптоанализе? Хорошее смешение настолько усложняет статистику взаимосвязей, что не работают даже мощные криптографические средства.

Диффузия распространяет влияние отдельных битов открытого текста на как можно большее количество шифротекста. Это также маскирует статистические взаимосвязи и усложняет криптоанализ.

Для безопасности достаточно одного смешения. Алгоритм, состоящий из единственной зависящей от ключа таблицы соответствия 64 битов открытого текста 64 битам шифротекста был бы достаточно сильным. Проблема в том, что для такой таблицы потребовалось бы слишком много памяти: 1020 байтов. Смысл создания блочного шифра и состоит в создании чего-то похожего на такую таблицу, но предъявляющего к памяти более умеренные требования.

Прием состоит в том, чтобы в одном шифре в различных комбинациях периодически перемежать смешив а-ние (с гораздо меньшими таблицами) и диффузию. Это называется результирующим шифром. Иногда блочный шифр, который включает последовательные перестановки и подстановки, называют сетью перестановок-подстановок (substitution-permutation network), или SP-сетью.

Взгляните снова на функцию f в DES. Перестановка с расширением и P-блок реализуют диффузию, а S-блоки - смешение. Перестановка с расширением и P-блок линейны, S-блоки - нелинейны. Каждая операция сама по себе очень проста, но вместе они работают очень хорошо.

На примере DES также можно показать еще несколько принципов проектирования блочного шифра. Первым является идея итеративного блочного шифра. При этом предполагается, что простая функция этапа будет п о-следовательно использована несколько раз. Двухэтапный DES не очень силен, чтобы все биты результата зав и-сели от всех битов ключа и всех битов исходных данных, нужно 5 этапов [1078, 1080]. 16-этапный DES - это сильный алгоритм, 32-этапный DES еще сильнее.

Сети Фейстела

Большинство блочных алгоритмов являются сетями Фейстела (Felstel networks). Эта идея датируется нач алом 70-х годов [552, 553]. Возьмите блок длиной n и разделите его на две половины длиной n/2: L и R. Конечно, n должно быть четным. Можно определить итеративный блочный шифр, в котором результат 7-го этапа определяется результатом предыдущего этапа:

L,- = Ri-1

Ri- = Li-1 © f(Ri-1, Ki)

Ki - это подключ, используемый на 7-ом этапе, а f - это произвольная функция этапа.

Эту концепцию можно увидеть в DES, Lucifer, FEAL, Khufu, Khafre, LOKI, COST, CAST, Blowfish и других алгоритмах. Почему это так важно? Гарантируется, что эта функция является обращаемой. Так как для объед и-нения левой половины с результатом функции этапа используется XOR, следующее выражение обязательно я в-ляется истинным:

Li-1 © f(Ri-1, Ki) © f(Ri-1, Ki)= Li-1

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

Простые соотношения

DES обладает следующим свойством: если Ek(P) = C, то E(P) = C, где P, C и K - побитовые дополнения P, C и K. Это свойство вдвое уменьшает сложность вскрытия грубой силой. Свойства комплиментарности алг о-ритма LOKI уменьшают сложность вскрытия грубой силой в 256 раз.

Простое соотношение можно определить как [857]:

Если Ek(P) = C, то Ef(K) (g(P,K)) = h(C,K)

где f, g и h - простые функции. Под "простыми функциями" я подразумеваю функции, которые вычисляются легко, намного легче, чем выполнение итерации блочного шифра. В DES f представляет собой побитовое л о-полнение K, g - побитовое дополнение P, а h - побитовое дополнение C. Это является результатом вкрапления ключа в часть текста с помощью XOR.

Для хорошего блочного шифра не существует простых соотношений. Методы поиска некоторых из подобных слабых мест можно найти в [917].

Групповая структура

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

Полезным, однако, является не вопрос о том, действительно ли алгоритм является группой, а о том, наскол ь-ко он близок к группе. Если не хватает только одного элемента, то алгоритм не образует группу, но двойное шифрование было бы - статистически говоря - просто потерей времени. Работа над DES показала, что DES очень далек от группы. Существует также ряд интересных вопросов о полугруппе, получаемой при шифровании DES. Содержит ли она тождество, то есть, не образует ли она группу? Иными словами, не генерирует ли когда-нибудь некоторая комбинация операций шифрования (не дешифрирования) тождественную функцию? Если так, насколько длинна самая короткая такая комбинация?

Целью исследования является оценка пространства ключей для теоретического вскрытия грубой силой, а р е-зультат представляет собой наибольшую нижнюю границу энтропии пространства ключей.

Слабые ключи

В хорошем блочном шифре все ключи одинаково сильны. 0бычно нет проблем и при алгоритме с малым количеством слабых ключей, таком как DES. Вероятность случайно выбрать один из них очень мала, такой ключ легко проверить и при необходимости отбросить. 0днако, иногда эти слабые ключи могут быть задейс т-вованы, если блочный фильтр используется как однонаправленная хэш-функция (см. раздел 18.11).

Устойчивость к дифференциальному и линейному криптоанализу

Исследование дифференциального и линейного криптоанализа значительно прояснило теорию проектиров а-ния хорошего блочного шифра. Авторы IDEA ввели понятие дифференциалов, обобщение основной идеи характеристик [931]. 0ни утверждали, что можно создавать блочные шифры, устойчивые к вскрытиям такого т и-па. Результатом подобного проектирования и является IDEA [931]. Позднее это понятие было формализовано в [1181, 1182], когда Кайса Ниберг (Kaisa Nyberg) и Ларс Кнудсен (Lars Knudsen) показали, как создавать бло ч-ные шифры доказуемо безопасные по отношению к дифференциальному криптоанализу. Эта теория была ра с-ширена на дифференциалы высших порядков [702, 161, 927, 858, 860] и частичные дифференциалы [860]. К а-жется, что дифференциалы высших порядков применимы только к шифрам с малым числом этапов, но части ч-ные дифференциалы прекрасно объединяются с дифференциалами.

Линейный криптоанализ новее, и он все еще совершенствуется. Были определены понятия классификации ключей [1019] и нескольких приближений [811, 812]. Еще одно расширение криптоанализа можно найти в [1270]. В [938] была предпринята попытка объединить дифференциальный и линейный криптоанализ в одном вскрытии. Пока неясно, какая методика проектирования сможет противостоять подобным вскрытиям.

Кнудсен добился некоторого успеха, рассматривая некоторые необходимые (но, возможно, не достаточные) критерии того, что он назвал практически безопасными сетями Фейстела- шифров, устойчивых как к дифференциальному, так и к линейному криптоанализу [857]. Ниберг ввел для линейного криптоанализа аналог понятия дифференциалов в дифференциальном криптоанализе [1180].

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

Проектирование S-блоков

Сила большинства сетей Фейстела - и особенно их устойчивость к дифференциальному и линейному кри п-тоанализу - непосредственно связана с их S-блоками. Это явилось причиной потока исследований, что же обр а-зует хороший S-блок.

S-блок - это просто подстановка: отображение m-битовых входов на n-битовые выходы. Ранее я упоминал об одной большой таблице отображения 64-битовых входов на 64-битовые выходы, такая таблица представляла бы собой S-блок размером 64*64 бита. S-блок с т-битовым входом и n-битовым выходом называется m*n-битовым S-блоком. S-блоки обычно являются единственным нелинейным действием в алгоритме, именно они