Función Hash

Función Hash


Una función de hash en funcionamiento.
A las funciones hash (adopción más o menos directa del término inglés hash function) también se les llama funciones picadillo, funciones resumen o funciones de digest (adopción más o menos directa del término inglés equivalente digest function)[1] [2] [3] Una función hash H es una función computable mediante un algoritmo,
 H: U → M
 x →h(x),
que tiene como entrada un conjunto de elementos, que suelen ser cadenas, y los convierte (mapea) en un rango de salida finito, normalmente cadenas de longitud fija. Es decir, la función actúa como una proyección del conjunto U sobre el conjunto M.
Observar que M puede ser un conjunto definido de enteros. En este caso podemos considerar que la longitud es fija si el conjunto es un rango denúmeros de enteros ya que podemos considerar que la longitud fija es la del número con mayor número de cifras. Todos los números se pueden convertir al número especificado de cifras simplemente anteponiendo ceros.
Normalmente el conjunto M tiene un número elevado de elementos y U es un conjunto de cadenas con un número más o menos pequeño de símbolos. Por esto se dice que estas funciones resumendatos del conjunto dominio.
La idea básica de un valor hash es que sirva como una representación compacta de la cadena de entrada. Por esta razón decimos que estas funciones resumen datos del conjunto dominio.
Orígenes del término
El término hash proviene, aparentemente, de la analogía con el significado estándar (en inglés) de dicha palabra en el mundo real: picar y mezclar. Donald Knuth creeque H. P. Luhn, empleado de IBM, fue el primero en utilizar el concepto en un memorándum fechado en enero de 1953. Su utilización masiva no fue hasta después de 10 años.
Terminología asociada
Al conjunto U se le llama dominio de la función hash. A un elemento de U se le llama preimagen o dependiendo del contexto clave o mensaje.
Al conjunto M se le llama imagen de la función hash. A unelemento de M se le llama valor hash, código hash o simplemente hash.
Se dice que se produce una colisión cuando dos entradas distintas de la función de hash producen la misma salida. De la definición de función hash podemos decir que U, el dominio de la función, puede tener infinitos elementos. Sin embargo M, el rango de la función, tiene un número finito de elementos debido a que el tamaño de suscadenas es fijo. Por tanto la posibilidad de existencia de colisiones es intrínseca a la definición de función hash. Una buena función de hash es una que tiene pocas colisiones en el conjunto esperado de entrada. Es decir, se desea que la probabilidad de colisión sea muy baja.
Parámetros adicionales
La definición formal dada, a veces se generaliza para poder aprovechar las funciones hash en otrosámbitos. Para ello a la función hash se le añaden nuevos parámetros de forma que el valor hash no es sólo función del contenido en sí, sino además de otros nuevos factores.
Para hallar valores hash de ficheros a veces se usan como parámetros, además del contenido en sí, diversos parámetros como el nombre del archivo, su longitud, hora de creación, etc.
Otras veces se añaden parámetros que permitenconfigurar el comportamiento de la función. Por ejemplo, la función hash puede recibir como parámetro una función de generación de valores pseudoaleatorios que es usada dentro del algoritmo de la función hash.
Otros ejemplos de parámetros son el uso de valores sal, el uso de claves secretas, el uso de parámetros que especifican el rango de la función (funciones hash de rango variable), el uso deparámetros que especifican el nivel de seguridad que se quiere en el valor hash de salida (funciones hash dinámicas),....
Funciones hash con clave
Una función hash con clave HK (en inglés keyed hash function) es una función hash H que tiene un parámetro secreto K que pertenece al conjunto posible de claves y en la que para una entrada x, hK(x) es el valor hash de x. Al resto de funciones hash...