Разностный криптоанализ

Дифференциальный криптоанализ(ДКА) основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю . Является статистической атакой, в результате работы предлагает список наиболее вероятных ключей шифрования блочного симметричного шифра.

На схеме представлено прохождение одного из этапов DES. Пусть X и X' - пара входов, различающихся на ΔX. Соответствующие им выходы известны и равны Y и Y', разница между ними - ΔY. Также известны перестановка с расширением и P-блок, поэтому известны ΔA и ΔC. B и B' неизвестны, но мы знаем, что их разность равна ΔA, т.к. различия XOR K_i c A и A' нейтрализуются. Вскрытие ключа основано на том факте, что для заданного ΔA не все значения ΔC равновероятны, а комбинация ΔA и ΔC позволяет предположить значения A XOR K_i и A' XOR K_i. При известных A и A' это дает нам информацию о K_i.

Таким образом, определенные отличия пар открытых текстов с высокой вероятностью вызывают определенные отличия получаемых шифротекстов. Такие различия называют характеристиками. Для нахождения характеристик составляется таблица, в которой строкам соответствуют возможные ΔX, столбцам - возможные ΔY, а на пересечении строки и столбца пишется, сколько раз заданное ΔY встречается для заданного ΔX. Различные характеристики можно объединять, и, при условии, что рассматриваемые этапы независимы, перемножать их вероятности.

Пара открытых текстов, которая соответствует характеристике называется правильной парой, а пара, не соответствующая характеристике - неправильной парой. Правильная пара указывает на правильный ключ рассматриваемого этапа, неправильная - на случайный ключ. Для нахождения правильного ключа этапа нужно собрать достаточное количество предположений - один из ключей будет встречаться среди правильных чаще, чем остальные. Зная вероятное значение K_i мы получаем 48 битов ключа шифрования K. Остальные 8 битов можно определить с помощью перебора.