Русская Википедия:IDEA
Шаблон:Другие значения Шаблон:Карточка блочного шифра IDEA (Шаблон:Lang-en, международный алгоритм шифрования данных) — симметричный блочный алгоритм шифрования данных, запатентованный швейцарской фирмой Ascom. Известен тем, что применялся в пакете программ шифрования PGP. В ноябре 2000 года IDEA был представлен в качестве кандидата в проекте NESSIE в рамках программы Европейской комиссии IST (Шаблон:Lang-en, информационные общественные технологии).
История
Первую версию алгоритма разработали в 1990 году Лай Сюэцзя (Xuejia Lai) и Джеймс Мэсси (James Massey) из Швейцарского института ETH Zürich (по контракту с Hasler Foundation, которая позже влилась в Ascom-Tech AG) в качестве замены DES (Шаблон:Lang-en, стандарт шифрования данных) и назвали её PES (Шаблон:Lang-en, предложенный стандарт шифрования). Затем, после публикации работ Бихама и Шамира по дифференциальному криптоанализу PES, алгоритм был улучшен с целью усиления криптостойкости и назван IPES (Шаблон:Lang-en, улучшенный предложенный стандарт шифрования). Через год его переименовали в IDEA (Шаблон:Lang-en).
Описание
Так как IDEA использует 128-битный ключ и 64-битный размер блока, открытый текст разбивается на блоки по 64 бит. Если такое разбиение невозможно, последний блок дополняется различными способами определённой последовательностью бит. Для избежания утечки информации о каждом отдельном блоке используются различные режимы шифрования. Каждый исходный незашифрованный 64-битный блок делится на четыре подблока по 16 бит каждый, так как все алгебраические операции, использующиеся в процессе шифрования, совершаются над 16-битными числами. Для шифрования и расшифрования IDEA использует один и тот же алгоритм.
Фундаментальным нововведением в алгоритме является использование операций из разных алгебраических групп, а именно:
- сложение по модулю <math>2^{16}</math>
- умножение по модулю <math>2^{16} + 1</math>
- побитовое исключающее ИЛИ (XOR).
Эти три операции несовместимы в том смысле, что:
- никакие две из них не удовлетворяют дистрибутивному закону, то есть <math>a*(b+c)\ \ne\ (a*b)+(a*c)</math>
- никакие две из них не удовлетворяют ассоциативному закону, то есть <math>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>(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>(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>K_1^{(1)}K_2^{(1)}K_3^{(1)}K_4^{(1)}K_5^{(1)}K_6^{(1)}</math> |
2 | <math>K_1^{(2)}K_2^{(2)}K_3^{(2)}K_4^{(2)}K_5^{(2)}K_6^{(2)}</math> |
3 | <math>K_1^{(3)}K_2^{(3)}K_3^{(3)}K_4^{(3)}K_5^{(3)}K_6^{(3)}</math> |
4 | <math>K_1^{(4)}K_2^{(4)}K_3^{(4)}K_4^{(4)}K_5^{(4)}K_6^{(4)}</math> |
5 | <math>K_1^{(5)}K_2^{(5)}K_3^{(5)}K_4^{(5)}K_5^{(5)}K_6^{(5)}</math> |
6 | <math>K_1^{(6)}K_2^{(6)}K_3^{(6)}K_4^{(6)}K_5^{(6)}K_6^{(6)}</math> |
7 | <math>K_1^{(7)}K_2^{(7)}K_3^{(7)}K_4^{(7)}K_5^{(7)}K_6^{(7)}</math> |
8 | <math>K_1^{(8)}K_2^{(8)}K_3^{(8)}K_4^{(8)}K_5^{(8)}K_6^{(8)}</math> |
выходное преобразование | <math>K_1^{(9)}K_2^{(9)}K_3^{(9)}K_4^{(9)}</math> |
Шифрование
Структура алгоритма IDEA показана на рисунке. Процесс шифрования состоит из восьми одинаковых раундов шифрования и одного выходного преобразования. Исходный незашифрованный текст делится на блоки по 64 бита. Каждый такой блок делится на четыре подблока по 16 бит каждый. На рисунке эти подблоки обозначены <math>D_1</math>, <math>D_2</math>, <math>D_3</math>, <math>D_4</math>. В каждом раунде используются свои подключи согласно таблице подключей. Над 16-битными подключами и подблоками незашифрованного текста производятся следующие операции:
- умножение по модулю <math>2^{16} + 1</math> = 65537, причем вместо нуля используется <math>2^{16}</math>
- сложение по модулю <math>2^{16}</math>
- побитовое исключающее ИЛИ
В конце каждого раунда шифрования имеется четыре 16-битных подблока, которые затем используются как входные подблоки для следующего раунда шифрования. Выходное преобразование представляет собой укороченный раунд, а именно, четыре 16-битных подблока на выходе восьмого раунда и четыре соответствующих подключа подвергаются операциям:
- умножение по модулю <math>2^{16} + 1</math>
- сложение по модулю <math>2^{16}</math>
После выполнения выходного преобразования конкатенация подблоков <math>D_1'</math>, <math>D_2'</math>, <math>D_3'</math> и <math>D_4'</math> представляет собой зашифрованный текст. Затем берется следующий 64-битный блок незашифрованного текста и алгоритм шифрования повторяется. Так продолжается до тех пор, пока не зашифруются все 64-битные блоки исходного текста.
Математическое описание
- Блок открытого текста размером 64 бит делится на четыре равных подблока размером по 16 бит <math>( D_1^{(0)}, D_2^{(0)}, D_3^{(0)}, D_4^{(0)} )</math>
- Для каждого раунда <math>( i=1...8 )</math> вычисляются:
<math>A^{(i)}\ =\ D_1^{(i-1)}*K_1^{(i)}</math>
<math>B^{(i)}\ =\ D_2^{(i-1)}+K_2^{(i)}</math>
<math>C^{(i)}\ =\ D_3^{(i-1)}+K_3^{(i)}</math>
<math>D^{(i)}\ =\ D_4^{(i-1)}*K_4^{(i)}</math>
<math>E^{(i)}\ =\ A^{(i)} \oplus C^{(i)}</math>
<math>F^{(i)}\ =\ B^{(i)} \oplus D^{(i)}</math>
<math>D_1^{(i)}\ =\ A^{(i)} \oplus ((F^{(i)} + E^{(i)}*K_5^{(i)})*K_6^{(i)})</math>
<math>D_2^{(i)}\ =\ C^{(i)} \oplus ((F^{(i)} + E^{(i)}*K_5^{(i)})*K_6^{(i)})</math>
<math>D_3^{(i)}\ =\ B^{(i)} \oplus (E^{(i)}*K_5^{(i)}+(F^{(i)} + E^{(i)}*K_5^{(i)})*K_6^{(i)})</math>
<math>D_4^{(i)}\ =\ D^{(i)} \oplus (E^{(i)}*K_5^{(i)}+(F^{(i)} + E^{(i)}*K_5^{(i)})*K_6^{(i)})</math>
Результатом выполнения восьми раундов будут следующие четыре подблока <math>( D_1^{(8)}, D_2^{(8)}, D_3^{(8)}, D_4^{(8)} )</math>
- Выполняется выходное преобразование <math>( i=9 )</math>:
<math>D_1^{(9)}\ =\ D_1^{(8)}*K_1^{(9)}</math>
<math>D_2^{(9)}\ =\ D_3^{(8)}+K_2^{(9)}</math>
<math>D_3^{(9)}\ =\ D_2^{(8)}+K_3^{(9)}</math>
<math>D_4^{(9)}\ =\ D_4^{(8)}*K_4^{(9)}</math>
Результатом выполнения выходного преобразования является зашифрованный текст <math>( 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>(1/K)*K=1\ mod\ (2^{16}+1)</math>. Так как <math>2^{16}+1</math> — простое число, каждое целое не равное нулю K имеет уникальную мультипликативную инверсию по модулю <math>2^{16}+1</math>. Аддитивная инверсия подключа K обозначается -K и <math>-K+K = 0\ mod\ (2^{16})</math>.
Номер раунда | Подключи |
---|---|
1 | <math>1/K_1^{(9)}\ -K_2^{(9)}\ -K_3^{(9)}\ 1/K_4^{(9)}\ K_5^{(8)}\ K_6^{(8)}</math> |
2 | <math>1/K_1^{(8)}\ -K_3^{(8)}\ -K_2^{(8)}\ 1/K_4^{(8)}\ K_5^{(7)}\ K_6^{(7)}</math> |
3 | <math>1/K_1^{(7)}\ -K_3^{(7)}\ -K_2^{(7)}\ 1/K_4^{(7)}\ K_5^{(6)}\ K_6^{(6)}</math> |
4 | <math>1/K_1^{(6)}\ -K_3^{(6)}\ -K_2^{(6)}\ 1/K_4^{(6)}\ K_5^{(5)}\ K_6^{(5)}</math> |
5 | <math>1/K_1^{(5)}\ -K_3^{(5)}\ -K_2^{(5)}\ 1/K_4^{(5)}\ K_5^{(4)}\ K_6^{(4)}</math> |
6 | <math>1/K_1^{(4)}\ -K_3^{(4)}\ -K_2^{(4)}\ 1/K_4^{(4)}\ K_5^{(3)}\ K_6^{(3)}</math> |
7 | <math>1/K_1^{(3)}\ -K_3^{(3)}\ -K_2^{(3)}\ 1/K_4^{(3)}\ K_5^{(2)}\ K_6^{(2)}</math> |
8 | <math>1/K_1^{(2)}\ -K_3^{(2)}\ -K_2^{(2)}\ 1/K_4^{(2)}\ K_5^{(1)}\ K_6^{(1)}</math> |
выходное преобразование | <math>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>K_1^{(i)}</math> | <math>K_2^{(i)}</math> | <math>K_3^{(i)}</math> | <math>K_4^{(i)}</math> | <math>K_5^{(i)}</math> | <math>K_6^{(i)}</math> | <math>D_1^{(i)}</math> | <math>D_2^{(i)}</math> | <math>D_3^{(i)}</math> | <math>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>K_1^{'(i)}</math> | <math>K_2^{'(i)}</math> | <math>K_3^{'(i)}</math> | <math>K_4^{'(i)}</math> | <math>K_5^{'(i)}</math> | <math>K_6^{'(i)}</math> | <math>D_1^{(i)}</math> | <math>D_2^{(i)}</math> | <math>D_3^{(i)}</math> | <math>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]:
- Режим электронной кодовой книги (Шаблон:Lang-en)
- Режим сцепления блоков шифротекста (Шаблон:Lang-en)
- Режим обратной связи по шифротексту (Шаблон:Lang-en)
- Режим обратной связи по выходу (Шаблон:Lang-en)
Алгоритм может также применяться для вычисления
- кода аутентификации сообщения (Шаблон:Lang-en)[ISO 2][ISO 3]
- хеш-значений[ISO 4]
- распределения ключей[ISO 5]
Аппаратная реализация
Аппаратная реализация имеет перед программной следующие преимущества:
- существенное повышение скорости шифрования за счёт использования параллелизма при выполнении операций
- меньшее энергопотребление
Первая реализация алгоритма IDEA на интегральной схеме(Шаблон:Lang-en) была разработана и верифицирована Лаем, Мэсси и Мёрфи в 1992 году с использованием технологического процесса 1,5 мкм и технологии КМОП [ИС 1]. Скорость шифрования данного устройства составляла 44 Мб/сек.
В 1994 году Каригером, Бонненбергом, Зиммерманом и др. было разработано устройство VINCI. Скорость шифрования данной реализации IDEA составляла 177 Мб/сек при тактовой частоте 25 МГц, техпроцесс 1,2 мкм. Это было первое полупроводниковое устройство, которое уже могло применяться для шифрования в реальном времени в таких высокоскоростных сетевых протоколах, как ATM (Шаблон:Lang-en, асинхронный способ передачи данных) или FDDI (Шаблон:Lang-en, распределённый волоконный интерфейс данных). Скорость 177 Мб/сек была достигнута благодаря использованию довольно изощрённой схемы конвейерной обработки и четырёх обычных умножителей по модулю <math>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>2^{16} + 1</math>. Результаты экспериментов с разными устройствами сведены в таблицу:
Устройство (XCV) | 300-6 | 600-6 | 1000-6 |
---|---|---|---|
масштабируемость | |||
число секций | |||
использование секций | |||
тактовая частота (МГц) | |||
шифрований в сек (x <math>10^6</math>) | |||
скорость шифрования (Мб/сек) | |||
латентность (мкс) |
Чуть позже теми же разработчиками была предложено устройство на ПЛИС фирмы Xilinx Virtex XCV300-6 на основе разрядно-параллельной архитектуры. При реализации с использованием разрядно-параллельной архитектуры при работе на частоте 82 МГц скорость шифрования XCV300-6 составляет 1166 Мб/сек, тогда как с разрядно-последовательной было достигнуто 600 Мб/сек на частоте 150 МГц. Устройство XCV300-6 с обеими архитектурами масштабируемо. С использованием разрядно-параллельной архитектуры предполагаемая скорость шифрования XCV1000-6 составляет 5,25 Гб/сек [ИС 10].
В том же 2000 году Гольдштейном и др. разработано устройство на PipeRench ПЛИС с использованием технологического процесса 0,25 мкм со скоростью шифрования 1013 Мб/сек [ИС 11].
Год | Реализация | Скорость шифрования (Мб/сек) | Авторы |
---|---|---|---|
1998 | |||
2000 | |||
1992 | |||
1994 | |||
1995 | |||
1998 | |||
1998 | |||
1999 | |||
2000 | |||
2000 |
В 2002 году была опубликована работа о реализации IDEA на ПЛИС все той же фирмы Xilinx семейства Virtex-E. Устройство XCV1000E-6BG560 при частоте 105,9 МГц достигает скорости шифрования 6,78 Гб/сек.[2]
Реализации на основе ПЛИС — хороший выбор, когда речь идёт о высокопроизводительной криптографии. Среди применений — VPN (Шаблон:Lang-en, виртуальная частная сеть), связь через спутник а также аппаратные ускорители для шифрования огромных файлов или жёстких дисков целиком.
Криптостойкость
Алгоритм IDEA появился в результате незначительных модификаций алгоритма PES. На рисунке приведены структуры обоих алгоритмов, и видно, что изменений не так уж и много:
- умножение подблока <math>D_2</math> со вторым подключом раунда заменено сложением
- сложение подблока <math>D_4</math> с четвёртым подключом раунда заменено на умножение
- изменён сдвиг подблоков в конце раунда
Один из наиболее известных в мире криптологов Брюс Шнайер в своей книге «Прикладная криптография» заметил: «…удивительно, как такие незначительные изменения могут привести к столь большим различиям».
В той же книге, вышедшей в 1996 году, Брюс Шнайер отозвался об IDEA так: «Мне кажется, это самый лучший и надежный блочный алгоритм, опубликованный до настоящего времени».
В алгоритме IDEA использует 64-битные блоки. Длина блока должна быть достаточной, чтобы скрыть статистические характеристики исходного сообщения. Но с увеличением размера блока экспоненциально возрастает сложность реализации криптографического алгоритма. В алгоритме IDEA используется 128-битный ключ. Длина ключа должна быть достаточно большой, чтобы предотвратить возможность перебора ключа. Для вскрытия 128-битного ключа полным перебором ключей при условии, что известен открытый и соответствующий ему зашифрованный текст, потребуется <math>2^{128}</math>(порядка <math>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>2^{64}</math> блоков из словаря кодов и сложность анализа составляет <math>2^{112}</math> операций [стойкость 4]. Лучшая атака на 2007 год применима ко всем ключам и может взломать IDEA с 6-ю раундами [стойкость 5].
Слабые ключи
Существуют большие классы слабых ключей. Слабые они в том смысле, что существуют процедуры, позволяющие определить, относится ли ключ к данному классу, а затем и сам ключ. В настоящее время известны следующие:
- <math>2^{23} + 2^{35} + 2^{51}</math> слабых к дифференциальному криптоанализу ключей. Принадлежность к классу <math>2^{51}</math> можно вычислить за <math>2^{12}</math> операций с помощью подобранного открытого текста. Авторы данной атаки предложили модификацию алгоритма IDEA. Данная модификация заключается в замене подключей <math>K_i^{(r)}</math> на соответствующие <math>K_i^{'(r)}\ = a \oplus K_i^{(r)}</math>, где r — номер раунда шифрования. Точное значение a не критично. Например при <math>a\ =\ 0dae</math> (в шестнадцатеричной системе счисления) данные слабые ключи исключаются[стойкость 6].
- <math>2^{63}</math> слабых к линейному дифференциальному криптоанализу ключей[стойкость 7]. Принадлежность к данному классу выясняется с помощью теста на связанных ключах.
- <math>2^{53} + 2^{56} + 2^{64}</math> слабых ключей было найдено с использованием метода бумеранга (Шаблон:Lang-en), предложенного Дэвидом Вагнером (David Wagner)[стойкость 8]. Тест на принадлежность к данному классу выполняется за <math>2^{16}</math> операций и потребует <math>2^{16}</math> ячеек памяти[стойкость 9].
Существование столь больших классов слабых ключей не влияет на практическую криптостойкость алгоритма IDEA, так как полное число всех возможных ключей равно <math>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 | |||||
IDEA | |||||
Blowfish | |||||
ГОСТ 28147-89 |
Далее приведена таблица сравнения скоростей в программной реализации на процессорах 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 | |||||
RC6 | |||||
4-way IDEA | |||||
Rijndael | |||||
Square | |||||
4-way IDEA | |||||
SC2000 | |||||
4-way IDEA | |||||
Twofish | |||||
Rijndael | |||||
Camellia | |||||
MARS | |||||
Blowfish | |||||
RC5-32/16 | |||||
CAST5 | |||||
DES | |||||
IDEA | |||||
SAFER (S)K-128 | |||||
SHARK | |||||
IDEA | |||||
3DES |
Преимущества и недостатки IDEA
Преимущества
В программной реализации на Intel486SX по сравнению с DES IDEA в два раза быстрее, что является существенным повышением скорости, длина ключа у IDEA имеет размер 128 бит, против 56 бит у DES, что является хорошим улучшением против полного перебора ключей. Вероятность использования слабых ключей очень мала и составляет <math>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
Алгоритм | Ключ, бит | Блок, бит | Примечания |
---|---|---|---|
Triple-DES | |||
AES (Rijndael) | |||
CAST6 | |||
IDEA | |||
Twofish | |||
Blowfish |
Применение IDEA
В прошлом алгоритм был запатентован во многих странах, а само название «IDEA» было зарегистрированной торговой маркой. Однако последний связанный с алгоритмом патент истёк в 2012, и теперь сам алгоритм может быть свободно использован в любых целях. В 2005 году MediaCrypt AG (лицензиат IDEA) официально представила новый шифр IDEA NXT (первоначальное название FOX), призванный заменить IDEA. Типичные области применения IDEA:
- шифрование аудио и видео данных для кабельного телевидения, видеоконференций, дистанционного обучения, VoIP
- защита коммерческой и финансовой информации, отражающей конъюнктурные колебания
- линии связи через модем, роутер или ATM линию, GSM технологию
- смарт-карты
- общедоступный пакет конфиденциальной версии электронной почты PGP v2.0[2] и (опционально) в OpenPGP
Регистрация алгоритма IDEA в стандартах
- ISO 9979/0002: ISO Register of Cryptographic Algorithms — регистрация криптографических алгоритмов в ISO
- UN/EDIFACT (Шаблон:Lang-en — ООН/обмен электронными данными для управления, коммерции и транспорта): EDIFACT Security Implementation Guidelines — рекомендации по обеспечению безопасности
- ITU-T Recommendation H.233: Confidentiality System for Audiovisual Services — рекомендация H.233: конфиденциальная система для аудиовизуальных служб
- IETF (Шаблон:Lang-en — специальная комиссия интернет разработок) RFC 3058: Использование алгоритма шифрования IDEA в CMS
- TBSS: Telematic Base Security Services — базовая безопасность службы дистанционной обработки данных
- OpenSSL — криптографический пакет с открытым исходным кодом для работы с SSL/TLS
- WAP (Шаблон:Lang-en — протокол беспроводного доступа) WTLS (Шаблон:Lang-en — безопасность транспортного уровня беспроводной передачи данных)
- NESSIE (Шаблон:Lang-en — новые европейские проекты по цифровой подписи, целостности и шифрования)
Источники
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Source
- Книга:Шнайер Б.: Прикладная криптография
- Шаблон:Статья
- Шаблон:Книга
Примечания
Криптостойкость
Аппаратная реализация
Стандарты
Ссылки
Реализации
Русские
Зарубежные
Шаблон:Симметричные криптоалгоритмы
Ошибка цитирования Для существующих тегов <ref>
группы «ISO» не найдено соответствующего тега <references group="ISO"/>
Ошибка цитирования Для существующих тегов <ref>
группы «ИС» не найдено соответствующего тега <references group="ИС"/>
Ошибка цитирования Для существующих тегов <ref>
группы «стойкость» не найдено соответствующего тега <references group="стойкость"/>