Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
36 Системы с секретный ключом
Глава 3
ния и рассеивания, даже несмотря на то, что один из двух шагов преобразования является стандартным и общеизвестным.
Алгоритм DES разработан таким образом, что дешифрование в нем выполняется с помощью точно такого же процесса (в прямом порядке), что и шифрование, за исключением того, что формирование частичных ключей для дешифрования тогда будет производиться в обратном порядке. Это очень удобно, поскольку одно и то же устройство может использоваться как для процедуры шифрования, так и для процедуры дешифрования.
Является ли использование DES достаточно надежным? В 1979 году Мартин Хеллман написал статью под названием «DES будет полностью раскрыт в течении десяти лет» [213]. Подобная полемика относительно стойкости DES обычно возникает из-за того, что пространство его ключей является относительно небольшим и позволяет сделать возможным его полный перебор, даже несмотря на то, что при этом он может быть довольно дорогостоящим. Миллион процессоров, работающих в параллель и проверяющих миллион ключей за одну секунду, перебрал бы все его ключевое пространство за двадцать часов. Однако несмотря на многочисленные исследования криптосистемы DES [215, 158, 213, 348, 137, 145, 179, 113, 319, 231, 93, и т.д.], никто еще пока не смог найти в ней другие сколь-нибудь существенные изъяны. Таким образом, она, по-видимому, вполне отвечает требованиям обеспечения секретности для небольших и средних приложений.
Тем не менее использование DES с целью установления подлинности (см. § 5.1) кажется более сомнительным, потому что последствия от нескольких успешно подделанных фальсификатором сообщений могут быть намного более серьезными, чем последствия от нескольких успешных расшифровок перехваченных шифртекстов.
Простой методикой, которая может быть использована, для того чтобы сделать полный перебор более трудоемким, и без которой DES вообще не должен применяться, является многократное шифрование. Вместо одного 64-битового ключа необходимо использовать два (или, еще лучше, три) таких ключа. Очевидным подходом было бы зашифровывать т по формуле с — DESki{DESk3(m)). Однако это не повышает стойкости, поскольку угроза простого полного перебора может возникнуть
Стандарт шифрования данных (DES) 37
вновь. Действительно, если имеются в распоряжении по крайней мере два соответствующих друг другу известных блока открытого и шифрованного текста, то к\ и к? могут быть вычислены с большой вероятностью после примерно 256 DES-шифрований и приблизительно такого же числа DES-дешифрований. Для того чтобы показать, как это делается, предположим, что mi, тп?, сх и С2 таковы, что с,- = D?Sfc1(D?Sfc2(mt)) для 1 <; i <; 2. Для каждого значения ключа к вычислим DESk(mi) и запишем полученный результат в некоторой хэш-таблице (так, чтобы по каждому результату можно было быстро определить соответствующий ему ключ к). Затем снова для каждого значения к вычислим 0?5^~2(с 1) и попробуем найти получившийся результат в хэш-таблице. Если он будет найден, то возможно, что соответствующее ему значение к является в действительности ключом Л?2, а то значение к, которое использовалось, чтобы получить этот результат (для записи его в хэш-таблицу), как раз и есть к\. Если же, кроме того, и С2 = DESkl (DESk2 (m2)), то, вполне вероятно, что пара (к\, &г) является правильной (с вероятностью ошибки, равной приблизительно 2-16). В противном случае перебор значений к и поиск результатов DES^1 (ci) в хэш-таблице может быть продолжен. Ожидаемое число «ложных тревог» (неправильных к, для которых DES^1 (ci) находится в хэш-таблице) равно примерно 248. Обратите внимание на то, что хэш-функция может быть очень грубой, так как ожидаемые результаты работы DES должны быть в большинстве своем почти случайными.
Хотя описанная выше атака ненамного медленнее, чем исчерпывающий поиск при однократном шифровании, она требует значительно большего пространства в оперативной памяти для хранения соответствующей хэш-таблицы. Альтернативное решение состоит в том, чтобы результаты вычислений 0?5*х (mi) для каждого значения ключа к^ (позволяющие при этом сохранять ссылки на значения ki) записывать на одних магнитных лентах, а результаты DESj^(ci) для каждого значения к^ (позволяющие также сохранять ссылки на значения кц) — на других. После сортировки содержимого таких лент последовательный просмотр позволяет легко находить подходящие пары (кх, &г), которые при дальнейшей проверке с использованием mi и с-t могут быть отброшены.
Вальтером Тахманом в [347] была предложена несколькр луч-
38 Системы с секретным ключом
Глава 3
шая процедура двухключевого шифрования при помощи алгоритма DES. Согласно ей шифртекст нужно вычислять по формуле с= DESkt (DES^1 (DESk1 (m)))- Использование в этой формуле обратного преобразования на втором шаге вычисления необходимо для того, чтобы обеспечить сопряжение с однократным шифрованием, когда к\ и &2 имеют одинаковые значения. Хотя указанный подход предотвращает простую атаку типа «навстречу друг-другу», которая была описана выше, Ральф Меркль и Мартин Хеллман [267] нашли способ, как раскрыть такую схему также приблизительно за 256 шагов (хотя им для этого потребовалась атака на основе выбранного открытого текста). По этой причине они рекомендовали схему шифрования с использованием трех независимых ключей согласно формуле с = DESk1{DES^21(DESk3(m))). Даже несмотря на то, что такое шифрование делает полный перебор в настоящее время практически неосуществимым, не ясно, приводит ли это к почти неуязвимому шифру, поскольку в криптосистеме DES могут существовать еще необнаруженные (или не до конца исследованные) слабости или лазейки. Тем не менее Дон Копперсмит написал в [122] относительно DES следующее: «Я горжусь тем, что принимал посильное участие в этом проекте [проект DES]. (...) Насколько мне известно, никто из пытавшихся сократить криптоанализ DES так и не смог сделать его существенно более простым, чем полный перебор всех ключей.».
