Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С

• Название: Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
• Дата: 29.04.2022
• Размер: 3.25 Mb.
• Имя файла: Shnayer_Prikladnaya-kriptografiya.352928.pdf
• Тип: Протокол; #504484
• страница: 30 из 78

0000,0000,0x00,0000,0000,000x,xxxx,x000
В позиции "x" может стоять любая цифра. При использовании такого ключа побитовое XOR определенных пар открытых текстов равно побитовому XOR получившихся пар шифротекстов.
В любом случае вероятность случайной генерации одного из таких слабых ключей очень мала: 1/2 96
. Опас- ность случайно выбрать такой ключ практически не существует. К тому же, несложно модифицировать IDEA
так, чтобы исключить наличие слабых ключей - достаточно выполнить XOR каждого подключа с числом 0x0dae
[409].
Хотя попыток выполнить криптоанализ IDEA было много, мне неизвестно ни об одной успешной.
Режимы работы и варианты IDEA
IDEA может работать в любом из режимов работы блочного шифра, описанных в главе 9. Против двойных реализаций IDEA может быть предпринято то же вскрытие "встреча посередине", что и против DES (см. раздел

15.1). Однако, так как ключ IDEA более чем в два раза длиннее ключа DES, это вскрытие непрактично. Объем нужной для такого вскрытия памяти составит 64*2 128
битов, или 10 39
байтов. Может быть во вселенной и дост а- точно материи, чтобы построить такое хранилище, но я в этом сомневаюсь.
Если вы учитываете возможность использования параллельной вселенной, используйте утроенную реализ а- цию IDEA (см. раздел 15.2):
C E D E P
K
K
K
=
3 2
1
(
(
( )))
Такая реализация устойчива против вскрытия "встреча посередине".
Кроме того, почему бы вам не реализовать IDEA независимыми подключами, особенно если ваши средства распределения ключей позволяют работать с длинными ключами. Для IDEA нужно всего 52 16-битовых ключа,
общей длиной 832 битов. Этот вариант определенно безопасней, но никто не сможет сказать насколько.
В наивной модификации может быть увеличен вдвое размер блока. Алгоритм также прекрасно работал бы с
32-битовыми подблоками вместо 16-битовых и с 256-битовым ключом. Шифрование выполнялось бы быстрее,
и безопасность возросла бы в 2 32
раза. Или нет? Теория, на которой основан алгоритм, опирается на то, что
2 16
+1 является простым числом. А 2 32
+ 1 простым числом не является. Может быть алгоритм и можно изм е- нить так, чтобы он работал, но его безопасность будет совсем иной. Лай говорит, что заставить работать такой алгоритм будет нелегко [926].
Хотя IDEA кажется намного безопаснее DES, не всегда можно легко заменить один алгоритм другим в с у- ществующем приложении. Если ваша база данных и шаблоны сообщений могут работать с 64-битовым кл ю- чом, реализация 128-битового ключа IDEA может быть возможной.
Для таких приложений создайте 128-битовый ключ, объединив 64-битовый ключ сам с собой. Не забывайте,
что эта модификация заметно ослабляет IDEA.
Если вас больше волнует скорость работы, а не безопасность, попробуйте вариант IDEA с меньшим числом этапов. Сегодня лучшее вскрытие IDEA быстрее вскрытия грубой силой только для 2.5 и менее этапов [1050],
4-этапный IDEA будет в два раза быстрее и, насколько мне известно, его безопасность не уменьшится.
Caveat Emptor
1
IDEA - это относительно новый алгоритм, многие вопросы пока остаются открытыми. Образует ли IDEA
группу? (Лай думает, что нет [926].) Не существует ли пока не открытых способов вскрытия этого шифра? У
IDEA твердая теоретическая основа, но снова и снова казавшиеся безопасными алгоритмы капитулируют перед новыми формами криптоанализа. Ряд групп академических и военных исследователей не опубликовали свои результаты криптоанализа IDEA. Возможно, кто-нибудь уже добился или когда-нибудь добьется успеха.
Патенты и лицензии
IDEA запатентован в Европе и Соединенных Штатах [1012, 1013]. Патент принадлежит Ascom-Tech AG.
Для некоммерческого использования лицензирование не нужно. При заинтересованности в лицензии для ко м- мерческого применения алгоритма следует обратиться по адресу Ascom Systec AG, Dept CMVV, Cewerbepark,
CH-5506, Mgenwil, Switzerland; [phone]; Fax: [phone]; [e-mail].
13.10 MMB
Недовольство использованием в IDEA 64-битового блока шифрования привело к созданию Джоном Дэйм о- ном алгоритма под названием MMB (Modular Multiplication-based Block cipher, модульный блочный шифр, и с- пользующий умножения) [385, 405, 406]. В основе MMB лежит теория, используемая и в IDEA: перемешива ю- щие операции из различных групп. MMB - это итеративный алгоритм, главным образом состоящий из лине й- ных действий (XOR и использование ключа) и параллельное использование четырех больших нелинейных и з- меняющих обычный порядок подстановок. Эти подстановки определяются с помощью умножения по модулю
2 32
-1 с постоянными множителями. Результатом применения этих действий является алгоритм, использующий и
128-битовый ключ и 128-битовый блок.
MMB оперирует 32-битовыми подблоками текста ( x
0
, x
1
, x
2
, x
3
) и 32-битовыми подблоками ключа (k
0
, k
1
, k
2
,
k
3
). Это делает удобным реализацию алгоритма на современных 32-битовых процессорах. Чередуясь с XOR,
шесть раз используется нелинейная функция f. Вот этот алгоритм (все операции с индексами выполняются по модулю 3):
x i
= x i
? k i
, для i = 0 до 3 1
Предупреждение покупателю

f(x
0
, x
1
, x
2
, x
3
)
x i
= x i
? k i+1
, для i = 0 до 3
f(x
0
, x
1
, x
2
, x
3
)
x i
= x i
? k i+2
, для i = 0 до 3
f(x
0
, x
1
, x
2
, x
3
)
x i
= x i
? k i
, для i = 0 до 3
f(x
0
, x
1
, x
2
, x
3
)
x i
= x i
? k i+1
, для i = 0 до 3
f(x
0
, x
1
, x
2
, x
3
)
x i
= x i
? k i+2
, для i = 0 до 3
f(x
0
, x
1
, x
2
, x
3
)
У функции f три этапа:
(1) x
1
= c i
* x i
, для i = 0 до 3 (Если на входе умножения одни единицы, то на выходе - тоже одни единицы.)
(2) Если младший значащий бит x
0
= 1, то x
0
= x
0
? C. Если младший значащий бит x
3
= 0, то x
3
= x
3
? C.
(3) x i
= x i-1
? x i
? x i+1
, для i = 0 до 3
Все операции с индексами выполняются по модулю 3. Операция умножения на этапе (1) выполняется по м о- дулю 2 32
-1. В данном алгоритме если второй операнд - это 2 32
-1, то результат также равен 2 32
-1. В алгоритме используются следующие константы:
C = 2aaaaaaa c
0
= 025f1cdb c
l
= 2 * c
0
c
2
= 2 3
* c
0
c
3
= 2 7
* c
0
Константа C - это "простейшая" константа с высоким троичным весом, нулевым младшим значащим битом и без круговой симметрии. У константы c0 несколько иные характеристики. Константы c l
, c
2
и c
3
являются сме- щенными версиями c
0
, и используются для предотвращения вскрытий основанных на симметрии. Подробности можно найти в [405].
Дешифрирование является обратным процессом. Этапы (2) и (3) заменяются на свою инверсию. На этапе (1)
вместо c i
-1
используется c i
. c i
-1
= 0dad4694.
Безопасность MMB
Схема MMB обеспечивает на каждом этапе значительное и независимое от ключа рассеяние. В IDEA ра с- сеяние до определенной степени зависит от конкретных подключей. В отличие от IDEA у MMB нет слабых ключей.
К сожалению MMB - это умерший алгоритм [402]. Это утверждение справедливо по многим причинам, хотя криптоанализ MMB и не был опубликован. Во первых, он проектировался без учета требований устойчивости к линейному криптоанализу. Выбор мультипликативных множителей обеспечил устойчивость к дифференциал ь- ному криптоанализу, но о линейном криптоанализе авторам алгоритма было еще неизвестно.
Во вторых, Эли Бихам реализовал эффективное вскрытие с выбранным ключом [160], использующеее тот факт, что все этапы идентичны, а ключ при использовании просто циклически сдвигается на 32 бита. В третьих,
несмотря на то, что программные реализации MMB были бы очень эффективны, в аппаратном исполнении а л- горитм менее эффективен, чем DES.
Дэймон предлагает, что тот, кто захочет улучшить MMB, должен сначала проанализировать умножение по модулю с помощью линейного криптоанализа и подобрать новый множитель, а затем сделать константу C ра з- личной для каждого этапа [402]. Затем, улучшив использование ключа, добавляя к ключам этапов константы с целью устранения смещения. Но сам не стал заниматься этим и разработал 3-Way (см. раздел 14.5).

13.11 CA-1.1
CA - это блочный шифр, основанный на клеточных автоматах и разработанный Говардом Гутовицом
(Howard Gutowitz) [677, 678, 679]. Он шифрует 384-битовые блоки открытого текста 1088-битовым ключом (на самом деле используется два ключа - 1024-битовый и 64- битовый). Из-за природы клеточных автоматов алг о- ритм наиболее эффективен при реализации в больших параллельных интегрированных схемах.
CA-1.1 использует как обратимые, так и необратимые правила клеточного автомата. При обратимом прав и- ле каждое состояние структуры получается из единственного предшествующего состояния, а при необратимом правиле у каждого состояния может быть несколько предшественников. При шифровании необратимые правила пошагово обращаются во времени. Для продвижения обратно от текущего состояния случайным образом дол ж- но выбираться одно из состояний-предшественников. Этот процесс многократно повторяется. Таким образом,
обратная итерация служит для смешивания случайной информации с инфорамацией сообщения. CA-1.1 испол ь- зует особый сорт частично линейного необратимого правила, такого, что для любого данного состояния может быть быстро построено случайное состояние-предшественник. На некоторых стадиях шифрования используются и обратимые правила.
Обратимые правила (простые параллельные перестановки подблоков состояния) нелинейны. Необратимые правила полностью определяются ключом, а обратимые зависят как от ключа, так и от случайной информации,
вставленной в ходе шифрования необратимыми правилами.
CA-1.1 основан на структуре блочных связей. То есть, обработка блока сообщения частично отделена от о б- работки потока случайной информации, вставленной при шифровании. Эта случайная информация служит для связи друг с другом стадий шифрования. Она также может быть использована для связи с потоком шифроте к- ста. Информация связи генерируется как часть шифрования.
Так как CA-1.1 представляет собой новый алгоритм, слишком рано делать какие-либо заявления о его без о- пасности. Гутовиц упоминает некоторые возможные вскрытия, включая дифференциальный криптоанализ, но ему не удалось вскрыть алгоритм. В качестве стимула Гутовиц предложил награду в 1000 долларов для "первого человека, который разработает доступную процедуру вскрытия CA-1.1."
CA-l.1 запатентован [678], но доступен для некоммерческого использования. При необходимости получить лицензию на алгоритм или объявленную награду за криптоанализ обращайтесь к Говарду Гутовицу по адресу
Howard Cutowitz, ESPCI, Laboratorie d'Electronique, 10 rue Vauquelin, 75005 Paris, France.
13.12 SKIPJACK
Skipjack разработан NSA в качестве алгоритма шифрования для микросхем Clipper и Capstone (см. разделы
24.16 и 24.17). Так как этот алгоритм объявлен секретным, его подробности никогда не публиковались. Он б у- дет реализован только как защищенная от взлома аппаратура.
Этот алгоритм объявлен секретным не потому, что это повышает его надежность, а потому что NSA не х о- чет, чтобы Skipjack использовался без механизма условного вручения ключей Clipper. Агентство не хочет, чт о- бы программные реализации алгоритма распространились по всему миру.
Безопасен ли Skipjack? Если NSA захочет создать безопасный алгоритм, оно, скорее всего, это сделает. С
другой стороны, если NSA захочет создать алгоритм с лазейкой, то оно сможет сделать и это. Вот что было опубликовано [1154, 462].
— Это итеративный блочный шифр.
— Размер блока - 64 бита.
— Алгоритм использует 80-битовый ключ.
— Он может быть использован в режимах ECB, CBC, 64-битовый OFB, либо 1-, 8-, 16-, 32- или 64-битовый
CFB.
— Операция шифрования или дешифрирования состоит из 32 этапов.
— NSA начало работу над ним в 1985 и завершило проверку в 1990.
В документации на микросхему Mykotronx Clipper утверждается, что задержка в выдаче результата, прис у- щая алгоритму Skipjack, составляет 64 такта. Это означает, что на каждый этап приходится два такта: один предположительно для подстановки с помощью S-блока, а другой - для заключительного XOR в конце каждого этапа. (Не забывайте, перестановки при аппаратных реализациях не занимают времени.) В документации
Mykotronx эта двухтактная операция называется "G-блоком", а все вместе - "сдвигом". (Часть G-блока носит название "F-таблицы" и является таблицей констант, а может быть таблицей функций.)
По одним слухам Skipjack использует 16 S-блоков, а по другим для хранения S-блоков нужно всего 128 байт

памяти. Непохоже, чтобы оба этих слуха были правдой.
Еще один слух утверждает, что этапы Skipjack, в отличие от DES, работают не с половиной блока. Это вм е- сте с замечанием о "сдвигах" и случайном заявлении на Crypto '94 о том, что в Skipjack применяется "48- битовая внутренняя структура", позволяет сделать вывод, что алгоритм по своей схеме похож на SHA (см. ра з- дел 18.7), но использует четыре 16-битовых подблока. Три подблока, обработанные зависящей от ключа одн о- направленной функцией, дают 16 битов, которые подвергаются операции XOR с оставшимся подблоком. Затем весь блок циклически сдвигается на 16 битов и поступает на вход следующего этапа, или сдвига. При этом та к- же используются 128 байтов данных S-блока. Я подозреваю, что S-блоки зависят от ключа.
По своей структуре Skipjack вероятно похож на DES. NSA понимает, что его защищенная от взлома аппар а- тура в конце концов будет вскрыта и исследована, они не будут рисковать никакими передовыми криптограф и- ческими методами.
То, что NSA планирует использовать алгоритм Skipjack для шифрования своей Системы защиты сообщений
(Defense Messaging System, DMS), свидетельствует о безопасности алгоритма. Чтобы убедить скептиков, NIST
разрешил комиссии "уважаемых неправительственных экспертов . . . получить доступ к конфиденциальным подробностям алгоритма, чтобы они исследовали его возможности и опубликовали результаты своих исслед о- ваний " [812].
В предварительном отчете этой комиссии экспертов [262] (окончательного отчета не было, и возможно ник о- гда не будет) сообщалось:
Принимая во внимание, что стоимость вычислительных мощностей уменьшается в два раза каждые 18 месяцев, сло ж- ность вскрытия Skipjack сравняется с сегодняшней сложностью вскрытия DES только через 36 лет. Следовательно, риск, что
Skipjack будет взломан в ближайшие 30-40 лет, незначителен.
Незначителен и риск взлома Skipjack с помощью более быстрых способов вскрытия, включая дифференциальный кри п- тоанализ. У алгоритма не слабых ключей, отсутствует и свойство комплиментарности. Эксперты в отсутствие времени для самостоятельного большого исследования алгоритма изучили представленное NSA описание разработки и проверки алг о- ритма
Устойчивость Skipjack к криптоанализу не зависит от хранения в тайне самого алгоритма.
Итак, участники дискуссии не смогли поработать с алгоритмом достаточно долго, чтобы прийти к каким- нибудь выводам самостоятельно. Все, что они смогли сделать - это взглянуть на результаты, показанные им
NSA.
Остался без ответа вопрос, является ли плоским пространство ключей Skipjack (см. раздел 8.2). Даже если у
Skipjack нет ключей, слабых в смысле DES, ряд особенностей процесса использования ключа может сделать одни ключи сильнее других. У Skipjack может быть 2 70
сильных ключей, гораздо больше чем у DES, вероя т- ность случайно выбрать один из этих сильных ключей будет приблизительно 1 к 1000. Лично я думаю, что пр о- странство ключей Skipjack - плоское, но то, что об этом никто не заявил публично, вызывает тревогу.
Skipjack запатентован, но в соответствии с соглашением о секретности патента [1122] этот патент хранится в тайне. Патент будет опубликован тогда и только тогда, когда алгоритм Skipjack будет успешно восстановлен кем-то посторонним. Это дает возможность правительству воспользоваться и преимуществом защиты патентом,
и преимуществом конфеденциальности торгового секрета.

Глава 14
И еще о блочных шифрах
14.1 ГОСТ
ГОСТ - это блочный алгоритм, разработанный в бывшем Советском Союзе [655, 1393]. Название "ГОСТ"
является сокращением от "Государственный стандарт", нечто похожее на FIPS за исключением того, что это название могут носить стандарты практически любого типа. (Полным названием является "Государственный стандарт Союза ССР", или "Государственный стандарт Союза Советских Социалистических Республик".) Н о- мер данного стандарта - 28147-89. Все эти стандарты утверждаются Государственным комитетом по стандартам
Союза ССР.
Я не знаю, использовался ли ГОСТ 28147-89 для засекреченного трафика или только для гражданского шифрования. Замечание в начале стандарта гласит, что алгоритм "удовлетворяет всем криптографическим тр е- бованиям, а степень защищаемой информации не ограничивается". Я слышал утверждения, что этот алгоритм первоначально использовался только для очень важных линий связи, включая секретные военные коммуник а- ции, но у меня нет подтверждений.
Описание ГОСТ
ГОСТ является 64-битовым алгоритмом с 256-битовым ключом. ГОСТ также использует дополнительный ключ, который рассматривается ниже. В процессе работы алгоритма на 32 этапах последовательно выполняется простой алгоритм шифрования.
Для шифрования текст сначала разбивается на левую половину L и правую половину R. На этапе i использу- ется подключ K
i
. На этапе i алгоритма ГОСТ выполняется следующее:
L
i
= R
i-1
R
i
= L
i-1
? f(R
i-1
, K
i
)
Этап ГОСТ показан на Рис. 14-1. Функция f проста. Сначала правая половина и i-ый подключ складываются по модулю 2 32
. Результат разбивается на восемь 4-битовых кусочков, каждый из которых поступает на вход св о- его S-блока. ГОСТ использует восемь различных S-блоков, первые 4 бита попадают в первый S-блок, вторые 4 4 бита - во второй S-блок, и т.д. Каждый S-блок представляет собой перестановку чисел от 0 до 15. Например,
S-блок может выглядеть как:
7, 10, 2, 4, 15, 9, 0, 3, 6, 12, 5, 13, 1, 8, 11
Подстановка S-блоком
Выбор подключа
R
i-1
L
i-1
Циклический сдвиг влево
R
i-1
L
i-1
Рис. 14-1. Этап ГОСТ.
В этом случае, если на входе S-блока 0, то на выходе 7. Если на входе 1, на выходе 10, и т.д. Все восемь
S-блоков различны, они фактически являются дополнительным ключевым материалом. S-блоки должны хр а- ниться в секрете.
Выходы всех восьми S-блоков объединяются в 32-битовое слово, затем все слово циклически сдвигается влево на 11 битов. Наконец результат объединяется с помощью XOR с левой половиной, и получается новая правая половина, а правая половина становится новой левой половиной. Выполните это 32 раза, и все в поря д-

ке.
Генерация подключей проста. 256-битовый ключ разбивается на восемь 32-битовых блоков: k
1
, k
2
, . . .k
8
. На каждом этапе используется свой подключ, как показано в Табл. 14-1. Дешифрирование выполняется также, как и шифрование, но инвертируется порядок подключей k i
Стандарт ГОСТ не определяет способ генерации S-блоков, говорится только, что блоки должны быть пр е- доставлены каким-то образом [655]. Это породило домыслы о том, что советский производитель может поста в- лять хорошие S-блоки "хорошим" организациям и плохие S-блоки тем организациям, которых производитель собирается надуть. Это вполне может быть так, но неофициальные переговоры с российским производителем микросхем ГОСТ выявили другую альтернативу. Производитель создает перестановки S-блока самостоятельно с помощью генератора случайных чисел.
Табл. 14-1.
Использование подключей на различных этапах ГОСТ
Этап:
1 2
3 4
5 6
7 8
9 10 11 12 13 14 15 16
Подключ:
1 2
3 4
5 6
7 8
1 2
3 4
5 6
7 8
Этап:
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
Подключ:
1 2
3 4
5 6
7 8
8 7
6 5
4 3
2 1
Совсем недавно стал известным набор S-блоков, используемых в приложениях Центрального Банка РФ. Эти
S-блоки также используются в однонаправленной хэш-функции ГОСТ (см. раздел 18.11) [657]. Они перечисл е- ны в Табл. 14-2.
Криптоанализ ГОСТ
Вот главные различия между DES и COST.
— DES использует сложную процедуру для генерации подключей из ключей. В ГОСТ эта процедура очень проста.
— В DES 56-битовый ключ, а в ГОСТ - 256-битовый. Если добавить секретные перестановки S-блоков, то полный объем секретной информации ГОСТ составит примерно 610 битов.
— У S-блоков DES 6-битовые входы и 4-битовые выходы, а у S-блоков ГОСТ 4-битовые входы и выходы. В
обоих алгоритмах используется по восемь S-блоков, но размер S-блока ГОСТ равен одной четвертой размера S-блока DES.
— В DES используются нерегулярные перестановки, названные P-блоком, а в ГОСТ используется 11- битовый циклический сдвиг влево.
— В DES 16 этапов, а в ГОСТ - 32.
Табл. 14-2.
S-блоки ГОСТ
S-блок 1:
4 10 9
2 13 8
0 14 6
11 1
12 7
15 5
3
S-блок 2:
14 11 4
12 6
13 15 10 2
3 8
1 0
7 5
9
S-блок 3:
5 8
1 13 10 3
4 2
14 15 12 7
6 0
9 11
S-блок 4:
7 13 10 1
0 8
9 15 14 4
6 12 11 2
5 3
S-блок 5:
6 12 7
1 5
15 13 8
4 10 9
14 0
3 11 2
S-блок 6:

4 11 10 0
7 2
1 13 3
6 8
5 9
12 15 14
S-блок 7:
13 11 4
1 3
15 5
9 0
10 14 7
6 8
2 12
S-блок 8:
1 15 13 0
5 7
10 4
9 2
3 14 6
11 8
12
Если лучшим способом вскрытия ГОСТ является грубая сила, то это очень безопасный алгоритм. ГОСТ и с- пользует 256-битовый ключ, а если учитывать секретные S-блоки, то длина ключа возрастает. ГОСТ, по вид и- мому, более устойчив к дифференциальному и линейному криптоанализу, чем DES. Хотя случайные S-блоки
ГОСТ возможно слабее фиксированных S-блоков DES, их секретность увеличивает устойчивость ГОСТ к ди ф- ференциальному и линейному криптоанализу. К тому же, эти способы вскрытия чувствительны к количеству этапов - чем больше этапов, тем труднее вскрытие. ГОСТ использует в два раза больше этапов, чем DES, одно это возможно делает несостоятельными и дифференциальный, и линейный криптоанализ.
Другие части ГОСТ такие же, как в DES, или слабее. ГОСТ не использует существующую в DES перест а- новку с расширением. Удаление этой перестановки из DES ослабляет его из-за уменьшения лавинного эффекта,
разумно считать, что отсутствие такой операции в ГОСТ ослабляет этот алгоритм. Сложение, используемое в
ГОСТ, не менее безопасно, чем используемая в DES операция XOR.
Самым большим различием представляется использование в ГОСТ циклического сдвига вместо перестано в- ки. Перестановка DES увеличивает лавинный эффект. В ГОСТ изменение одного входного бита влияет на один
S-блок одного этапа, который затем влияет на два S-блока следующего этапа, три блока следующего этапа, и т.д.. В ГОСТ потребуется 8 этапов прежде, чем изменение одного входного бита повлияет на каждый бит р е- зультата, алгоритму DES для этого нужно только 5 этапов. Это, конечно же, слабое место. Но не забывайте:
ГОСТ состоит из 32 этапов, а DES только из 16.
Разработчики ГОСТ пытались достигнуть равновесия между безопасностью и эффективностью. Они изм е- нили идеологию DES так, чтобы создать алгоритм, который больше подходит для программной реализации.
Они, по видимому, менее уверены в безопасности своего алгоритма и попытались скомпенсировать это очень большой длиной ключа, сохранением в секрете S-блоков и удвоением количества итераций. Вопрос, увенчались ли их усилия созданием более безопасного, чем DES, алгоритма, остается открытым.
14.2 CAST
CAST был разработан в Канаде Карлайслом Адамсом (Carlisle Adams) и Стаффордом Таваресом (Stafford
Tavares) [10, 7]. Они утверждают, что название обусловлено ходом разработки и должно напоминать о вероя т- ностном характере процесса, а не об инициалах авторов. Описываемый алгоритм CAST использует 64-битовый блок и 64-битовый ключ.
CAST имеет знакомую структуру. Алгоритм использует шесть S-блоков с 8-битовым входом и 32-битовым выходом. Работа этих S-блоков сложна и зависит от реализации, подробности можно найти в литературе.
Для шифрования сначала блок открытого текста разбивается на левую и правую половины. Алгоритм сост о- ит из 8 этапов. На каждом этапе правая половина объединяется с частью ключа с помощью функции f, а затем
XOR результата и левой половины выполняется для получения новой правой половины. Первоначальная (до этапа) правая половина становится новой левой половиной. После 8 этапов (не переставьте левую и правую п о- ловины после восьмого этапа) две половины объединяются, образуя шифротекст. Функция f проста:
(1) Разбейте 32-битовый вход на четыре 8-битовых части: a, b, c, d.
(2) Разбейте 16-битовый подключ на две 8-битовых половины: e, f.
(3) Подайте a на вход S-блока 1, b - на вход S-блока 2, c - на вход S-блока 3, d - на вход S-блока 4, e - на вход
S-блока 5 и f - на вход S-блока 6.
(4) Выполните XOR шести выходов S-блоков, получая 32-битовый результат.
Иначе, 32-битовый вход может быть объединен с помощью XOR с 32 битами ключа, разбит на четыре 8- битовых части, которые обрабатываются S-блоками и затем объединяются с помощью XOR [7]. Безопасность N
этапов, организованных таким образом, по видимому, соответствует N + 2 этапам другого варианта.
16-битовые подключи этапов легко получаются из 64-битового ключа. Если k
1
, k
2
, . . .k
8
- это 8 байтов клю- ча, то на этапах алгоритма используются следующие подключи:
Этап 1: k
1
, k
2

Этап 2: k
3
, k
4
Этап 3: k
5
, k
6
Этап 4: k
7
, k
8
Этап 5: k
4
, k
3
Этап 6: k
2
, k
1
Этап 7: k
8
, k
7
Этап 8: k
6
, k
5
Сила этого алгоритма заключена в его S-блоках. У CAST нет фиксированных S-блоков, для каждого прил о- жения они конструируются заново. Критерии проектирования описаны в [10], изогнутыми функциями являются столбцы S-блоков, обеспечивающие необходимые свойства S-блоков (см. раздел 14.10). Созданный для данной реализации CAST S-блоков уже больше никогда не меняется. S-блоки зависят от реализации, а не от ключа.
В [10] было показано, что CAST устойчив к дифференциальному криптоанализу, а в [728] - что CAST усто й- чив и к линейному криптоанализу. Неизвестно иного, чем грубая сила, способа вскрыть CAST.
Northern Telecom использует CAST в своем пакете программ Entrust для компьютеров Macintosh, PC и р а- бочих станций UNIX. Выбранные ими S-блоки не опубликованы. Канадское правительство считает CAST н о- вым стандартом шифрования. Патентная заявка на CAST находится в процессе рассмотрения.
14.3 BLOWFISH
Blowfish - это алгоритм, разработанный лично мной для реализации на больших микропроцессорах [1388,
1389]. Алгоритм незапатентован, и его код на языке C приведен в конце этой книги для широкого пользования.
При проектировании Blowfish я использовал следующие критерии:
1. Скорость. Blowfish шифрует данные на 32-битовых микропроцессорах со скоростью 26 тактов на байт.
2. Компактность. Blowfish может работать менее, чем в 5 Кбайт памяти.
3. Простота. Blowfish использует только простые операции: сложение, XOR и выборка из таблицы по 32- битовому операнду. Анализ его схемы несложен, что делает при реализации алгоритма уменьшает к о- личество ошибок [1391].
4. Настраиваемая безопасность. Длина ключа Blowfish переменна и может достигать 448 битов.
Blowfish оптимизирован для тех приложений, в которых нет частой смены ключей, таких как линии связи или программа автоматического шифрования файлов. При реализации на 32-битовых микропроцессорах с большим кэшем данных, таких как Pentium и PowerPC, Blowfish заметно быстрее DES. Blowfish не подходит для использования в приложениях с частой сменой ключей, например, при коммутации пакетов, или для и с- пользования в качестве однонаправленной хэш-функции. Большие требования к памяти делают невозможным использование этого алгоритма в интеллектуальных платах.
Описание Blowfish
Blowfish представляет собой 64-битовый блочный шифр с ключом переменной длины. Алгоритм состоит из двух частей: развертывание ключа и шифрование данных. Развертывание ключа преобразует ключ длиной до
448 битов в несколько массивов подключей, общим объемом 4168 байтов.
Шифрование данных состоит из простой функции, последовательно выполняемой 16 раз. Каждый этап с о- стоит из зависимой от ключа перестановки и зависимой от ключа и данных подстановки. Используются только сложения и XOR 32-битовых слов. Единственными дополнительными операциями на каждом этапе являются четыре извлечения данных из индексированного массива.
В Blowfish используется много подключей. Эти подключи должны быть рассчитаны до начала шифрования или дешифрирования данных.
P-массив состоит из 18 32-битовых подключей:
P1, P2, . . ., P18
Каждый из четырех 32-битовых S-блоков содержит 256 элементов:
S
1,0
, S
1,1
, . . ., S
1,255
S
2,0
, S
2,2
, . . ., S
2,255

S
3,0
, S
3,3
, . . ., S
3,255
S
4,0
, S
4,4
, . . ., S
4,255
Точный метод, используемый при вычислении этих подключей описан в этом разделе ниже.
F
32 бита
P
1 32 бита
32 бита
32 бита
32 бита
64 бита
Открытый текст
F
P
2
F
Еще 13 итераций
P
16
P
18
P
17 32 бита
32 бита
64 бита
Шифротекст
Рис. 14-2. Blowfish.
Blowfish является сетью Фейстела (Feistel) (см. раздел 14.10), состоящей из 16 этапов. На вход подается 64- битовый элемент данных x. Для шифрования:
Разбейте x на две 32-битовых половины: x
L
, x
R
Для i = 1 по 16:
x
L
= x
L
? P
18
x
R
= F(x
L
) ? x
R
Переставить x
L
и x
R
(кроме последнего этапа.)
x
R
= x
R
? P
17
x
L
= x
L
? P
18
Объединить x
L
и x
R

8 битов
8 битов
8 битов
8 битов
32 бита
S-блок 4
S-блок 3
S-блок 2
S-блок 1 32 бита
Рис. 14-3. Функция F.
Функция F представляет собой следующее (см. Рис. 14-3):
Разделить x
L
на четыре 8-битовых части: a, b, c и d
F(x
L
) = ((S
1,a
+ S
2,b mod 2 32
) ? S
3,c
)+ S
4,d mod 2 32
Дешифрирование выполняется точно также, как и шифрование, но P
1
, P
2
, . . ., P
18
используются в обратном порядке.
В реализациях Blowfish, для которых требуется очень большая скорость, цикл должен быть развернут, а все ключи должны храниться в кэше. Подробности приведены в [568].
Подключи рассчитываются с помощью специального алгоритма. Вот какова точная последовательность де й- ствий.
(1) Сначала P-массив, а затем четыре S-блока по порядку инициализируются фиксированной строкой. Эта строка состоит из шестнадцатиричных цифр ?.
(2) Выполняется XOR P
1
с первыми 32 битами ключа, XOR P
2
со вторыми 32 битами ключа, и так далее для всех битов ключа (до P
18
). Используется циклически, пока для всего P-массива не будет выполнена опер а- ция XOR с битами ключа.
(3) Используя подключи, полученные на этапах (1) и (2), алгоритмом Blowfish шифруется строка из одних нулей.
(4) P
1
и P
2
заменяются результатом этапа (3).
(5) Результат этапа (3) шифруется с помощью алгоритма Blowfish и измененных подключей.
(6) P
3
и P
4
заменяются результатом этапа (5).
(7) Далее в ходе процесса все элементы P-массива и затем по порядку все четыре S-блока заменяются вых о- дом постоянно меняющегося алгоритма Blowfish.
Всего для генерации всех необходимых подключей требуется 521 итерация. Приложения могут сохранять подключи - нет необходимости выполнять процесс их получения многократно.
Безопасность Blowfish
Серж Воденэ (Serge Vaudenay) исследовал Blowfish с известными S-блоками и r этапами, дифференциал ь- ный криптоанализ может раскрыть P-массив с помощью 2 8r+1
выбранных открытых текстов [1568]. Для некот о- рых слабых ключей, которые генерируют плохие S-блоки (вероятность выбора такого ключа составляет 1 к 2 14
),
это же вскрытие раскрывает P-массив с помощью всего 2 4r+1
. При неизвестных S-блоках это вскрытие может обнаружить использование слабого ключа, но не может определит сам ключ (ни S-блоки, ни P-массив). Это вскрытие эффективно только против вариантов с уменьшенным числом этапов и совершенно бесполезно против
16-этапного Blowfish.
Конечно, важно и раскрытие слабых ключей, даже хотя они скорее всего не будут использоваться. Слабым является ключ, для которого два элемента данного S-блока идентичны. До выполнения развертывания ключа невозможно определить, является ли он слабым. Если вы беспокоитесь об этом, вам придется выполнить ра з-

вертывание ключа и проверить, нет ли в S-одинаковых элементов. Хотя я не думаю, что это так уж необходимо.
Мне неизвестно об успешном криптоанализе Blowfish. Для безопасности не реализуйте Blowfish с умен ь- шенным числом этапов.
Kent Marsh Ltd. встроила Blowfish в свой продукт обеспечения безопасности FolderBolt, предназначенный для Microsoft Windows и Macintosh. Алгоритм также входит в Nautilus и PGPfone.
14.4 SAFER
SAFER K-64 означает Secure And Fast Encryption Routine with a Key of 64 bits - Безопасная и быстрая проц е- дура шифрования с 64-битовым ключом [1009]. Этот не являющийся частной собственностью алгоритм, разр а- ботанный Джеймсом Массеем (James Massey) для Cylink Corp., используется в некоторых из продуктов этой компании. Правительство Сингапура собирается использовать этот алгоритм - с 128-битовым ключом [1010] - для широкого спектра приложений. Его использование не ограничено патентом, авторскими правами или др у- гими ограничениями.
Алгоритм работает с 64-битовым блоком и 64-битовым ключом. В отличие от DES он является не сетью
Фейстела (см. раздел 14.10), а итеративным блочным шифром: для некоторого количества этапов применяется одна и та же функция. На каждом этапе используются два 64-битовых подключа. Алгоритм оперирует только байтами.
Описание SAFER K-64
Блок открытого текста делится на восемь байтовых подблоков: B
1
, B
2
, . . . , B
7
, B
8
. Затем подблоки обрабаты- ваются в ходе r этапов. Наконец подблоки подвергаются заключительному преобразованию. На каждом этапе используется два подключа: K
2r-1
и K
2r
На Рис. 14-4 показан один этап SAFER K-64. Сначала над подблоками выполняется либо операция XOR, л и- бо сложени с байтами подключа K
2r-1
. Затем восемь подблоков подвергаются одному из двух нелинейных пр е- образований:
y = 45
x mod 257. (Если x = 0, то y = 0.)
y = log
45
x. (Если x = 0, то y = 0.)

log
45
log
45
log
45 45
(.)
45
(.)
45
(.)
log
45 2-PHT
2-PHT
2-PHT
2-PHT
45
(.)
add xor xor add add xor xor add xor add add xor xor add add xor
1 2
3 4
5 6
7 8
Выход этапа (8 байтов)
Вход этапа (8 байтов)
1 2
3 4
5 6
7 8
K
2i-1
K
2i
2-PHT
2-PHT
2-PHT
2-PHT
2-PHT
2-PHT
2-PHT
2-PHT
Рис. 14-4. Один этап SAFER.
Это операции в конечном поле GF(257), а 45 - элемент поля, являющийся примитивом. В реализациях
SAFER K-64 быстрее выполнять поиск в таблице, чем все время рассчитывать новые результаты.
Затем подблоки либо подвергаются XOR, либо складываются с байтами подключа K
2r
. Результат этого дей- ствия проходит через три уровня линейных операций, целью которых является увеличение лавинного эффекта.
Каждая операция называется псевдоадамаровым преобразованием (Pseudo-Hadamard Transform, PHT). Если на входе PHT a
1
и a
2
, то на выходе:
b
1
= (2a
1
+ a
2
) mod 256
b
2
= (a
1
+ a
2
) mod 256
После r этапов выполняется заключительное преобразование. Оно совпадает с преобразованием, являющи м- ся первым действием каждого этапа. Над B
1
, B
4
, B
5
и B
8
выполняется XOR с соответствующими байтами п о- следнего подключа, а B
2
, B
3
, B
6
и B
7
складываются с соответствующими байтами последнего подключа. В р е- зультате и получается шифротекст.
Дешифрирование представляет собой обратный процесс: сначала заключительное преобразование (с выч и- танием вместо сложения), затем r инвертированных этапов. Обратное PHT (Inverse PHT, IPHT) - это:
a
1
= (b
1
- b
2
) mod 256
a
2
= (-b
1
+ 2b
2
) mod 256
Массей рекомендует использовать 6 этапов, но для большей безопасности количество этапов можно увел и- чить.
Генерировать подключи совсем не трудно. Первый подключ, K
1
, - это просто ключ пользователя. После- дующие ключи генерируются в соответствии со следующей процедурой:
K
i+1
= (K
i
<<<3i) + c i
Символ "<<<" обозначает циклический сдвиг налево. Сдвиг выполняется побайтно, а c i
является константой этапа. Если c ij
- это j-ый байт константы i-го этапа, то можно рассчитать все константы этапов по следующей

формуле c
ij
= 45 45^((9i+j) mod 256) mod 257
mod 257
Обычно эти значения хранятся в таблице.
SAFER K-128
Этот альтернативный способ использования ключа был разработан Министерством внутренних дел Синг а- пура, а затем был встроен Массеем в SAFER [1010]. В этом способе используются два ключа, K
a и K
b
, по 64
бита каждый. Прием состоит в том, чтобы генерировать параллельно две последовательности подключей, а з а- тем чередовать подключи из каждой последовательности. Это означает, что при выборе K
a
= K
b
128-битовый ключ совместим с 64-битовым ключом K
a
Безопасность SAFER K-64
Массей показал, что SAFER K-64 после 6 этапов абсолютно защищен от дифференциального криптоанализа после 8 этапов и достаточно безопасен. Уже после 3 этапов против этого алгоритма становится неэффективным и линейный криптоанализ [1010].
Кнудсен (Knudsen) обнаружил слабое место в распределении ключей: практически для каждого ключа сущ е- ствует не меньше одного (а иногда даже девять) другого ключа, который при шифровании какого-то другого открытого текста превращает его в тот же шифротекст [862]. Число различных открытых текстов, которые шифруются одинаковыми шифротекстами, находится в промежутке от 2 22
до 2 28
. Хотя такое вскрытие не может повлиять на безопасность SAFER как алгоритма шифрования, оно значительно уменьшает его надежность при использовании в качестве однонаправленной хэш-функции. В любом случае Кнудсен рекомендует использовать не меньше 8 этапов.
SAFER был спроектирован для Cylink, а Cylink были предъявлены различные обвинения со стороны NSA
[80]. Я рекомендовал бы потратить несколько лет на интенсивный криптоанализ прежде, чем как-либо испол ь- зовать SAFER.
14.5 3-WAY
3-Way - это блочный шифр, разработанный Джоном Дэйменом (Joan Daemen) [402, 410]. Он использует блок и ключ длиной 96 бит, и его схема предполагает очень эффективную аппаратную реализацию.
3-Way является не сетью Фейстела, а итеративным блочным шифром. У 3-Way может быть n этапов, Дэ й- мен рекомендует 11.
Описание S-Way
Этот алгоритм описать несложно. Для шифрования блока открытого текста x:
For i = 0 to n - 1
x = x XOR K
i x = theta (x)
x = pi - 1 (x)
x = gamma (x)
x = pi - 2 (x)
x = x ? K
n+1
x = theta (x)
При этом используются следующие функции:
— theta(x) - функция линейной подстановки, в основном набор циклических сдвигов и XOR.
— pi - 1 (x) и pi - 2 (x) - простые перестановки.
— gamma (x) - функция нелинейной подстановки. Именно это действие и дало имя всему алгоритму, оно представляет собой параллельное выполнение подстановки 3-битовых данных.
Дешифрирование аналогично шифрованию за исключением того, что нужно изменить на обратный порядок битов исходных данных и результата. Исходный код, реализующий 3-Way, можно найти в конце этой книги.
Пока об успешном криптоанализе 3-Way неизвестно. Алгоритм незапатентован.

14.6 CRAB
Этот алгоритм был разработан Бертом Калиски [Burt Kaliski] и Мэттом Робшоу [Matt Robshaw] из RSA
Laboratories [810]. В основе Crab лежит идея использовать методы однонаправленных хэш-функций для созд а- ния быстрого алгоритма шифрования. Следовательно, Crab очень похож на MD5, и в этом разделе предполаг а- ется, что вы знакомы с материалом раздела 18.5.
У Crab очень большой блок: 1024 байта. Так как Crab был представлен скорее как материал для исследов а- ния, а не реальный алгоритм, конкретной процедуры генерации ключей не было предложено. Авторы рассмо т- рели метод, который позволяет превратить 80-битовый ключ в три вспомогательных подключа, хотя алгоритм позволяет легко использовать ключи переменной длины. В Crab используется два набора больших подключей:
Перестановка чисел с 0 до 255: P
0
, P
1
, P
2
, ..., P
255
Массив из 2048 32-битовых чисел: S
0
, S
1
, S
2
,..., S
2047
Все эти подключи должны быть вычислены до шифрования или дешифрирования. Для шифрования 1024- байтового блока X:
(1) Разделите X на 256 32-битовых подблоков: X
0
, X
1
, X
2
, ..., X
255
(2) Переставьте подблоки X в соответствии с P.
(3) For r=0 to 3
For g = 0 to 63
A = X
(4g) <<< 2r
B = X
(4g+1) <<< 2r
C = X
(4g+2) <<< 2r
D = X
(4g+3) <<< 2r
For step s = 0 to 7
A = A ? (B + f r
(B, C, D) + S
512r+8g+s
)
TEMP = D
D = C
C = B
B = A <<< 5
A = TEMP
X
(4g) <<< 2r
= A
X
(4g+1) <<< 2r
= B
X
(4g+2) <<< 2r
= C
X
(4g+3) <<< 2r
= D
(4) Снова объединить X
0
, X
1
, X
2
, ..., X
255
, получая шифротекст.
Функции f r
(B, C, D) аналогичны используемым в MD5:
f
0
(B, C, D) = (B ? C) ? ((¬ B) ? D)
f
1
(B, C, D) = (B ? D) ? (C ? (¬ D))
f
2
(B, C, D) = B ? C ? D
f
3
(B, C, D) = C ? (B ? (¬ D))
Дешифрирование представляет собой обратный процесс. Генерирование подключей является непростой з а- дачей. Вот как по 80-битовому ключу K может быть сгенерирован массив перестановок P.
(1) Проинициализируйте K
0
, K
1
, K
2
, ..., K
9 10 байтами K.
(2) For i=10 to 255
K
i
= K
i-2
? K
i-6
? K
i-7
? K
i-10
(3) For i=10 to 255, P
i
= i

(4) m=0
(5) For j=0 to 1
For i = 256 to 1 step -1
m = (K
256-i
+ K
257-i
) mod i
K
257-i
= K
257-i
<<< 3
Переставить P
i и P
i-1
S-массив из 2048 32-битовых слов может быть сгенерирован аналогичным образом либо по тому же
80
_
битовому ключу, либо по другому ключу. Авторы предупреждают, что эти детали должны "рассматриваться только в качестве мотивации, могут быть и другие эффективные схемы, обеспечивающие лучшую безопасность"
[810].
Crab был предложен как испытательный стенд для новых идей, а не как рабочий алгоритм. Во многом он использует те же приемы, что и MD5. Бихам заметил, что очень большой блок упрощает криптоанализ алг о- ритма [160]. С другой стороны Crab может позволять эффективно использовать очень большой ключ. В этом случае "упрощение криптоанализа" может ничего не значить.
14.7 SXAL8/MBAL
Это 64-битовый блочный алгоритм из Японии [769]. SXAL8 - это основной алгоритм, а MBAL представляет собой расширенную версию с переменной длиной блока. Так как внутри MBAL выполняется ряд умных дейс т- вий, авторы утверждают, что они могут обеспечить достаточную безопасность за малое число этапов. При длине блока 1024 байта MBAL примерно в 70 раз быстрее, чем DES. К несчастью в [1174] показано, что MBAL чу в- ствителен к дифференциальному криптоанализу, а в [865] - что он чувствителен и к линейному криптоанал изу.
14.8 RC5
RC5 представляет собой блочный фильтр с большим числом параметров: размером блока, размером ключа и количеством этапов. Он был изобретен Роном Ривестом и проанализирован в RSA Laboratories [1324, 1325].
Используется три действия: XOR, сложение и циклические сдвиги. На большинстве процессоров операции циклического сдвига выполняются за постоянное время, переменные циклические сдвиги являются нелинейной функцией. Эти циклические сдвиги, зависящие и от ключа, и от данных, представляют собой интересную оп е- рацию.
RC5 использует блок переменной длины, но в приводимом примере мы остановимся на 64-битовом блоке данных. Шифрование использует 2r+2 зависящих от ключа 32-битовых слов - S
0
, S
1
, S
2
, ... S
2r+1
- где r - число этапов. Эти слова мы сгенерируем позднее. Для шифрования сначала разделим блок открытого текста на два
32-битовых слова: A и B. (RC5 предполагает следующее соглашение по упаковке байтов в слова: первый байт занимает младшие биты регистра A, и т.д.) Затем:
A = A + S
0
B = B + S
1
For i = 1 to r:
A = ((A ? B) <<< B) + S
2i
B = ((B ? A) <<< A) + S
2i+1
Результат находится в регистрах A и B.
Дешифрирование также просто. Разбейте блок открытого текста на два слова, A и B, а затем:
For i = r down to 1:
B = ((B - S
2i+1
) >>> A) ? A
A = ((A - S
2i
) >>> B) ? B
B = B - S
1
A = A - S
0
Символ ">>>" обозначает циклический сдвиг направо. Конечно же, все сложения и вычитания выполняются по модулю 2 32

Создание массива ключей более сложно, но также прямолинейно. Сначала, байты ключа копируются в ма с- сив L из c 32-битовых слов, дополняя при необходимости заключительное слово нулями. Затем массив S ини- циализируется при помощи линейного конгруэнтного генератора по модулю 2 32
:
S
0
= P
for i = 1 to 2(r + 1) - 1:
S
i
= (S
i-1
+ Q) mod 2 32
P = 0xb7e15163 и Q = 0x9e3779b9, эти константы основываются на двоичном представлении e и phi.
Наконец, подставляем L в S:
i = j = 0
A = B = 0
выполнить n раз (где n - максимум 2(r + 1) и c):
A = S
i
= (S
i
+ A + B) <<< 3
B = L
i
= (L
i
+ 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 этапов, 2 53
для 12 этапов и 2 68
для 15 этапов. Конечно же,
существует только 2 64
возможных открытых текстов, поэтому такое вскрытие неприменимо против алгоритма с
15 и более этапами. Оценка для линейного криптоанализа показывает, что алгоритм безопасен после 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 должно быть четным. Можно определить итеративный блочный шифр, в котором результат j-го этапа опреде- ляется результатом предыдущего этапа:
L
i
= R
i-1
R
i
= L
i-1
? f(R
i-1
, K
i
)
K
i
- это подключ, используемый на j-ом этапе, а f - это произвольная функция этапа.
Эту концепцию можно увидеть в DES, Lucifer, FEAL, Khufu, Khafre, LOKI, COST, CAST, Blowfish и других алгоритмах. Почему это так важно? Гарантируется, что эта функция является обращаемой. Так как для объед и- нения левой половины с результатом функции этапа используется XOR, следующее выражение обязательно я в- ляется истинным:
L
i-1
? f(R
i-1
, K
i
) ? f(R
i-1
, K
i
)= L
i-1
Гарантируется, что шифр, использующий такую конструкцию, обратим, если можно восстановить исходные данные f на каждом этапе. Сама функция f неважна, он не обязана быть обратимой. Мы можем спроектировать f настолько сложной, насколько захотим, и нам не потребуется реализовывать два различных алгоритма - один для шифрования, а другой для дешифрирования. Структура сети Фейстела автоматически позаботится об этом.
Простые соотношения
DES обладает следующим свойством: если E
K
(P) = C, то E
K'
(P') = C', где P', C' и K' - побитовые дополнения
P, C и K. Это свойство вдвое уменьшает сложность вскрытия грубой силой. Свойства комплиментарности алг о- ритма LOKI уменьшают сложность вскрытия грубой силой в 256 раз.
Простое соотношение можно определить как [857]:
Если E
K
(P) = C, то E
f(K)
(g(P,K)) = h(C,K)
где f, g и h - простые функции. Под "простыми функциями" я подразумеваю функции, которые вычисляются легко, намного легче, чем выполнение итерации блочного шифра. В DES f представляет собой побитовое л о- полнение K, g - побитовое дополнение P, а h - побитовое дополнение C. Это является результатом вкрапления ключа в часть текста с помощью XOR.

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