Cómo revertir esta AND bit a bit XOR-algoritmo de codificación?

Question

Me han dado una "codificación" algoritmo que realiza bit a bit XOR y and bit a bit. Originalmente se trata de un código C que opera en números enteros con poco cambios, pero me lo han traducido en un simple pseudocódigo que utiliza matrices de bits (1-indexada):

N es una potencia de 2 estrictamente mayor que 1.

encode

A modo de ilustración, aquí hay un "en vivo" programa de C++: http://ideone.com/NBGGPS

---

Por ejemplo yo tengo desenrolló para N = 8, entonces B es como este (símbolos: & Y, ^ para XOR):

B[1] = 0
B[2] = (A1[1] Y UN2[1])
B[3] = (A1[1] Y UN2[2]) ^ (1[2] Y UN2[1])
B[4] = (A1[1] Y UN2[3]) ^ (1[2] Y UN2[2]) ^ (1[3] Y UN2[1])
B[5] = (A1[1] Y UN2[4]) ^ (1[2] Y UN2[3]) ^ (1[3] Y UN2[2]) ^ (1[4] Y UN2[1])
B[6] =  (A1[2] Y UN2[4]) ^ (1[3] Y UN2[3]) ^ (1[4] Y UN2[2])
B[7] =  (A1[3] Y UN2[4]) ^ (1[4] Y UN2[3])
B[8] =  (A1[4] Y UN2[4])

Que se asemeja a un sistema de N ecuaciones con N variables (a sabiendas de que para los bits ( y A):

$$\begin{eqnarray} b_1 & = & 0 & & & & & & & \\ b_2 & = & x_1 \cdot x_5 & & & & & & & \\ b_3 & = & x_1 \cdot x_6 & + & x_2 \cdot x_5 & & & & & \pmod 2 \\ b_4 & = & x_1 \cdot x_7 & + & x_2 \cdot x_6 & + & x_3 \cdot x_5 & & & \pmod 2 \\ b_5 & = & x_1 \cdot x_8 & + & x_2 \cdot x_7 & + & x_3 \cdot x_6 & + & x_4 \cdot x_5 & \pmod 2 \\ b_6 & = & & & x_2 \cdot x_8 & + & x_3 \cdot x_7 & + & x_4 \cdot x_6 & \pmod 2 \\ b_7 & = & & & & & x_3 \cdot x_8 & + & x_4 \cdot x_7 & \pmod 2 \\ b_8 & = & & & & & & & x_4 \cdot x_8 & \\ \end{eqnarray}$$

---

Algunos (informal) pensamientos:

1. Es una especie de "simétrico": se obtiene el mismo resultado si intercambia las dos mitades de A.
2. He visto ejemplos que usted puede conseguir el mismo resultado para los diferentes insumos ("diferentes", no sólo por simetría), por lo que es de "pérdida".
3. Parece un "sin llave de cifrado XOR" (bueno, no estoy seguro, éste aún tiene sentido...).

---

Ahora el reto es "inversa", es decir, escribir algún algoritmo de decodificación tal que decodificar( codificar(A) ) = A.

Pero después de la viñeta 2 de arriba (y también 1) sabemos que la solución no es única, por lo que debe más bien encontrar una posible solución que codifican( decode_one( codificar(A) ) ) = codificar(A), o tal vez podamos encontrar todas las soluciones posibles, es decir, un algoritmo que decode_all( codificar(A) ) = { X | codificar(X) = codificar(A) }.

(Por supuesto, "fuerza bruta", no es interesante.)

Ahora estoy completamente atascado en... Por ejemplo, si B[2] = 1, entonces sé que tanto a₁[1] y₂[1] son el 1, pero si B[2] = 0, entonces sólo puedo decir que Un₁[1] y₂[1] no son ambos 1 (que puede ser 0 o un 0 y el 1). A continuación, para B[3] el XOR entra y multiplica las posibilidades...

He intentado de alguna manera "combinar" varias ecuaciones de la desenrollar el condón pero no es lineal.

¿Cuál sería el camino a seguir?

_{(También siéntase libre de editar el post por ejemplo, para añadir etiquetas relevantes.)}

Answer 1

Cifrado:

Lo que su sistema de ecuaciones que muestra es que el cifrado es equivalente a la multiplicación de dos polinomios de grado N/2 en GF(2) (álgebra de dos elementos {1,0}, donde 1+1=0, es decir + = XOR).

La "prueba":

Vamos A1 ser una matriz de los coeficientes de A1: $A1[1]\times x^0+A1[2]\times x^1+A1[3]\times x^2+...$

Lo mismo va para el A2

Deje que B es el producto de polinomio de $B=A1\times A2$

Polinomio de multiplicación te ofrece:

$B=(A1[1]\times x^0+A1[2]\times x^1+A1[3]\times x^2+...)\times(A2[1]\times x^0+A2[2]\times x^1+A2[3]\times x^2+...)$

$B=(A1[1]\times A2[1]\times x^0+(A1[2]\times A2[1]+A2[2]\times A1[1])\times x^1+...)$

En general $B[i]=Sum(A1[n]\times A2[l],n+l==i+1)$ (%2 porque de GF(2))

Usted escribió:

$B[5] = (A1[1] & A2[4]) ^ (A1[2] & A2[3]) ^ (A1[3] & A2[2]) ^ (A1[4] & A2[1])$

Esta es exactamente la fórmula anterior para i=4, usted tiene $B[1]=0$, por lo que hay un cambio: su $B[5]$ es el coeficiente de frente x^3.

Descifrado:

Si el cifrado es el polinomio de la multiplicación de dos polinomios de grado N/2, el descifrado es el polinomio factorización en dos partes de grado menor que N/2. Esto se puede hacer con el Algoritmo de Berlekamp o Cantor–Zassenhaus Algoritmo

Nota estos algoritmos se va a trabajar, porque estamos en un campo finito GF(2) donde los coeficientes se han finito de valores posibles.