Convirtiendo una cadena de inicialización única en un valor de flotación aleatorio, aunque determinista, en Ruby

Question

Estoy teniendo un momento difícil con esto, conceptualmente.

Básicamente, tengo que aceptar alguna cadena única arbitraria, y ser capaz de convertir eso en un valor flotante normalizado. Cuál es el valor flotante de salida realmente no importa, siempre que la misma entrada de cadena siempre resulte en la misma salida de flotación normalizada.

Así que este es un algoritmo hash ¿verdad? Estoy familiarizado con SHA1 o MD5, y esto parece similar al hash de la contraseña donde el resultado es el mismo para la contraseña correcta. Pero esos métodos producen cadenas de caracteres, creo. Y lo que no entiendo es cómo convertiría el resultado de SHA1 o MD5 en un valor flotante constante.

# Goal 
def string_to_float(seed_string) 
    # ... 
end 

string_to_float('abc-123') #=> 0.15789 
string_to_float('abc-123') #=> 0.15789 

string_to_float('def-456') #=> 0.57654 
string_to_float('def-456') #=> 0.57654 

Entonces, ¿qué tipo de enfoque en Ruby puedo tomar eso sería convertir una cadena arbitraria en un valor flotante al azar, pero consistente?

Answer 1

la parte clave que desea es una manera de convertir una SHA1 o salida hash MD5 en un flotador que es a la vez determinista y 1-1. Aquí hay una solución simple basada en md5. Esto también podría usarse como números enteros.

require 'digest/md5' 

class String 
    def float_hash 
    (Digest::MD5.hexdigest(self).to_i(16)).to_f 
    end 
end 

puts "example_string".float_hash # returns 1.3084281619666243e+38 

Esto genera un hash hexadecimal, entonces la convierte a un entero, entonces convertidos que a un flotador. Cada paso es determinista.

Nota: como señala @emboss, esto reduce la resistencia a la colisión porque un doble tiene 8 bytes y el hash es de 16 bytes. Sin embargo, no debería ser un gran problema según los sonidos de tu aplicación.

Answer 2

Sí, usted está describiendo un algoritmo de hash. Puede usar un resumen MD5 o SHA1 (ya que solo producen bits aleatorios) para generar un número de coma flotante simplemente usando el String#unpack method con un argumento de "G" (float de doble precisión, orden de bytes de red) desde un resumen:

require 'digest/sha1' 

def string_to_float(str) 
    Digest::SHA1.digest(str).unpack("G")[0] 
end 

string_to_float("abc-123") # => -2.86011943713676e-154 
string_to_float("def-456") # => -1.13232994606094e+214 
string_to_float("abc-123") # => -2.86011943713676e-154 OK! 
string_to_float("def-456") # => -1.13232994606094e+214 OK! 

Tenga en cuenta que si desea que los flotadores resultantes estén en un rango particular, entonces tendrá que hacer algunos masajes.

También tenga en cuenta que el número no empaquetado no utiliza todos los bits del resumen, por lo que puede combinar el número de bytes para un número doble de punto flotante (aunque deberá tener cuidado de no reducirlo). la entropía de la función hash, si se preocupan por ese tipo de cosas), por ejemplo:

def str2float(s) 
    d = Digest::SHA1.digest(s) 
    x, y = d[0..9], d[10..19] 
    # XOR the 1st (x) and 2nd (y) halves to use all bits. 
    (0..9).map {|i| x[i]^y[i]}.pack("c*").unpack("G")[0] 
end 

Answer 3

Si la seguridad no es un problema, lo que está describiendo es en mi opinión no una función hash. Una función hash es una función unidireccional, lo que significa que el cálculo del hash es fácil, pero revertirlo es "difícil" o, idealmente, imposible.

Sus necesidades en lugar describen un injective function dado ninguna x1, x2 en su dominio X se cumple lo siguiente:

For all x1, x2 element of X, x1 != x2 => f(x1) != f(x2) 

f (x) = x es una función, f (x) = x² no lo es. En inglés simple: desea tener resultados diferentes si sus entradas son diferentes, los mismos resultados solo si las entradas son las mismas. Es cierto que esto también es cierto para los valores hash seguros, pero también proporcionan las características unidireccionales, como la propiedad de no poder encontrar (fácilmente) x si solo se le da f (x), entre otros. Por lo que yo entiendo, no necesita estas propiedades de seguridad.

Trivialmente, una asignación de tales inyectiva de cadena sería dada simplemente la interpretación de los "bytes de Cuerda" flotar como "Float bytes" de ahora en adelante, es decir, a interpretar los bytes de manera diferente (piense C:

unsigned char *bytes = "..."; 
double d = (double)bytes; 

). Pero el inconveniente es que Float tiene una precisión máxima, por lo que se encontrará con una situación de desbordamiento si las cadenas son demasiado largas (los flotantes se representan internamente como valores double, eso es 8 bytes en un bit de 32 bits máquina). Así que no hay espacio suficiente para casi cualquier caso de uso. Incluso MD5-ing tus cadenas primero no resuelve el problema: la salida MD5 ya tiene 16 bytes de longitud.

Esto podría ser un problema real, dependiendo de sus requisitos exactos. Aunque MD5 (o cualquier otro hash) se meterá lo suficiente con la entrada para hacerlo tan aleatorio como sea posible, aún se corta el rango de valores posibles de 16 bytes a 8 bytes efectivamente. (Nota: truncar la salida aleatoria de 16 bytes a 8 bytes generalmente se considera "segura" en términos de preservar la aleatoriedad. La Criptografía de Curva Elíptica hace algo similar. Pero hasta donde yo sé, nadie realmente puede probarlo, pero ninguno podría probar el al contrario hasta ahora). Entonces, una colisión es mucho más probable con su rango de Flotación restringido. Por la paradoja del cumpleaños, encontrar una colisión requiere intentos sqrt (cantidad de valores en un rango finito). Para MD5 esto es 2^64, pero para su esquema es solo 2^32. Todavía es muy, muy poco probable que produzca una colisión. Probablemente sea algo del orden de ganar la lotería mientras que al mismo tiempo es golpeado por un rayo. Si se puede vivir con esta mínima posibilidad, ir a por ello:

def string_to_float(str) 
    Digest::MD5.new.digest(str).unpack('D') 
end 

Si singularidad es de prioridad absoluta, recomendaría pasar de flotadores a enteros. Ruby tiene soporte incorporado para enteros grandes que no están restringidos por las restricciones internas de un valor long (eso es lo que reduce a Fixnum). Por lo tanto, cualquier salida de hash arbitraria podría representarse como un número entero grande.