Первоначальный вариант алгоритма 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-й степени}.

Fig.1 Рис. 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 бита ключевой информации). Данная процедура весьма проста, и выполняется она следующим образом:

  1. 128-битный ключ шифрования делится на восемь подключей по 16 бит; они становятся первыми восемью подключами алгоритма (K11, K12, K13, K14, K15, K16, K21, K22).
  2. Ключ шифрования циклически сдвигается влево на 25 бит.
  3. Результат делится на восемь следующих подключей.
  4. Ключ шифрования циклически сдвигается влево на 25 бит, и так далее до выработки необходимого количества подключей.

Криптостойкость алгоритма

Уже в следующем году после появления алгоритма PES его авторы опубликовали работу, в которой была доказана слабость алгоритма по отношению к дифференциальному криптоанализу (см., например, статью "Атаки на алгоритмы шифрования", "BYTE/Россия" No 11'2004): для определения ключа шифрования достаточно выполнения 2{в 64-й степени} операций шифрования, тогда как полный перебор значений 128-битного ключа потребовал бы выполнения 2{в 128-й степени} операций.

Алгоритм IDEA появился в результате достаточно незначительных модификаций алгоритма PES (рис. 2). Если сравнить схемы алгоритмов IDEA и PES, видно не так уж много отличий:

  • операция умножения субблока B со вторым подключом раунда заменена операцией сложения,
  • операция сложения субблока D с четвертым подключом раунда заменена операцией умножения,
  • по-другому выполняется сдвиг субблоков в конце раунда.

Fig.2 Рис. 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.