¿Qué es el Hashing?
¿Qué es el Hashing?
El hashing es la transformación de una cadena de caracteres en un valor o clave de longitud fija, normalmente más corta, que representa la cadena original. El hashing se utiliza en particular para indexar y recuperar elementos en una base de datos. Esto se debe a que es más rápido encontrar el elemento basándose en la clave hash reducida en lugar de utilizar el valor original. Esta función también se utiliza en muchos algoritmos de cifrado.
Para ilustrar el uso del hashing, imaginemos un grupo de contactos organizados en una base de datos de la siguiente manera:
Amblard, Sarah Epadingue, Roger Mourié, Vincent Santi, David (y muchos otros ordenados alfabéticamente)
Cada uno de estos nombres es la clave que representa los datos del contacto en la base de datos. Un mecanismo de búsqueda tendría que buscar primero los caracteres del nombre uno por uno, hasta encontrar la coincidencia (o eliminar las otras entradas). Sin embargo, si cada nombre tuviera un hash, sería posible (dependiendo del número de nombres en la base de datos) generar una clave única de cuatro dígitos para cada nombre. Por ejemplo:
7864 Amblard, Sarah 9802 Epadingue, Roger 1990 Mourié, Vincent 8822 Santi, David (y otros)
En este caso, la búsqueda de un nombre implica el cálculo del valor hash (utilizando la función hash utilizada para almacenar el elemento) y luego la comparación de los elementos para encontrar una coincidencia utilizando ese valor. Por regla general, es mucho más rápido buscar una coincidencia en cuatro dígitos -cada uno de los cuales tiene sólo diez posibilidades- que en valores de longitud impredecible, donde cada carácter tiene 26 posibilidades.
El algoritmo utilizado se denomina función hash, probablemente porque el valor resultante es una especie de versión "hash" de la cadena que representa.
Cifrado y descifrado de la firma digital
Además de acelerar la recuperación de datos, el hashing puede utilizarse para cifrar y descifrar firmas digitales (utilizadas para autenticar a los remitentes y destinatarios de los mensajes). La firma digital se transforma utilizando la función hash, y luego el valor hash (llamado huella digital o compendio de mensajes) y la firma se envían por separado al destinatario. El receptor, utilizando la misma función que el emisor, extrae un hash de la firma y lo compara con el hash recibido (los dos deben ser idénticos).
La función hash permite indexar el valor original (o la clave) para utilizarlo en el futuro cuando sea necesario extraer los datos asociados. Por lo tanto, siempre es una operación unidireccional y no es necesario "invertir" la función analizando los valores hash. Idealmente, no debería ser posible derivar una función hash a través de dicho análisis. Además, para ser eficaz, dicha función no debe producir el mismo valor hash para dos entradas diferentes, ya que esto daría lugar a una colisión. Se considera aceptable una función hash con un riesgo de colisión extremadamente bajo.
Algunos ejemplos de funciones hash relativamente sencillas son
Transformación de división (o módulo): primero se estima el tamaño del número de elementos de la tabla. Este número se utiliza entonces como divisor de cada valor original o clave, para extraer un cociente y un resto. El resto es el valor hash. Como es probable que este método genere varias colisiones, los mecanismos de búsqueda deben ser capaces de reconocer una colisión y proponer un mecanismo de búsqueda alternativo.
Plegado: Este método divide el valor original (dígitos en nuestro ejemplo) en varias partes, suma estas partes entre sí y luego utiliza los últimos cuatro dígitos (o cualquier número arbitrario de dígitos) como clave o valor hash.
Conversión de base: cuando el valor o la clave es numérica, se cambia la base de numeración para cambiar la secuencia de dígitos. Por ejemplo, una clave numérica decimal puede cambiarse a numérica hexadecimal. El dígito más significativo puede ser ignorado para que el valor hash tenga una longitud uniforme.
Reordenación de dígitos: Este método simplemente invierte el orden de los dígitos en parte del valor o clave original, por ejemplo, los dígitos en las posiciones 3 a 6. Esta nueva secuencia de dígitos representa la huella digital o la clave.
Varias funciones hash se utilizan con frecuencia en el cifrado. Por ejemplo, MD2, MD4 y MD5 permiten convertir las firmas digitales en valores más cortos (huellas digitales), mientras que SHA (Secure Hash Algorithm), un algoritmo estándar similar a MD4, genera una huella digital más larga (60 bits). No obstante, hay que tener en cuenta que una función hash adecuada para almacenar y recuperar elementos de una base de datos no será necesariamente adecuada para el cifrado o la comprobación de errores.
