ВНОВЬ. Действительно, если имеются в распоряжении по крайней мере два соответствующих друг другу известных блока открытого и шифрованного текста, то и 2 могут быть вычислены с большой вероятностью после примерно 2® ОБ8-шифроваяий и приблизительно такого же числа DES-дешифрований. Для того чтобы показать, как это делается, предположим, что тпх, т, ci и С2 таковы, что с,- = DESki{DESk{mi)) для 1 » 2. Для каждого значения ключа к вычислим DESk{mi) и запишем полученный результат в некоторой хэш-таблице (так, чтобы по каждому результату можно было быстро определить соответствующий ему ключ к). Затем снова для каждого значения к вычислим DESk{ci) и попробуем найти получившийся результат в хэш-таблице. Если он будет найден, то возможно, что соответствующее ему значение к является в действительности ключом fcg, а то значение к, которое использовалось, чтобы получить этот результат (для записи его в хэш-таблицу), как раз и есть ki. Если же, кроме того, и сг = 0£5к,(0£5кз(т2)), то, вполне вероятно, что пара (1,2) является правильной (с вероятностью ошибки, равной приблизительно 2~®). В противном случае перебор значений к и поиск результатов DESj{ci) в хэш-таблице может быть продолжен. Ожидаемое число «ложных тревог» (неправильных к, для которых DES(ci) находится в хэш-таблице) равно примерно 2®. Обратите внимание на то, что хэш-функция может быть очень грубой, так как ожидаемые результаты работы DES должны быть в большинстве своем почти случайными.

Хотя описсшная выше атака ненамного медленнее, чем исчерпывающий поиск при однократном шифровании, она требует значительно большего пространства в оперативной памяти для хранения соответствующей хэш-таблицы. Альтернативное решение состоит в том, чтобы результаты вычислений DESk{mi) для каждого значения ключа ki (позволяющие при этом сохранять ссылки на значения ki) записывать на одних магнитных лентах, а результаты DfSj~(ci) для каждого значения 2 (позволяющие также сохранять ссылки на значения 2) - на других. После сортировки содержимого таких лент последовательный просмотр позволяет легко находить подходящие пары {ki, Лг), которые при дальнейшей проверке с использованием и С2 могут быть отброшены.

Вальтером Тахманом в [347] была предложена несколькр луч-

шая процедура двухключевого шифрования при номопц! алгоритма DES. Согласно ей шифртекст нужно вычислять по формуле с= DESki{DESl{DESki{m))). Использование в этой формуле обратного преобразования на втором шаге вычисления необходимо для того, чтобы обеспечить сопряжение с однократным шифрованием, когда ki и 2 имеют одинаковые значения. Хотя указанный подход предотвращает простую атаку типа «навстречу друг-другу», которая была описана выше, Ральф Меркль и Мартин Хеллман [267] нашли способ, как раскрыть такую схему также приблизительно за 2 шагов (хотя им для этого потребовалась атака на основе выбранного открытого текста). По этой причине они рекомендовали схему шифрования с использованием трех независимых ключей согласно формуле с= DESkiiDES{ОЕ5кз{т))). Даже несмотря на то, что такое шифрование делает полный перебор в настоящее время практически неосуществимым, не ясно, приводит ли это к почти неуязвимому шифру, поскольку в криптосистеме DES могут существовать еще необнаруженные (или не до конца исследованные) слабости или лазейки. Тем не менее Дон Копперсмит написал в [122] относительно DES следующее: «Я горжусь тем, что принимал посильное участие в этом проекте [проект DES]. (...) Насколько мне известно, никто из пытавшихся сократить криптоанализ DES так и не смог сделать его существенно более простым, чем полный перебор всех ключей.».

Если DES реализуется в аппаратуре, то с его помощью может быть достигнута очень высокая скорость шифрования и дешифрования. В наиболее быстром в настоящее время коммерчески используемом шифраторе скорость шифрования достигает 90 мегабит в секунду. Описание других аппаратных реализаций можно найти в [256, 13, 217, 351]. Добиться высокого быстродействия схем можно, если при их проектировании правильно использовать идеи, изложенные в [137]. Указанное быстродействие вполне достаточно для того, чтобы зашифровывать или расшифровывать данные без потери скорости при чтении или записи их на диск, и оно вполне приемлемо для большинства прикладных программ передачи данных. Довольно приличные скорости - до 650 килобит в секунду на 80-ой модели IBM PS/2 -

этом абзгще указаны данные на 1993 год, которые приведены во фран-.цузской издании книги.

можно получить также посредством только программной реализации [205]. Относительно других программ, реализуюпщх DES см. [138, 359, 160].

§ 5. Режимы операций

Рассмотрим криптографическую систему наподобие DES, в которой пространство сообщений состоит из блоков длиной по 64 бита. Как с ее помоиц>ю нужно шифровать более длинные сообщения? Очевидное решение состоит в том, чтобы разбить текст сообщения на отрезки длиной по 64 бита каждый и шифровать их последовательно и независимо, используя один и тот же секретный ключ. Однако такого подхода, который известен под названием режима электронной кодовой книги (ЕСВ), необходимо максимально избегать везде, где только возможно. Наиболее очевидная его слабость заключается в том, что два одинаковых отрезка шифрованного текста однозначно указывают криптоаналитику, что два соответствующих им отрезка открытого текста также идентичны. Подобная информация может быть очень ценной отправной точкой для вычисления всего открытого текста. Если же DES используется с целью подтверждения подлинности (аутентификации), то ситуация оказывается еще хуже (см. § 5.1).

Существует по крайней мере четыре альтернативы режиму ЕСВ. Во всех этих режимах два одинаковых блока открытого текста (почти наверняка) шифруются по-разному. В режимах СВС и CFB (которые описываются ниже) надлежащим образом используется понятие рассеивания: каждый блок шифртекста зависит от всего предшествующего ему открытого текста. Это делает их пригодными, для целей аутентификации, так как таким образом в них предотвращаются попытки удаления и вставки нарушителем предварительно преобразованных частей шифр-текста (см. § 5.1). Кроме того, оба этих режима являются самосинхронизирующимися в том смысле, что если при передаче возникает ошибка или, если в процессе шифрования и дешифрования происходит случайный сбой, или даже, если теряется некоторый, причем неизвестно какой, блок шифртекста, то при этом могут быть неправильно дешифрованы лишь несколько блоков открытого текста. В режимах OFB и счетчика (которые также описаны ниже) могут одинаково хорошо исправляться случай-