Международный алгоритм шифрования данных - International Data Encryption Algorithm

ИДЕЯ
Международный алгоритм шифрования данных InfoBox Diagram.svg
Раунд шифрования IDEA
Общий
ДизайнеровСюэцзя Лай и Джеймс Мэсси
Происходит отPES
ПреемникиMMB, СЕТКА, Акеларре,
ИДЕЯ NXT (ЛИСА)
Деталь шифра
Ключевые размеры128 бит
Размеры блоков64 бит
СтруктураСхема Лая – Мэсси
Раундов8.5
Лучшая публика криптоанализ
Ключ может быть восстановлен с вычислительной сложностью 2126.1 используя узкий биклики. Эта атака вычислительно быстрее, чем полная атака грубой силой, хотя по состоянию на 2013 год она не является вычислительно возможной.[1]

В криптография, то Международный алгоритм шифрования данных (ИДЕЯ), первоначально назывался Улучшенный предлагаемый стандарт шифрования (IPES), это симметричный ключ блочный шифр разработано Джеймс Мэсси из ETH Цюрих и Сюэцзя Лай и впервые был описан в 1991 году. Алгоритм был задуман как замена Стандарт шифрования данных (DES). IDEA - это небольшая переработка более ранней шифр Предлагаемый стандарт шифрования (PES).

Шифр был разработан в рамках исследовательского контракта с Фондом Хаслера, который стал частью Ascom-Tech AG. Шифр был запатентован в ряде стран, но был свободно доступен для некоммерческого использования. Название «ИДЕЯ» также является товарный знак. Последний патенты срок действия истек в 2012 году, и теперь IDEA не имеет патентов и, следовательно, полностью бесплатна для любого использования.[2][3]

IDEA использовалась в Довольно хорошая конфиденциальность (PGP) v2.0 и был включен после исходного шифра, использованного в v1.0, BassOmatic, оказался небезопасным.[4] IDEA - это необязательный алгоритм в OpenPGP стандарт.

Операция

IDEA работает на 64-битной блоки используя 128-битный ключ и состоит из серии из 8 одинаковых преобразований (a круглый, см. иллюстрацию) и выходное преобразование ( полукруглый). Процессы шифрования и дешифрования аналогичны. Безопасность IDEA во многом обеспечивается за счет чередования операций из разных группы — модульный сложение и умножение, а также побитовое Исключающее ИЛИ (XOR) - которые в некотором смысле алгебраически «несовместимы». Более подробно, эти операторы, которые все имеют дело с 16-битными величинами, следующие:

  • Побитовое XOR (исключающее ИЛИ) (обозначено синим плюсом в кружке ⊕).
  • Сложение по модулю 216 (обозначен плюсом в зеленой рамке ⊞).
  • Умножение по модулю 216 + 1, где нулевое слово (0x0000) во входных данных интерпретируется как 216, и 216 в выводе интерпретируется как слово со всеми нулями (0x0000) (обозначается красной точкой в ​​кружке ⊙).

После 8 раундов наступает последний «полукруг», выходное преобразование, показанное ниже (замена двух средних значений отменяет обмен в конце последнего раунда, так что нет никакого чистого обмена):

Международный алгоритм шифрования данных InfoBox Diagram Output Trans.png

Структура

Общая структура IDEA следует Схема Лая – Мэсси. XOR используется как для вычитания, так и для сложения. IDEA использует зависимую от ключа полукруглую функцию. Для работы с 16-битными словами (что означает 4 входа вместо 2 для 64-битного размера блока), IDEA использует схему Лая-Месси дважды параллельно, при этом две параллельные циклические функции переплетаются друг с другом. Для обеспечения достаточного распространения два субблока меняются местами после каждого раунда.

Ключевой график

В каждом раунде используется 6 16-битных подключей, а в полукруге - 4, всего 52 для 8,5 раундов. Первые 8 подключей извлекаются непосредственно из ключа, причем K1 из первого раунда является младшими 16 битами; следующие группы из 8 ключей создаются путем поворота основного ключа влево на 25 бит между каждой группой из 8. Это означает, что он поворачивается менее одного раза за раунд, в среднем, всего 6 оборотов.

Расшифровка

Расшифровка работает как шифрование, но порядок ключей раунда инвертируется, а подключи для нечетных раундов инвертируются. Например, значения подключей K1 – K4 заменяются на значения, обратные K49 – K52 для соответствующей групповой операции, K5 и K6 каждой группы должны быть заменены на K47 и K48 для дешифрования.

Безопасность

Дизайнеры проанализировали IDEA, чтобы сравнить ее силу с дифференциальный криптоанализ и пришел к выводу, что он невосприимчив при определенных предположениях. Не удалось линейный или алгебраической слабости. По состоянию на 2007 год, лучшая атака, примененная ко всем ключам, может взломать IDEA, сокращенную до 6 раундов (полный шифр IDEA использует 8,5 раундов).[5] Обратите внимание, что "перерыв" - это любая атака, требующая менее 2128 операции; 6-раундовая атака требует 264 известные открытые тексты и 2126.8 операции.

Брюс Шнайер В 1996 году высоко оценил IDEA, написав: «На мой взгляд, это лучший и наиболее безопасный алгоритм блокировки, доступный для общественности в настоящее время». (Прикладная криптография, 2-е изд.) Однако к 1999 году он больше не рекомендовал IDEA из-за доступности более быстрых алгоритмов, некоторого прогресса в ее криптоанализе и проблемы патентов.[6]

В 2011 году полная 8,5-раундовая IDEA была взломана с помощью атаки «встречай посередине».[7] Независимо в 2012 году полная 8,5-раундовая IDEA была взломана с использованием узконаправленнойатака бикликов, с уменьшением криптографической стойкости примерно на 2 бита, аналогично эффекту предыдущей атаки bicliques на AES; однако на практике эта атака не угрожает безопасности IDEA.[8]

Слабые ключи

Очень простое расписание ключей делает IDEA подчиненным классу слабые ключи; некоторые ключи, содержащие большое количество 0 бит, создают слабое шифрование.[9] На практике это не вызывает особого беспокойства, так как они достаточно редки, и в них нет необходимости явно избегать при генерации ключей случайным образом. Было предложено простое исправление: выполнение операции XOR для каждого подключа с 16-разрядной константой, например 0x0DAE.[9][10]

Более крупные классы слабых ключей были обнаружены в 2002 году.[11]

Это по-прежнему с ничтожно малой вероятностью может быть проблемой для случайно выбранного ключа, и некоторые проблемы решаются с помощью константы XOR, предложенной ранее, но в статье нет уверенности, все ли из них. Может потребоваться более полная переработка ключевого расписания IDEA.[11]

Доступность

Заявка на патент IDEA была впервые подана в Швейцария (CH A 1690/90) 18 мая 1990 г. тогда была подана международная заявка на патент под Договор о патентной кооперации 16 мая 1991 г. В конечном итоге были получены патенты в г. Австрия, Франция, Германия, Италия, то Нидерланды, Испания, Швеция, Швейцария, то объединенное Королевство, (Запись в Европейском патентном реестре для Европейский патент № 0482154, поданной 16 мая 1991 г., выданной 22 июня 1994 г. и истекшей 16 мая 2011 г.), Соединенные Штаты (Патент США 5214703 (выдан 25 мая 1993 г. и истек 7 января 2012 г.) и Япония (JP 3225440) (срок действия истек 16 мая 2011 г.).[12]

MediaCrypt AG теперь предлагает преемника IDEA и фокусируется на своем новом шифре (официальный выпуск в мае 2005 г.) ИДЕЯ NXT, который ранее назывался FOX.

Литература

Рекомендации

  1. ^ "Narrow-Bicliques: криптоанализ полной идеи" (PDF). www.cs.bris.ac.uk.
  2. ^ "Espacenet - Bibliografische Daten" (на немецком). Worldwide.espacenet.com. Получено 2013-06-15.
  3. ^ "Espacenet - Bibliografische Daten" (на немецком). Worldwide.espacenet.com. Получено 2013-06-15.
  4. ^ Гарфинкель, Симсон (1 декабря 1994 г.), PGP: Довольно хорошая конфиденциальность, O'Reilly Media, стр. 101–102, ISBN  978-1-56592-098-9.
  5. ^ Бихам, Э.; Дункельман, О .; Келлер, Н. «Новая атака на 6-раундовую IDEA». Springer-Verlag.
  6. ^ "Slashdot: ответы на вопросы гуру криптографии Брюса Шнайера". slashdot.org. Получено 2010-08-15.
  7. ^ Бихам, Эли; Дункельман, Орр; Келлер, Натан; Шамир, Ади (2011-08-22). «Новые атаки на IDEA с использованием как минимум 6 раундов». Журнал криптологии. 28 (2): 209–239. Дои:10.1007 / s00145-013-9162-9. ISSN  0933-2790.
  8. ^ Ховратович, Дмитрий; Леурент, Гаэтан; Рехбергер, Кристиан (2012). Narrow-Bicliques: криптоанализ полной идеи. Достижения в криптологии - EUROCRYPT 2012. Конспект лекций по информатике. 7237. С. 392–410. Дои:10.1007/978-3-642-29011-4_24. ISBN  978-3-642-29010-7.
  9. ^ а б Дэмен, Джоан; Говертс, Рене; Вандевалле, Джоос (1993), "Слабые ключи для IDEA", Достижения в криптологии, Труды CRYPTO 93: 224–231, CiteSeerX  10.1.1.51.9466
  10. ^ Накахара, Хорхе-младший; Пренил, Барт; Вандевалле, Джус (2002), Примечание о слабых ключах PES, IDEA и некоторых расширенных вариантах, CiteSeerX  10.1.1.20.1681
  11. ^ а б Бирюков Алексей; Накахара, Хорхе-младший; Пренил, Барт; Вандевалле, Джус, «Новые слабые ключевые классы IDEA» (PDF), Информационная и коммуникационная безопасность, 4-я Международная конференция, ICICS 2002, Конспект лекций по информатике 2513: 315–326, В то время как проблема слабых ключей нуля или единицы в IDEA может быть исправлена ​​путем XOR фиксированной константы для всех ключей (одна такая константа может быть 0DAEИкс как предложено в [4]) проблема с запуском одного может все еще оставаться и потребует полного изменения ключевого расписания IDEA.
  12. ^ «Выпущен GnuPG 1.4.13». Вернер Кох. Получено 2013-10-06.

внешняя ссылка