Первоначальный вариант алгоритма IDEA появился в 1990 г. Разработчики алгоритма, Ксуеджа Лай (Xuejia Lai) и Джеймс Мэсси (James Massey) из Швейцарского института ETH Zurich, дали ему название PES (Proposed Encryption Standard - предлагаемый стандарт шифрования), поскольку данный алгоритм был предложен на замену стандарта DES. Стоит отметить, что институт ETH Zurich и профессор Джеймс Мэсси известны также благодаря разработанным ими алгоритмам семейств SAFER/SAFER+/SAFER++.
Через год алгоритм был модифицирован с целью усиления криптостойкости к дифференциальному криптоанализу. Новая версия получила название IPES (Improved PES - улучшенный PES), а еще через год алгоритм сменил название на IDEA (International Data Encryption Algorithm - международный алгоритм шифрования данных).
Основные характеристики и структура
Алгоритм IDEA шифрует данные блоками по 64 бит, а ключ шифрования алгоритма имеет размер 128 бит. Блок шифруемых данных разбивается на четыре 16-битных субблока A, B, C и D (рис. 1), над которыми выполняется восемь раундов преобразований:
A = A [x] Kr1 B = B + Kr2 C = C + Kr3 D = D [x] Kr4 T1 = A [+] C T2 = B [+] D T1 = T1 [x] Kr5 T2 = T1 + T2 T2 = T2 [x] Kr6 T1 = T1 + T2 A = A [+] T2 B = B [+] T1 C = C [+] T2 D = D [+] T1,
где Krn - подключ n раунда r, "+" - операция сложения 16-битных операндов по модулю 2{в 16-й степени}, [+] - побитовая логическая операция "исключающее или" (XOR), [x] - умножение 16-битных операндов по модулю (2{в 16-й степени} + 1), причем в качестве значения субблока, состоящего из одних нулей, берется значение 2{в 16-й степени}.
![]() |
Рис. 1. Структура алгоритма IDEA.
|
После выполнения описанных выше действий два внутренних субблока (B и C) меняются местами - во всех раундах, кроме последнего. По завершении восьми раундов выполняются дополнительные преобразования (иногда называемые девятым раундом алгоритма):
A' = A [x] K91 B' = B + K92 C' = C + K93 D' = D [x] K94
Шифртекст представляет собой результат конкатенации полученных значений A', B', C' и D'.
Операция расшифрования аналогична зашифрованию, с той разницей, что при расшифровании используются модифицированные подключи и в другой последовательности:
K'r1 = (K(10-r)1)-1 K'r2 = -K(10-r)3 K'r3 = -K(10-r)2 K'r4 = (K(10-r)4)-1 K'r5 = K(9-r)5 K'r6 = K(9-r)6,
за исключением раундов 1 и 9, в которых подключи K'r2 и K'r3 меняются местами. Здесь K'rn - подключ n раунда расшифрования r, -x и x-1 - обратные значения x относительно описанных выше операций сложения по модулю 2{в 16-й степени} и умножения по модулю (2{в 16-й степени} + 1) соответственно. При этом 0{в -1-й степени} = 0.
Процедура расширения ключа
Задача процедуры расширения ключа - формирование 52 16-битных подключей, используемых в раундах шифрования и дополнительных преобразованиях (т. е. всего 832 бита ключевой информации). Данная процедура весьма проста, и выполняется она следующим образом:
- 128-битный ключ шифрования делится на восемь подключей по 16 бит; они становятся первыми восемью подключами алгоритма (K11, K12, K13, K14, K15, K16, K21, K22).
- Ключ шифрования циклически сдвигается влево на 25 бит.
- Результат делится на восемь следующих подключей.
- Ключ шифрования циклически сдвигается влево на 25 бит, и так далее до выработки необходимого количества подключей.
Криптостойкость алгоритма
Уже в следующем году после появления алгоритма PES его авторы опубликовали работу, в которой была доказана слабость алгоритма по отношению к дифференциальному криптоанализу (см., например, статью "Атаки на алгоритмы шифрования", "BYTE/Россия" No 11'2004): для определения ключа шифрования достаточно выполнения 2{в 64-й степени} операций шифрования, тогда как полный перебор значений 128-битного ключа потребовал бы выполнения 2{в 128-й степени} операций.
Алгоритм IDEA появился в результате достаточно незначительных модификаций алгоритма PES (рис. 2). Если сравнить схемы алгоритмов IDEA и PES, видно не так уж много отличий:
- операция умножения субблока B со вторым подключом раунда заменена операцией сложения,
- операция сложения субблока D с четвертым подключом раунда заменена операцией умножения,
- по-другому выполняется сдвиг субблоков в конце раунда.
![]() |
Рис. 2. Структура алгоритма PES.
|
Как заметил один из наиболее известных в мире специалистов-криптологов Брюс Шнайер (Bruce Schneier) в своей книге "Прикладная криптография", "...удивительно, как такие незначительные изменения могут привести к столь большим различиям". Алгоритм IDEA оказался фактически неуязвим к дифференциальному криптоанализу, а в той же книге (вышедшей в 1996 г.) Брюс Шнайер отозвался о нем следующим образом: "Мне кажется, это самый лучший и надежный блочный алгоритм, опубликованный до настоящего времени".
Однако в том же 1996 г. известный криптоаналитик Пол Кохер (Paul Kocher) изобрел достаточно сложно реализуемую атаку, позволяющую путем многократных высокоточных замеров времени выполнения шифрования 2{в 20-й степени} случайно выбранных открытых текстов на ключах, связанных определенным соотношением с искомым ключом, и последующего анализа результатов вычислить искомый ключ шифрования. Данная атака (как и другие атаки на связанных ключах) предполагает, что криптоаналитик не имеет прямого доступа к искомому ключу (например, ключ прошит в каком-либо аппаратном шифраторе или смарт-карте), но может изменять определенным образом различные фрагменты ключа.
А ранее, в 1993 г., несколько криптологов из Бельгии обнаружили в алгоритме IDEA несколько классов слабых ключей (всего 2{в 23-й степени} + 2{в 35-й степени} + 2{в 51-й степени} ключей различной степени слабости), часть из которых, например, можно вычислить криптоаналитической атакой с подобранным открытым текстом. Однако сами авторы данной атаки предложили "противоядие" - слабые ключи исключаются путем наложения операцией XOR специальной шестнадцатеричной константы 0DAE на каждый подключ перед его использованием.
Таким образом, несмотря на обнаруженные недостатки, алгоритм IDEA считается алгоритмом с высокой криптостойкостью. Неоспоримое же достоинство данного алгоритма - высокая скорость зашифрования, не менее, чем в два раза больше, чем у алгоритма DES (в зависимости от платформы, на которой выполняется шифрование). А возможность выполнения операции расширения ключа "на лету" (т. е. параллельно с выполнением раундов шифрования) весьма приветствуется и в более современных алгоритмах шифрования. Однако стоит сказать, что скорость расшифрования несколько снижается из-за наличия ресурсоемких операций вычисления мультипликативных обратных величин по модулю (2{в 16-й степени}+ 1).
***
Алгоритм IDEA не стал международным стандартом шифрования, как того желали его авторы. Однако его можно считать одним из наиболее распространенных в мире алгоритмов шифрования. IDEA используется до сих пор во множестве различных приложений, в том числе в широко известной и используемой программе защиты данных PGP.