Funció hash

La funció resum (hash function en anglès) és un algorisme o funció que converteix un o més elements d'entrada en un altre element. S'empra per a resumir o identificar una dada a través de la probabilitat. El resum (hash en anglès) és el resultat de dita funció o algorisme. Alguns exemples són el MD5, el SHA-1 i en general els CRCs. Una propietat fonamental de les funcions resum és precisament que són funcions, que si dos resums, utilitzant la mateixa funció, són diferents, llavors les dues entrades que generaren aquests resums també ho són. La funció resum s'utilitza principalment tant en el camp de la criptografia com en el de la indexació de dades i en el de les comunicacions digitals com a codi de redundància per a corregir errors de transmissió. Molts sistemes relacionats amb la seguretat informàtica, amb les bases de dades o les transmissions de dades, usen funcions o taules de resum (taules hash).

En una funció resum, qualsevol alteració de l'entrada provoca una sortida diferent

Propietats

Una funció és quelcom que relaciona una entrada $x$ amb una sortida $y$ :

$y=f(x)$

i una funció hash relaciona unes dades de entrada amb un valor de sortida que s'acostuma a expressar en hexadecimal, per exemple la funció hash md5 :

$md5(hola-mon-soc-una-frase)=a23abc5$

• Baix cost computacional i memòria
• Compressió de dades
• Uniformitat : valors de sortida imparcialment distrubuïts
• Determinisme : amb el mateix valor d'entrada sempre s'ha d'obtenir la mateixa sortida.

Tipus de funcions hash

• Checksum
• CRC
• Hash universal
• Hash no criptogràfiques
• Hash criptogràfiques

Aplicacions

Les funciones hash son usades en múltiples camps. Per exemple:

• Són una eina bàsica per a la construcció d'utilitats més complexes:
  • Construcció d'estructures de dades: fan més eficients les cerques, i/o permeten assegurar les dades que contenen. Per exemple, les taules hash, o els arbres de Merkle.
  • Construcció d'esquemes de compromís.
  • Construcció d'algoritmes de xifrat/desxifrat.
  • Construcció de algoritmes generadors de nombres pseudoaleatoris.
  • Construcció de cadenes pseudoaleatòries.
  • Construcció d'algoritmes de prova de pertinència o no a un conjunt.
  • Construcció de mètodes de generació de segells de temps confiables.
• Com a eina per a protegir la integritat:
  • En la firma digital.
  • Suma de verificació (de l'anglés checksum).
  • Prova de la integritat de continguts.
• Com a eina vinculada a la autenticació i control d'accés:
  • Autenticació d'entitats.
  • Protecció de claus.
  • Derivació de claus.
• Com a eina pera la identificació i la rápida comparació de dades:
  • Empremtes digitals.
  • Identificació de continguts, com ara per exemple en xarxes P2P.
  • Identificació de registres en una base de dades per permetre un accés més ràpid als registres (fins i tot més ràpid que usant índexos).
  • Algoritmes de cerca de subcadenes.
  • Detecció de virus.

Bibliografia

• Krawczyk, Hugo. «Leccion 14. Funciones Unidireccionales y algoritmos de hash (guión)». Intypedia. Criptored, 2012. Arxivat de l'original el 14 de novembre 2018. [Consulta: 13 novembre 2018].