Криптостойкость алгоритма DES

С самого начала использования алгоритма DES криптоаналитики всего мира прилагали множество усилий по его взлому. Фактически DES дал невиданный доселе толчок развитию криптоанализа. Вышли сотни трудов, посвященных различным методам криптоанализа именно в приложении к алгоритму DES, а также деталям самого алгоритма и их влиянию на криптостойкость DES. Можно утверждать, что именно благодаря DES появились целые направления криптоанализа, такие как:
линейный криптоанализ;
дифференциальный криптоанализ;
криптоанализ на связанных ключах;
стоит сказать, что в работе было доказано, что DES неуязвим к данному виду атак благодаря тому, что в описанной выше процедуре расширения ключа циклический сдвиг выполняется на различное число битов в разных раундах.

«DES стойко выдержал 20 лет массового всемирного криптоанализа» — десятилетия криптоанализа не привели к обнаружению серьезных уязвимостей в алгоритме. Основными результатами усилий по взлому DES можно считать следущие.

Японский специалист Мицуру Мацуи (Mitsuru Matsui), изобретатель ли-нейного криптоанализа, в 1993 г. доказал возможность вычисления ключа шифрования DES методом линейного криптоанализа при наличии у атакующего 247 пар известных открытых текстов.

Криптологи из Израиля — изобретатели дифференциального криптоанализа Эли Бихам и Эди Шамир (считается, что дифференциальный криптоанализ был известен АНБ США еще в 1970-х гг., однако, именно Бихам и Шамир сформулировали данный вид атак и сделали его доступным всему криптологическому сообществу)— в 1991 г. представили атаку, в которой ключ шифрования вычисляется методом дифференциального криптоанализа при наличии у атакующего возможности генерации 247 пар выбранных открытых текстов.

В 1994 г. Эли Бихам и Алекс Бирюков усилили известный с 1987 г. метод вычисления ключа DES — метод Дэвиса (Davies), основанный на специфических свойствах таблиц замен DES. Усиленный метод позволяет вычислить 6 битов ключа DES (остальные 50 битов — полным перебором возможных вариантов) при наличии 250 пар известных открытых текстов и шифртекстов или вычислить 24 бита ключа при наличии 2 пар.

В дальнейшем эти атаки были несколько усилены (например, атака линейным криптоанализом при наличии 243 пар известных открытых текстов вместо 247), появлялись также новые виды атак на DES (например, атака, позволяющая вычислить ключ высокоточным облучением аппаратного шифратора и последующим анализом ошибок шифрования). Однако стоит сказать, что все эти атаки требуют наличия огромного количества пар «открытый текст— шифртекст», получение которых на практике является настолько трудоемкой операцией, что наиболее простой атакой на DES считается полный перебор возможных вариантов ключа шифрования.

Кроме того, практически сразу после появления DES были обнаружены следующие проблемы с ключами шифрования DES.

По материалам книги Сергея Панасенко «Алгоритмы шифрования»

Алгоритмы шифрования