El hashing 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 . Dada una entrada que consta 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 sólo 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 a través de 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 fuerte , pero es útil para implementar tablas hash o como código de verificación de integridad de datos , para cuyos fines ofrece estos beneficios:
Uno de sus inconvenientes en comparación con otros algoritmos 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 utilizar una función de permutación simple en lugar de una tabla almacenada en la memoria del programa. Sin embargo, el uso de una función demasiado simple, como T[i] = 255-i, anula en parte la usabilidad como función hash, ya que los anagramas darán como resultado el mismo valor hash; Por otro lado, el uso de una función demasiado compleja afectará negativamente a la velocidad. Usar una función en lugar de una tabla también permite ampliar el tamaño del bloque. Naturalmente, estas funciones tienen que 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 permutación T :
algoritmo hash de Pearson es h := 0 para cada c en el bucle C h := T[ h xor c ] bucle final volver h
La variable hash ( h) se puede inicializar de manera diferente, por ejemplo, a la longitud de los datos ( C) módulo 256.
clase pública PearsonHashing { Hash de byte estático público ( entrada de cadena ) { byte [] T = { /* Permutación de 0-255 */ }; hash de bytes = 0 ; byte [] bytes = Codificación . UTF8 . GetBytes ( entrada ); foreach ( byte b en bytes ) { hash = T [ hash ^ b ]; } hash de retorno ; }}