Convertir una cadena semilla única en un valor flotante aleatorio, aunque determinista, en Ruby

string floating-point

Question

Estoy teniendo dificultades con esto, conceptualmente.

Básicamente, necesito aceptar alguna cadena única arbitraria y poder convertirla a un valor flotante normalizado. El valor flotante de la salida realmente no importa, siempre que la misma entrada de cadena resulte en la misma salida flotante normalizada.

Así que este es un algoritmo de hash ¿verdad? Estoy familiarizado con SHA1 o MD5, y esto parece similar al hashing de 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 un SHA1 o MD5 en un valor flotante consistente.

# 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 puedo tomar en Ruby que convertiría una cadena arbitraria en un valor flotante aleatorio pero consistente?

Answer 1

La parte clave que desea es una forma de convertir una salida de hash SHA1 o MD5 en una flotación que sea determinista y 1-1. Aquí hay una solución simple basada en md5. Esto también podría ser usado como 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, luego lo convierte en un entero, luego lo convierte en un flotador. Cada paso es determinista.

Nota: como lo señala @emboss, esto reduce la resistencia a la colisión porque un doble es de 8 bytes y el hash es de 16 bytes. No debería ser un gran problema, sin embargo, por los sonidos de su aplicación.

Answer 2

Sí, estás describiendo un algoritmo hash. Puede usar un resumen MD5 o SHA1 (ya que solo producen bits aleatorios) para generar un número de punto flotante simplemente usando el método de String#unpack con un argumento de "G" (flotación de doble precisión, orden de bytes de red) de 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 deberá realizar un masaje.

También tenga en cuenta que el número desempaquetado no utiliza todos los bits del resumen, por lo que es posible que desee combinar la cantidad de bytes para obtener un número de punto flotante doble (aunque deberá tener cuidado de no disminuir la entropía del función hash, si te importa 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 calcular el hash es fácil, pero revertirla es "difícil" o, idealmente, imposible.

Sus requisitos, en lugar de eso, describen una función inyectiva. Dado lo anterior 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 tal función, f (x) = x² no lo es. En un lenguaje sencillo: 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 se aplica a los hash seguros, pero además proporcionan características de un solo sentido, como la propiedad de no poder (fácilmente) encontrar x si solo se le da f (x), entre otras. Por lo que he entendido, no necesita estas propiedades de seguridad.

Trivialmente, tal mapeo inyectivo de String a Float se daría simplemente interpretando los "bytes de String" como "bytes de Float" a partir de ahora, es decir, interpreta los bytes de manera diferente (piense C:

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

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

Así que esto podría ser un problema real, dependiendo de sus requisitos exactos. Aunque MD5 (o cualquier otro hash) se enredará lo suficiente con la entrada para que sea lo más aleatorio posible, aún se puede reducir el rango de valores posibles de 16 bytes a efectivamente 8 bytes. (Nota: Truncar la salida aleatoria de 16 bytes a 8 bytes generalmente se considera "seguro" en términos de preservación de la aleatoriedad. La criptografía de curva elíptica hace algo similar. Pero por lo que sé, nadie puede realmente probarlo, pero nadie podría probar la contrario hasta ahora). Por lo tanto, 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 de sqrt (número de valores en un rango finito). Para MD5 esto es 2 ^ 64, pero para su esquema es solo 2 ^ 32. Eso sigue siendo muy, muy poco probable que produzca una colisión. Es probable que sea algo en el orden de ganar la lotería y al mismo tiempo ser golpeado por un rayo. Si pudieras vivir con esta mínima posibilidad, hazlo:

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

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