Все возможные 64-битовые блоки открытого текста можно отобразить на 64-битовые блоки шифротекста
264! Различными способами. Алгоритм DES, используя 56-битовый ключ, предоставляет нам 2 56 (приблизительно 1017) таких отображений. Использование многократного шифрования на первый взгляд позв о-ляет значительно увеличить долю возможных отображений. Но это правильно только, если действие DES не обладает определенной алгебраической структурой.
Если бы DES был замкнутым,то для любых Кг и К2 всегда существовало бы такое К3, что
ЕК2(ЕК1(Р)) = ЕКз(Р)
Другими словами, операция шифрования DES образовала бы группу, и шифрование набора блоков открыт о-го текста последовательно с помощью К1 и К2 было бы идентично шифрованию блоков ключом КЗ. Что еще хуже, DES был бы чувствителен к вскрытию "встреча посередине" с известным открытым текстом, для которого потребовалось бы только 228 этапов [807].
Если бы DES был чистым,то для любых Ки К2 и К3 всегда существовало бы такое К4, что
ЕКз(ЕК2(ЕК1(Р))) = ЕК4(Р)
Тройное шифрование было бы бесполезным. (Заметьте, что замкнутый шифр обязательно является и чи с-тым, но чистый шифр не обязательно является замкнутым.)
Ряд подсказок можно найти в ранней теоретической работе Дона Копперсмита, но этого недостаточно [377]. Различные криптографы пытались решить эту проблему [588, 427, 431, 527, 723, 789]. В повторяющихся эксп е-риментах собирались "неопровержимые доказательства" того, что DES не является группой [807, 371, 808, 1116, 809], но только в 1992 году криптографам удалось это доказать окончательно [293]. Копперсмит утве р-ждает, что команда IBM знала об этом с самого н ачала.
Длина ключа
В оригинальной заявке фирмы IBM в NBS предполагалось использовать 112-битовый ключ. К тому времени, когда DES стандартом, длина ключа уменьшилась до 56 бит. Многие криптографы настаивали на более дли н-ном ключе. Основным их аргументом было вскрытие грубой силой (см. раздел 7.1).
В 1976 и 1977 гг. Диффи и Хеллман утверждали, что специализированный параллельный компьютер для вскрытия DES, стоящий 20 миллионов долларов, сможет раскрыть ключ за день. В 1981 году Диффи увеличил время поиска до двух дней, а стоимость - до 50 миллионов долларов [491]. Диффи и Хеллман утверждали, что вскрытие в тот момент времени находилось за пределами возможностей любой организации, кроме подобных NSA, но что к 1990 году DES должен полностью утратить свою безопасность [714].
Хеллман [716] продемонстрировал еще один аргумент против малого размера ключа: разменивая объем п а-мяти на время, можно ускорить процесс поиска. Он предложил вычислять и хранить 2 56 возможных результатов шифрования каждым возможным ключом единственного блока открытого текста. Тогда для взлома неизвестн о-го ключа криптоаналитику потребуется только вставить блок открытого текста в шифруемый поток, вскрыть получившийся результат и найти ключ. Хеллман оценил стоимость такого устройства вскрытия в 5 миллионов долларов.
Аргументы за и против существования в каком-нибудь тайном бункере правительственного устройства вскрытия DES продолжают появляться. Многие указывают на то, что среднее время наработки на отказ для микросхем DES никогда не было большим настолько, чтобы обеспечивать работу устройства. В [1278] было показано, что этого возражения более чем достаточно. Другие исследователи предлагают способы еще больше ускорить процесс и уменьшить эффект отказа микросхем.
Между тем, аппаратные реализации DES постепенно приблизились к реализации требования о миллионе шифрований в секунду, предъявляемого специализированной машиной Диффи и Хеллмана. В 1984 году были выпущены микросхемы DES, способные выполнять 256000 шифрования в секунду [533, 534]. К 1987 году были разработаны микросхемы DES, выполняющие 512000 шифрований в секунду, и стало возможным появление варианта, способного проверять свыше миллиона ключей в секунду [738, 1573]. А в 1993 Майкл Винер (Michael Wiener) спроектировал машину стоимостью 1 миллион долларов, которая может выполнить вскрытие DES гр у-бой силой в среднем за 3.5 часа (см. раздел 7.1).
Никто открыто не заявил о создании этой машины, хоте разумно предположить, что кому-то это удалось. Миллион долларов - это не слишком большие деньги для большой и даже не очень большой страны.
В 1990 году два израильских математика, Бихам (Biham) и Шамир, открыли дифференциальный криптоанализ,метод, который позволил оставить в покое вопрос длины ключа. Прежде, чем мы рассмотрим этот метод, вернемся к некоторым другим критическим замечаниям в адрес DES.