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

В криптографии , то International Data Encryption Algorithm ( IDEA ), первоначально названный Улучшено Предлагаемый стандарт шифрования ( ИПЭС ), является симметричным ключом блочного шифра разработанный Джеймсом Мэсси из ETH Zurich и Xuejia Lai и был впервые описан в 1991 году алгоритм был предназначен в качестве замены стандарта шифрования данных (DES). IDEA является несовершеннолетним пересмотр более раннего шифра Предполагаемого Encryption Standard (ПЭС).

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

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

Операция [ править ]

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

  • Побитовое исключающее ИЛИ (исключающее ИЛИ) (обозначено синим кружком плюс ⊕ ).
  • Сложение по модулю 2 16 (обозначено плюсом в зеленой рамке ).
  • Умножение по модулю 2 16 + 1, где слово полностью нуля (0x0000) на входах интерпретируется как 2 16 , а 2 16 на выходе интерпретируется как слово полностью нуля (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 раундов). [4] Обратите внимание, что «перерыв» - это любая атака, которая требует менее 2 128 операций; 6-раундовая атака требует 2 64 известных открытых текстов и 2 операций 126,8 .

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

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

Слабые ключи [ править ]

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

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

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

Доступность [ править ]

Заявка на патент 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 г.). [11]

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

Литература [ править ]

  • Хусейн Демирджи, Эркан Тюре, Али Айдын Сельчук, Новая встреча в середине атаки на блочный шифр IDEA, 10-й ежегодный семинар по отдельным областям криптографии , 2004.
  • Сюэцзя Лай и Джеймс Л. Мэсси, Предложение по новому стандарту блочного шифрования , EUROCRYPT 1990, стр. 389–404.
  • Сюэцзя Лай, Джеймс Л. Мэсси и С. Мерфи, Марковские шифры и дифференциальный криптоанализ, Успехи в криптологии - Eurocrypt '91 , Springer-Verlag (1992), стр. 17–38.

Ссылки [ править ]

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

Внешние ссылки [ править ]

  • Часто задаваемые вопросы RSA по блочным шифрам
  • SCAN запись для IDEA
  • IDEA в 448 байтах 80x86
  • Апплет IDEA
  • Исходный код Java