Hash (parte 1)

Introducción Hash (Parte 1)

---

Primero ante todo necesitamos saber que es Hash, prefiero citar lo que dice wikipedia para que entiendan mejor:

Citar

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 es una 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 una misma función son diferentes, entonces las dos entradas que generaron dichos resultados también lo son.

Bueno, hasta aquí es fácil, tenemos que coger entradas de un conjunto grande y convertirlos en enteros o un subconjunto de los enteros. Vamos a trabajar con el conjunto de todas las cadenas de caracteres posibles que es ciertamente un gran dominio y obtener un entero de cada una de ellas.

Código:

  >>> def mihash(cadena):
 ...     return len(cadena)
 ...
 >>> mihash('Nuestra desconfianza justifica el engaño ajeno')
 46
 >>> mihash('La simplicidad afectada es una impostura refinada')
 49

Bueno, simplemente la longitud de la cadena hasta aquí nos sirve. Pero seguimos leyendo:

Las caracteristica de las funciones hash nos dan por defecto que H(x) = H(y) es probable que x = y.

Mmmm... cadenas distintas hashes distintas...

Código:

  >>> mihash('La mitad está hecha cuando tienen buen principio las cosas')
 58
 >>> mihash('Nada necesita tanto una reforma como las costumbres ajenas')
 58

Pues no funciona. Hay que pensar algo mejor, que cadenas distintas tengan hashes distintos... Probemos esto:

Código:

  def mihash(cadena):
         s = 0
       base = 1
       for i in range(len(cadena)):
               s += ord(cadena[i])* base
               base *= 256
       return s

En esta función se suma el equivalente numérico de cada letra multiplicado por un peso que aumenta según su posición en la cadena. Como los caracteres están entre 0 y 255 es fácil ver que las cadenas que antes daban el mismo hash por tener la misma longitud ahora lo tendrán distinto.

Código:

  >>> mihash('madurar')
 32195291568693613L
 >>> mihash('saltear')
 32195235717865843L

El artículo sigue diciendo que cuando el conjunto de llegada es menor que el de entrada es imposible que todos los elementos tengan hashes distintos pero que debería ser "difícil" encontrar elementos diferentes con el mismo hash, concretamente el artículo pone la siguiente condición: "Dado x es com@@@@@cionalmente difícil encontrar y tal que H(x)=H(y)". Y aquí fallamos miserablemente, de hecho ¡ dado H(x) encontramos x !

Por ejemplo H(x)=7106419. Como es mayor que 256^2=65536 pero menor que 256^3=16777216 resulta que x es una cadena con tres caracteres. Además 7106419/65536 = 108.4 y el código ascii de 'l' es precisamente 108 luego la tercera letra es 'l'. Ahora seguimos con 7106419-108*65536=28531 y 28531/256=111.4 luego la segunda letra es 'o' (ascii 111). Después 28531-111*256=115 así que la primera letra es 's'. En resumen x='sol'; H('sol')=7106419.

Tenemos una función inversible lo que es malo para una función hash tal y como se usa en criptografía, otra dificultad es que el resultado es demasiado grande para ser manejable, no tiene un tamaño fijo como 128, 160, 256 o 512 bits que son tamaños habituales para las funciones hash. Véase:

Código:

  >>> mihash('Es duro caer, pero es peor todavía no
 haber intentado nunca subir')
 153400954361420347149098469424201707143190953984170802136
 287935903055595510635613188203179335624783334059327856635
 8972930507578856041601550303152308360344389

---

Bueno no sé si entienda mucho el documento pero se trato de ser lo más especifico para hacer una introducción de este tipo de funciones algoritmicas, agradezco a Jaime Suárez Martínez y quien publico esto en una web de seguridad informática. Doy gracias por la gran colaboración en el tema. Dentro de poco sacare la segunda parte para entender un algo más del desarrollo de las funciones de hash.

continua en

Hash (parte 2)

Por: rufiopunkrock