función de transformación lineal

Question

Necesito escribir una función que tome 4 bytes como entrada, realice una transformación lineal reversible en esto y la devuelva como 4 bytes.

Pero espere, hay más: también tiene que ser distributivo, por lo que cambiar un byte en la entrada debería afectar a los 4 bytes de salida.

Los problemas:

• si uso la multiplicación, no será reversible después de que se modifique 255 a través del almacenamiento como un byte (y necesita permanecer como un byte)
• si uso la suma no puede ser reversible y distributiva

Una solución: Podría crear una matriz de bytes de 256 ^ 4 de largo y completarla, en un mapeo uno a uno, esto funcionaría, pero hay problemas: esto significa que tengo que buscar un gráfico de tamaño 256 ^ 8 debido a tener que buscar para números libres para cada valor (debe tener en cuenta que la distributividad debe ser sudo aleatoria en función de una matriz de bytes de 64 * 64). Esta solución también tiene el problema MENOR (lol) de necesitar 8 GB de RAM, lo que hace que esta solución no tenga sentido.

El dominio de la entrada es el mismo que el dominio de la salida, cada entrada tiene una salida única, en otras palabras: un mapeo uno a uno. Como señalé en '' una solución '' esto es muy posible y he usado ese método cuando un dominio más pequeño (solo 256) estaba en cuestión. El hecho es que, a medida que los números se hacen más grandes, ese método se vuelve extraordinariamente ineficiente, el defecto delta era O (n ^ 5) y omega era O (n ^ 8) con una astucia similar en uso de memoria.

Me preguntaba si había una manera inteligente de hacerlo. En pocas palabras, es una asignación de dominio uno a uno (4 bytes o 256 ^ 4). Ah, y cosas tan simples como N + 1 no se pueden usar, se debe extraer de una matriz de 64 * 64 de valores de bytes que son sudo aleatorios pero que se pueden recrear para transformaciones inversas.

Answer 1

Aquí están sus requisitos tal como los entiendo:

1. Deje que B sea el espacio de bytes. Desea una función uno a uno (y, por lo tanto, sobre) f: B ^ 4 - > B ^ 4 .
2. Si cambia cualquier byte de entrada, todos los bytes de salida cambian.

Aquí está la solución más simple que tengo hasta ahora . He evitado publicar durante un tiempo porque seguí intentando encontrar una solución mejor, pero no he pensado en nada.

Bien, antes que nada, necesitamos una función g: B - > B que toma un solo byte y devuelve un solo byte. Esta función debe tener dos propiedades: g (x) es reversible y x ^ g (x) es reversible. [Nota: ^ es el operador XOR.] Cualquiera de estos g funcionará, pero definiré uno específico más adelante.

Dado tal ag, definimos f por f (a, b, c, d) = (a ^ b ^ c ^ d, g (a) ^ b ^ c ^ d, a ^ g (b) ^ c ^ d, a ^ b ^ g (c) ^ d). Verifiquemos sus requisitos:

1. Reversible: sí. Si XOR los primeros dos bytes de salida, obtenemos a ^ g (a), pero por la segunda propiedad de g, podemos recuperar a. Del mismo modo para el byc. Podemos recuperar d después de obtener a, byc haciendo XOR al primer byte con (a ^ b ^ c).
2. Distributivo: sí. Supongamos que b, cyd son fijos. Entonces la función toma la forma f (a, b, c, d) = (a ^ const, g (a) ^ const, a ^ const, a ^ const). Si a cambia, también lo hará a ^ const; de manera similar, si a cambia, también lo hará g (a), y así también lo hará g (a) ^ const. (El hecho de que g (a) cambie si a does es por la primera propiedad de g; si no fuera así, g (x) no sería reversible). Lo mismo vale para byc. Para d, es aún más fácil porque entonces f (a, b, c, d) = (d ^ const, d ^ const, d ^ const, d ^ const) así que si d cambia, cada byte cambia.

Finalmente, construimos dicha función g. Sea T el espacio de los valores de dos bits y h: T - > T la función de modo que h (0) = 0, h (1) = 2, h (2) = 3 y h (3) = 1. Esta función tiene las dos propiedades deseadas de g, es decir, h (x) es reversible y también lo es x ^ h (x). (Para lo último, verifique que 0 ^ h (0) = 0, 1 ^ h (1) = 3, 2 ^ h (2) = 1 y 3 ^ h (3) = 2.) Entonces, finalmente, a calcule g (x), divida x en cuatro grupos de dos bits y tome h de cada cuarto por separado. Debido a que h satisface las dos propiedades deseadas, y no hay interacción entre los trimestres, también lo hace g.

Answer 2

Mezcladores de bloque equilibrados son exactamente lo que estás buscando.

¿Quién sabía?

Answer 3

Editar! Es no posible, si realmente desea una transformación lineal. Aquí está la solución matemática:

Tienes cuatro bytes, a_1, a_2, a_3, a_4 , que consideraremos como un vector a con 4 componentes, cada uno de los cuales es un número mod 256. Una transformación lineal es solo una matriz 4x4 M cuyos elementos también son números mod 256. Tiene dos condiciones:

1. De Ma , podemos deducir a (esto significa que M es una matriz invertible ).
2. Si a y a' difieren en una sola coordenada, entonces M a y Ma' deben diferir en cada coord.

La condición (2) es un poco más complicada, pero esto es lo que significa. Como M es una transformación lineal, sabemos que

  

M(a - a ) = M a - Ma'

A la izquierda, ya que a y a' difieren en una sola coordenada, < code> a - a tiene exactamente una coordenada distinta de cero. A la derecha, desde Ma y M a ' debe diferir en cada coordenada, Ma - M a ' debe tener cada coordenada distinta de cero.

Entonces la matriz M debe tomar un vector con una sola coordenada distinta de cero a una con todas las coordenadas distintas de cero. Por lo tanto, solo necesitamos que cada entrada de M sea un mod 256 distinto de cero divisor , es decir, que sea impar.

Volviendo a la condición (1), ¿qué significa que M sea invertible? Como lo estamos considerando mod 256, solo necesitamos que su determinante sea mod 256 invertible; es decir, su determinante debe ser impar.

Entonces necesita una matriz 4x4 con entradas impares mod 256 cuyo determinante es impar. Pero esto es imposible! ¿Por qué? El determinante se calcula sumando varios productos de entradas. Para una matriz 4x4, ¡hay 4! = 24 sumandos diferentes, y cada uno, como producto de entradas impares , es impar. Pero la suma de 24 números impares es par, por lo que el determinante de dicha matriz debe ser par.

Answer 4

No estoy seguro de entender tu pregunta, pero creo que entiendo lo que intentas hacer.

Bitwise Exclusive O es tu amigo.

Si R = A XOR B, R XOR A da B y R XOR B devuelve A. Por lo tanto, es una transformación reversible, suponiendo que conozca el resultado y una de las entradas.

Answer 5

Suponiendo que entendí lo que estás tratando de hacer, creo que cualquier cifra de bloque lo hará hacer el trabajo.
Un cifrado de bloque toma un bloque de bits (digamos 128) y los asigna de forma reversible a un bloque diferente con el mismo tamaño.

Además, si está utilizando modo OFB puede usar un cifrado de bloque para generar Un flujo infinito de bits seudoaleatorios. XORing estos bits con su flujo de bits le dará una transformación para cualquier longitud de datos.

Answer 6

Voy a descartar una idea que puede o no funcionar.

Use un conjunto de funciones lineales mod 256, con coeficientes primos impares.

Por ejemplo:

b0 = 3 * a0 + 5 * a1 + 7 * a2 + 11 * a3;
b1 = 13 * a0 + 17 * a1 + 19 * a2 + 23 * a3;

Si recuerdo el Teorema del resto chino correctamente, y no lo he mirado en años, el hacha se puede recuperar del bx. Incluso puede haber una forma rápida de hacerlo.

Esta es, creo, una transformación reversible. Es lineal, en ese af (x) mod 256 = f (ax) yf (x) + f (y) mod 256 = f (x + y). Claramente, cambiar un byte de entrada cambiará todos los bytes de salida.

Entonces, busque el Teorema del resto chino y vea si esto funciona.

Answer 7

¿Qué quiere decir con "lineal"? ¿transformación? O (n), o una función f con f (c * (a + b)) = c * f (a) + c * f (b)?

Un enfoque fácil sería un desplazamiento de bits giratorio (no estoy seguro si esto cumple la definición matemática anterior). Es reversible y cada byte se puede cambiar. Pero con esto no exige que se modifique cada byte.

EDITAR: Mi solución sería esta:

b0 = (a0 ^ a1 ^ a2 ^ a3)
b1 = a1 + b0 ( mod 256)
b2 = a2 + b0 ( mod 256)
b3 = a3 + b0 ( mod 256)

Sería reversible (solo resta el primer byte del otro, y luego XOR los 3 bytes resultantes en el primero), y un cambio en un bit cambiaría cada byte (ya que b0 es el resultado de todos los bytes e impactos todos los demás).

Answer 8

Pegue todos los bytes en un número de 32 bits y luego haga un shl o shr (desplazamiento a la izquierda o desplazamiento a la derecha) en uno, dos o tres. Luego, divídalo nuevamente en bytes (podría usar un registro variante). Esto moverá bits de cada byte al byte adyacente.

Aquí hay una serie de buenas sugerencias (XOR, etc.). Sugeriría combinarlas.

Answer 9

Podrías reasignar los bits. Usemos ii para entrada y oo para salida:

oo[0] = (ii[0] & 0xC0) | (ii[1] & 0x30) | (ii[2] & 0x0C) | (ii[3] | 0x03)
oo[1] = (ii[0] & 0x30) | (ii[1] & 0x0C) | (ii[2] & 0x03) | (ii[3] | 0xC0)
oo[2] = (ii[0] & 0x0C) | (ii[1] & 0x03) | (ii[2] & 0xC0) | (ii[3] | 0x30)
oo[3] = (ii[0] & 0x03) | (ii[1] & 0xC0) | (ii[2] & 0x30) | (ii[3] | 0x0C)

No es lineal, pero cambiar significativamente un byte en la entrada afectará a todos los bytes en la salida. No creo que pueda tener una transformación reversible, como cambiar un bit en la entrada afectará a los cuatro bytes de la salida, pero no tengo una prueba.