( англ. I nternational D ata E ncryption A lgorithm , международный алгоритм шифрования данных) — симметричный блочный алгоритм шифрования данных , запатентованный швейцарской фирмой . Известен тем, что применялся в пакете программ шифрования PGP . В ноябре 2000 года IDEA был представлен в качестве кандидата в проекте NESSIE в рамках программы Европейской комиссии IST ( англ. Information Societies Technology , информационные общественные технологии).

История

Первую версию алгоритма разработали в 1990 году Лай Сюэцзя ( Xuejia Lai ) и Джеймс Мэсси ( James Massey ) из Швейцарского института ETH Zürich (по контракту с , которая позже влилась в Ascom-Tech AG) в качестве замены DES ( англ. Data Encryption Standard , стандарт шифрования данных) и назвали её PES ( англ. Proposed Encryption Standard , предложенный стандарт шифрования). Затем, после публикации работ Бихама и Шамира по дифференциальному криптоанализу PES, алгоритм был улучшен с целью усиления криптостойкости и назван IPES ( англ. Improved Proposed Encryption Standard , улучшенный предложенный стандарт шифрования). Через год его переименовали в IDEA ( англ. International Data Encryption Algorithm ).

Описание

Так как IDEA использует 128-битный ключ и 64-битный размер блока , открытый текст разбивается на блоки по 64 бит. Если такое разбиение невозможно, последний блок дополняется различными способами определённой последовательностью бит. Для избежания утечки информации о каждом отдельном блоке используются различные режимы шифрования . Каждый исходный незашифрованный 64- битный блок делится на четыре подблока по 16 бит каждый, так как все алгебраические операции, использующиеся в процессе шифрования, совершаются над 16-битными числами. Для шифрования и расшифрования IDEA использует один и тот же алгоритм.

Фундаментальным нововведением в алгоритме является использование операций из разных алгебраических групп , а именно:

• сложение по модулю ${\displaystyle 2^{16}}$
• умножение по модулю ${\displaystyle 2^{16}+1}$
• побитовое исключающее ИЛИ ( XOR ).

Эти три операции несовместимы в том смысле, что:

• никакие две из них не удовлетворяют дистрибутивному закону, то есть ${\displaystyle a*(b+c)\ \neq \ (a*b)+(a*c)}$
• никакие две из них не удовлетворяют ассоциативному закону, то есть ${\displaystyle a+(b\oplus c)\ \neq \ (a+b)\oplus c}$

Применение этих трех операций затрудняет криптоанализ IDEA по сравнению с DES , который основан исключительно на операции исключающее ИЛИ , а также позволяет отказаться от использования S-блоков и таблиц замены. IDEA является модификацией сети Фейстеля .

Генерация ключей

Из 128-битного ключа для каждого из восьми раундов шифрования генерируется по шесть 16-битных подключей, а для выходного преобразования генерируется четыре 16-битных подключа. Всего потребуется 52 = 8 x 6 + 4 различных подключей по 16 бит каждый. Процесс генерации пятидесяти двух 16-битных ключей заключается в следующем:

• Первым делом, 128-битный ключ разбивается на восемь 16-битных блоков. Это будут первые восемь подключей по 16 бит каждый — ${\displaystyle (K_{1}^{(1)}K_{2}^{(1)}K_{3}^{(1)}K_{4}^{(1)}K_{5}^{(1)}K_{6}^{(1)}K_{1}^{(2)}K_{2}^{(2)})}$
• Затем этот 128-битный ключ циклически сдвигается влево на 25 позиций, после чего новый 128-битный блок снова разбивается на восемь 16-битных блоков. Это уже следующие восемь подключей по 16 бит каждый — ${\displaystyle (K_{3}^{(2)}K_{4}^{(2)}K_{5}^{(2)}K_{6}^{(2)}K_{1}^{(3)}K_{2}^{(3)}K_{3}^{(3)}K_{4}^{(3)})}$
• Процедура циклического сдвига и разбивки на блоки продолжается до тех пор, пока не будут сгенерированы все 52 16-битных подключа.

Таблица подключей для каждого раунда

Номер раунда	Подключи
1	${\displaystyle K_{1}^{(1)}K_{2}^{(1)}K_{3}^{(1)}K_{4}^{(1)}K_{5}^{(1)}K_{6}^{(1)}}$
2	${\displaystyle K_{1}^{(2)}K_{2}^{(2)}K_{3}^{(2)}K_{4}^{(2)}K_{5}^{(2)}K_{6}^{(2)}}$
3	${\displaystyle K_{1}^{(3)}K_{2}^{(3)}K_{3}^{(3)}K_{4}^{(3)}K_{5}^{(3)}K_{6}^{(3)}}$
4	${\displaystyle K_{1}^{(4)}K_{2}^{(4)}K_{3}^{(4)}K_{4}^{(4)}K_{5}^{(4)}K_{6}^{(4)}}$
5	${\displaystyle K_{1}^{(5)}K_{2}^{(5)}K_{3}^{(5)}K_{4}^{(5)}K_{5}^{(5)}K_{6}^{(5)}}$
6	${\displaystyle K_{1}^{(6)}K_{2}^{(6)}K_{3}^{(6)}K_{4}^{(6)}K_{5}^{(6)}K_{6}^{(6)}}$
7	${\displaystyle K_{1}^{(7)}K_{2}^{(7)}K_{3}^{(7)}K_{4}^{(7)}K_{5}^{(7)}K_{6}^{(7)}}$
8	${\displaystyle K_{1}^{(8)}K_{2}^{(8)}K_{3}^{(8)}K_{4}^{(8)}K_{5}^{(8)}K_{6}^{(8)}}$
выходное преобразование	${\displaystyle K_{1}^{(9)}K_{2}^{(9)}K_{3}^{(9)}K_{4}^{(9)}}$

Шифрование

Структура алгоритма IDEA показана на рисунке. Процесс шифрования состоит из восьми одинаковых раундов шифрования и одного выходного преобразования. Исходный незашифрованный текст делится на блоки по 64 бита. Каждый такой блок делится на четыре подблока по 16 бит каждый. На рисунке эти подблоки обозначены ${\displaystyle D_{1}}$ , ${\displaystyle D_{2}}$ , ${\displaystyle D_{3}}$ , ${\displaystyle D_{4}}$ . В каждом раунде используются свои подключи согласно таблице подключей. Над 16-битными подключами и подблоками незашифрованного текста производятся следующие операции:

• умножение по модулю ${\displaystyle 2^{16}+1}$ = 65537, причем вместо нуля используется ${\displaystyle 2^{16}}$
• сложение по модулю ${\displaystyle 2^{16}}$
• побитовое исключающее ИЛИ

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

• умножение по модулю ${\displaystyle 2^{16}+1}$
• сложение по модулю ${\displaystyle 2^{16}}$

После выполнения выходного преобразования конкатенация подблоков ${\displaystyle D_{1}'}$ , ${\displaystyle D_{2}'}$ , ${\displaystyle D_{3}'}$ и ${\displaystyle D_{4}'}$ представляет собой зашифрованный текст. Затем берется следующий 64-битный блок незашифрованного текста и алгоритм шифрования повторяется. Так продолжается до тех пор, пока не зашифруются все 64-битные блоки исходного текста.

Математическое описание

• Блок открытого текста размером 64 бит делится на четыре равных подблока размером по 16 бит ${\displaystyle (D_{1}^{(0)},D_{2}^{(0)},D_{3}^{(0)},D_{4}^{(0)})}$
• Для каждого раунда ${\displaystyle (i=1...8)}$ вычисляются:

${\displaystyle A^{(i)}\ =\ D_{1}^{(i-1)}*K_{1}^{(i)}}$
${\displaystyle B^{(i)}\ =\ D_{2}^{(i-1)}+K_{2}^{(i)}}$
${\displaystyle C^{(i)}\ =\ D_{3}^{(i-1)}+K_{3}^{(i)}}$
${\displaystyle D^{(i)}\ =\ D_{4}^{(i-1)}*K_{4}^{(i)}}$
${\displaystyle E^{(i)}\ =\ A^{(i)}\oplus C^{(i)}}$
${\displaystyle F^{(i)}\ =\ B^{(i)}\oplus D^{(i)}}$

${\displaystyle D_{1}^{(i)}\ =\ A^{(i)}\oplus ((F^{(i)}+E^{(i)}*K_{5}^{(i)})*K_{6}^{(i)})}$
${\displaystyle D_{2}^{(i)}\ =\ C^{(i)}\oplus ((F^{(i)}+E^{(i)}*K_{5}^{(i)})*K_{6}^{(i)})}$
${\displaystyle D_{3}^{(i)}\ =\ B^{(i)}\oplus (E^{(i)}*K_{5}^{(i)}+(F^{(i)}+E^{(i)}*K_{5}^{(i)})*K_{6}^{(i)})}$
${\displaystyle D_{4}^{(i)}\ =\ D^{(i)}\oplus (E^{(i)}*K_{5}^{(i)}+(F^{(i)}+E^{(i)}*K_{5}^{(i)})*K_{6}^{(i)})}$
Результатом выполнения восьми раундов будут следующие четыре подблока ${\displaystyle (D_{1}^{(8)},D_{2}^{(8)},D_{3}^{(8)},D_{4}^{(8)})}$

• Выполняется выходное преобразование ${\displaystyle (i=9)}$ :

${\displaystyle D_{1}^{(9)}\ =\ D_{1}^{(8)}*K_{1}^{(9)}}$
${\displaystyle D_{2}^{(9)}\ =\ D_{3}^{(8)}+K_{2}^{(9)}}$
${\displaystyle D_{3}^{(9)}\ =\ D_{2}^{(8)}+K_{3}^{(9)}}$
${\displaystyle D_{4}^{(9)}\ =\ D_{4}^{(8)}*K_{4}^{(9)}}$
Результатом выполнения выходного преобразования является зашифрованный текст ${\displaystyle (D_{1}^{(9)},D_{2}^{(9)},D_{3}^{(9)},D_{4}^{(9)})}$

Расшифровка

Метод вычисления, использующийся для расшифровки текста по существу такой же, как и при его шифровании. Единственное отличие состоит в том, что для расшифровки используются другие подключи. В процессе расшифровки подключи должны использоваться в обратном порядке. Первый и четвёртый подключи i-го раунда расшифровки получаются из первого и четвёртого подключа (10-i)-го раунда шифрования мультипликативной инверсией. Для 1-го и 9-го раундов второй и третий подключи расшифровки получаются из второго и третьего подключей 9-го и 1-го раундов шифрования аддитивной инверсией. Для раундов со 2-го по 8-й второй и третий подключи расшифровки получаются из третьего и второго подключей с 8-го по 2-й раундов шифрования аддитивной инверсией. Последние два подключа i-го раунда расшифровки равны последним двум подключам (9-i)-го раунда шифрования. Мультипликативная инверсия подключа K обозначается 1/K и ${\displaystyle (1/K)*K=1\ mod\ (2^{16}+1)}$ . Так как ${\displaystyle 2^{16}+1}$ — простое число , каждое целое не равное нулю K имеет уникальную мультипликативную инверсию по модулю ${\displaystyle 2^{16}+1}$ . Аддитивная инверсия подключа K обозначается -K и ${\displaystyle -K+K=0\ mod\ (2^{16})}$ .

Таблица подключей для каждого раунда

Номер раунда	Подключи
1	${\displaystyle 1/K_{1}^{(9)}\ -K_{2}^{(9)}\ -K_{3}^{(9)}\ 1/K_{4}^{(9)}\ K_{5}^{(8)}\ K_{6}^{(8)}}$
2	${\displaystyle 1/K_{1}^{(8)}\ -K_{3}^{(8)}\ -K_{2}^{(8)}\ 1/K_{4}^{(8)}\ K_{5}^{(7)}\ K_{6}^{(7)}}$
3	${\displaystyle 1/K_{1}^{(7)}\ -K_{3}^{(7)}\ -K_{2}^{(7)}\ 1/K_{4}^{(7)}\ K_{5}^{(6)}\ K_{6}^{(6)}}$
4	${\displaystyle 1/K_{1}^{(6)}\ -K_{3}^{(6)}\ -K_{2}^{(6)}\ 1/K_{4}^{(6)}\ K_{5}^{(5)}\ K_{6}^{(5)}}$
5	${\displaystyle 1/K_{1}^{(5)}\ -K_{3}^{(5)}\ -K_{2}^{(5)}\ 1/K_{4}^{(5)}\ K_{5}^{(4)}\ K_{6}^{(4)}}$
6	${\displaystyle 1/K_{1}^{(4)}\ -K_{3}^{(4)}\ -K_{2}^{(4)}\ 1/K_{4}^{(4)}\ K_{5}^{(3)}\ K_{6}^{(3)}}$
7	${\displaystyle 1/K_{1}^{(3)}\ -K_{3}^{(3)}\ -K_{2}^{(3)}\ 1/K_{4}^{(3)}\ K_{5}^{(2)}\ K_{6}^{(2)}}$
8	${\displaystyle 1/K_{1}^{(2)}\ -K_{3}^{(2)}\ -K_{2}^{(2)}\ 1/K_{4}^{(2)}\ K_{5}^{(1)}\ K_{6}^{(1)}}$
выходное преобразование	${\displaystyle 1/K_{1}^{(1)}\ -K_{2}^{(1)}\ -K_{3}^{(1)}\ 1/K_{4}^{(1)}}$

Пример

Для удобства числа представляем в шестнадцатеричном виде.

Пример шифрования

В качестве 128-битного ключа используем K = (0001,0002,0003,0004,0005,0006,0007,0008), а в качестве 64-битного открытого текста M = (0000,0001,0002,0003)

Таблица подключей и подблоков для каждого раунда

Раунд	Раундовые ключи						Значения блоков данных
	${\displaystyle K_{1}^{(i)}}$	${\displaystyle K_{2}^{(i)}}$	${\displaystyle K_{3}^{(i)}}$	${\displaystyle K_{4}^{(i)}}$	${\displaystyle K_{5}^{(i)}}$	${\displaystyle K_{6}^{(i)}}$	${\displaystyle D_{1}^{(i)}}$	${\displaystyle D_{2}^{(i)}}$	${\displaystyle D_{3}^{(i)}}$	${\displaystyle D_{4}^{(i)}}$
—	—	—	—	—	—	—	0000	0001	0002	0003
1	0001	0002	0003	0004	0005	0006	00f0	00f5	010a	0105
2	0007	0008	0400	0600	0800	0a00	222f	21b5	f45e	e959
3	0c00	0e00	1000	0200	0010	0014	0f86	39be	8ee8	1173
4	0018	001c	0020	0004	0008	000c	57df	ac58	c65b	ba4d
5	2800	3000	3800	4000	0800	1000	8e81	ba9c	f77f	3a4a
6	1800	2000	0070	0080	0010	0020	6942	9409	e21b	1c64
7	0030	0040	0050	0060	0000	2000	99d0	c7f6	5331	620e
8	4000	6000	8000	a000	c000	e001	0a24	0098	ec6b	4925
9	0080	00c0	0100	0140	-	-	11fb	ed2b	0198	6de5

Пример расшифровки

В качестве 128-битного ключа используем K = (0001,0002,0003,0004,0005,0006,0007,0008), а в качестве 64-битного зашифрованного текста C = (11fb, ed2b, 0198, 6de5)

Таблица подключей и подблоков для каждого раунда

Раунд	Раундовые ключи						Значения блоков данных
	${\displaystyle K_{1}^{'(i)}}$	${\displaystyle K_{2}^{'(i)}}$	${\displaystyle K_{3}^{'(i)}}$	${\displaystyle K_{4}^{'(i)}}$	${\displaystyle K_{5}^{'(i)}}$	${\displaystyle K_{6}^{'(i)}}$	${\displaystyle D_{1}^{(i)}}$	${\displaystyle D_{2}^{(i)}}$	${\displaystyle D_{3}^{(i)}}$	${\displaystyle D_{4}^{(i)}}$
1	fe01	ff40	ff00	659a	c000	e001	d98d	d331	27f6	82b8
2	fffd	8000	a000	cccc	0000	2000	bc4d	e26b	9449	a576
3	a556	ffb0	ffc0	52ab	0010	0020	0aa4	f7ef	da9c	24e3
4	554b	ff90	e000	fe01	0800	1000	ca46	fe5b	dc58	116d
5	332d	c800	d000	fffd	0008	000c	748f	8f08	39da	45cc
6	4aab	ffe0	ffe4	c001	0010	0014	3266	045e	2fb5	b02e
7	aa96	f000	f200	ff81	0800	0a00	0690	050a	00fd	1dfa
8	4925	fc00	fff8	552b	0005	0006	0000	0005	0003	000c
9	0001	fffe	fffd	c001	-	-	0000	0001	0002	0003

Режимы шифрования

IDEA является блочным алгоритмом шифрования, работающим с блоками по 64 бита. При несовпадении размера шифруемого текста с этим фиксированным размером, блок дополняется до 64.

Алгоритм используется в одном из следующих режимов шифрования :

• Режим электронной кодовой книги ( англ. Electronic Codebook (ECB) )
• Режим сцепления блоков шифротекста ( англ. Cipher Block Chaining (CBC) )
• Режим обратной связи по шифротексту ( англ. Cipher Feedback (CFB) )
• Режим обратной связи по выходу ( англ. Output Feedback (OFB) )

Алгоритм может также применяться для вычисления

• кода аутентификации сообщения ( англ. Message Authentication Code (MAC) )
• хеш -значений
• распределения ключей

Аппаратная реализация

Аппаратная реализация имеет перед программной следующие преимущества:

• существенное повышение скорости шифрования за счёт использования параллелизма при выполнении операций
• меньшее энергопотребление

Первая реализация алгоритма IDEA на интегральной схеме ( англ. Very Large Scale Integration ) была разработана и верифицирована Лаем, Мэсси и Мёрфи в 1992 году с использованием технологического процесса 1,5 мкм и технологии КМОП . Скорость шифрования данного устройства составляла 44 Мб/сек.

В 1994 году Каригером, Бонненбергом, Зиммерманом и др. было разработано устройство VINCI . Скорость шифрования данной реализации IDEA составляла 177 Мб/сек при тактовой частоте 25 МГц , техпроцесс 1,2 мкм. Это было первое полупроводниковое устройство, которое уже могло применяться для шифрования в реальном времени в таких высокоскоростных сетевых протоколах , как ATM ( англ. Asynchronous Transfer Mode , асинхронный способ передачи данных) или FDDI ( англ. Fiber Distributed Data Interface , распределённый волоконный интерфейс данных). Скорость 177 Мб/сек была достигнута благодаря использованию довольно изощрённой схемы конвейерной обработки и четырёх обычных умножителей по модулю ${\displaystyle 2^{16}+1}$ . В устройстве также используются два однонаправленных высокоскоростных 16-битных порта данных. Эти порты обеспечивают постоянную загруженность блоков шифрования .

Уже в следующем году Вольтер и др. представили устройство со скоростью шифрования 355 Мб/сек. Такой скорости удалось добиться благодаря реализации одного раунда шифрования на технологическом процессе 0,8 мкм с использованием технологии КМОП . Архитектура данного устройства включает в себя параллельное самотестирование, основанное на системе обработки ошибок с вычислениями по модулю 3, которая позволяет определять возникающие ошибки в одном или нескольких разрядах в тракте данных IDEA, что позволяет надёжно предотвращать искажения зашифрованных или расшифрованных данных .

Наибольшей скорости шифрования 424 Мб/сек в 1998 году на одной интегральной схеме достигла группа инженеров во главе с Саломао из на технологическом процессе 0,7 мкм при частоте 53 МГц. Архитектура данной реализации использует как пространственный, так и временной параллелизм, доступные в алгоритме IDEA .

В том же году IDEA Менсером и др. был реализован на четырёх устройствах XC4020XL. Скорость шифрования 4 x XC4020XL составляет 528 Мб/сек .

В 1999 году фирмой Ascom были представлены две коммерческие реализации IDEA. Первая называется IDEACrypt Kernel и достигает скорости 720 Мб/сек при использовании технологии 0,25 мкм . Вторая называется IDEACrypt Coprocessor, основана на IDEACrypt Kernel и достигает скорости шифрования 300 Мб/сек .

В 2000 году инженерами из Китайского университета Гонконга Лионгом и др. были выпущены устройства шифрования на ПЛИС фирмы Xilinx : Virtex XCV300-6 и XCV1000-6 . Скорость шифрования Virtex XCV300-6 достигает 500 Мб/сек при частоте 125 МГц, а предполагаемая производительность XCV1000-6 составляет 2,35 Гб/сек, что позволяет использовать данное устройство для шифрования в высокоскоростных сетях. Высокой скорости шифрования удалось достигнуть используя разрядно-последовательную архитектуру для выполнения операции умножения по модулю ${\displaystyle 2^{16}+1}$ . Результаты экспериментов с разными устройствами сведены в таблицу:

Характеристики устройств

Устройство (XCV)	300-6	600-6	1000-6
масштабируемость	1x	2x	4x
число секций	2801	5602	11204
использование секций	91,18 %	81,05 %	91,18 %
тактовая частота (МГц)	125,0	136,6	147,1
шифрований в сек (x ${\displaystyle 10^{6}}$ )	7,813	17,075	36,775
скорость шифрования (Мб/сек)	500,0	1092,8	2353,6
латентность (мкс)	7,384	6,757	6,275

Чуть позже теми же разработчиками была предложено устройство на ПЛИС фирмы Xilinx Virtex XCV300-6 на основе разрядно-параллельной архитектуры. При реализации с использованием разрядно-параллельной архитектуры при работе на частоте 82 МГц скорость шифрования XCV300-6 составляет 1166 Мб/сек, тогда как с разрядно-последовательной было достигнуто 600 Мб/сек на частоте 150 МГц. Устройство XCV300-6 с обеими архитектурами масштабируемо. С использованием разрядно-параллельной архитектуры предполагаемая скорость шифрования XCV1000-6 составляет 5,25 Гб/сек .

В том же 2000 году Гольдштейном и др. разработано устройство на PipeRench ПЛИС с использованием технологического процесса 0,25 мкм со скоростью шифрования 1013 Мб/сек .

Развитие аппаратных реализаций IDEA

Год	Реализация	Скорость шифрования (Мб/сек)	Авторы
1998	программная	23,53	Limpaa
2000	программная	44	Limpaa
1992	ASIC 1,5 мкм КМОП	44	Bonnenberg и др.
1994	ASIC 1,2 мкм КМОП	177	Curiger, Zimmermann и др.
1995	ASIC 0,8 мкм КМОП	355	Wolter и др.
1998	ASIC 0,7 мкм КМОП	424	Salomao и др.
1998	4 x XC4020XL	528	Mencer и др.
1999	ASIC 0,25 мкм КМОП	720	Ascom
2000	Xilinx Virtex XCV300-6	1166	Leong и др.
2000	ASIC 0,25 мкм КМОП	1013	Goldstein и др.

В 2002 году была опубликована работа о реализации IDEA на ПЛИС все той же фирмы Xilinx семейства Virtex-E. Устройство XCV1000E-6BG560 при частоте 105,9 МГц достигает скорости шифрования 6,78 Гб/сек.

Реализации на основе ПЛИС — хороший выбор, когда речь идёт о высокопроизводительной криптографии. Среди применений — VPN ( англ. Virtual Private Networks , виртуальная частная сеть), связь через спутник а также аппаратные ускорители для шифрования огромных файлов или жёстких дисков целиком.

Криптостойкость

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

• умножение подблока ${\displaystyle D_{2}}$ со вторым подключом раунда заменено сложением
• сложение подблока ${\displaystyle D_{4}}$ с четвёртым подключом раунда заменено на умножение
• изменён сдвиг подблоков в конце раунда

Один из наиболее известных в мире криптологов Брюс Шнайер в своей книге «Прикладная криптография» заметил: «…удивительно, как такие незначительные изменения могут привести к столь большим различиям».

В той же книге, вышедшей в 1996 году , Брюс Шнайер отозвался об IDEA так: «Мне кажется, это самый лучший и надежный блочный алгоритм, опубликованный до настоящего времени».

В алгоритме IDEA использует 64-битные блоки. Длина блока должна быть достаточной, чтобы скрыть статистические характеристики исходного сообщения. Но с увеличением размера блока экспоненциально возрастает сложность реализации криптографического алгоритма. В алгоритме IDEA используется 128-битный ключ. Длина ключа должна быть достаточно большой, чтобы предотвратить возможность перебора ключа. Для вскрытия 128-битного ключа полным перебором ключей при условии, что известен открытый и соответствующий ему зашифрованный текст, потребуется ${\displaystyle 2^{128}}$ (порядка ${\displaystyle 10^{38}}$ ) шифрований. При такой длине ключа IDEA считается довольно безопасным. Высокая криптостойкость IDEA обеспечивается также такими характеристиками:

• запутывание — шифрование зависит от ключа сложным и запутанным образом
• рассеяние — каждый бит незашифрованного текста влияет на каждый бит зашифрованного текста

Лай Сюэцзя ( Xuejia Lai ) и Джеймс Мэсси ( James Massey ) провели тщательный анализ IDEA с целью выяснения его криптостойкости к дифференциальному криптоанализу . Для этого ими было введено понятие марковского шифра и продемонстрировано, что устойчивость к дифференциальному криптоанализу может быть промоделирована и оценена количественно . Линейных или алгебраических слабостей у IDEA выявлено не было. Попытка вскрытия с помощью криптоанализа со связанными ключами, проведенная Бихамом ( Biham ), также не увенчалась успехом .

Существуют успешные атаки, применимые к IDEA с меньшим числом раундов (полный IDEA имеет 8.5 раундов). Успешной считается атака, если вскрытие шифра с её помощью требует меньшего количества операций, чем при полном переборе ключей. Метод вскрытия Вилли Майера ( Willi Meier ) оказался эффективнее вскрытия полным перебором ключей только для IDEA с 2 раундами . Методом « встреча посередине » был вскрыт IDEA с 4,5 раундами. Для этого требуется знание всех ${\displaystyle 2^{64}}$ блоков из словаря кодов и сложность анализа составляет ${\displaystyle 2^{112}}$ операций . Лучшая атака на 2007 год применима ко всем ключам и может взломать IDEA с 6-ю раундами .

Слабые ключи

Существуют большие классы . Слабые они в том смысле, что существуют процедуры, позволяющие определить, относится ли ключ к данному классу, а затем и сам ключ. В настоящее время известны следующие:

• ${\displaystyle 2^{23}+2^{35}+2^{51}}$ слабых к дифференциальному криптоанализу ключей. Принадлежность к классу ${\displaystyle 2^{51}}$ можно вычислить за ${\displaystyle 2^{12}}$ операций с помощью подобранного открытого текста. Авторы данной атаки предложили модификацию алгоритма IDEA. Данная модификация заключается в замене подключей ${\displaystyle K_{i}^{(r)}}$ на соответствующие ${\displaystyle K_{i}^{'(r)}\ =a\oplus K_{i}^{(r)}}$ , где r — номер раунда шифрования. Точное значение a не критично. Например при ${\displaystyle a\ =\ 0dae}$ (в шестнадцатеричной системе счисления ) данные слабые ключи исключаются .

• ${\displaystyle 2^{63}}$ слабых к линейному дифференциальному криптоанализу ключей . Принадлежность к данному классу выясняется с помощью теста на связанных ключах.

• ${\displaystyle 2^{53}+2^{56}+2^{64}}$ слабых ключей было найдено с использованием метода бумеранга ( англ. boomerang attack ), предложенного Дэвидом Вагнером ( David Wagner ) . Тест на принадлежность к данному классу выполняется за ${\displaystyle 2^{16}}$ операций и потребует ${\displaystyle 2^{16}}$ ячеек памяти .

Существование столь больших классов слабых ключей не влияет на практическую криптостойкость алгоритма IDEA, так как полное число всех возможных ключей равно ${\displaystyle 2^{128}}$ .

Сравнение с некоторыми блочными алгоритмами

Для сравнения с IDEA выбраны DES , Blowfish и ГОСТ 28147-89 . Выбор DES обусловлен тем, что IDEA проектировался как его замена. Blowfish выбран потому, что он быстр, и был придуман известным криптологом Брюсом Шнайером. Для сравнения также выбран ГОСТ 28147-89 , блочный шифр, разработанный в СССР . Как видно из таблицы, размер ключа у IDEA больше, чем у DES, но меньше, чем у ГОСТ 28147-89 и Blowfish. Скорость шифрования IDEA на Intel486SX /33МГц больше в 2 раза, чем у DES, выше чем у ГОСТ 28147-89, но почти в 2 раза меньше, чем у Blowfish.

Таблица параметров

Алгоритм	Размер ключа, бит	Длина блока, бит	Число раундов	Скорость шифрования на Intel486SX /33МГц (Кбайт/с)	Основные операции
DES	56	64	16	35	Подстановка, перестановка, побитовое исключающее ИЛИ
IDEA	128	64	8	70	Умножение по модулю ${\displaystyle 2^{16}+1}$ , сложение по модулю ${\displaystyle 2^{16}}$ , побитовое исключающее ИЛИ
Blowfish	32-448	64	16	135	Сложение по модулю ${\displaystyle 2^{32}}$ , подстановка, побитовое исключающее ИЛИ
ГОСТ 28147-89	256	64	32	53	Сложение по модулю ${\displaystyle 2^{32}}$ , подстановка, побитовое исключающее ИЛИ, циклический сдвиг

Далее приведена таблица сравнения скоростей в программной реализации на процессорах Pentium , Pentium MMX , Pentium II , Pentium III . Обозначение 4-way IDEA означает, что 4 операции шифрования или расшифрования выполняются параллельно. Для этого алгоритм используется в параллельных режимах шифрования. Хельгер Лимпа ( Helger Limpaa ) реализовал 4-way IDEA в режиме шифрования электронной кодовой книги (CBC4) и режиме счётчика (CTR4). Таким образом была достигнута скорость шифрования/расшифрования 260—275 Мбит/с при использовании CBC4 на 500 МГц Pentium III и при использовании CTR4 на 450 МГц Pentium III . В приведенной таблице скорости отмасштабированы на гипотетическую 3200 МГц машину.

Таблица сравнения скоростей

Блочный шифр	Длина блока, бит	Число циклов	Скорость шифрования, Мбайт/с	Автор	Процессор
Square	128	192	254,4	Limpaa	Pentium II
RC6	128	219	222,8	Limpaa	Pentium II , Pentium III
4-way IDEA	4x64	440	222,0	Limpaa	Pentium III
Rijndael	128	226	216,0	Limpaa	Pentium II , Pentium III
Square	128	244	200,0	Bosselaers	Pentium
4-way IDEA	4x64	543	180,0	Limpaa	Pentium MMX
SC2000	128	270	180,8	Limpaa	Pentium II , Pentium III , gcc (без asm )
4-way IDEA	4x64	554	176,4	Limpaa	AMD Athlon
Twofish	128	277	176,4	Aoki, Limpaa	Pentium II , Pentium III
Rijndael	128	300	162,8	Gladman	Pentium III
Camellia	128	302	161,6	Aoki	Pentium II , Pentium III
MARS	128	306	160,0	Limpaa	Pentium II , Pentium III
Blowfish	64	158	154,4	Bosselaers	Pentium
RC5-32/16	64	199	122,8	Bosselaers	Pentium
CAST5	64	220	110,8	Bosselaers	Pentium
DES	64	340	72,0	Bosselaers	Pentium
IDEA	64	358	68,0	Limpaa	Pentium MMX
SAFER (S)K-128	64	418	58,4	Bosselaers	Pentium
SHARK	64	585	41,6	Bosselaers	Pentium
IDEA	64	590	41,2	Bosselaers	Pentium
3DES	64	158	154,4	Bosselaers	Pentium

Преимущества и недостатки IDEA

Преимущества

В программной реализации на Intel486SX по сравнению с DES IDEA в два раза быстрее, что является существенным повышением скорости, длина ключа у IDEA имеет размер 128 бит, против 56 бит у DES, что является хорошим улучшением против полного перебора ключей. Вероятность использования слабых ключей очень мала и составляет ${\displaystyle 1/2^{64}}$ . IDEA быстрее алгоритма ГОСТ 28147-89 (в программной реализации на Intel486SX ). Использование IDEA в параллельных режимах шифрования на процессорах Pentium III и Pentium MMX позволяет получать высокие скорости. По сравнению с финалистами AES, 4-way IDEA лишь слегка медленнее, чем RC6 и Rijndael на Pentium II , но быстрее, чем Twofish и MARS . На Pentium III 4-way IDEA даже быстрее RC6 и Rijndael . Преимуществом также является хорошая изученность и устойчивость к общеизвестным средствам криптоанализа.

Недостатки

IDEA значительно медленнее, почти в два раза, чем Blowfish (в программной реализации на Intel486SX ). IDEA не предусматривает увеличение длины ключа.

Сравнение с некоторыми блочными шифрами в реализации PGP

Таблица сравнения основных параметров блочных шифров в реализации PGP

Алгоритм	Ключ, бит	Блок, бит	Примечания
Triple-DES	168	64	Сеть Фейстеля ; имеет пространство полуслабых и слабых ключей.
AES ( Rijndael )	256	128	Основан на операциях с таблицами массивов данных; принят в качестве гос. стандарта в США; обладает высокой криптостойкостью.
CAST6	128	64	Сеть Фейстеля ; не имеет слабых ключей;устойчив к криптоанализу.
IDEA	128	64	Основан на смешении операций из разных алгебраических групп; имеет пространство слабых ключей; не все работы по криптоанализу были опубликованы.
Twofish	256	128	Сеть Фейстеля ; быстр при шифровании, медленная установка ключа; устроен сравнительно сложно, что затрудняет анализ; имеет большой запас прочности.
Blowfish	max 448	64	Сеть Фейстеля ; быстр при шифровании, медленная установка ключа; сравнительно прост; имеет небольшое пространство слабых ключей; имеет большой запас прочности.

Применение IDEA

В прошлом алгоритм был запатентован во многих странах, а само название «IDEA» было зарегистрированной торговой маркой. Однако последний связанный с алгоритмом патент истёк в 2012, и теперь сам алгоритм может быть свободно использован в любых целях. В 2005 году MediaCrypt AG (лицензиат IDEA) официально представила новый шифр (первоначальное название FOX), призванный заменить IDEA. Типичные области применения IDEA:

• шифрование аудио и видео данных для кабельного телевидения , видеоконференций , дистанционного обучения , VoIP
• защита коммерческой и финансовой информации, отражающей колебания
• линии связи через модем , роутер или ATM линию, GSM технологию
• смарт-карты
• общедоступный пакет конфиденциальной версии электронной почты PGP v2.0 и (опционально) в OpenPGP

Регистрация алгоритма IDEA в стандартах

• : — регистрация криптографических алгоритмов в ISO
• UN/EDIFACT ( англ. United Nations/Electronic Data Interchange For Administration, Commerce, and Transport — ООН /обмен электронными данными для управления, коммерции и транспорта): — рекомендации по обеспечению безопасности
• — рекомендация H.233: конфиденциальная система для аудиовизуальных служб
• IETF ( англ. Internet Engineering Task Force — специальная комиссия интернет разработок) : Использование алгоритма шифрования IDEA в CMS
• — базовая безопасность службы дистанционной обработки данных
• OpenSSL — криптографический пакет с открытым исходным кодом для работы с SSL / TLS
• WAP ( англ. Wireless Application Protocol — протокол беспроводного доступа) WTLS ( англ. Wireless Transport Layer Security — безопасность транспортного уровня беспроводной передачи данных)
• ( англ. New European Schemes for Signature, Integrity, and Encryption — новые европейские проекты по цифровой подписи, целостности и шифрования)

Источники

• Xuejia Lai and James Massey. Предложение нового блочного стандарта шифрования = A Proposal for a New Block Encryption Standard, 1990. — Springer-Verlag, 1991. — P. 389—404. — ISBN 3-540-53587-X .
• Xuejia Lai and James Massey. Марковские шифры и дифференциальный криптоанализ = Markov ciphers and differential cryptanalysis, Advances in Cryptology, 1991. — Springer-Verlag, 1992. — P. 17—38. — ISBN 3540546200 .
• Menezes A. J. , Oorschot P. v. , Vanstone S. A. (англ.) — CRC Press , 1996. — 816 p. — ( ) — ISBN 978-0-8493-8523-0
• Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М. : Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4 .
• Hüseyin Demirci, Erkan Türe, Ali Aydin Selçuk. A New Meet in the Middle Attack on The IDEA Block Cipher : Материалы конф. / 10th Annual Workshop on Selected Areas in Cryptography, 2003.
• Helger Limpaa. IDEA: Шифр для мультимедиа архитектур? = IDEA: A cipher for multimedia architectures? In Stafford Tavares and Henk Meijer, editors, Selected Areas in Cryptography '98, volume 1556 of Lecture Notes in Computer Science — Springer-Verlag, 17—18 August 1998. — P. 248—263.

Примечания

Криптостойкость

Аппаратная реализация

Стандарты

Ссылки

• Аппаратный синтез криптоалгоритма IDEA

Реализации

• (англ.) . — реализации IDEA на языке программирования Ассемблер . Дата обращения: 6 ноября 2008. 28 января 2012 года.

Русские

• (рус.) . — по материалам конференции fido7.ru.crypt. Дата обращения: 6 ноября 2008. Архивировано из 22 августа 2011 года.
• (рус.) . — Анализ надежности блочных шифров в реализации PGP. Дата обращения: 6 ноября 2008.

Зарубежные

• (англ.) . Дата обращения: 6 ноября 2008. 19 октября 2004 года.
• (англ.) . Дата обращения: 6 ноября 2008. 28 января 2012 года.
• (нем.) . Дата обращения: 6 ноября 2008. 1 февраля 2012 года.
• (нем.) . Дата обращения: 6 ноября 2008. 28 января 2012 года.