algorithm - international - Algoritmo biyectivo simétrico para enteros
como funciona el algoritmo aes (11)
Necesito un algoritmo que pueda hacer un mapeo uno-a-uno (es decir, sin colisión) de un entero con signo de 32 bits en otro entero con signo de 32 bits.
Mi verdadera preocupación es la suficiente entropía para que el resultado de la función parezca ser aleatorio. Básicamente, estoy buscando un cifrado similar a XOR Cipher, pero eso puede generar resultados de aspecto más arbitrario. La seguridad no es mi verdadera preocupación, aunque la oscuridad sí lo es.
Editar para fines de aclaración:
- El algoritmo debe ser simétrico, de modo que pueda revertir la operación sin un par de teclas.
- El algoritmo debe ser bijective, cada número de entrada de 32 bits debe generar un número único de 32 bits.
- La salida de la función debe ser lo suficientemente oscura, agregar solo una a la entrada debe tener un gran efecto en la salida.
Ejemplo de resultado esperado:
F (100) = 98456
F (101) = -758
F (102) = 10875498
F (103) = 986541
F (104) = 945451245
F (105) = -488554
Al igual que MD5, cambiar una cosa puede cambiar muchas cosas.
Estoy buscando una función matemática, por lo que mapear números enteros manualmente no es una solución para mí. Para aquellos que preguntan, la velocidad del algoritmo no es muy importante.
¡Usa cualquier cifra de bloque de 32 bits! Por definición, un cifrado de bloques mapea cada valor de entrada posible en su rango a un valor de salida único, de forma reversible y, por diseño, es difícil determinar a qué asignará un valor determinado sin la clave. Simplemente elija una clave, manténgala en secreto si la seguridad u oscuridad es importante, y use el cifrado como su transformación.
Para una extensión de esta idea a rangos que no sean de potencia de 2, consulte mi publicación sobre permutaciones seguras con cifrado en bloque .
Abordando sus preocupaciones específicas:
- El algoritmo es de hecho simétrico. No estoy seguro de lo que quiere decir con "invertir la operación sin un par de llaves". Si no desea utilizar una clave, codifique una fuente generada aleatoriamente y considérela parte del algoritmo.
- Sí, por definición, un cifrado de bloque es bijectivo.
- Sip. No sería una buena cifra si ese no fuera el caso.
¿Puedes usar una tabla de búsqueda generada aleatoriamente? Siempre que los números aleatorios en la tabla sean únicos, obtendrá un mapeo biyectivo. Sin embargo, no es simétrico.
Una tabla de búsqueda de 16 GB para todos los valores de 32 bits probablemente no sea práctica, pero podría usar dos tablas de búsqueda separadas de 16 bits para la palabra alta y la palabra baja.
PD: creo que puedes generar una tabla de búsqueda simétrica de biyectivos, si eso es importante. El algoritmo comenzaría con un LUT vacío:
+----+ +----+
| 1 | -> | |
+----+ +----+
| 2 | -> | |
+----+ +----+
| 3 | -> | |
+----+ +----+
| 4 | -> | |
+----+ +----+
Elige el primer elemento, asígnale un mapeo aleatorio. Para hacer el mapeo simétrico, asigne el inverso también:
+----+ +----+
| 1 | -> | 3 |
+----+ +----+
| 2 | -> | |
+----+ +----+
| 3 | -> | 1 |
+----+ +----+
| 4 | -> | |
+----+ +----+
Elija el siguiente número, asigne de nuevo un mapeo aleatorio, pero elija un número que aún no haya sido asignado. (es decir, en este caso, no elija 1 o 3). Repita hasta que la LUT esté completa. Esto debería generar un mapeo simétrico de biyeye aleatorio.
Además de generar tablas de búsqueda aleatorias, puede usar una combinación de funciones:
- XOR
- permutación simétrica de bits (por ejemplo, desplazamiento de 16 bits, o flip 0-31 a 31-0, o flip 0-3 a 3-0, 4-7 a 7-4, ...)
- ¿Más?
Aquí está mi idea simple: puedes moverte por los bits del número, como propuso PeterK, pero puedes tener una permutación diferente de bits para cada número, y aún ser capaz de descifrarlo.
El cifrado es el siguiente: trate el número de entrada como una matriz de bits I[0..31] , y la salida como O[0..31] . Prepare una matriz K[0..63] de 64 números generados aleatoriamente. Esta será tu clave. Tome el bit del número de entrada de la posición determinada por el primer número aleatorio ( I[K[0] mod 32] ) y colóquelo al comienzo de su resultado ( O[0] ). Ahora, para decidir qué bit colocar en O[1] , use el bit utilizado anteriormente. Si es 0, usa K [1] para generar la posición en I partir de la cual tomar, es 1, usa K [2] (lo que simplemente significa omitir un número aleatorio).
Ahora esto no funcionará bien, ya que puede tomar el mismo bit dos veces. Para evitarlo, vuelva a numerar los bits después de cada iteración, omitiendo los bits utilizados. Para generar la posición desde la que tomar O[1] use I[K[p] mod 31] , donde p es 1 o 2, dependiendo del bit O[0] , ya que quedan 31 bits, numerados de 0 a 30.
Para ilustrar esto, daré un ejemplo:
Tenemos un número de 4 bits y 8 números aleatorios: 25, 5, 28, 19, 14, 20, 0, 18.
I: 0111 O: ____
_
25 mod 4 = 1, entonces tomaremos bit cuya posición es 1 (contando desde 0)
I: 0_11 O: 1___
_
Acabamos de tomar un poco de valor 1, así que omitimos un número al azar y usamos 28. Quedan 3 bits, entonces para contar la posición tomamos 28 mod 3 = 1. Tomamos el primero (contando desde 0) del bits restantes:
I: 0__1 O: 11__
_
Nuevamente omitimos un número, y tomamos 14. 14 mod 2 = 0, así que tomamos el 0º bit:
I: ___1 O: 110_
_
Ahora no importa, pero el bit anterior era 0, entonces tomamos 20. 20 mod 1 = 0:
I: ____ O: 1101
Y esto es todo.
Descifrar ese número es fácil, uno solo tiene que hacer las mismas cosas. La posición en la que colocar el primer bit del código se conoce a partir de la clave, las siguientes posiciones están determinadas por los bits previamente insertados.
Obviamente, esto tiene todas las desventajas de cualquier cosa que simplemente mueva los bits (por ejemplo, 0 se convierte en 0 y MAXINT se convierte en MAXINT), pero parece más difícil encontrar cómo alguien ha cifrado el número sin conocer la clave, que debe ser secreta.
Dibuja un círculo grande en una hoja grande de papel. Escriba todos los números enteros desde 0 hasta MAXINT en el sentido de las agujas del reloj desde la parte superior del círculo, igualmente espaciados. Escriba todos los enteros de 0 a MININT en sentido contrario a las agujas del reloj, igualmente espaciados de nuevo. Observe que MININT está al lado de MAXINT en la parte inferior del círculo. Ahora haga un duplicado de esta figura en ambos lados de una tarjeta rígida. Fija la tarjeta rígida al círculo a través de los centros de ambos. Elija un ángulo de rotación, cualquier ángulo que desee. Ahora tiene una asignación de 1-1 que cumple con algunos de sus requisitos, pero probablemente no sea lo suficientemente oscura. Suelte la tarjeta, déle vuelta alrededor de un diámetro, cualquier diámetro. Repita estos pasos (en cualquier orden) hasta que tenga una bijection con la que esté satisfecho.
Si lo ha estado siguiendo de cerca, no debería ser difícil programarlo en su idioma preferido.
Para aclarar después del comentario: si solo gira la tarjeta contra el papel, entonces el método es tan simple como usted se queja. Sin embargo, cuando voltea la tarjeta sobre el mapeo no es equivalente a (x+m) mod MAXINT para cualquier m . Por ejemplo, si deja la tarjeta sin girar y la gira alrededor del diámetro a través de 0 (que está en la parte superior de la esfera del reloj), entonces 1 se mapea a -1, 2 a -2, y así sucesivamente. (x+m) mod MAXINT corresponde a las rotaciones de la tarjeta solamente.
Divida el número en dos (16 bits más significativos y 16 bits menos significativos) y considere los bits en los dos resultados de 16 bits como tarjetas en dos mazos. Mezcla las cubiertas forzando una en la otra.
Entonces, si su número inicial es b31,b30,...,b1,b0 , termina con b15,b31,b14,b30,...,b1,b17,b0,b16 . Es rápido y rápido de implementar, al igual que el inverso.
Si miras la representación decimal de los resultados, la serie parece bastante oscura.
Puede mapear manualmente 0 -> maxvalue y maxvalue -> 0 para evitar que se mapeen.
El siguiente documento le brinda 4 o 5 ejemplos de mapeo, que le proporcionan funciones en lugar de crear conjuntos mapeados: www.cs.auckland.ac.nz/~john-rugis/pdf/BijectiveMapping.pdf
Si no desea utilizar los algoritmos criptográficos adecuados (quizás por motivos de rendimiento y complejidad), puede utilizar un cifrado más simple como el cifrado Vigenère . Este cifrado en realidad se describió como le chiffre indéchiffrable (francés para ''el cifrado irrompible'').
Aquí hay una implementación simple de C # que cambia los valores basados en un valor clave correspondiente:
void Main()
{
var clearText = Enumerable.Range(0, 10);
var key = new[] { 10, 20, Int32.MaxValue };
var cipherText = Encode(clearText, key);
var clearText2 = Decode(cipherText, key);
}
IEnumerable<Int32> Encode(IEnumerable<Int32> clearText, IList<Int32> key) {
return clearText.Select((i, n) => unchecked(i + key[n%key.Count]));
}
IEnumerable<Int32> Decode(IEnumerable<Int32> cipherText, IList<Int32> key) {
return cipherText.Select((i, n) => unchecked(i - key[n%key.Count]));
}
Este algoritmo no crea un gran cambio en la salida cuando la entrada cambia ligeramente. Sin embargo, puede usar otra operación de bijective en lugar de la suma para lograr eso.
Si su objetivo es simplemente obtener una permutación aparentemente aleatoria de números de un tamaño aproximado , existe otra forma posible: reducir el conjunto de números a un número primo.
Entonces puedes usar un mapeo de la forma
f (i) = (i * a + b)% p
y si p es realmente un primo, esto será una biyección para todos a! = 0 y todos b. Se verá bastante aleatorio para mayores a y b.
Por ejemplo, en mi caso, por el cual tropecé con esta pregunta, utilicé 1073741789 como primo para el rango de números menores a 1 << 30. Eso me hace perder solo 35 números, lo cual está bien en mi caso.
Mi codificación es entonces
((n + 173741789) * 507371178) % 1073741789
y la descodificación es
(n * 233233408 + 1073741789 - 173741789) % 1073741789
Tenga en cuenta que 507371178 * 233233408% 1073741789 == 1, por lo que esos dos números son inversos en el campo de números módulo 1073741789 (puede averiguar los números inversos en dichos campos con el algoritmo euclidiano extendido).
Escogí ayb de manera bastante arbitraria, simplemente me aseguré de que tuvieran aproximadamente la mitad del tamaño de p.
Tome un número, se multiplica por 9, dígitos inversos, divida por 9.
123 <> 1107 <> 7011 <> 779
256 <> 2304 <> 4032 <> 448
1028 <> 9252 <> 2529 <> 281
Debería ser lo suficientemente oscuro !!
Editar: no es una biyección para un entero final 0
900 <> 8100 <> 18 <> 2
2 <> 18 <> 81 <> 9
Siempre puede agregar una regla específica como: tomar un número, dividir entre 10 veces, multiplicar por 9, dígitos inversos, dividir por 9, multiplica por 10 ^ x.
Y entonces
900 <> 9 <> 81 <> 18 <> 2 <> 200
200 <> 2 <> 18 <> 81 <> 9 <> 900
¡W00t funciona!
Editar 2: para obtener más oscuridad, puede agregar un número arbitrario y restar al final.
900 < +256 > 1156 < *9 > 10404 < invert > 40401 < /9 > 4489 < -256 > 4233
123 < +256 > 379 < *9 > 3411 < invert > 1143 < /9 > 127 < -256 > -129
Trataré de explicar mi solución a esto en un ejemplo mucho más simple, que luego se puede ampliar fácilmente para el grande.
Digamos que tengo un número de 4 bits. Hay 16 valores distintos. Mírelo como si fuera un cubo de cuatro dimensiones: cubo de 4 dimensiones http://www.ams.org/featurecolumn/images/january2009/klee8.jpg .
Cada vértice representa uno de esos números, cada bit representa una dimensión. Entonces, básicamente es XYZW, donde cada una de las dimensiones puede tener solo valores 0 o 1. Ahora imagine que usa un orden diferente de dimensiones. Por ejemplo XZYW. ¡Cada uno de los vértices ahora cambió su número!
Puede hacer esto para cualquier cantidad de dimensiones, solo permute esas dimensiones. Si la seguridad no es su problema, esta podría ser una buena solución rápida para usted. Por otro lado, no sé si la salida será lo suficientemente "oscura" para sus necesidades y, desde luego, después de realizar una gran cantidad de mapeos, se puede revertir (lo que puede ser una ventaja o una desventaja, según sus necesidades).