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

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

Примеры [ править ]

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

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

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

Пусть набор

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

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

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

Приложения [ править ]

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

Дальнейшее чтение [ править ]

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

Ссылки [ править ]