Fonction de hachage
(hash function)
Soit M={0,1}* l'ensemble des mots (finis) construits sur l'alphabet à deux éléments {0,1}. Fixons une taille n et considérons l'ensemble B={0,1}^n des blocs de tailles n. Soit alors f une fonction de M dans B. Supposons que f possède les deux propriétés suivantes :
étant donné un y dans B, il est impossible en pratique de calculer un x tel que y=f(x) (résistance à la pré-image).
il est impossible en pratique de trouver deux éléments distincts de M ayant la même image par f (résistance aux collisions).
Dans ce cas on dit que f est une fonction de hachage. Si m est un élément de M, f(m) est appelé le haché de m ou encore l'empreinte de m. En pratique on restreint la taille des mots de M, toutefois cette taille peut rester très grande devant la taille du haché. Par exemple un message d'entrée peut avoir de l'ordre de 2^64 bits et son haché (ou empreinte) 256 bits. A coté de ce type de fonction de hachage dite fonction de hachage à usage de la cryptographie, il existe des fonctions de hachage à deux entrées, le texte à hacher et une clé.