logo search
Коды и шифры

Стойкость des-алгоритма

Стоит заметить, что два человека, желающие связываться друг с другом с помощью DES-алгоритма, должны договориться об общем ключе. Это можно сделать с использованием системы ключевого обмена Диффи-Хеллмана. Эта процедура является безопасной, если только третья сторона не может перехватывать и изменять содержание сообщений.

Что касается самого DES-алгоритма, то данные, зашифрованные с его помощью на большом количестве ключей, подвергались различным тестам, в том числе статистическим, и все они дали хорошие результаты. Один из самых важных тестов называется "лавина": сколько именно разрядов из 64-х изменится на выходе, если изменить один из 64-х разрядов на входе? Для слабого шифра ответ был бы "1"; в идеальной системе шифрования ответ должен быть "около 32-х" - именно так обстоит дело в DES-алгоритме (примеры см. в [13.5]).

Несмотря на это, дебаты относительно его уровня стойкости шли даже еще до введения DES-алгоритма в эксплуатацию. Так как пользователи задают 56-разрядный ключ, то противнику надо опробовать "всего лишь" 256 возможных ключей. Так как 256 составляет около 1016,86, то компьютеру, способному проверять один ключ в микросекунду, понадобится 2300 лет для их полного перебора. Ясно, что это практически невыполнимо. Однако критики DES-алгоритма заявляли, что миллион таких компьютеров, работающих параллельно, смогут найти ключ всего за один день. И так как это будет стоить огромной суммы денег и потребует больших организационных усилий, то трудно себе представить, чтобы кто-нибудь посчитал стоящим такое предприятие, если только заранее не известно, что сообщение относится к жизненно важному вопросу национальной безопасности. Также выдвигались предположения, что возможно существование тайной "лазейки", или Ахиллесовой пяты, известной разработчикам DES‑алгоритма, что позволит осведомленным о ее существовании находить ключ за приемлемое время. Это может быть правдой, но никто до сих пор не обнаружил данных, свидетельствующих о ее существовании.

Также высказывались предположения, что в DES-алгоритме надо было использовать ключ большей длины, и чаще всего при этом говорили о 128 разрядах. Это, конечно, устранило бы все сомнения по поводу его стойкости, и с тех пор 128-битовое шифрование появилось в составе других систем, но в 1977 году это не сочли необходимым.

Альтернативой использования 128-разрядного ключа могло бы быть последовательное шифрование на двух 64-разрядных ключах, но можно показать, что в этом случае стойкость возрастает всего лишь вдвое по сравнению с использованием одного 64-разрядного ключа (если у криптоаналитика в наличии имеется компьютер с огромным объемом памяти). Данный метод вскрытия требует знания открытого текста и его шифрованного эквивалента. Известный открытый текст зашифровывается на всех возможных 64-разрядных ключах, а известный шифрованный текст расшифровывается на всех возможных 64-разрядных ключах. Затем происходит сортировка и сравнение двух построенных множеств данных. Это означает, что потребуется всего лишь 257 испытаний, а не 2112. Если обнаружены два одинаковых текста, то это значит, что у нас есть возможные значения для пары неизвестных нам ключей. Будет найдено много ложных пар ключей (их окажется около 248, см. M27), их придется проверять на других известных парах открытого/шифрованного текстов. Такой метод "встречного поиска" в настоящее время невозможно реализовать практически, до и в обозримом будущем это вряд ли удастся.

Однако, стойкость DES-алгоритма чрезвычайно возрастает, если применить тройное шифрование. Потребуется всего два ключа, которые применяются следующим образом:

  1. зашифровать сообщение на 1-м ключе;

  2. расшифровать сообщение на 2-м ключе;

  3. зашифровать сообщение на 1-м ключе.

Теперь противнику необходимо опробовать 2112 возможных пар ключей, а это считается невозможным ни за какое реальное время. Такое тройное DES-преобразование считается стойким и используется в настоящее время. Такая форма тройного шифрования имеет дополнительное преимущество, состоящее в том, что для двух одинаковых ключей оно становится идентично одинарному DES‑преобразованию. Это позволяет пользователю, применяющему тройное шифрование, связываться с пользователем, применяющим одинарное, и наоборот. В другой форме тройного шифрования на всех трех стадиях используются различные ключи. И снова совместимости с другими вариантами можно добиться, положив два или более ключа одинаковыми.