Simétrica Bijective Algoritmo para Enteros

https://stackoverflow.com/questions/3131193

01-10-2019
|

Pregunta

Necesito un algoritmo que puede hacer un mapeo de uno a uno (es decir. Ninguna colisión) de un entero con signo de 32 bits en otro entero con signo de 32 bits.

Mi verdadera preocupación es suficiente entropía para que la salida de la función parece ser al azar. Básicamente Busco a una cifra similar a la XOR de cifrado, pero que puede generar salidas de aspecto más arbitrarias. La seguridad no es mi verdadera preocupación, aunque la oscuridad es.

Editar para el propósito aclaración:

El algoritmo debe a ser simétrica, de modo que pueda invertir la operación sin un par de claves.
El algoritmo debe ser biyectiva, cada número de entrada de 32 bits debe generar una 32 bits número único.
La salida de la función debe ser lo suficientemente oscura, añadiendo solamente uno a la entrada debe dar lugar a gran efecto en la salida.

Ejemplo espera resultado:

F (100) = 98 456
F (101) = -758
F (102) = 10.875.498
F (103) = 986 541
F (104) = 945 451 245
F (105) = -488 554

Al igual que MD5, el cambio de una cosa puede cambiar un montón de cosas.

Busco a una función mathmetical, por lo que los números enteros que trazan manualmente no es una solución para mí. Para aquellos que están pidiendo, la velocidad del algoritmo no es muy importante.

Solución

El uso de cualquier bloque de cifrado de 32 bits! Por definición, un cifrado de bloques mapea cada valor de entrada es posible en su gama a un valor de salida única, de forma reversible, y por diseño, es difícil determinar lo que cualquier valor dado se correlaciona con un sin la llave. Sólo tiene que elegir una clave, mantenerlo en secreto si la seguridad o la oscuridad es importante, y utilizar el sistema de cifrado como su transformación.

Para una extensión de esta idea de no poder-de-2 rangos, ver mi post sobre permutaciones seguras con Bloquear cifrados .

Dirigiéndose a sus preocupaciones específicas:

El algoritmo es, en efecto simétrico. No estoy seguro de lo que entendemos por "invertir la operación sin un par de claves". Si no desea utilizar una clave, codificar una generada aleatoriamente y consideramos que es parte del algoritmo.
Sí -., Por definición, un cifrado de bloques es biyectiva
Sí. No sería una buena cifra si ese no fuera el caso.

Otros consejos

Voy a tratar de explicar mi solución a esto en un ejemplo mucho más simple, que luego se puede extender fácilmente para su grande.

decir que tengo un número de 4 bits. Hay 16 valores distintos. Mirada en ella como si fuera un cubo de cuatro dimensiones:
_{(fuente: ams.org )}
.

Cada vértice representa uno de esos números, cada bit representa una dimensión. Por lo que su XYZW basicaly, donde cada una de las dimensiones puede tener sólo los valores 0 o 1. Ahora imagina que utiliza un orden diferente de dimensiones. Por ejemplo XZYW. Cada uno de los vértices ahora cambió su número!

Se puede hacer esto para cualquier número de dimensiones, simplemente permutar esas dimensiones. Si la seguridad no es su preocupación esto podría ser una solución rápida agradable para usted. Por otro lado, no sé si la salida será "oscuro" suficiente para sus necesidades y, ciertamente, después de una gran cantidad de mapeo hecho, el mapeo puede ser invertida (que puede ser una ventaja o desventaja, dependiendo de sus necesidades.)

El siguiente documento le da 4 o 5 ejemplos de mapeo, que le da funciones en lugar de construir conjuntos mapeadas: www.cs.auckland.ac.nz/~john-rugis/pdf/BijectiveMapping.pdf

Además de la generación al azar de búsqueda mesas, se puede utilizar una combinación de funciones:

XOR
permutación de bits simétrica (por ejemplo de desplazamiento de 16 bits, o flip 0-31 a 31-0, o voltear 0-3 a 3-0, 4-7 a 7-4, ...)
más?

Si su objetivo es simplemente para obtener una permutación aparentemente aleatoria de números de un más o menos tamaño definido, entonces hay otra manera posible:. Reducir el conjunto de números a un número primo

A continuación, se puede utilizar un mapeo de la forma

f (i) = (i * a + b)% p

y si p es de hecho un primo, esta será una biyección para todo a! = 0 y todos b. Se verá bastante aleatorio para ampliar a y b.

Por ejemplo, en mi caso para el que me encontré con esta pregunta, he usado 1073741789 como principal para el rango de números menores que 1 << 30. Eso me hace perder sólo 35 números, lo cual está bien en mi caso.

Mi codificación es entonces

((n + 173741789) * 507371178) % 1073741789

y la decodificación es

(n * 233233408 + 1073741789 - 173741789) % 1073741789

Tenga en cuenta que * 507371178 233233408 1073741789% == 1, por lo que esos dos números son inversas al campo de los números de módulo 1073741789 (se puede averiguar inversa números en estos campos con el algoritmo de Euclides extendido).

Me eligió a y b bastante arbitraria, simplemente me aseguré de que son aproximadamente la mitad del tamaño de p.

Se puede utilizar una tabla de consulta generada al azar? Mientras los números aleatorios en la tabla son únicos, se obtiene una biyectiva. No es simétrica, sin embargo.

Uno de 16 GB tabla de consulta para todos los valores de 32 bits es probablemente no es práctico, pero se pueden utilizar dos tablas separadas de búsqueda de 16 bits para la alta palabra y la palabra baja.

PS: Creo que se puede generar una tabla de búsqueda biyectiva simétrica, si eso es importante. El algoritmo comenzaría con una LUT vacío:

+----+        +----+
|  1 |   ->   |    |
+----+        +----+
|  2 |   ->   |    |
+----+        +----+
|  3 |   ->   |    |
+----+        +----+
|  4 |   ->   |    |
+----+        +----+

Pick el primer elemento, asignar una asignación al azar. Para hacer el mapeo simétrica, asignar la inversa, también:

+----+        +----+
|  1 |   ->   |  3 |
+----+        +----+
|  2 |   ->   |    |
+----+        +----+
|  3 |   ->   |  1 |
+----+        +----+
|  4 |   ->   |    |
+----+        +----+

Escoja el número siguiente, de nuevo asignar una asignación al azar, pero escoger un número que no se ha asignado todavía. (Es decir, en este caso, no recoger 1 o 3). Repita hasta que la LUT es completa. Esto debería generar un mapeo simétrica biyectiva aleatorio.

Tome un número, se multiplica por 9, dígitos inversos, se divide por 9.

123  <> 1107 <> 7011 <> 779
256  <> 2304 <> 4032 <> 448
1028 <> 9252 <> 2529 <> 281

Debe ser lo suficientemente oscura !!

Editar: no es una biyección de 0 terminando entero

900 <> 8100 <> 18 <> 2
2   <> 18   <> 81 <> 9

Siempre se puede añadir una regla específica como: Tome un número, se divide por 10 x veces, se multiplica por 9, dígitos inversos, se divide por 9, múltiplos de 10 ^ x.

Y así

900 <> 9 <> 81 <> 18 <> 2 <> 200
200 <> 2 <> 18 <> 81 <> 9 <> 900

W00t funciona!

Editar. 2: Para obtener más obscurness, se puede añadir 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

Aquí está mi idea simple: Puede desplazarse por los bits del número, como PeterK propuesto, pero se puede tener una permutación diferente de bits para cada número, y aún así ser capaz de descifrarlo.

El cifrado es el siguiente: Tratar el número de entrada como una matriz de bits I[0..31], y la salida como O[0..31]. Preparar un K[0..63] gama de 64 números generados aleatoriamente. Esta será su clave. Tome el bit de número de entrada de la posición determinada por el primer número aleatorio (I[K[0] mod 32]) y colocarlo en el comienzo de su resultado (O[0]). Ahora decidir qué mordió a cabo en O[1], utilizar el bit utilizado anteriormente. Si es 0, el uso K [1] para generar posición en I desde la que tomar, es 1, utilice K [2] (que significa simplemente omitir un número aleatorio).

Ahora bien, esto no va a funcionar bien, ya que puede tomar el mismo bit dos veces. Con el fin de evitarlo, renumerar los bits después de cada iteración, omitiendo los bits usados. Para generar la posición desde la cual tomar O[1] uso I[K[p] mod 31], donde p es 1 o 2, dependiendo de la O[0] poco, ya que hay 31 bits a la izquierda, 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, por lo que vamos a tomar bit cuya posición es 1 (contando desde 0)

I: 0_11    O: 1___
     _

Nos acaba de tomar un poco de valor 1, por lo que nos saltamos un número aleatorio y usamos 28. Hay 3 bits a la izquierda, de modo de contar la posición que tomamos 28 mod 3 = 1. Tomamos la primera (contando desde 0 ) de los bits restantes:

I: 0__1    O: 11__
   _

Una vez más nos saltamos un número, y tomamos 14. 14 mod 2 = 0, por lo que tomamos el bit 0 ª:

I: ___1    O: 110_
      _

Ahora no importa, pero el bit anterior fue de 0, por lo que tomamos 20. 20 mod 1 = 0:

I: ____    O: 1101

Y eso es todo.

Descifrando número a tal es fácil, sólo hay 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 se determinan por los bits insertados previamente.

Esto, obviamente, tiene todas las desventajas de nada, que sólo se mueve los bits de alrededor (por ejemplo, 0 es 0 y MAXINT convierte MAXINT), pero se parece más difícil de encontrar cómo alguien ha cifrado el número sin conocer la clave, que debe secretas.

Si no desea utilizar algoritmos criptográficos adecuados (tal vez por razones de rendimiento y complejidad) en su lugar puede utilizar un cifrado más simple como la Vigenère . Esta cifra era en realidad describe como Le Chiffre indéchiffrable (francés para 'el sistema de cifrado irrompible').

Esta es una sencilla aplicación C # que los valores turnos basan en un valor de 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 se cambia ligeramente. Sin embargo, puede utilizar otra operación biyectiva en lugar de la suma para lograrlo.

Dibuje un círculo grande en una hoja grande de papel. Escribir todos los números enteros de 0 a MAXINT las agujas del reloj desde la parte superior del círculo, igualmente espaciados. Escribe todos los números enteros de 0 a MININT en sentido antihorario, igualmente espaciados de nuevo. Observe que el MININT está al lado de MAXINT en la parte inferior del círculo. Ahora hacer un duplicado de esta figura en ambos lados de un trozo de cartón rígido. Pin de la tarjeta de rigidez a la circunferencia que pasa por los centros de ambos. Escoja un ángulo de giro, el ángulo que desee. Ahora usted tiene una asignación de 1-1 que se reúne algunos de sus requisitos, pero probablemente no es lo suficientemente oscura. Desanclar la tarjeta, darle la vuelta alrededor de un diámetro, cualquier diámetro. Repita estos pasos (en cualquier orden) hasta que tenga una biyección que esté satisfecho con.

Si usted ha estado siguiendo de cerca, no debería ser difícil de programar esta en su idioma preferido.

Para Aclaración siguiente comentario: Si sólo girar la tarjeta contra el papel, entonces el método es tan simple como usted se queja. Sin embargo, cuando se le da la vuelta a la tarjeta de la asignación no es equivalente a (x+m) mod MAXINT para cualquier m. Por ejemplo, si se deja la tarjeta sin rotar y darle la vuelta el diámetro a través de 0 (que es en la parte superior de la esfera del reloj), entonces se asigna 1 a -1, de 2 a -2, y así sucesivamente. (x+m) mod MAXINT corresponde a rotaciones de la tarjeta solamente.

Dividir el número en dos (16 bits más significativos y los 16 bits menos significativos) y considerar los bits en los dos resultados de 16 bits como tarjetas en dos cubiertas. Mezclar las cubiertas obligando a uno en el otro.

Así que si su número inicial es b31,b30,...,b1,b0 se termina con b15,b31,b14,b30,...,b1,b17,b0,b16. Es rápido y rápido de implementar, ya que es la inversa.

Si nos fijamos en la representación decimal de los resultados, las miradas de la serie bastante oscuro.

Se puede asignar manualmente 0 -> maxvalue y maxvalue -.> 0 para evitarlos mapeo sobre sí mismos

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow