IDEA

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
(перенаправлено с «International Data Encryption Algorithm»)
IDEA, International Data Encryption Algorithm
Создатель Ascom
Создан 1991 год
Опубликован 1991 год
Размер ключа 128 бит
Размер блока 64 бит
Число раундов 8.5
Тип модификация сети Фейстеля[1]

IDEA (англ. International Data Encryption Algorithm, международный алгоритм шифрования данных) — симметричный блочный алгоритм шифрования данных, запатентованный швейцарской фирмой Ascom. Известен тем, что применялся в пакете программ шифрования PGP. В ноябре 2000 года IDEA был представлен в качестве кандидата в проекте NESSIE в рамках программы Европейской комиссии IST (англ. Information Societies Technology, информационные общественные технологии).

История

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

Описание

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

Используемые обозначения операций

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

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

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

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

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

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

  • Первым делом, 128-битный ключ разбивается на восемь 16-битных блоков. Это будут первые восемь подключей по 16 бит каждый — [math]\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)}) }[/math]
  • Затем этот 128-битный ключ циклически сдвигается влево на 25 позиций, после чего новый 128-битный блок снова разбивается на восемь 16-битных блоков. Это уже следующие восемь подключей по 16 бит каждый — [math]\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)}) }[/math]
  • Процедура циклического сдвига и разбивки на блоки продолжается до тех пор, пока не будут сгенерированы все 52 16-битных подключа.
Таблица подключей для каждого раунда
Номер раунда Подключи
1 [math]\displaystyle{ K_1^{(1)}K_2^{(1)}K_3^{(1)}K_4^{(1)}K_5^{(1)}K_6^{(1)} }[/math]
2 [math]\displaystyle{ K_1^{(2)}K_2^{(2)}K_3^{(2)}K_4^{(2)}K_5^{(2)}K_6^{(2)} }[/math]
3 [math]\displaystyle{ K_1^{(3)}K_2^{(3)}K_3^{(3)}K_4^{(3)}K_5^{(3)}K_6^{(3)} }[/math]
4 [math]\displaystyle{ K_1^{(4)}K_2^{(4)}K_3^{(4)}K_4^{(4)}K_5^{(4)}K_6^{(4)} }[/math]
5 [math]\displaystyle{ K_1^{(5)}K_2^{(5)}K_3^{(5)}K_4^{(5)}K_5^{(5)}K_6^{(5)} }[/math]
6 [math]\displaystyle{ K_1^{(6)}K_2^{(6)}K_3^{(6)}K_4^{(6)}K_5^{(6)}K_6^{(6)} }[/math]
7 [math]\displaystyle{ K_1^{(7)}K_2^{(7)}K_3^{(7)}K_4^{(7)}K_5^{(7)}K_6^{(7)} }[/math]
8 [math]\displaystyle{ K_1^{(8)}K_2^{(8)}K_3^{(8)}K_4^{(8)}K_5^{(8)}K_6^{(8)} }[/math]
выходное преобразование [math]\displaystyle{ K_1^{(9)}K_2^{(9)}K_3^{(9)}K_4^{(9)} }[/math]

Шифрование

Схема шифрования IDEA

Структура алгоритма IDEA показана на рисунке. Процесс шифрования состоит из восьми одинаковых раундов шифрования и одного выходного преобразования. Исходный незашифрованный текст делится на блоки по 64 бита. Каждый такой блок делится на четыре подблока по 16 бит каждый. На рисунке эти подблоки обозначены [math]\displaystyle{ D_1 }[/math], [math]\displaystyle{ D_2 }[/math], [math]\displaystyle{ D_3 }[/math], [math]\displaystyle{ D_4 }[/math]. В каждом раунде используются свои подключи согласно таблице подключей. Над 16-битными подключами и подблоками незашифрованного текста производятся следующие операции:

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

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

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

После выполнения выходного преобразования конкатенация подблоков [math]\displaystyle{ D_1' }[/math], [math]\displaystyle{ D_2' }[/math], [math]\displaystyle{ D_3' }[/math] и [math]\displaystyle{ D_4' }[/math] представляет собой зашифрованный текст. Затем берется следующий 64-битный блок незашифрованного текста и алгоритм шифрования повторяется. Так продолжается до тех пор, пока не зашифруются все 64-битные блоки исходного текста.

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

  • Блок открытого текста размером 64 бит делится на четыре равных подблока размером по 16 бит [math]\displaystyle{ ( D_1^{(0)}, D_2^{(0)}, D_3^{(0)}, D_4^{(0)} ) }[/math]
  • Для каждого раунда [math]\displaystyle{ ( i=1...8 ) }[/math] вычисляются:

[math]\displaystyle{ A^{(i)}\ =\ D_1^{(i-1)}*K_1^{(i)} }[/math]
[math]\displaystyle{ B^{(i)}\ =\ D_2^{(i-1)}+K_2^{(i)} }[/math]
[math]\displaystyle{ C^{(i)}\ =\ D_3^{(i-1)}+K_3^{(i)} }[/math]
[math]\displaystyle{ D^{(i)}\ =\ D_4^{(i-1)}*K_4^{(i)} }[/math]
[math]\displaystyle{ E^{(i)}\ =\ A^{(i)} \oplus C^{(i)} }[/math]
[math]\displaystyle{ F^{(i)}\ =\ B^{(i)} \oplus D^{(i)} }[/math]

[math]\displaystyle{ D_1^{(i)}\ =\ A^{(i)} \oplus ((F^{(i)} + E^{(i)}*K_5^{(i)})*K_6^{(i)}) }[/math]
[math]\displaystyle{ D_2^{(i)}\ =\ C^{(i)} \oplus ((F^{(i)} + E^{(i)}*K_5^{(i)})*K_6^{(i)}) }[/math]
[math]\displaystyle{ D_3^{(i)}\ =\ B^{(i)} \oplus (E^{(i)}*K_5^{(i)}+(F^{(i)} + E^{(i)}*K_5^{(i)})*K_6^{(i)}) }[/math]
[math]\displaystyle{ D_4^{(i)}\ =\ D^{(i)} \oplus (E^{(i)}*K_5^{(i)}+(F^{(i)} + E^{(i)}*K_5^{(i)})*K_6^{(i)}) }[/math]
Результатом выполнения восьми раундов будут следующие четыре подблока [math]\displaystyle{ ( D_1^{(8)}, D_2^{(8)}, D_3^{(8)}, D_4^{(8)} ) }[/math]

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

[math]\displaystyle{ D_1^{(9)}\ =\ D_1^{(8)}*K_1^{(9)} }[/math]
[math]\displaystyle{ D_2^{(9)}\ =\ D_3^{(8)}+K_2^{(9)} }[/math]
[math]\displaystyle{ D_3^{(9)}\ =\ D_2^{(8)}+K_3^{(9)} }[/math]
[math]\displaystyle{ D_4^{(9)}\ =\ D_4^{(8)}*K_4^{(9)} }[/math]
Результатом выполнения выходного преобразования является зашифрованный текст [math]\displaystyle{ ( D_1^{(9)}, D_2^{(9)}, D_3^{(9)}, D_4^{(9)} ) }[/math]

Расшифровка

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

Таблица подключей для каждого раунда
Номер раунда Подключи
1 [math]\displaystyle{ 1/K_1^{(9)}\ -K_2^{(9)}\ -K_3^{(9)}\ 1/K_4^{(9)}\ K_5^{(8)}\ K_6^{(8)} }[/math]
2 [math]\displaystyle{ 1/K_1^{(8)}\ -K_3^{(8)}\ -K_2^{(8)}\ 1/K_4^{(8)}\ K_5^{(7)}\ K_6^{(7)} }[/math]
3 [math]\displaystyle{ 1/K_1^{(7)}\ -K_3^{(7)}\ -K_2^{(7)}\ 1/K_4^{(7)}\ K_5^{(6)}\ K_6^{(6)} }[/math]
4 [math]\displaystyle{ 1/K_1^{(6)}\ -K_3^{(6)}\ -K_2^{(6)}\ 1/K_4^{(6)}\ K_5^{(5)}\ K_6^{(5)} }[/math]
5 [math]\displaystyle{ 1/K_1^{(5)}\ -K_3^{(5)}\ -K_2^{(5)}\ 1/K_4^{(5)}\ K_5^{(4)}\ K_6^{(4)} }[/math]
6 [math]\displaystyle{ 1/K_1^{(4)}\ -K_3^{(4)}\ -K_2^{(4)}\ 1/K_4^{(4)}\ K_5^{(3)}\ K_6^{(3)} }[/math]
7 [math]\displaystyle{ 1/K_1^{(3)}\ -K_3^{(3)}\ -K_2^{(3)}\ 1/K_4^{(3)}\ K_5^{(2)}\ K_6^{(2)} }[/math]
8 [math]\displaystyle{ 1/K_1^{(2)}\ -K_3^{(2)}\ -K_2^{(2)}\ 1/K_4^{(2)}\ K_5^{(1)}\ K_6^{(1)} }[/math]
выходное преобразование [math]\displaystyle{ 1/K_1^{(1)}\ -K_2^{(1)}\ -K_3^{(1)}\ 1/K_4^{(1)} }[/math]

Пример

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

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

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

Таблица подключей и подблоков для каждого раунда
Раунд Раундовые ключи Значения блоков данных
[math]\displaystyle{ K_1^{(i)} }[/math] [math]\displaystyle{ K_2^{(i)} }[/math] [math]\displaystyle{ K_3^{(i)} }[/math] [math]\displaystyle{ K_4^{(i)} }[/math] [math]\displaystyle{ K_5^{(i)} }[/math] [math]\displaystyle{ K_6^{(i)} }[/math] [math]\displaystyle{ D_1^{(i)} }[/math] [math]\displaystyle{ D_2^{(i)} }[/math] [math]\displaystyle{ D_3^{(i)} }[/math] [math]\displaystyle{ D_4^{(i)} }[/math]
 — 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)

Таблица подключей и подблоков для каждого раунда
Раунд Раундовые ключи Значения блоков данных
[math]\displaystyle{ K_1^{'(i)} }[/math] [math]\displaystyle{ K_2^{'(i)} }[/math] [math]\displaystyle{ K_3^{'(i)} }[/math] [math]\displaystyle{ K_4^{'(i)} }[/math] [math]\displaystyle{ K_5^{'(i)} }[/math] [math]\displaystyle{ K_6^{'(i)} }[/math] [math]\displaystyle{ D_1^{(i)} }[/math] [math]\displaystyle{ D_2^{(i)} }[/math] [math]\displaystyle{ D_3^{(i)} }[/math] [math]\displaystyle{ D_4^{(i)} }[/math]
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.

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

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

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

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

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

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

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

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

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

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

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

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

Характеристики устройств
Устройство (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 [math]\displaystyle{ 10^6 }[/math])
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 Гб/сек [ИС 10].

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

Развитие аппаратных реализаций IDEA
Год Реализация Скорость шифрования (Мб/сек) Авторы
1998
программная
23,53
Limpaa
2000
программная [1]
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 Гб/сек.[2]

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

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

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

  • умножение подблока [math]\displaystyle{ D_2 }[/math] со вторым подключом раунда заменено сложением
  • сложение подблока [math]\displaystyle{ D_4 }[/math] с четвёртым подключом раунда заменено на умножение
  • изменён сдвиг подблоков в конце раунда

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

Структуры алгоритмов PES и IDEA

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

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

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

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

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

Слабые ключи

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

  • [math]\displaystyle{ 2^{23} + 2^{35} + 2^{51} }[/math] слабых к дифференциальному криптоанализу ключей. Принадлежность к классу [math]\displaystyle{ 2^{51} }[/math] можно вычислить за [math]\displaystyle{ 2^{12} }[/math] операций с помощью подобранного открытого текста. Авторы данной атаки предложили модификацию алгоритма IDEA. Данная модификация заключается в замене подключей [math]\displaystyle{ K_i^{(r)} }[/math] на соответствующие [math]\displaystyle{ K_i^{'(r)}\ = a \oplus K_i^{(r)} }[/math], где r — номер раунда шифрования. Точное значение a не критично. Например при [math]\displaystyle{ a\ =\ 0dae }[/math]шестнадцатеричной системе счисления) данные слабые ключи исключаются[стойкость 6].
  • [math]\displaystyle{ 2^{63} }[/math] слабых к линейному дифференциальному криптоанализу ключей[стойкость 7]. Принадлежность к данному классу выясняется с помощью теста на связанных ключах.
  • [math]\displaystyle{ 2^{53} + 2^{56} + 2^{64} }[/math] слабых ключей было найдено с использованием метода бумеранга (англ. boomerang attack), предложенного Дэвидом Вагнером (David Wagner)[стойкость 8]. Тест на принадлежность к данному классу выполняется за [math]\displaystyle{ 2^{16} }[/math] операций и потребует [math]\displaystyle{ 2^{16} }[/math] ячеек памяти[стойкость 9].

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

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

Для сравнения с 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
Умножение по модулю [math]\displaystyle{ 2^{16} + 1 }[/math], сложение по модулю [math]\displaystyle{ 2^{16} }[/math], побитовое исключающее ИЛИ
Blowfish
32-448
64
16
135
Сложение по модулю [math]\displaystyle{ 2^{32} }[/math], подстановка, побитовое исключающее ИЛИ
ГОСТ 28147-89
256
64
32
53
Сложение по модулю [math]\displaystyle{ 2^{32} }[/math], подстановка, побитовое исключающее ИЛИ, циклический сдвиг

Далее приведена таблица сравнения скоростей в программной реализации на процессорах 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, что является хорошим улучшением против полного перебора ключей. Вероятность использования слабых ключей очень мала и составляет [math]\displaystyle{ 1/2^{64} }[/math]. 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[2]
Алгоритм Ключ, бит Блок, бит Примечания
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) официально представила новый шифр IDEA NXT (первоначальное название FOX), призванный заменить IDEA. Типичные области применения IDEA:

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

Источники

  • Xuejia Lai and James Massey. Предложение нового блочного стандарта шифрования = A Proposal for a New Block Encryption Standard, EUROCRYPT 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, EUROCRYPT 1991. — Springer-Verlag, 1992. — P. 17—38. — ISBN 3540546200.
  • Шаблон:Source
  • Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = 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.

Примечания

  1. Menezes, Oorschot, Vanstone, 1996, pp. 263.
  2. Сравнительный обзор алгоритмов PGP. Дата обращения: 10 ноября 2008. Архивировано 13 мая 2012 года.
  3. S. Garfinkel. Довольно неплохая конфиденциальность = PGP: Pretty Good Privacy. — December 1, 1994. — 430 p. — ISBN 978-1565920989.

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

  1. X. Lai. On the Design and Security of Block Ciphers, ETH Series in Information Processing // Лекционные записи по теории вычислительных систем = Lecture Notes in Computer Science. — Berlin / Heidelberg: Springer-Verlag, 10 апреля 2006 г. — P. 213—222. — ISBN 978-3-540-62031-0.
  2. E. Biham, personal communication, 1993
  3. W. Meier, HTL. Brugg-Windisch, Switzerland. On the Security of the IDEA Block Cipher // Семинар по теории и применению криптографических техник в работе комиссии Advances in Сryptology EUROCRYPT '93 = Workshop on the theory and application of cryptographic techniques on Advances in Сryptology EUROCRYPT '93 Proceedings. — Secaucus, NJ, USA: Springer-Verlag New York, Inc, 1994. — P. 371—385. — ISBN 3-540-57600-2.
  4. Шаблон:Source
  5. E. Biham, O. Dunkelman, N. Keller. A New Attack on 6-Round IDEA // Лекционные записи по теории вычислительных систем = Lecture Notes In Computer Science. — Berlin / Heidelberg: Springer-Verlag, 18 августа 2007 г. — P. 211—224. — ISBN 978-3-540-74617-1.
  6. J. Daemen, R. Govaerts, and J. Vandewalle. Weak Keys for IDEA // Лекционные записи по теории вычислительных систем; Работа комиссии на 13-й ежегодной международной конференции по криптологии EUROCRYPT 1993 = Lecture Notes In Computer Science; Proceedings of the 13th Annual International Cryptology Conference on Advances in Cryptology. — London, UK: Springer-Verlag, 1993. — P. 224—231. — ISBN 3-540-57766-1.
  7. P. Hawkes. Differential-Linear Weak Key Classes of IDEA // Лекционные записи по теории вычислительных систем = Lecture Notes In Computer Science. — Berlin / Heidelberg: Springer-Verlag, 28 июля 2006 г. — P. 112—126. — ISBN 978-3-540-64518-4.
  8. D. Wagner. The Boomerang Attack // Лекционные записи по теории вычислительных систем; Работа комиссии на шестом международном семинаре по быстрому программному шифрованию = Lecture Notes In Computer Science; Proceedings of the 6th International Workshop on Fast Software Encryption. — London, UK: Springer-Verlag, 1999. — P. 156—170. — ISBN 3-540-66226-X.
  9. A. Biryukov, J. Nakahara Jr, B. Preneel, J. Vandewalle. New Weak-Key Classes of IDEA // Лекционные записи по теории вычислительных систем; Работа комиссии на четвёртой международной конференции по безопасности информации и связи = Lecture Notes In Computer Science; Proceedings of the 4th International Conference on Information and Communications Security. — London, UK: Springer-Verlag, 2002. — P. 315—326. — ISBN 3-540-00164-6. Архивная копия от 28 сентября 2011 на Wayback Machine

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

  1. H. Bonnenberg, A. Curiger, N. Felber, H. Kaeslin, and X. Lai. VLSI implementation of a new block cipher // Работа комиссии IEEE на международной конференции компьютерного проектирования: интегральные схемы в компьютерах и процессорах = Proceedings of the IEEE International Conference on Computer Design: VLSI in Computer and Processors. — Washington, DC, USA: IEEE Computer Society, 1991. — P. 510—513. — ISBN 0-8186-2270-9.
  2. A. Curiger, H. Bonnenberg, R. Zimmerman, N. Felber, H. Kaeslin, and W. Fichtner. VINCI: VLSI implementation of the new secret-key block cipher IDEA // Работа комиссии IEEE на конференции по специализированным интегральным микросхемам = Proceedings of the IEEE Custom Integrated Circuits Conference. — San Diego, CA, USA: IEEE Computer Society, 9-12 May 1993. — P. 15.5.1-15.5.4. — ISBN 0-7803-0826-3.
  3. R. Zimmermann, A. Curiger, H. Bonnenberg, H. Kaeslin, N. Felber, and W. Fichtner. A 177Mb/sec VLSI implementation of the international data encryption algorithm // IEEE Journal of Solid-State Circuits. — March 1994. — Т. 29. — С. 303—307.
  4. S. Wolter, H. Matz, A. Schubert, and R. Laur. On the VLSI implementation of the international data encryption algorithm IDEA // Работа комиссии IEEE на международном симпозиуме по схемам и системам = Proceedings of the IEEE International Symposium on Circuits and Systems. — Seattle, Washington, USA: IEEE Computer Society, 30 Apr-3 May 1995. — P. 397—400. — ISBN 0-7803-2570-2.
  5. S. L. C. Salomao, V. C. Alves, and E. M. C. Filho. HiPCrypto: A high-performance VLSI cryptographic chip // Работа комиссии на одиннадцатой ежегодной конференции IEEE по ASIC = Proceedings of the Eleventh Annual IEEE ASIC Conference. — Rochester, NY, USA: IEEE Computer Society, 13-16 Sep 1998. — P. 7—11. — ISBN 0-7803-4980-6.
  6. O. Mencer, M. Morf, and M. J. Flynn. Hardware software tri-design of encryption for mobile communication units // Работа комиссии IEEE на международной конференции по обработке акустики, речи и сигналов = Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing. — Seattle, Washington, USA: IEEE Computer Society, 12-15 May 1998. — P. 3045—3048. — ISBN 0-7803-4428-6.
  7. Ascom, IDEACrypt Kernel Data Sheet, 1999.
  8. Ascom, IDEACrypt Coprocessor Data Sheet, 1999.
  9. M. P. Leong, O. Y. H. Cheung, K. H. Tsoi and P. H. W. Leong. A Bit-Serial Implementation of the International Data Encryption Algorithm IDEA // Работа комиссии IEEE на симпозиуме 2000 по программируемым в условиях эксплуатации специализированным вычислительным машинам = Proceedings of the 2000 IEEE Symposium on Field-Programmable Custom Computing Machines. — Seattle, Washington, USA: IEEE Computer Society, 2000. — P. 122—131. — ISBN 0-7695-0871-5.
  10. O. Y. H. Cheung, K. H. Tsoi, P. H. W. Leong and M. P. Leong. Tradeoffs in Parallel and Serial Implementations of the International Data Encryption Algorithm IDEA // Криптографические аппаратные и встроенные системы 2001 = CHES 2001 : cryptographic hardware and embedded systems. — INIST-CNRS, Cote INIST : 16343, 35400009702003.0270: Springer, Berlin, ALLEMAGNE ETATS-UNIS (2001) (Monographie), 2001. — P. 333—347. — ISBN 3-540-42521-7.
  11. S. C. Goldstein, H. Schmit, M. Budiu, M. Moe, and R. R. Taylor. Piperench: A recongurable architecture and compiler // Computer. — April 2000. — Т. 33, № 4. — С. 70—77.

Стандарты

  1. ISO 10116: Information Processing — Modes of Operation for an n-bit block cipher algorithm.
  2. ISO 9797: Data cryptographic techniques — Data integrity mechanism using a cryptographic check function employing a block cipher algorithm.
  3. ISO 9798-2: Information technology — Security technicues — Entity authentication mechanisms — Part 2: Entity authentication using symmetric techniques.
  4. ISO 10118-2: Information technology — Security technicues — Hash-functions — Part 2: Hash-functions using an n-bit block cipher algorithm.
  5. ISO 11770-2: Information technology — Security technicues — Key management — Part 2: Key management mechanisms using symmetric techniques.

Ссылки

Реализации

Русские

Зарубежные