Hispanopedia Wiki
Articulo de referencia

Hash de Pearson

El hash de Pearson es una función hash no criptográfica diseñada para una ejecución rápida en procesadores con registros de 8 bits . A partir de una entrada de cualquier número ...

Hispanopedia WikiContenido en espanolLectura gratuita

El hash de Pearson es una función hash no criptográfica diseñada para una ejecución rápida en procesadores con registros de 8 bits . A partir de una entrada de cualquier número de bytes, produce como salida un único byte que depende en gran medida de cada byte de la entrada. Su implementación requiere solo unas pocas instrucciones, además de una tabla de búsqueda de 256 bytes que contiene una permutación de los valores del 0 al 255. [ 1 ]

Esta función hash es un CBC-MAC que utiliza un cifrado de sustitución de 8 bits implementado mediante la tabla de sustitución . Un cifrado de 8 bits tiene una seguridad criptográfica insignificante, por lo que la función hash de Pearson no es criptográficamente robusta , pero es útil para implementar tablas hash o como código de verificación de integridad de datos , para lo cual ofrece los siguientes beneficios:

  • Es extremadamente sencillo.
  • Se ejecuta rápidamente en procesadores con recursos limitados.
  • No existe una clase simple de entradas para las cuales las colisiones (salidas idénticas) sean especialmente probables.
  • Dado un pequeño conjunto de entradas privilegiadas (por ejemplo, palabras reservadas para un compilador ), la tabla de permutación se puede ajustar de manera que esas entradas produzcan valores hash distintos, generando lo que se denomina una función hash perfecta .
  • Dos cadenas de entrada que difieren en exactamente un carácter nunca colisionan. [ 2 ] Por ejemplo, aplicar el algoritmo a las cadenas ABC y AEC nunca producirá el mismo valor.

Una de sus desventajas en comparación con otros algoritmos de hash diseñados para procesadores de 8 bits es la tabla de búsqueda sugerida de 256 bytes, que puede ser prohibitivamente grande para un microcontrolador pequeño con un tamaño de memoria de programa del orden de cientos de bytes. Una solución a esto es usar una función de permutación simple en lugar de una tabla almacenada en la memoria de programa. Sin embargo, usar una función demasiado simple, como T[i] = 255-i, compromete parcialmente su utilidad como función hash, ya que los anagramas darán como resultado el mismo valor hash; por otro lado, usar una función demasiado compleja afectará negativamente la velocidad. Usar una función en lugar de una tabla también permite extender el tamaño del bloque. Estas funciones naturalmente deben ser biyectivas , al igual que sus variantes de tabla.

El algoritmo se puede describir mediante el siguiente pseudocódigo , que calcula el hash del mensaje C utilizando la tabla de permutaciones T :  

El algoritmo de hash de Pearson es h := 0 for each c in C loop h := T[ h xor c ] end loopreturn h

The hash variable (h) may be initialized differently, e.g. to the length of the data (C) modulo 256.

Example implementations

C#, 8-bit

publicclassPearsonHashing{publicstaticbyteHash(stringinput){byte[]T={/* Permutation of 0-255 */};bytehash=0;byte[]bytes=Encoding.UTF8.GetBytes(input);foreach(bytebinbytes){hash=T[hash^b];}returnhash;}}

See also

References

  1. ↑Pearson, Peter K. (June 1990), "Fast Hashing of Variable-Length Text Strings"(PDF), Communications of the ACM, 33 (6): 677–680, doi:10.1145/78973.78978, archived from the original(PDF) on 2012-07-04, retrieved 2013-07-13
  2. ↑Lemire, Daniel (2012), "The universality of iterated hashing over variable-length strings", Discrete Applied Mathematics, 160 (4–5): 604–617, arXiv:1008.1715, doi:10.1016/j.dam.2011.11.009