Патенты

И Khufu, и Khafre запатентованы [1072]. Исходный код этих алгоритмов содержится в патенте. При желании получить лицензию на любой или оба алгоритма следует обратиться к директору по лицензированию корпор а-ции Xerox (Director of Licensing, Xerox Corporation, P.O. Box 1600, Stamford, CT, 06904-1600).

13.8 RC2

RC2 представляет собой алгоритм с переменной длиной ключа, спроектированный Роном Ривестом (Ron Rivest) для RSA Data Security, Inc. (RSADSI). Очевидно "RC" - это сокращенное "Ron's Code" ("Код Рона"), хотя официально это "Rivest Cipher" ("Шифр Ривеста"). (RC3 был взломан в RSADSI в процессе разработки, RC1 не вышел за пределы записной книжки Ривеста.) Он представляет собой частную собственность, и его детали не были опубликованы. Не думайте ни минуты, что это увеличивает его безопасность. RC2 уже появился в ко м-мерческих продуктах. Насколько мне известно, RC2 не был запатентован и защищен только как торговый се к-рет.

RC2 - это шифр с 64-битовым блоком и переменной длиной ключа, предназначенный заменить DES. В соо т-ветствии с утверждениями компании программные реализации RC2 в три раза быстрее DES. Алгоритм может использовать ключ переменной длины, от 0 байтов до максимальной длины строки, поддерживаемой компь ю-терной системой, скорость шифрования не зависит от размера ключа. Этот ключ предварительно используется для заполнения 128-байтовой таблицы, зависящей от ключа. Поэтому множество действительно различных ключей составляет 21024. RC2 не использует S-блоков [805], используются две операции - "смешивание" и "перемешивание" ("mix" и "mash"), для каждого этапа выбирается одна из них. В соответствии с литературой [1334]:

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

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

Тем не менее, Рон Ривест - не шарлатан. Он уважаемый и компетентный криптограф. Я лично в значител ь-ной степени верю в этот алгоритм, хотя я лично и не видел кода. RC4, также являющийся интеллектуальной собственностью RSADSI, был опубликован в Internet (см. раздел 17.1), и, вероятно, опубликование RC2 являе т-ся только вопросом времени.

По соглашению между Ассоциацией издателей программного обеспечения (Software Publishers Association, SPA) и правительством США RC2 и RC4 (см. раздел 17.1) получили специальный экспортный статус (см. ра з-дел 25.14). Процесс получения разрешения на экспорт продуктов, реализующих один из этих двух алгоритмов, значительно упрощен при условии, что длина ключа не превышает 40 битов.

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

RSA Data Security, Inc., утверждает, что, хотя шифрование и дешифрирования выполняются для быстро, и с-черпывающего поиска потребуется намного больше времени. Заметное количество времени тратится на форм и-рование плана использования ключа. Хотя это время пренебрежимо мало при шифровании и дешифрировании сообщений, это не так при проверке каждого возможного ключа.

Правительство США никогда не позволило бы экспортировать любой алгоритм, который оно, по крайней мере в теории, не смогло бы вскрыть. Оно может создать магнитную ленту или CD с конкретным блоком о т-крытого текста, зашифрованным каждым возможным ключом. Для вскрытия сообщения остается только вст а-вить ленту и сравнить блоки шифротекста в сообщении с блоками шифротекста на ленте. При совпадении мо ж-но проверить возможный ключ и посмотреть, имеет ли сообщение какой-нибудь смысл. Если они выберут часто встречающийся блок (все нули, ASCII-символы пробела, и т.д.), этот метод будет работать. Объем данных, нужный для хранения результатов шифрования 64-битового блока открытого текста всеми 10 ^п возможными ключами, составляет 8 терабайтов - вполне реально. По поводу лицензирования RC2 обращайтесь в RSADSI (см. раздел 25.4).

IDEA

Первый вариант шифра IDEA, предложенный Ксуеджа Лай (Xuejia Lai) и Джеймсом Масси (James Massey), появился в 1990 году [929]. Он назывался PES (Proposed Encryption Standard, предложенный стандарт шифр о-вания). В следующем году, после демонстрации Бихамом и Шамиром возможностей дифференциального кри п-тоанализа, авторы усилили свой шифр против такого вскрытия и назвали новый алгоритм IPES (Improved Proposed Encryption Standard, улучшенный предложенный стандарт шифрования) [931, 924]. В 1992 году назв а-ние IPES было изменено на IDEA (International Data Encryption Algorithm, международный алгоритм шифров а-ния данных) [925].

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

Будущее IDEA пока неясно. Попыток заменить им DES предпринято не было, частично потому, что он зап а-тентован и должен быть лицензирован для коммерческих приложений, и частично потому, что люди пока все еще ждут, наблюдая насколько хорошо поведет себя алгоритм в предстоящие годы криптоанализа. Его сег о-

дняшняя известность объясняется тем, что он является частью PGP (см. раздел 24.12).

Обзор IDEA

IDEA является блочным шифром, он работает с 64-битовыми блоками открытого текста. Длина ключа - 128 битов. Для шифрования и дешифрирования используется один и тот же алгоритм.

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

— XOR

-Сложение по модулю 2¹⁶

- Умножение по модулю 2¹⁶ + 1. (Это операцию можно рассматривать как S-блок IDEA.)

Все эти операции (а в алгоритме используются только они, перестановки на битовом уровне не применяю т-ся) работают с 16-битовыми подблоками. Этот алгоритм даже эффективнее на 16-битовых процессорах.

Описание IDEA

Схема IDEA представлена на Рис. 13-9. 64-битовый блок данных делится на четыре 16-битовых подблока: Х_и Х₂, Х₃ и Х₄. Эти четыре подблока становятся входными данными для первого этапа алгоритма. Всего в алг о-ритме восемь этапов. На каждом этапе четыре подблока подвергаются операциям XOR, сложениям и умнож е-ниям друг с другом и с шестью 16-битовыми подключами. Между этапами обмениваются местами второй и третий подблоки. Наконец четыре подблока объединяются с четырьмя подключами в окончательном преобраз о-вании. На каждом этапе события происходят в следующей последовательности:

(1) Перемножаются Х\ и первый подключ.

(2) Складываются Х₂ и второй подключ.

(3) Складываются Х₃ и третий подключ.

(4) Перемножаются Х₄ и четвертый подключ.

(5) Выполняется XOR над результатами этапов (1) и (3).

(6) Выполняется XOR над результатами этапов (2) и (4).

(7) Перемножаются результаты этапа (5) и пятый подключ.

(8) Складываются результаты этапов (6) и (7).

(9) Перемножаются результаты этапа (8) и шестой подключ.

(10) Складываются результаты этапов (7) и (9).

(И) Выполняется XOR над результатами этапов (1) и (9).

(12) Выполняется XOR над результатами этапов (3) и (9).

(13) Выполняется XOR над результатами этапов (1) и (10).

(14) Выполняется XOR над результатами этапов (4) и (10).

Х2

Zl<1L>0Z2 (1L£]

один этап

еще

семь

этап

Х,

Х₃

Х_А

(9)

Выход

Z/LJ

Z₄

У Y₂

Уз

Ya

X: 16-битовый подблок открытого текста

Y, ■ 16-битовый подблок шифротекста

Z/^r): 16-битовый подблок ключа

Ф: побитовое "исключающее или" (xoR) 16-битовых подблоков

ЕВ: сложение по модулю 2¹⁶ 16-битовых целых

©: умножение по модулю 2¹⁶+1 16-битовых целых при условии,

что нулевой подблок соответствует 2

Рис. 13-9. IDEA.

Выходом этапа являются четыре подблока - результаты действий (И), (12), (13) и (14). Поменяйте местами два внутренних подблока (но не в последнем этапе), и вы получите исходные данные для следующего этапа.

После восьмого этапа выполняется заключительное преобразование:

(1) Перемножаются Х_х и первый подключ.

(2) Складываются Х₂ и второй подключ.

(3) Складываются Х₃ и третий подключ.

(4) Перемножаются Х₄ и четвертый подключ.

Наконец четыре подблока снова соединяются, образуя шифротекст.

Также несложно создавать подключи. Алгоритм использует 52 из них (шесть для каждого из восьми этапов и еще четыре для заключительного преобразования). Сначала 128-битовый ключ делится на восемь 16-битовых подключей. Это первые восемь подключей алгоритма (шесть для первого этапа и два - для второго). Затем ключ циклически сдвигается налево на 25 битов и снова делится на восемь подключей. Первые четыре используются на этапе 2, а оставшиеся четыре - на этапе 3. Ключ циклически сдвигается налево на 25 битов для получения следующих восьми подключей, и так до конца алгоритма.

Дешифрирование выполняется точно также за исключением того, что подключи инвертируются и слегка и з-меняются. Подключи при дешифрировании представляют собой обратные значения ключей шифрования по отношению к операциям либо сложения, либо умножения. (Для IDEA подблоки, состоящие из одних нулей, считаются равными 2¹⁶ = -1 для умножения по модулю 2¹⁶ + 1, следовательно, обратным значением 0 относи­тельно умножения является 0.) Эти вычисления могут занять некоторое время, но их нужно выполнить один раз для каждого ключа дешифрирования. В Табл. 13-4 представлены подключи шифрования и соответствующие

подключи дешифрирования.

Табл. 13-4. Подключи шифрования и дешифрирования IDEA

Этап	Подключи шифрования
	Z,m Z2(1)	z3w	z4w	z5w	z6(1)
	z/2) z2(2)	z/2>	z/2>	Z5p)	z6(2)
	z/3) z2(3)	z/3>	z4®	z5p)	z6(3)
	z/4) z2(4)	z/4>	z/4>	z/4>	z6(4)
	z/5) z2(5)	z3«	z4«	Z5(5)	z6(5)
	Z1(6) Z2(6)	z3(6)	z4®	z5(6)	z6(6)
	z/7) z2(7)	z/7>	z/7>	z/7>	z6(7)
	Zi(8) Z2(8)	z3(8)	z/8>	z/8>	z6(8)
заключительное	z/9> z/9>	z/9>	z/9>
преобразование

Подключи дешифрирования