В1990 году Эли Бихам и Ади Шамир ввели понятие дифференциального криптоанализа[167, 168, 171, 172]. Это был новый, ранее неизвестный метод криптоанализа. Используя этот метод, Бихам и Шамир нашли способ вскрытия DES с использованием выбранного открытого текста, который был эффективнее вскрытия гр у-бой силой.
Дифференциальный криптоанализ работает с парами шифротекстов,открытые тексты которых содержат определенные отличия. Метод анализирует эволюцию этих отличий в процессе прохождения открытых текстов
через этапы DES при шифровании одним и тем же ключом.
Просто выберем пару открытых текстов с фиксированным различием. Можно выбрать два открытых текста случайным образом, лишь бы они отличались друг от друга определенным образом, криптоаналитику даже не нужно знать их значений. (Для DES термин "различие" определяется с помощью XOR. Для других алгоритмов этот термин может определяться по другому.) Затем, используя различия в получившихся шифротекстах, пр и-своим различные вероятности различным ключам. В процессе дальнейшего анализа следующих пар шифроте к-стов один из ключей станет наиболее вероятным. Это и есть правильный ключ.
Подробности гораздо сложнее. На 7-й представлена функция одного этапа DES. Представьте себе пару вх о-дов, ХиХ', с различием АХ. Выходы, 7 и У известны, следовательно, известно и различие между ними А У. Известны и перестановка с расширением, и Р-блок, поэтому известны АА и АС. В и В' неизвестны, но их разность AS известна и равна АА. (При рассмотрении различия XOR К, с А и А' нейтрализуются.) Пока все просто. Фокус вот в чем: для любого заданного АА не все значения АС равновероятны. Комбинация АА и АС позволяет предположить значения битов для A XOR К, и А' XOR Kt. Так как А и А' известны, это дает нам информацию о Kt.
X
D x
Е
| Е(Х) | *С | К | |||
| D | h* | ||||
| >(J |
i
S-блок
DC
P
D Y
Y