WikiDer > Дифференциальные уравнения сложения

В криптография, дифференциальные уравнения сложения (DEA) - одно из самых основных уравнений, связанных с дифференциальный криптоанализ которые смешивают сложения по двум разным группам (например, сложение по модулю 2³² и сложение по GF (2)), и где входные и выходные различия выражаются как XOR.

Примеры дифференциальных уравнений сложения.

Дифференциальные уравнения сложения (DEA) имеют следующий вид:

${displaystyle (x + y) oplus ((xoplus a) + (yoplus b)) = c}$

где ${displaystyle x}$ и ${displaystyle y}$ находятся ${displaystyle n}$-немного неизвестно переменные и ${displaystyle a}$, ${displaystyle b}$ и ${displaystyle c}$ находятся известный переменные. Символы ${displaystyle +}$ и ${displaystyle oplus}$ обозначать сложение по модулю ${displaystyle 2 ^ {n}}$ и побитовое исключающее ИЛИ соответственно. Вышеприведенное уравнение обозначено ${displaystyle (a, b, c)}$.

Пусть набор ${displaystyle S = {(a_ {i}, b_ {i}, c_ {i}) | i}$ целое число меньше, чем ${displaystyle k}}$ обозначают систему ${displaystyle k}$ ДЭА где ${displaystyle k}$ является многочленом от ${displaystyle n}$. Доказано, что выполнимость произвольного набора DEA находится в класс сложности P когда поиск грубой силы требует экспоненциальное время. В 2013 году некоторые свойства особой формы

О DEA сообщили Chengqing Li et al., Где ${displaystyle a = 0}$ и ${displaystyle y}$ считается известным. По сути, специальный DEA можно представить в виде ${displaystyle (xdotplus alpha) oplus (xdotplus eta) = c}$. На основании найденных свойств разработан алгоритм вывода ${displaystyle x}$ был предложен и проанализирован.^[1]

Использование дифференциальных уравнений сложения.

Решение произвольного набора DEA (либо в пакетном режиме, либо в модели адаптивного запроса) было связано с Сурадьюти Пол и Барт Пренил. Методы решения были использованы для атаки на потоковый шифр. Спираль.

использованная литература

• Сурадьюти Пол и Барт Пренил, Решение систем дифференциальных уравнений сложения, ACISP 2005. Полная версия (PDF)
• Сурадьюти Пол и Барт Пренил, Алгоритмы, близкие к оптимальным для решения дифференциальных уравнений сложения с помощью пакетных запросов, Индокрипт 2005. Полная версия (PDF)
• Хельгер Липмаа, Йохан Валлен, Филипп Дюма: об аддитивной дифференциальной вероятности исключающего ИЛИ. FSE 2004: 317-331.