Скорость IDEA
Ya
Х,
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
-Сложение по модулю 216
- Умножение по модулю 216 + 1. (Это операцию можно рассматривать как S-блок IDEA.)
Все эти операции (а в алгоритме используются только они, перестановки на битовом уровне не применяю т-ся) работают с 16-битовыми подблоками. Этот алгоритм даже эффективнее на 16-битовых процессорах.
Описание IDEA
Схема IDEA представлена на Рис. 13-9. 64-битовый блок данных делится на четыре 16-битовых подблока: Хи Х2, Х3 и Х4. Эти четыре подблока становятся входными данными для первого этапа алгоритма. Всего в алг о-ритме восемь этапов. На каждом этапе четыре подблока подвергаются операциям XOR, сложениям и умнож е-ниям друг с другом и с шестью 16-битовыми подключами. Между этапами обмениваются местами второй и третий подблоки. Наконец четыре подблока объединяются с четырьмя подключами в окончательном преобраз о-вании. На каждом этапе события происходят в следующей последовательности:
(1) Перемножаются Х\ и первый подключ.
(2) Складываются Х2 и второй подключ.
(3) Складываются Х3 и третий подключ.
(4) Перемножаются Х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£] |
один этап
еще
семь
этап
Х3
ХА
|
| ( 9 ) |
Выход
Z/LJ
Z4
У Y2
Уз
X : 16-битовый подблок открытого текста
Y, ■ 16-битовый подблок шифротекста
Z/r) : 16-битовый подблок ключа
Ф : побитовое "исключающее или" (xoR) 16-битовых подблоков
ЕВ: сложение по модулю 216 16-битовых целых
© : умножение по модулю 216+1 16-битовых целых при условии,
что нулевой подблок соответствует 2
Рис. 13-9. IDEA.
Выходом этапа являются четыре подблока - результаты действий (И), (12), (13) и (14). Поменяйте местами два внутренних подблока (но не в последнем этапе), и вы получите исходные данные для следующего этапа.
После восьмого этапа выполняется заключительное преобразование:
(1) Перемножаются Хх и первый подключ.
(2) Складываются Х2 и второй подключ.
(3) Складываются Х3 и третий подключ.
(4) Перемножаются Х4 и четвертый подключ.
Наконец четыре подблока снова соединяются, образуя шифротекст.
Также несложно создавать подключи. Алгоритм использует 52 из них (шесть для каждого из восьми этапов и еще четыре для заключительного преобразования). Сначала 128-битовый ключ делится на восемь 16-битовых подключей. Это первые восемь подключей алгоритма (шесть для первого этапа и два - для второго). Затем ключ циклически сдвигается налево на 25 битов и снова делится на восемь подключей. Первые четыре используются на этапе 2, а оставшиеся четыре - на этапе 3. Ключ циклически сдвигается налево на 25 битов для получения следующих восьми подключей, и так до конца алгоритма.
Дешифрирование выполняется точно также за исключением того, что подключи инвертируются и слегка и з-меняются. Подключи при дешифрировании представляют собой обратные значения ключей шифрования по отношению к операциям либо сложения, либо умножения. (Для IDEA подблоки, состоящие из одних нулей, считаются равными 216 = -1 для умножения по модулю 216 + 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> | ||
| преобразование |
Подключи дешифрирования
| Z (9-и | -z/9> | -z3(9) | z (9)~1 | z^ | z6(8) |
| 7 С8)-1 | -z/8> | -z3(8) | 7 (8)-l | z5<7> | z6(7) |
| z (7-и | -z/7> | -z3(7) | z (7)~1 | z5(6) | z6(6) |
| 7 W"1 | -z2® | -z3(6) | 7 (6)-l | Z5(5) | z6(5) |
| Z (5-и | -z2« | -Zs(5) | z (5)_1 | z5<4> | z6(4) |
| Z (4)_1 | -z/4> | -z/4> | z (4)_1 | z5p) | z6(3) |
| Z (3-и | -z/3> | -z/3> | Z (3)"1 | Z5p) | z6(2) |
| Z (2-и | -z/2> | -z/2> | z (2)_1 | z5« | z6(1) |
| Z (1-и | -z2« | -z3« | z (1)_1 |
Современные программные реализации IDEA примерно в два раза быстрее, чем DES. На компьютере с i386/33 МГц IDEA шифрует данные со скоростью 880 Кбит/с, а на компьютере с i486/33 МГц - со скоростью 2400 Кбит/с. Вы могли подумать, что IDEA должен был быть побыстрее, но умножения - недешевое удовольс т-вие. Умножение двух 32-битовых чисел на процессоре i486 занимает 40 тактов (10 на процессоре Pentium).
Реализация PES на базе СБИС шифрует данные со скоростью 55 Мбит/с при тактовой частоте 25 МГц [208,398]. Другая СБИС, разработанная ЕТН Zurich и состоящая из of 251000 транзисторов на кристалле пл о-щадью 107.8 мм2, шифрует данные с помощью алгоритма IDEA со скоростью 177 Мбит/с при тактовой частоте 25 МГц [926, 207, 397].