Hashing

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

Función hash[editar]

A las Función hash, también se les llama funciones picadillofunciones resumen o funciones de digest

Una función hash es un método para generar claves o llaves que representen de manera casi unívoca a un documento o conjunto de datos. Es una operación matemática que se realiza sobre este conjunto de datos de cualquier longitud, y su salida es una huella digital, de tamaño fijo e independiente de la dimensión del documento original. El contenido es ilegible.

Al igual que todos los datos informáticos, los hashes no son números grandes ya que se escriben en sistema hexadecimal (números entre 0 y 9 y letras entre A y F).


Una función hash H es una función computable mediante un algoritmo, actúa como una proyección del conjunto U sobre el conjunto M.

Observa 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 de números enteros ya que podemos considerar que la longitud fija es la del número con mayor cantidad de cifras. Todos los números se pueden convertir al número especificado de cifras simplemente anteponiendo ceros.

Normalmente el conjunto U tiene un número elevado de elementos y M es un conjunto de cadenas con un número relativamente 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.

Requisitos

La función deben cumplir los siguientes requisitos:


– Imposibilidad de obtener el texto original a partir de la huella digital.

– Imposibilidad de encontrar un conjunto de datos diferentes que tengan la misma huella digital.

– Poder transformar un texto de longitud variable en una huella de tamaño fijo.

– Facilidad de empleo e implementación.


Funciones Deterministas[editar]

Una función se puede llamar determinista si se crea el mismo resumen con la misma entrada aunque el resumen parezca aleatorio.


Ejemplos de algoritmos hash[editar]

MD5[editar]

Es una función hash de 128 bits. Como todas las funciones hash, toman determinados tamaños a la entrada, y salen con una longitud fija (128bits), número de pasos 64.

El algoritmo MD5 no sirve para cifrar un mensaje. La información original no se puede recuperar ya que hay pérdida de datos.


SHA-1[editar]

Tiene un bloque de 160bits. La función de compresión es más compleja que la función de MD5. SHA-1 es más lento porque consta de 80 pasos y tiene mayor longitud. Lo que lo convierte más robusto y seguro.


Residuo de la división[editar]

La idea principal de este método es la de dividir el valor de la llave (entrada) entre un número apropiado, y después utilizar el residuo de la división como dirección relativa para el registro.


Medio del cuadrado[editar]

En esta técnica, la llave (entrada) es elevada al cuadrado, después algunos dígitos específicos se extraen de la mitad del resultado para constituir la dirección relativa. Si se desea una dirección de n dígitos, entonces los dígitos se truncan en ambos extremos de la llave elevada al cuadrado, tomando n dígitos intermedios. Las mismas posiciones de n dígitos deben extraerse para cada llave.


Pliegue[editar]

En esta técnica, la llave es elevada al cuadrado, después algunos dígitos específicos se extraen de la mitad del resultado para constituir la dirección relativa. Si se desea una dirección de n dígitos, entonces los dígitos se truncan en ambos extremos de la llave elevada al cuadrado, tomando n dígitos intermedios. Las mismas posiciones de n dígitos deben extraerse para cada llave.


Colisión[editar]

Una colisión ocurre cuando dos valores de entrada diferente generan el mismo resumen. Una función hash debe ser resistente a la colisión.

El mismo hash siempre será el resultado de los mismos datos (funciones deterministas), pero la modificación de la información, aunque sea un solo bit dará como resultado un hash totalmente distinto.

La idea básica de un valor hash es que sirva como una representación compacta de la cadena de entrada.

Cuando dos claves se apuntan a la misma dirección o bucket se dice que hay una colisión y a las claves se les denomina sinónimos.

Formas de disminuir el número de colisiones y garantizar el funcionamiento de la función

  • Esparcir los registros
  • Usar memoria adicional.
  • Colocar más de un registro en una dirección (Compartimientos)


Definición hashing[editar]

Consiste en una transformación matemática de una clave k con una función h (k) que da como resultado la posición de k en una tabla llamada también transformación key-to-address o kat.

Hashing Perfecto Es una función de hash que logra evitar al 100% las colisiones.

Desventaja El conjunto de posibles claves es siempre mayor al número de espacios disponibles. Es decir, dos o más claves pueden asignarse a la misma dirección en la tabla de hash.

Tablas hash[editar]

Las tablas hash, una de las aplicaciones más extendidas de las funciones de hash, aceleran el proceso de búsqueda de un registro de información según una clave. 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 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.


Hashing vs Cifrado[editar]

Hashing y cifrado son dos técnicas que sirven para proteger la información. El cifrado permite descifrar posteriormente el texto original y recuperarlo. El hashing resume el texto en una pequeña huella que no puede descifrarse.


Aplicaciones[editar]

  • Criptografía
  • Almacenamiento de contraseñas
  • Firmas digitales
  • Procesamiento de datos



Referencias[editar]