Дифференциальные уравнения сложения - Differential equations of addition

В криптография, дифференциальные уравнения сложения (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.

Ли, Чэнцин; Лю Юаньшэн; Чжан, Лео Ю; Чен, Майкл З. К. (2013-04-01). «Взлом алгоритма шифрования хаотических изображений, основанного на сложении по модулю и операции xor». Международный журнал бифуркаций и хаоса. 23 (4): 1350075. arXiv:1207.6536. Bibcode:2013IJBC ... 2350075L. Дои:10.1142 / S0218127413500752. ISSN  0218-1274.