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

Первые открытые упоминания в литературе с 1990 года в работах Мерфи, Бихема и Шамира. Методика анализа строится индивидуально для каждого алгоритма и основана на знании пар сообщений m и m’ для которых известны соответствующие шифртексты Ek(m) и Ek(m’) и XOR-разности между ними с рассмотрением разности между промежуточными частями блоков сообщений.

Для двухветвевой сети Файстеля Δmi = mi Å m’i. При этом для каждого раунда в отдельности справедливо следующее:

Δmi+1 = mi+1 Å m’i+1 = Δmi-1 Å [f(mi,Ki) Å f(m’i,Ki)]

Предполагается, что для многих пар входных данных функции f, имеющих одну и ту же XOR-разность, при использовании одного и того же подключа одинаковой оказывается и XOR-разность для соответствующих выходных пар. Формально говорят, что X влечет Y с вероятностью р, если для относительной доли р входных пар с XOR-разностью Х для соответствующих выходных пар XOR-разность оказывается равной Y. Предположим теперь, что имеется ряд значений X, которые с высокой вероятностью влекут определенные разности выходных значений. Тогда если нам с большой вероятностью известны значения Δmi-1 и Δmi то мы с большой вероятностью можем определить и Δmi-1. А если удастся найти достаточно много таких значений разности, становится возможным определить подключ, используемый функцией f.

Общая стратегия дифференциального криптоанализа основывается на представленной выше методике для каждого раунда шифрования в отдельности. Процедура начинается с рассмотрения двух сообщений открытого текста m и m' с заданной разностью и имеет своей целью получение вероятностных оценок разностей промежуточных результатов последовательно раунд за раундом с тем, чтобы определить вероятностную оценку для разности соответствующих шифрованных текстов. На самом деле получаются вероятностные оценки для двух 32-битовых половинок сообщения (m17 || m16). После этого выполняется шифрование m и m’, чтобы определить реальные разности при неизвестном ключе, а затем , сравнить результат с вычисленными вероятностными оценками. Если результаты совпадают, т.е.

Ек(m) Å Ек(m’) = (Δm17||m16),

то можно ожидать, что вероятностные оценки для всех раундов соответствуют реальности. Это позволяет сделать определенные заключения о некоторых битах ключа. Чтобы определить все биты ключа, процедуру приходится повторять много раз.