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

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

Примеры

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

$(x+y)\oplus ((x\oplus a)+(y\oplus b))=c$

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

Пусть набор

$S=\{(a_{i},b_{i},c_{i})|i<k\}$

для целого числа $i$ обозначают систему $k(n)$ DEA , где $k(n)$ является полиномом по $n$. Доказано, что выполнимость произвольного набора DEA находится в классе сложности P , когда перебор требует экспоненциального времени .

В 2013 году о некоторых свойствах особой формы DEA сообщили Chengqing Li et al., где $a=0$ и $y$ предполагается известным. По существу, специальный DEA можно представить в виде $(x\dotplus \alpha )\oplus (x\dotplus \beta )=c$. На основе найденных свойств разработан алгоритм вывода $x$ было предложено и проанализировано.

Приложения

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

Дальнейшее чтение

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