Hashing
De Wikipedia, la enciclopedia libre
En informática, Hashing es un método para resumir o identificar un dato a través de la probabilidad, utilizando una función hash o algoritmo hash. Un hash es el resultado de dicha función o algoritmo.
Una función hash es una función para sumarizar o identificar probabilísticamente un gran conjunto de información (dominio), dando como resultado un conjunto imagen finito generalmente menor (un subconjunto de los números naturales por ejemplo). Varían en los conjunto de partida y de llegada y en cómo afectan a la salida similaridades o patrones de la entrada. Una propiedad fundamental del hashing es que si dos hashes, utilizando la misma función, son diferentes, entonces las dos entradas que generaron dichos hashes también lo son.
Son usadas en múltiples aplicaciones, como los arrays asociativos, criptografía, procesamiento de datos y firmas digitales entre otros. Una buena función hash es una que experimenta pocas colisiones en el conjunto esperado de entrada; es decir que se podrá identificar unívocamente las entradas (ver función inyectiva).
Muchos sistemas relacionados con la seguridad informatica usan funciones o tablas de hashing.
Tabla de contenidos |
[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 datado Enero de 1953. Su utilización masiva no fue hasta después de 10 años.
En el algoritmo SHA-1, por ejemplo, el conjunto de partida de la función es dividido en palabras que son mezcladas entre sí utilizando funciones matemáticas seleccionadas especialmente. Se hace que el rango de valores que puede devolver la función sea de longitud fija: 160 bits utilizando la adición modular.
[editar] Formal
Más formalmente, la función hash está definida por su dominio (cadenas de bytes de longitud variable), su imagen (secuencias de bytes de longitud fija) y por la función que relaciona dichos conjuntos (llamada función H). La característica deseada en una función Hash es:
Primer criterio: H(x) = H(y) implica x = y.
Desafortunadamente esta idealización (denominada colisiones de hash) es precisa pero indeterminada. Si el conjunto de valores que puede tomar H(x) es mucho menor que las posibilidades de x, entonces esto no puede ser cierto siempre que todos los valores de x pueden ser igualmente probables. Entonces, existe una segunda condición para hacer la función útil. Por ejemplo:
Segundo criterio (1): dado un H(x) es complejo encontrar y tal que H(y) = H(x).
Segundo criterio (2): dados x y H(x + s) no es sencillo encontrar s.
En estos ejemplos anteriores, al referirse al grado de dificultad de una tarea se habla siempre en un sentido puramente computacional. Esto es, que el tiempo necesario para ejecutar dicha tarea sea increíblemente grande (ver NP-C). Además, + puede ser cualquier operación válida sobre el conjunto de partida.
En la práctica, para la mayoría de las aplicaciones sin contar la corrección de errores las funciones hash criptográficas son suficientemente útiles. Los algoritmos MD5 y SHA son dos de los más populares.
Nota: Éste artículo fue traducido de su versión en inglés.
[editar] Tablas Hash
Las tablas hash, una de las aplicaciones más extendidas de las funciones hash, aceleran el proceso de búsqueda de un registro de información según una clave (nota: este uso de la palabra poco se relaciona con su significado habitual). Por ejemplo, una cadena alfanumérica puede ser utilizada para buscar la información de un empleado en la base de datos de un sistema.
La utilización de tablas hash provee de un acceso casi directo a dichos registros, lo que significa que, en promedio, una búsqueda puede llegar a requerir sólo uno o dos intentos en la memoria o el archivo que contiene la información. Naturalmente, se prefiere una buena función hash que evitará colisiones de hash.
Si asumimos que la clave es una cadena de bytes, entonces la función hash debería ser como un índice de los registros que tiene una distribución aleatoria sobre las cadenas de entrada esperadas. De otra forma, habría más colisiones de hash degradando así el tiempo de búsqueda. Si, por ejemplo, la clave es alfabética, cada byte puede tener sólo 26 de sus 256 valores posibles. Funciones tan simples no distribuirán los índices de una forma pareja.
Para una comparación de velocidad y calidad de varias funciones de hash, referirse a los enlaces externos.
[editar] Corrección de errores
Para la corrección de errores, se asume una proximidad de la distribución de perturbaciones altamente probables. Las perturbaciones son clasificadas en: errores grandes (improbables) y pequeños (probables). El segundo criterio de las funciones hash se modifica como sigue:
Segundo criterio (3): dados H(x) y x + s, se puede conseguir x si s es lo suficientemente pequeño.
Las funciones que se guían según estos criterios son conocidas como "códigos de corrección de errores". Las derivaciones más importantes de este tipo de códigos de corrección son los chequeos redundancia cíclica y los códigos Reed-Solomon.
[editar] Identificación de audio
Para la identificación de audio, como verificar si un archivo MP3 coincide con alguno de una lista conocida, uno podría utilizar una función hash conocida como la MD5. Sin embargo, esto sería extremadamente sensible a perturbaciones extremadamente probables como variación de ritmo, errores de lectura, cambios en el algoritmo de compresión o diferencias en el volumen del sonido. El utilizar al MD5 es útil como un primer paso para encontrar archivos idénticos, pero se requeire un algoritmo más sofisticado para encontrar los elementos coincidentes.
Contrariamente a lo que se cree, existen algoritmos robustos para funciones hash con estas características. La mayoría de los que se encuentran disponibles no son extremadamente precisos con respecto a estos cambios, pero algunos son lo suficientemente precisos como para identificar la música que proviene de los altoparlantes en una sala ruidosa.
[editar] Algoritmo Rabin-Karp
Éste algoritmo es relativamente rápido para la búsqueda de cadena de caracteres. En promedio, el tiempo de ejecución es lineal con respecto a la longitud de la entrada. Se basa en la utilización de funciones hash para comparar cadenas.
[[:Imagen:]]==Ejemplo== Un modelo simple (e ineficiente) de función hash es
f(x) = 0 para todo entero x.
Obviamente, la colisión hash en esta función es total. Una un poco más interesante es:
f(x) = x mod 1021
Esto es devuelve el resto de la división x entre 1021. Obviamente, la colisión es menor siempre que el conjunto del cual toma valores x no sea muy grande o lo suficientemente aleatorio. Además, nótese que el hecho de que 1021 sea un número primo no es algo azaroso sino que fue cuidadosamente elegido ya que mecanismos que utilizan éste tipo de funciones con números primos como base son muy comunes en criptografía.
