password - hashids python

Función hash reversible?

Question

Necesito una función hash reversible (obviamente, la entrada será mucho más pequeña en tamaño que la salida) que mapea la entrada a la salida de forma aleatoria. Básicamente, quiero una forma de transformar un número como "123" a un número más grande como "9874362483910978", pero no de una manera que preserve las comparaciones, por lo que no siempre debe ser cierto que, si x1> x2, f (x1) )> f (x2) (pero tampoco debe ser siempre falso).

El caso de uso para esto es que necesito encontrar una manera de transformar números pequeños en grandes, de aspecto aleatorio. En realidad, no es necesario que sean aleatorios (de hecho, deben ser deterministas, por lo que la misma entrada siempre se asigna al mismo resultado), pero deben verse al azar (al menos cuando se codifican en base64 en cadenas, por lo que se desplazan por Z los bits no funcionarán, ya que los números similares tendrán MSB similares).

Además, el cálculo y la reversión fácil (rápido) es un plus, pero no obligatorio.

No sé si estoy siendo claro, o si existe tal algoritmo, ¡pero agradecería toda ayuda!

Answer 1

¿Por qué no solo XOR con un buen número largo?

Fácil. Rápido. Reversible.

O bien, si no es necesario que sea terriblemente seguro, puede convertir de la base 10 a una base más pequeña (como la base 8 o la base 4, según el tiempo que desee que sean los números).

Answer 2

Básicamente, está buscando encriptación de 2 vías, y una que probablemente usa una salt .

Usted tiene una serie de opciones:

1. TripleDES
2. AES

Aquí hay un ejemplo: " Ofuscación bidireccional insegura simple" para C #

¿Qué idioma estás mirando? Si .NET luego mira el espacio de nombres de cifrado para algunas ideas.

Answer 3

Lo que está pidiendo es cifrado. Un cifrado de bloque en su modo de funcionamiento básico, ECB, asigna de forma reversible un bloque de entrada a un bloque de salida del mismo tamaño. Los bloques de entrada y salida se pueden interpretar como números.

Por ejemplo, AES es un cifrado de bloque de 128 bits, por lo que asigna un número de entrada de 128 bits a un número de 128 bits de salida. Si 128 bits es lo suficientemente bueno para sus propósitos, entonces simplemente puede rellenar su número de entrada a 128 bits, transformar ese bloque individual con AES, luego formatear la salida como un número de 128 bits.

Si 128 bits es demasiado grande, puede usar un cifrado de bloque de 64 bits, como 3DES, IDEA o Blowfish.

El modo ECB se considera débil, pero su debilidad es la restricción que ha postulado como requisito (es decir, que el mapeo sea "determinista"). Esto es una debilidad, porque una vez que un atacante ha observado que 123 mapas a 9874362483910978, a partir de ese momento cada vez que ve el último número, sabe que el texto en claro era 123. Un atacante puede realizar análisis de frecuencia y / o construir un diccionario de texto llano conocido / pares de texto cifrado.

Answer 4

Ninguna de las respuestas proporcionadas parecía particularmente útil, dada la pregunta. Tuve el mismo problema, necesitaba un hash reversible simple para fines no relacionados con la seguridad, y decidí ir con la reubicación de bits. Es simple, es rápido y no requiere saber nada sobre las matemáticas booleanas o los algoritmos crypo o cualquier otra cosa que requiera un pensamiento real.

Lo más simple sería simplemente mover la mitad de los bits restantes, y la otra mitad a la derecha:

def hash(n):
  return ((0x0000FFFF & n)<<16) + ((0xFFFF0000 & n)>>16)

Esto es reversible, en ese hash (hash (n)) = n, y tiene pares no secuenciales {n, m}, n <m, donde hash (m) <hash (n).

Para obtener una implementación de aspecto menos secuencial, también puede considerar una reordenación entrelazada de [msb, z, ..., a, lsb] a [msb, lsb, z, a, ...] o [lsb, msb , a, z, ...] o cualquier otra reubicación que crea da una secuencia apropiadamente no secuencial para los números que maneja.

(La función anterior es segura para números que caben en 32 bits, se garantiza que los números más grandes causarán colisiones y necesitarían más cobertura de máscaras de bits para evitar problemas. Dicho esto, 32 bits suele ser suficiente para cualquier uid que no sea de seguridad).

Answer 5

Otra solución simple es usar inversas multiplicativas (ver el blog de Eri Clippert) :

Mostramos cómo puede tomar dos números enteros positivos coprimos xym y calcular un tercer entero positivo y con la propiedad que (x * y)% m == 1, y por lo tanto ese (x * z * y)% m == z% m para cualquier entero positivo z. Es decir, siempre existe una "inversa multiplicativa", que "deshace" los resultados de multiplicar por x módulo m.

Tomamos un gran número, por ejemplo, 4000000000 y un gran número coprime, por ejemplo, 387420489:

def rhash(n):
    return n * 387420489 % 4000000000

>>> rhash(12)
649045868

Primero calculamos el inverso multiplicativo con modinv que resulta ser 3513180409:

>>> 3513180409 * 387420489 % 4000000000
1

Ahora, podemos definir lo inverso:

def un_rhash(h):
    return h * 3513180409 % 4000000000

>>> un_rhash(649045868)  # un_rhash(rhash(12))
12

Nota: Esta respuesta es rápida de calcular y funciona para números de hasta 4000000000, si necesita manejar números más grandes, elija un número suficientemente grande (y otro coprimario).

Es posible que desee hacer esto con hexadecimal (para empaquetar el int):

def rhash(n):
    return "%08x" % (n * 387420489 % 4000000000)

>>> rhash(12)
''26afa76c''

def un_rhash(h):
    return int(h, 16) * 3513180409 % 4000000000

>>> un_rhash(''26afa76c'')  # un_rhash(rhash(12))
12

Si eliges un coprimero relativamente grande, parecerá aleatorio, no secuencial y rápido de calcular.