15-10-2023
IDEA, International Data Encryption Algorithm | |
Создатель: | |
---|---|
Создан: | |
Опубликован: | |
Размер ключа: |
128 бит |
Размер блока: |
64 бит |
Число раундов: |
8.5 |
Тип: |
модификация сети Фейстеля[1] |
IDEA (NESSIE в рамках программы Европейской комиссии IST (англ. Information Societes 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 использует один и тот же алгоритм.
Фундаментальным нововведением в алгоритме является использование операций из разных алгебраических групп, а именно:
Эти три операции несовместимы в том смысле, что:
Применение этих трех операций затрудняет криптоанализ IDEA по сравнению с DES, который основан исключительно на операции исключающее ИЛИ, а также позволяет отказаться от использования S-блоков и таблиц замены. IDEA является модификацией сети Фейстеля.
Из 128-битного ключа для каждого из восьми раундов шифрования генерируется по шесть 16-битных подключей, а для выходного преобразования генерируется четыре 16-битных подключа. Всего потребуется 52 = 8 x 6 + 4 различных подключей по 16 бит каждый. Процесс генерации пятидесяти двух 16-битных ключей заключается в следующем:
Номер раунда | Подключи |
---|---|
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
выходное преобразование |
Структура алгоритма IDEA показана на рисунке. Процесс шифрования состоит из восьми одинаковых раундов шифрования и одного выходного преобразования. Исходный незашифрованный текст делится на блоки по 64 бита. Каждый такой блок делится на четыре подблока по 16 бит каждый. На рисунке эти подблоки обозначены , , , . В каждом раунде используются свои подключи согласно таблице подключей. Над 16-битными подключами и подблоками незашифрованного текста производятся следующие операции:
В конце каждого раунда шифрования имеется четыре 16-битных подблока, которые затем используются как входные подблоки для следующего раунда шифрования. Выходное преобразование представляет собой укороченный раунд, а именно, четыре 16-битных подблока на выходе восьмого раунда и четыре соответствующих подключа подвергаются операциям:
После выполнения выходного преобразования конкатенация подблоков , , и представляет собой зашифрованный текст. Затем берется следующий 64-битный блок незашифрованного текста и алгоритм шифрования повторяется. Так продолжается до тех пор, пока не зашифруются все 64-битные блоки исходного текста.
Результатом выполнения восьми раундов будут следующие четыре подблока
Результатом выполнения выходного преобразования является зашифрованный текст
Метод вычисления, использующийся для расшифровки текста по существу такой же, как и при его шифровании. Единственное отличие состоит в том, что для расшифровки используются другие подключи. В процессе расшифровки подключи должны использоваться в обратном порядке. Первый и четвёртый подключи i-го раунда расшифровки получаются из первого и четвёртого подключа (10-i)-го раунда шифрования мультипликативной инверсией. Для 1-го и 9-го раундов второй и третий подключи расшифровки получаются из второго и третьего подключей 9-го и 1-го раундов шифрования аддитивной инверсией. Для раундов со 2-го по 8-й второй и третий подключи расшифровки получаются из третьего и второго подключей с 8-го по 2-й раундов шифрования аддитивной инверсией. Последние два подключа i-го раунда расшифровки равны последним двум подключам (9-i)-го раунда шифрования. Мультипликативная инверсия подключа K обозначается 1/K и . Так как — простое число, каждое целое не равное нулю K имеет уникальную мультипликативную инверсию по модулю . Аддитивная инверсия подключа K обозначается -K и .
Номер раунда | Подключи |
---|---|
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
выходное преобразование |
Для удобства числа представляем в шестнадцатеричном виде.
В качестве 128-битного ключа используем K = (0001,0002,0003,0004,0005,0006,0007,0008), а в качестве 64-битного открытого текста M = (0000,0001,0002,0003)
Раунд | Раундовые ключи | Значения блоков данных | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
— | — | — | — | — | — | - | 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)
Раунд | Раундовые ключи | Значения блоков данных | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
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 Мб/сек была достигнута благодаря использованию довольно изощрённой схемы конвейерной обработки и четырёх обычных умножителей по модулю . В устройстве также используются два однонаправленных высокоскоростных 16-битных порта данных. Эти порты обеспечивают постоянную загруженность блоков шифрования[ИС 2] [ИС 3].
Уже в следующем году Вольтер и др. представили устройство со скоростью шифрования 355 Мб/сек. Такой скорости удалось добиться благодаря реализации одного раунда шифрования на технологическом процессе 0,8 мкм с использованием технологии КМОП. Архитектура данного устройства включает в себя параллельное самотестирование, основанное на системе обработки ошибок с вычислениями по модулю 3, которая позволяет определять возникающие ошибки в одном или нескольких разрядах в тракте данных IDEA, что позволяет надёжно предотвращать искажения зашифрованных или расшифрованных данных [ИС 4].
Наибольшей скорости шифрования 424 Мб/сек в 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 Гб/сек, что позволяет использовать данное устройство для шифрования в высокоскоростных сетях. Высокой скорости шифрования удалось достигнуть используя разрядно-последовательную архитектуру для выполнения операции умножения по модулю . Результаты экспериментов с разными устройствами сведены в таблицу:
Устройство (XCV) | 300-6 | 600-6 | 1000-6 |
---|---|---|---|
масштабируемость |
|
|
|
число секций |
|
|
|
использование секций |
|
|
|
тактовая частота (МГц) |
|
|
|
шифрований в сек (x ) |
|
|
|
скорость шифрования (Мб/сек) |
|
|
|
латентность (мкс) |
|
|
|
Чуть позже теми же разработчиками была предложено устройство на ПЛИС фирмы 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 |
|
|
|
В [2]
Реализации на основе ПЛИС — хороший выбор, когда речь идёт о высокопроизводительной криптографии. Среди применений — VPN (англ. Virtual Private Networks, виртуальная частная сеть), связь через спутник а также аппаратные ускорители для шифрования огромных файлов или жёстких дисков целиком.
Алгоритм IDEA появился в результате незначительных модификаций алгоритма PES. На рисунке приведены структуры обоих алгоритмов, и видно, что изменений не так уж и много:
Один из наиболее известных в мире криптологов Брюс Шнайер в своей книге «Прикладная криптография» заметил: «…удивительно, как такие незначительные изменения могут привести к столь большим различиям».
В той же книге, вышедшей в 1996 году, Брюс Шнайер отозвался об IDEA так: «Мне кажется, это самый лучший и надежный блочный алгоритм, опубликованный до настоящего времени».
В алгоритме IDEA использует 64-битные блоки. Длина блока должна быть достаточной, чтобы скрыть статистические характеристики исходного сообщения. Но с увеличением размера блока экспоненциально возрастает сложность реализации криптографического алгоритма. В алгоритме IDEA используется 128-битный ключ. Длина ключа должна быть достаточно большой, чтобы предотвратить возможность перебора ключа. Для вскрытия 128-битного ключа полным перебором ключей при условии, что известен открытый и соответствующий ему зашифрованный текст, потребуется (порядка ) шифрований. При такой длине ключа IDEA считается довольно безопасным. Высокая криптостойкость IDEA обеспечивается также такими характеристиками:
Лай Сюэцзя (Xuejia Lai) и Джеймс Мэсси (James Massey) провели тщательный анализ IDEA с целью выяснения его криптостойкости к дифференциальному криптоанализу. Для этого ими было введено понятие марковского шифра и продемонстрировано, что устойчивость к дифференциальному криптоанализу может быть промоделирована и оценена количественно [стойкость 1]. Линейных или алгебраических слабостей у IDEA выявлено не было. Попытка вскрытия с помощью криптоанализа со связанными ключами, проведенная Бихамом (Biham), также не увенчалась успехом [стойкость 2].
Существуют успешные атаки, применимые к IDEA с меньшим числом раундов (полный IDEA имеет 8.5 раундов). Успешной считается атака, если вскрытие шифра с её помощью требует меньшего количества операций, чем при полном переборе ключей. Метод вскрытия Вилли Майера (Willi Meier) оказался эффективнее вскрытия полным перебором ключей только для IDEA с 2 раундами [стойкость 3]. Методом «встреча посередине» был вскрыт IDEA с 4,5 раундами. Для этого требуется знание всех блоков из словаря кодов и сложность анализа составляет операций [стойкость 4]. Лучшая атака на 2007 год применима ко всем ключам и может взломать IDEA с 6-ю раундами [стойкость 5].
Существуют большие классы слабых ключей. Слабые они в том смысле, что существуют процедуры, позволяющие определить, относится ли ключ к данному классу, а затем и сам ключ. В настоящее время известны следующие:
Существование столь больших классов слабых ключей не влияет на практическую криптостойкость алгоритма IDEA, так как полное число всех возможных ключей равно .
Для сравнения с 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 |
|
|
|
|
|
В программной реализации на Intel486SX по сравнению с DES IDEA в два раза быстрее, что является существенным повышением скорости, длина ключа у IDEA имеет размер 128 бит, против 56 бит у DES, что является хорошим улучшением против полного перебора ключей. Вероятность использования слабых ключей очень мала и составляет . 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 запатентован, так как это препятствует его свободному распространению. IDEA не предусматривает увеличение длины ключа. Недостатком можно также считать тот факт, что не все работы по криптоанализу были опубликованы, то есть вполне возможно, что шифр взломан, или будет взломан в будущем.
Алгоритм | Ключ, бит | Блок, бит | Примечания |
---|---|---|---|
Triple-DES |
|
|
|
AES (Rijndael) |
|
|
|
CAST6 |
|
|
|
IDEA |
|
|
|
Twofish |
|
|
|
Blowfish |
|
|
|
Алгоритм IDEA является U.S. Patent 5 214 703, выпущен 25 Мая, 1993) и в Японии (JP 3225440). Действие патента истекает в 2010—2011 годах. Сегодня лицензия принадлежит компании MediaCrypt и позволяет свободно использовать алгоритм в некоммерческих приложениях. В Мае 2005 года MediaCrypt официально представила новый шифр IDEA NXT (первоначальное название FOX), призванный заменить IDEA. Типичные области применения IDEA:
Симметричные криптоалгоритмы | |
---|---|
Поточный шифр | |
Сеть Фейстеля |
ГОСТ 28147-89 • Blowfish • Camellia • CAST-128 • CAST-256 • CIPHERUNICORN-A • CIPHERUNICORN-E • CLEFIA • Cobra • DFC • DEAL • DES • DESX • EnRUPT • FEAL • FNAm2 • HPC • IDEA • KASUMI • Khufu • LOKI97 • MARS • NewDES • Raiden • RC5 • RC6 • RTEA • SEED • Sinople • TEA • Triple DES • Twofish • XTEA • XXTEA |
SP-сеть | |
Другие |