Funciones 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óncomputable 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 lalongitud es fija si el conjunto es un rango de nú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 resumen datos 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.
Contenido  [ocultar]  * 1 Orígenes del término * 2 Terminología asociada * 3 Parámetros adicionales * 3.1 Funciones hash con clave* 4 Propiedades * 4.1 Bajo coste * 4.2 Compresión * 4.3 Uniforme * 4.4 De rango variable * 4.5 Inyectividad. Función hash perfecta * 4.6 Determinista * 4.7 Propiedades para analizar la resistencia frente a colisiones * 4.7.1 Resistencia a la primera imagen * 4.7.2 Resistencia a la segunda preimagen * 4.7.3 Resistencia a colisiones (CRHF)* 4.7.4 Función hash de un solo sentido (OWHF) * 4.7.5 Resistencia a la casi colisión * 4.7.6 Resistencia a las preimágenes parciales * 4.8 Con normalización de datos * 4.9 Continuidad. Efecto avalancha * 4.10 Resistencia a la computación de nuevos valores hash * 5 Familias de funciones hash y propiedades asociadas * 5.1 Motivación[17] *5.2 Concepto * 5.3 Familia de funciones hash resistente a colisiones * 5.3.1 Definición formal * 5.4 Función hash universal * 5.4.1 Definición formal[23] * 5.5 Familia de funciones hash universal de un solo sentido * 5.5.1 Definición formal * 5.6 Comparación UOWHF y CRHF[27] * 6 Funciones hash iterativas. Construcción de Merkle-Damgård * 7 Aplicaciones *8 Véase también * 9 Referencias * 10 Enlaces externos |
-------------------------------------------------
[editar]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 cree que H. P. Luhn, empleado de IBM, fue el primero en utilizar el concepto en un memorándum fechadoen enero de 1953. Su utilización masiva no fue hasta después de 10 años.
-------------------------------------------------
[editar]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 un elemento de M se le llama valor hash, códigohash 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 sus cadenas es fijo. Por tanto la...