IDEA (, международный алгоритм шифрования данных) — симметричный блочный алгоритм шифрования данных, запатентованный швейцарской фирмой Ascom. Известен тем, что применялся в пакете программ шифрования PGP. В ноябре 2000 года IDEA был представлен в качестве кандидата в проекте NESSIE в рамках программы Европейской комиссии IST (, информационные общественные технологии).
История Первую версию алгоритма разработали в 1990 году Лай Сюэцзя (Xuejia Lai) и Джеймс Мэсси (James Massey) из Швейцарского института ETH Zürich (по контракту с Hasler Foundation, которая позже влилась в Ascom-Tech AG) в качестве замены DES (, стандарт шифрования данных) и назвали её PES (, предложенный стандарт шифрования). Затем, после публикации работ Бихама и Шамира по дифференциальному криптоанализу PES, алгоритм был улучшен с целью усиления криптостойкости и назван IPES (, улучшенный предложенный стандарт шифрования). Через год его переименовали в IDEA ().
Описание Так как IDEA использует 128-битный ключ и 64-битный размер блока, открытый текст разбивается на блоки по 64 бит. Если такое разбиение невозможно, последний блок дополняется различными способами определённой последовательностью бит. Для избежания утечки информации о каждом отдельном блоке используются различные режимы шифрования. Каждый исходный незашифрованный 64-битный блок делится на четыре подблока по 16 бит каждый, так как все алгебраические операции, использующиеся в процессе шифрования, совершаются над 16-битными числами. Для шифрования и расшифрования IDEA использует один и тот же алгоритм.
Фундаментальным нововведением в алгоритме является использование операций из разных алгебраических групп, а именно: сложение по модулю умножение по модулю побитовое исключающее ИЛИ (XOR). Эти три операции несовместимы в том смысле, что: никакие две из них не удовлетворяют дистрибутивному закону, то есть никакие две из них не удовлетворяют ассоциативному закону, то есть Применение этих трех операций затрудняет криптоанализ IDEA по сравнению с DES, который основан исключительно на операции исключающее ИЛИ, а также позволяет отказаться от использования S-блоков и таблиц замены. IDEA является модификацией сети Фейстеля.
Генерация ключей Из 128-битного ключа для каждого из восьми раундов шифрования генерируется по шесть 16-битных подключей, а для выходного преобразования генерируется четыре 16-битных подключа. Всего потребуется 52 = 8 x 6 + 4 различных подключей по 16 бит каждый. Процесс генерации пятидесяти двух 16-битных ключей заключается в следующем: Первым делом, 128-битный ключ разбивается на восемь 16-битных блоков. Это будут первые восемь подключей по 16 бит каждый — Затем этот 128-битный ключ циклически сдвигается влево на 25 позиций, после чего новый 128-битный блок снова разбивается на восемь 16-битных блоков. Это уже следующие восемь подключей по 16 бит каждый — Процедура циклического сдвига и разбивки на блоки продолжается до тех пор, пока не будут сгенерированы все 52 16-битных подключа. + Таблица подключей для каждого раундаНомер раундаПодключи12345678выходное преобразование
Шифрование
Структура алгоритма IDEA показана на рисунке. Процесс шифрования состоит из восьми одинаковых раундов шифрования и одного выходного преобразования. Исходный незашифрованный текст делится на блоки по 64 бита. Каждый такой блок делится на четыре подблока по 16 бит каждый. На рисунке эти подблоки обозначены , , , . В каждом раунде используются свои подключи согласно таблице подключей. Над 16-битными подключами и подблоками незашифрованного текста производятся следующие операции: умножение по модулю = 65537, причем вместо нуля используется сложение по модулю побитовое исключающее ИЛИ В конце каждого раунда шифрования имеется четыре 16-битных подблока, которые затем используются как входные подблоки для следующего раунда шифрования. Выходное преобразование представляет собой укороченный раунд, а именно, четыре 16-битных подблока на выходе восьмого раунда и четыре соответствующих подключа подвергаются операциям: умножение по модулю сложение по модулю После выполнения выходного преобразования конкатенация подблоков , , и представляет собой зашифрованный текст. Затем берется следующий 64-битный блок незашифрованного текста и алгоритм шифрования повторяется. Так продолжается до тех пор, пока не зашифруются все 64-битные блоки исходного текста.
Математическое описание Блок открытого текста размером 64 бит делится на четыре равных подблока размером по 16 бит Для каждого раунда вычисляются:
Результатом выполнения восьми раундов будут следующие четыре подблока Выполняется выходное преобразование :
Результатом выполнения выходного преобразования является зашифрованный текст
Расшифровка Метод вычисления, использующийся для расшифровки текста по существу такой же, как и при его шифровании. Единственное отличие состоит в том, что для расшифровки используются другие подключи. В процессе расшифровки подключи должны использоваться в обратном порядке. Первый и четвёртый подключи i-го раунда расшифровки получаются из первого и четвёртого подключа (10-i)-го раунда шифрования мультипликативной инверсией. Для 1-го и 9-го раундов второй и третий подключи расшифровки получаются из второго и третьего подключей 9-го и 1-го раундов шифрования аддитивной инверсией. Для раундов со 2-го по 8-й второй и третий подключи расшифровки получаются из третьего и второго подключей с 8-го по 2-й раундов шифрования аддитивной инверсией. Последние два подключа i-го раунда расшифровки равны последним двум подключам (9-i)-го раунда шифрования. Мультипликативная инверсия подключа K обозначается 1/K и . Так как — простое число, каждое целое не равное нулю K имеет уникальную мультипликативную инверсию по модулю . Аддитивная инверсия подключа K обозначается -K и . + Таблица подключей для каждого раундаНомер раундаПодключи12345678выходное преобразование
Пример Для удобства числа представляем в шестнадцатеричном виде.
Пример шифрования В качестве 128-битного ключа используем K = (0001,0002,0003,0004,0005,0006,0007,0008), а в качестве 64-битного открытого текста M = (0000,0001,0002,0003) + Таблица подключей и подблоков для каждого раунда Раунд Раундовые ключи Значения блоков данных — — — — — — — 0000 0001 0002 0003100010002000300040005000600f000f5010a01052000700080400060008000a00222f21b5f45ee95930c000e0010000200001000140f8639be8ee8117340018001c002000040008000c57dfac58c65bba4d52800300038004000080010008e81ba9cf77f3a4a618002000007000800010002069429409e21b1c64700300040005000600000200099d0c7f65331620e8400060008000a000c000e0010a240098ec6b49259008000c001000140 - -11fbed2b01986de5
Пример расшифровки В качестве 128-битного ключа используем K = (0001,0002,0003,0004,0005,0006,0007,0008), а в качестве 64-битного зашифрованного текста C = (11fb, ed2b, 0198, 6de5) + Таблица подключей и подблоков для каждого раунда Раунд Раундовые ключи Значения блоков данных1fe01ff40ff00659ac000e001d98dd33127f682b82fffd8000a000cccc00002000bc4de26b9449a5763a556ffb0ffc052ab001000200aa4f7efda9c24e34554bff90e000fe0108001000ca46fe5bdc58116d5332dc800d000fffd0008000c748f8f0839da45cc64aabffe0ffe4c001001000143266045e2fb5b02e7aa96f000f200ff8108000a000690050a00fd1dfa84925fc00fff8552b00050006000000050003000c90001fffefffdc001 - -0000000100020003
Режимы шифрования IDEA является блочным алгоритмом шифрования, работающим с блоками по 64 бита. При несовпадении размера шифруемого текста с этим фиксированным размером, блок дополняется до 64.
Алгоритм используется в одном из следующих режимов шифрованияISO 10116: Information Processing — Modes of Operation for an n-bit block cipher algorithm.: Режим электронной кодовой книги () Режим сцепления блоков шифротекста () Режим обратной связи по шифротексту () Режим обратной связи по выходу () Алгоритм может также применяться для вычисления кода аутентификации сообщения ()ISO 9797: Data cryptographic techniques — Data integrity mechanism using a cryptographic check function employing a block cipher algorithm.ISO 9798-2: Information technology — Security technicues — Entity authentication mechanisms — Part 2: Entity authentication using symmetric techniques. хеш-значенийISO 10118-2: Information technology — Security technicues — Hash-functions — Part 2: Hash-functions using an n-bit block cipher algorithm. распределения ключейISO 11770-2: Information technology — Security technicues — Key management — Part 2: Key management mechanisms using symmetric techniques.
Аппаратная реализация Аппаратная реализация имеет перед программной следующие преимущества: существенное повышение скорости шифрования за счёт использования параллелизма при выполнении операций меньшее энергопотребление Первая реализация алгоритма IDEA на интегральной схеме() была разработана и верифицирована Лаем, Мэсси и Мёрфи в 1992 году с использованием технологического процесса 1,5 мкм и технологии КМОП . Скорость шифрования данного устройства составляла 44 Мб/сек.
В 1994 году Каригером, Бонненбергом, Зиммерманом и др. было разработано устройство VINCI. Скорость шифрования данной реализации IDEA составляла 177 Мб/сек при тактовой частоте 25 МГц, техпроцесс 1,2 мкм. Это было первое полупроводниковое устройство, которое уже могло применяться для шифрования в реальном времени в таких высокоскоростных сетевых протоколах, как ATM (, асинхронный способ передачи данных) или FDDI (, распределённый волоконный интерфейс данных). Скорость 177 Мб/сек была достигнута благодаря использованию довольно изощрённой схемы конвейерной обработки и четырёх обычных умножителей по модулю . В устройстве также используются два однонаправленных высокоскоростных 16-битных порта данных. Эти порты обеспечивают постоянную загруженность блоков шифрования .
Уже в следующем году Вольтер и др. представили устройство со скоростью шифрования 355 Мб/сек. Такой скорости удалось добиться благодаря реализации одного раунда шифрования на технологическом процессе 0,8 мкм с использованием технологии КМОП. Архитектура данного устройства включает в себя параллельное самотестирование, основанное на системе обработки ошибок с вычислениями по модулю 3, которая позволяет определять возникающие ошибки в одном или нескольких разрядах в тракте данных IDEA, что позволяет надёжно предотвращать искажения зашифрованных или расшифрованных данных .
Наибольшей скорости шифрования 424 Мб/сек в 1998 году на одной интегральной схеме достигла группа инженеров во главе с Саломао из Федерального Университета Рио-де-Жанейро COPPE на технологическом процессе 0,7 мкм при частоте 53 МГц. Архитектура данной реализации использует как пространственный, так и временной параллелизм, доступные в алгоритме IDEA .
В том же году IDEA Менсером и др. был реализован на четырёх устройствах XC4020XL. Скорость шифрования 4 x XC4020XL составляет 528 Мб/сек .
В 1999 году фирмой Ascom были представлены две коммерческие реализации IDEA. Первая называется IDEACrypt Kernel и достигает скорости 720 Мб/сек при использовании технологии 0,25 мкм Ascom, IDEACrypt Kernel Data Sheet, 1999.. Вторая называется IDEACrypt Coprocessor, основана на IDEACrypt Kernel и достигает скорости шифрования 300 Мб/сек Ascom, IDEACrypt Coprocessor Data Sheet, 1999..
В 2000 году инженерами из Китайского университета Гонконга Лионгом и др. были выпущены устройства шифрования на ПЛИС фирмы Xilinx: Virtex XCV300-6 и XCV1000-6 . Скорость шифрования Virtex XCV300-6 достигает 500 Мб/сек при частоте 125 МГц, а предполагаемая производительность XCV1000-6 составляет 2,35 Гб/сек, что позволяет использовать данное устройство для шифрования в высокоскоростных сетях. Высокой скорости шифрования удалось достигнуть используя разрядно-последовательную архитектуру для выполнения операции умножения по модулю . Результаты экспериментов с разными устройствами сведены в таблицу: