WikiSort.ru - Не сортированное

Анализ одного раунда

Базовый метод дифференциального криптоанализа — это атака на основе адаптивно подобранных открытых текстов, хотя у него есть расширение для атаки на основе открытых текстов. Для проведения атаки используются пары открытых текстов, связанных определенной разницей. Для DES и DES-подобных систем она определяется как исключающее ИЛИ (XOR). При расшифровке необходимо только значение соответствующих пар шифротекстов.

На схеме изображена функция Фейстеля . Пусть ${\displaystyle X}$ и ${\displaystyle X'}$ - пара входов, различающихся на ${\displaystyle \Delta X}$ . Соответствующие им выходы известны и равны ${\displaystyle Y}$ и ${\displaystyle Y'}$ , разница между ними - ${\displaystyle \Delta Y}$ . Также известны перестановка с расширением и ${\displaystyle P}$ -блок, поэтому известны ${\displaystyle \Delta A}$ и ${\displaystyle \Delta C}$ . ${\displaystyle B}$ и ${\displaystyle B'}$ неизвестны, но мы знаем, что их разность равна ${\displaystyle \Delta A}$ , т.к. различия ${\displaystyle XOR\ K_{i}}$ c ${\displaystyle A}$ и ${\displaystyle A'}$ нейтрализуются. Единственные нелинейные элементы в схеме — это ${\displaystyle S}$ -блоки. Для каждого ${\displaystyle S}$ -блока можно хранить таблицу, строки которой — разности на входе ${\displaystyle S}$ -блока, столбцы — разности на выходе, а на пересечении — число пар, имеющих данные входную и выходную разности, и где-то хранить сами эти пары.

Вскрытие раундового ключа основано на том факте, что для заданного ${\displaystyle \Delta A}$ не все значения ${\displaystyle \Delta C}$ равновероятны, а комбинация ${\displaystyle \Delta A}$ и ${\displaystyle \Delta C}$ позволяет предположить значения ${\displaystyle A\ XOR\ K_{i}}$ и ${\displaystyle A'\ XOR\ K_{i}}$ . При известных ${\displaystyle A}$ и ${\displaystyle A'}$ это позволяет определить ${\displaystyle K_{i}}$ . За исключением ${\displaystyle \Delta C}$ вся необходимая информация для последнего раунда содержится в итоговой паре шифротекстов.

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

Характеристики

Для определения возможных отличий полученных на i-м раунде шифротекстов используются раундовые характеристики.

N-раундовая характеристика представляет собой кортеж ${\displaystyle \Omega \ =\ (\Omega _{P},\Omega _{\Lambda },\Omega _{T})}$ , составляется из различий открытого текста ${\displaystyle \Omega _{P}}$ , различий шифротекста ${\displaystyle \Omega _{T}}$ и набора ${\displaystyle \Omega _{\Lambda }\ =\ (\Lambda _{1},\Lambda _{2},\ ...\ ,\Lambda _{n})}$ различий промежуточных результатов шифрования для каждого прошедшего раунда.

Характеристике присваивается вероятность, равная вероятности что случайная пара открытых текстов с различием ${\displaystyle \Omega _{P}}$ в результате шифрования со случайными ключами имеет раундовые различия и различия шифротекстов, совпадающие с указанными в характеристике. Соответствующая характеристике пара открытых текстов называется «правильной». Не соответствующие характеристике пары открытых текстов зовутся «неправильными».

Примем значение разницы текстов на выходе предпоследнего цикла, используемое при определении возможного подключа последнего раунда, ${\displaystyle \Delta A=\Omega _{T}}$ . В таком случая «правильная» пара текстов позволяет определить правильный ключ, в то время как «неправильная» пара определяет случайный ключ.

В атаке обычно одновременно используются несколько характеристик. Для экономии памяти обычно используются структуры.

• Квартет — структура из четырёх текстов, которая одновременно содержит в себе по две пары текстов для двух разных характеристик. Позволяет сэкономить 1/2 памяти для открытых текстов.
• Октет — структура из 16 текстов, содержащая 8 пар, по 4 на каждую характеристику. Позволяет сэкономить 2/3 памяти для открытых текстов.

Эффективность взлома

С увеличением числа раундов сложность криптоанализа увеличивается, однако остаётся меньше сложности полного перебора при количестве циклов меньше 16.

Зависимость от количества раундов
Число раундов	Трудоёмкость атаки
${\displaystyle 4}$	${\displaystyle 2^{4}}$
${\displaystyle 6}$	${\displaystyle 2^{8}}$
${\displaystyle 8}$	${\displaystyle 2^{16}}$
${\displaystyle 9}$	${\displaystyle 2^{26}}$
${\displaystyle 10}$	${\displaystyle 2^{35}}$
${\displaystyle 11}$	${\displaystyle 2^{36}}$
${\displaystyle 12}$	${\displaystyle 2^{43}}$
${\displaystyle 13}$	${\displaystyle 2^{44}}$
${\displaystyle 14}$	${\displaystyle 2^{51}}$
${\displaystyle 15}$	${\displaystyle 2^{52}}$
${\displaystyle 16}$	${\displaystyle 2^{58}}$

Устройство S-блоков также значительно влияет на эффективность дифференциального криптоанализа. S-блоки DES, в частности, оптимизированы для устойчивости к атаке.

Сравнение с другими методами

См. Известные атаки на DES