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

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

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

Шифр был разработан в рамках исследовательского контракта с Hasler Foundation, который стал частью 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 ¹⁶ (обозначено плюсом ⊞ в зеленой рамке ).
Умножение по модулю 2 ¹⁶ + 1, где нулевое слово (0x0000) во входных данных интерпретируется как 2 ¹⁶, и 2 ¹⁶ на выходе интерпретируется как нулевое слово (0x0000) (обозначается красной точкой в кружке ⊙ ).

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

Структура

Общая структура 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 год ^[update], лучшая атака, примененная ко всем ключам, может взломать IDEA, сократив время до 6 раундов (полный шифр IDEA использует 8,5 раундов). ^[4] Обратите внимание, что «прорыв» — это любая атака, требующая менее 2 ¹²⁸ операции; атака из 6 раундов требует 2 ⁶⁴ известные открытые тексты и 2 ^126.8 операции.

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

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

Слабые ключи

Очень простое расписание ключей делает IDEA объектом класса слабых ключей ; некоторые ключи, содержащие большое количество нулевых битов, обеспечивают слабое шифрование . ^[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 г.), США. США ( патент США 5,214,703 , выдан 25 мая 1993 г., срок действия истек 7 января 2012 г.) и Японии (JP 3225440, срок действия истек 16 мая 2011 г.). ^[11]

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

Литература

Демирчи, Хусейн; Сельчук, Али Айдын; Тюре, Эркан (2004). «Новая атака по принципу «встреча посередине» на блочный шифр IDEA». Избранные области криптографии . Конспекты лекций по информатике. Том. 3006. стр. 117–129. дои : 10.1007/978-3-540-24654-1_9 . ISBN 978-3-540-21370-3 .
Лай, Сюэцзя; Мэсси, Джеймс Л. (1991). «Предложение по новому стандарту блочного шифрования». Достижения в криптологии — EUROCRYPT '90 . Конспекты лекций по информатике. Том. 473. стр. 389–404. CiteSeerX 10.1.1.14.3451 . дои : 10.1007/3-540-46877-3_35 . ISBN 978-3-540-53587-4 .
Лай, Сюэцзя; Мэсси, Джеймс Л.; Мерфи, Шон (1991). «Марковские шифры и дифференциальный криптоанализ». Достижения в криптологии — EUROCRYPT '91 . Конспекты лекций по информатике. Том. 547. стр. 17–38. дои : 10.1007/3-540-46416-6_2 . ISBN 978-3-540-54620-7 .

Ссылки

^ «Узкие биклики: криптоанализ полной IDEA» (PDF) . www.cs.bris.ac.uk.
^ «Espacenet - Библиографические данные» (на немецком языке). Worldwide.espacenet.com . Проверено 15 июня 2013 г.
^ Гарфинкель, Симсон (1 декабря 1994 г.), PGP: Pretty Good Privacy , O'Reilly Media , стр. 101–102, ISBN 978-1-56592-098-9 .
^ Бихам, Э .; Данкельман, О.; Келлер, Н. «Новая атака на 6-раундовую ИДЕЮ». Proceedings of Fast Software Encryption, 2007, Конспекты лекций по информатике . Спрингер-Верлаг .
^ «Slashdot: ответы крипто-гуру Брюса Шнайера» . slashdot.org. 29 октября 1999 года . Проверено 15 августа 2010 г.
^ Бихам, Эли ; Данкельман, Орр; Келлер, Натан; Шамир, Ади (22 августа 2011 г.). «Новые атаки на IDEA минимум с 6 раундами» . Журнал криптологии . 28 (2): 209–239. дои : 10.1007/s00145-013-9162-9 . ISSN 0933-2790 .
^ Ховратович Дмитрий; Леран, Гаэтан; Рехбергер, Кристиан (2012). «Узкие биклики: криптоанализ полной IDEA». Достижения в криптологии – EUROCRYPT 2012 . Конспекты лекций по информатике. Том. 7237. стр. 392–410. дои : 10.1007/978-3-642-29011-4_24 . ISBN 978-3-642-29010-7 .
^ Перейти обратно: ^а ^б Дэмен, Джоан ; Говертс, Рене; Вандевалле, Йоос (1994). «Слабые ключи к ИДЕЕ». Достижения криптологии — КРИПТО' 93 . Конспекты лекций по информатике. Полный. 773. стр. 224–231. CiteSeerX 10.1.1.51.9466 . дои : 10.1007/3-540-48329-2_20 . ISBN 978-3-540-57766-9 .
^ Накахара, Хорхе младший; Пренил, Барт; Вандевалле, Йоос (2002), Заметка о слабых ключах PES, IDEA и некоторых расширенных вариантах , CiteSeerX 10.1.1.20.1681
^ Перейти обратно: ^а ^б Бирюков, Алекс; Накахара, Хорхе младший; Пренил, Барт; Вандевалле, Йоос, «Новые классы IDEA со слабыми ключами» (PDF) , Информационная и коммуникационная безопасность, 4-я Международная конференция, ICICS 2002 , Конспекты лекций по информатике 2513: 315–326, В то время как проблема слабых ключей IDEA с нулевым значением единицы можно исправить, просто выполняя XOR фиксированную константу для всех ключей (одной из таких констант может быть 0DAE _x , как предложено в [4]), проблема с прогонами единиц все еще может оставаться и потребует полной переработки расписания ключей IDEA.
^ «Выпущена GnuPG 1.4.13» . Вернер Кох. 21 декабря 2012 года . Проверено 6 октября 2013 г.

Внешние ссылки

[1] «Узкие биклики: криптоанализ полной IDEA» (PDF) . www.cs.bris.ac.uk.

[2] «Espacenet - Библиографические данные» (на немецком языке). Worldwide.espacenet.com . Проверено 15 июня 2013 г.

[3] Гарфинкель, Симсон (1 декабря 1994 г.), PGP: Pretty Good Privacy , O'Reilly Media , стр. 101–102, ISBN 978-1-56592-098-9 .

[idea-cryptanalysis-4] Бихам, Э .; Данкельман, О.; Келлер, Н. «Новая атака на 6-раундовую ИДЕЮ». Proceedings of Fast Software Encryption, 2007, Конспекты лекций по информатике . Спрингер-Верлаг .

[5] «Slashdot: ответы крипто-гуру Брюса Шнайера» . slashdot.org. 29 октября 1999 года . Проверено 15 августа 2010 г.

[6] Бихам, Эли ; Данкельман, Орр; Келлер, Натан; Шамир, Ади (22 августа 2011 г.). «Новые атаки на IDEA минимум с 6 раундами» . Журнал криптологии . 28 (2): 209–239. дои : 10.1007/s00145-013-9162-9 . ISSN 0933-2790 .

[idea-narrow-bicliques-7] Ховратович Дмитрий; Леран, Гаэтан; Рехбергер, Кристиан (2012). «Узкие биклики: криптоанализ полной IDEA». Достижения в криптологии – EUROCRYPT 2012 . Конспекты лекций по информатике. Том. 7237. стр. 392–410. дои : 10.1007/978-3-642-29011-4_24 . ISBN 978-3-642-29010-7 .

[weak-8] Перейти обратно: ^а ^б Дэмен, Джоан ; Говертс, Рене; Вандевалле, Йоос (1994). «Слабые ключи к ИДЕЕ». Достижения криптологии — КРИПТО' 93 . Конспекты лекций по информатике. Полный. 773. стр. 224–231. CiteSeerX 10.1.1.51.9466 . дои : 10.1007/3-540-48329-2_20 . ISBN 978-3-540-57766-9 .

[9] Накахара, Хорхе младший; Пренил, Барт; Вандевалле, Йоос (2002), Заметка о слабых ключах PES, IDEA и некоторых расширенных вариантах , CiteSeerX 10.1.1.20.1681

[weak2-10] Перейти обратно: ^а ^б Бирюков, Алекс; Накахара, Хорхе младший; Пренил, Барт; Вандевалле, Йоос, «Новые классы IDEA со слабыми ключами» (PDF) , Информационная и коммуникационная безопасность, 4-я Международная конференция, ICICS 2002 , Конспекты лекций по информатике 2513: 315–326, В то время как проблема слабых ключей IDEA с нулевым значением единицы можно исправить, просто выполняя XOR фиксированную константу для всех ключей (одной из таких констант может быть 0DAE _x , как предложено в [4]), проблема с прогонами единиц все еще может оставаться и потребует полной переработки расписания ключей IDEA.

[11] «Выпущена GnuPG 1.4.13» . Вернер Кох. 21 декабря 2012 года . Проверено 6 октября 2013 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]