8.4.8Дифференциальный метод криптоанализа des.

Дифференциальный метод криптоанализа (ДКА) был предложен Э.Бихамом и A.Шамиром в 1990 г. Дифференциальный криптоанализ - это попытка вскрытия секретного ключа блочных шифров. При анализе предполагается, что на каждом цикле используется свой подключ шифрования. Данный метод основан на анализе пар открытых текстов, между которыми существует определенная разность (difference). При анализе различных алгоритмов разность текстов может быть определена различным образом. Для DES разность открытых текстов и определена как операция XOR между данными текстами:

.

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

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

= .

Разность Å , т.е. разность после обработки и расширяющей перестановкой EP, весьма легко определить, поскольку:

.

Наложение фрагмента ключа операцией XOR вообще не меняет разность, т.е.:

Å .

Аналогично преобразованию EP, легко вычислить разность D_bp после перестановки P:

Å Å .

Таким образом, единственной операцией из выполняемых функцией f(), существенно влияющей на значение разности, остается табличная замена. Значение зависит не только от разности , но и от конкретных входных значений и . Здесь-то и проявляется влияние наложенного предыдущей операцией ключа шифрования. Как было сказано выше, таблицы замен меняют 6-битное входное значение на 4- битное. Это означает, что любой входной разности (где n – номер таблицы) соответствует = 64 возможных пар входных значений (обозначим их и ).

Соответственно, любой выходной разности соответствует 4 = 16 возможных пар и . Дифференциальный криптоанализ алгоритма DES эксплуатирует тот факт, что, во- первых, каждое конкретное значение приводит не ко всем возможным 16 значениям , а во-вторых, данные значения имеют весьма различную вероятность. Бихам и Шамир в качестве примера рассматривают таблицу S1 и ее входную разность = 34.

Возможные значения и их вероятности (в количестве значений пар и из 64 возможных, которые приводят к данному значению ) приведены в следующей таблице

Значение	Вероятность
1	8
2	16
3	6
4	2
7	12
8	6
D	8
F	6
Остальные	0
Всего	64

Как с помощью всего этого можно определить ключ, рассмотрим на простейшем примере. Предположим, что в распоряжении криптоаналитика имеется пара текстов с = 34. Кроме того, у криптоаналитика есть соответствующие им шифротексты (опять же, предположим, что для их зашифрования использовался однораундовый DES) с = 4. Входные значения S1 при таких условиях известны – это значения 13 и 27 ( = 13, а = 27, или наоборот). Получается, что криптоаналитик знает значения и (поскольку ему известны открытые тексты), а также два варианта значений и . В результате криптоаналитик может простейшей операцией XOR вычислить 2 возможных варианта первых шести бит . Выбрать из двух вариантов правильный криптоаналитику поможет вторая пара открытых текстов, если таковая у него есть. Даже если такой пары нет, криптоаналитик существенно сузил область возможных значений ключа: в раз.