Дифференциальный криптоанализ

Этот метод атак на алгоритмы шифрования был изобретен в 1990 г. известными израильскими криптологами Эли Бихамом (Eli Biham) и Эди Шамиром (Adi Shamir) и опубликован в их работе. Однако не менее известный криптолог Брюс Шнайер в своей книге утверждает, что дифференциальный криптоанализ был открыт существенно раньше, но не появлялся в открытой печати. Тем не менее, именно Бихам и Шамир до сих пор считаются изобретателями дифференциального криптоанализа.

Характеристики используются следующим образом (на примере трехраундового DES и приведенной выше характеристики).

Генерируется необходимое количество выбранных открытых текстов (пары которых соответствуют выбранной характеристике) и соответствующих им шифртекстов. Количество пар с требуемой разностью оценивается в как «некоторое число» (several).

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

Версии алгоритма с большим количеством раундов (включая полную 16-раундовую) вскрываются различными путями.

Использованием характеристик, распространяющихся на большее количество раундов (но с меньшей вероятностью). Например, в приведена 5-раундовая характеристика для DES с вероятностью 0,000095.

Параллельное использование двух и более различных характеристик.

Итеративные характеристики могут «размножаться» на требуемое количество раундов (конечно, также с потерей в вероятности), поскольку их структура подразумевает, что в выходной разности значения, меняются местами относительно входной разности (что необходимо для «размножения» характеристики, поскольку субблоки в DES меняются местами в конце раунда).

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

Если дифференциальный криптоанализ и был известен еще в середине 1970-х гг., то явно не всем разработчикам алгоритмов шифрования — многие из более поздних алгоритмов могут быть вскрыты этим методом. Рассмотрим наиболее показательные примеры.

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