Ecuaciones diferenciales de adición

Ecuaciones en criptoanálisis diferencial

En criptografía , las ecuaciones diferenciales de adición (DEA) son una de las ecuaciones más básicas relacionadas con el criptoanálisis diferencial que mezclan adiciones sobre dos grupos diferentes (por ejemplo, adición módulo 2 ³² y adición sobre GF(2)) y donde las diferencias de entrada y salida se expresan como XOR.

Ejemplos

Las ecuaciones diferenciales de adición (EDA) tienen la siguiente forma:

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

donde y son variables desconocidas de -bit y , y son variables conocidas . Los símbolos y denotan adición módulo y operación exclusiva-or a nivel de bits respectivamente. La ecuación anterior se denota por . ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle +}$ ${\displaystyle \oplus }$ ${\displaystyle 2^{n}}$ ${\displaystyle (a,b,c)}$

Deje un conjunto

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

para entero denota un sistema de DEA donde es un polinomio en . Se ha demostrado que la satisfacibilidad de un conjunto arbitrario de DEA está en la clase de complejidad P cuando una búsqueda de fuerza bruta requiere un tiempo exponencial . ${\displaystyle i}$ ${\displaystyle k(n)}$ ${\displaystyle k(n)}$ ${\displaystyle n}$

En 2013, Chengqing Li et al. informaron algunas propiedades de una forma especial de DEA, donde se supone que y se conocen. Básicamente, la DEA especial se puede representar como . Con base en las propiedades encontradas, se propuso y analizó un algoritmo para derivar . ^[1] ${\displaystyle a=0}$ ${\displaystyle y}$ ${\displaystyle (x\dotplus \alpha )\oplus (x\dotplus \beta )=c}$ ${\displaystyle x}$

Aplicaciones

La solución a un conjunto arbitrario de DEA (ya sea en lotes o en un modelo de consulta adaptativo) se debió a Souradyuti Paul y Bart Preneel . Las técnicas de solución se han utilizado para atacar el cifrado de flujo Helix .

Lectura adicional

• Souradyuti Paul y Bart Preneel , Resolución de sistemas de ecuaciones diferenciales de adición, ACISP 2005. Versión completa ( PDF )
• Souradyuti Paul y Bart Preneel , Algoritmos casi óptimos para resolver ecuaciones diferenciales de suma con consultas por lotes, Indocrypt 2005. Versión completa ( PDF )
• Helger Lipmaa, Johan Wallén, Philippe Dumas: Sobre la probabilidad diferencial aditiva de O-exclusivo. FSE 2004: 317-331.

Referencias

1. Li, Chengqing; Liu, Yuansheng; Zhang, Leo Yu; Chen, Michael ZQ (1 de abril de 2013). "Rompiendo un algoritmo de cifrado de imágenes caótico basado en la adición de módulo y la operación xor". Revista Internacional de Bifurcación y Caos . 23 (4): 1350075. arXiv : 1207.6536 . Bibcode :2013IJBC...2350075L. doi :10.1142/S0218127413500752. ISSN  0218-1274. S2CID  15990771.