Busqueda hash
Páginas: 18 (4331 palabras)
Publicado: 19 de noviembre de 2009
Hash
]
Una función de hash en funcionamiento
En informática, Hash se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un documento, registro, archivo, etc., 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 de Hash esuna función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor (un subconjunto de los números naturales por ejemplo). Varían en los conjuntos de partida y de llegada y en cómo afectan a la salida similitudes o patrones de la entrada. Una propiedad fundamental del Hashing es que si dos resultados de unamisma función son diferentes, entonces las dos entradas que generaron dichos resultados también lo son.
Es posible que existan claves resultantes iguales para objetos diferentes, ya que el rango de posibles claves es mucho menor que el de posibles objetos a resumir (las claves suelen tener en torno al centenar de bits, pero los ficheros no tienen un tamaño límite).
Son usadas en múltiplesaplicaciones, como los arrays asociativos, criptografía, procesamiento de datos y firmas digitales, entre otros. Una buena función de Hash es una que experimenta pocas colisiones en el conjunto esperado de entrada; es decir que se podrán identificar unívocamente las entradas.
Muchos sistemas relacionados con la seguridad informática usan funciones o tablas hash.
Orígenes del término
Elté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 en enero de1953. 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 lafunció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.
Formal
Más formalmente, la función de Hash está definida por su dominio (cadenas de bytes de longitud variable), su imagen (secuencias de bytes delongitud 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:
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 losvalores 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 sentidopuramente 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-1 son dos de los más populares.Funciones Resumen
Estos métodos son muy variados, pueden llegar a tomar en cuenta diversos parámetros tales como el nombre de un archivo, su longitud, hora de creación, datos que contenga, etc. aplicándole diversas transformaciones y operaciones matemáticas. Algunas aplicaciones de las funciones resumen son las siguientes:
▪ Identificar algún archivo de computadora independientemente...
]
Una función de hash en funcionamiento
En informática, Hash se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un documento, registro, archivo, etc., 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 de Hash esuna función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor (un subconjunto de los números naturales por ejemplo). Varían en los conjuntos de partida y de llegada y en cómo afectan a la salida similitudes o patrones de la entrada. Una propiedad fundamental del Hashing es que si dos resultados de unamisma función son diferentes, entonces las dos entradas que generaron dichos resultados también lo son.
Es posible que existan claves resultantes iguales para objetos diferentes, ya que el rango de posibles claves es mucho menor que el de posibles objetos a resumir (las claves suelen tener en torno al centenar de bits, pero los ficheros no tienen un tamaño límite).
Son usadas en múltiplesaplicaciones, como los arrays asociativos, criptografía, procesamiento de datos y firmas digitales, entre otros. Una buena función de Hash es una que experimenta pocas colisiones en el conjunto esperado de entrada; es decir que se podrán identificar unívocamente las entradas.
Muchos sistemas relacionados con la seguridad informática usan funciones o tablas hash.
Orígenes del término
Elté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 en enero de1953. 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 lafunció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.
Formal
Más formalmente, la función de Hash está definida por su dominio (cadenas de bytes de longitud variable), su imagen (secuencias de bytes delongitud 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:
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 losvalores 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 sentidopuramente 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-1 son dos de los más populares.Funciones Resumen
Estos métodos son muy variados, pueden llegar a tomar en cuenta diversos parámetros tales como el nombre de un archivo, su longitud, hora de creación, datos que contenga, etc. aplicándole diversas transformaciones y operaciones matemáticas. Algunas aplicaciones de las funciones resumen son las siguientes:
▪ Identificar algún archivo de computadora independientemente...
Leer documento completo
Regístrate para leer el documento completo.