Fonction de hachage

Une bonne fonction de hachage doit répartir les entrées attendues de la manière la plus uniforme possible sur son intervalle de sortie. Autrement dit, chaque valeur de hachage de l'intervalle de sortie doit être générée avec une probabilité sensiblement égale . Cette exigence se justifie par le fait que le coût des méthodes de hachage augmente fortement avec le nombre de collisions (paires d'entrées associées à la même valeur de hachage). Si certaines valeurs de hachage sont plus fréquentes que d'autres, une plus grande proportion des opérations de recherche devra parcourir un ensemble plus important d'entrées de la table présentant des collisions.

Ce critère exige seulement que la valeur soit uniformément distribuée , et non aléatoire au sens strict. Une bonne fonction de randomisation est généralement un bon choix comme fonction de hachage (abstraction faite des considérations d'efficacité de calcul), mais la réciproque n'est pas nécessairement vraie.

Les tables de hachage ne contiennent souvent qu'un petit sous-ensemble des entrées valides. Par exemple, la liste des membres d'un club peut ne contenir qu'une centaine de noms, parmi le très grand ensemble de tous les noms possibles. Dans ces cas, le critère d'uniformité doit être vérifié pour presque tous les sous-ensembles typiques d'entrées que l'on peut trouver dans la table, et non seulement pour l'ensemble global de toutes les entrées possibles.

Autrement dit, si un ensemble typique de enregistrements est haché dans emplacements de table, la probabilité qu'un compartiment contienne beaucoup plus de enregistrements est infime. En particulier, si , très peu de compartiments devraient contenir plus d'un ou deux enregistrements. Un petit nombre de collisions est quasiment inévitable, même si est beaucoup plus grand que (voir le paradoxe des anniversaires ).

Dans certains cas particuliers où les clés sont connues à l'avance et où l'ensemble de clés est statique, il est possible de trouver une fonction de hachage qui garantit une uniformité absolue (ou sans collision). On dit alors que cette fonction est parfaite . Il n'existe aucun algorithme permettant de construire une telle fonction ; sa recherche est une fonction factorielle du nombre de clés à mapper par rapport au nombre d'emplacements dans la table de hachage. Trouver une fonction de hachage parfaite pour un ensemble de clés relativement important est généralement impossible en pratique ; la fonction résultante est souvent plus complexe à calculer qu'une fonction de hachage standard et n'offre qu'un avantage marginal par rapport à une fonction aux bonnes propriétés statistiques qui minimise le nombre de collisions. Voir fonction de hachage universelle .

Lors du test d'une fonction de hachage, l'uniformité de la distribution des valeurs de hachage peut être évaluée par le test du χ² . Ce test est une mesure d'adéquation : il compare la distribution réelle des éléments dans les compartiments à la distribution attendue (ou uniforme) des éléments. La formule est

où est le nombre de compartiments et est le nombre d'éléments dans le compartiment non-puissance de 2 sans pour autant effectuer de reste ni de division, car ces calculs sont parfois coûteux. Par exemple, supposons que soit nettement inférieur à . Considérons une fonction génératrice de nombres pseudo-aléatoires uniforme sur l'intervalle − 1] . Une fonction de hachage uniforme sur l'intervalle 1] est . On peut remplacer la division par un décalage binaire à droite (potentiellement plus rapide) : .

Si les clés sont hachées de manière répétée et que la fonction de hachage est coûteuse, on peut gagner du temps de calcul en précalculant les codes de hachage et en les stockant avec les clés. Des codes de hachage identiques impliquent presque certainement que les clés sont identiques. Cette technique est utilisée pour la table de transposition dans les programmes de jeux, qui stocke une représentation hachée sur 64 bits de la position des pièces sur le plateau.

Une fonction de hachage qui n'autorise que certaines tailles de table ou des chaînes de caractères jusqu'à une certaine longueur, ou qui ne peut pas accepter de graine (c'est-à-dire qui autorise le double hachage), est moins utile qu'une fonction qui le fait.

Une fonction de hachage est applicable dans diverses situations. En particulier en cryptographie, on peut citer les applications notables suivantes :

• Contrôle d'intégrité : des valeurs de hachage identiques pour différents fichiers impliquent l'égalité, fournissant un moyen fiable de détecter les modifications de fichiers.
• Dérivation de clés : De légères modifications des données d’entrée entraînent une altération de la sortie d’apparence aléatoire, un phénomène connu sous le nom de diffusion. C’est pourquoi les fonctions de hachage sont précieuses pour la dérivation de clés.
• Codes d'authentification de message (MAC) : Grâce à l'intégration d'une clé confidentielle avec les données d'entrée, les fonctions de hachage peuvent générer des MAC garantissant l'authenticité des données, comme dans les HMAC .
• Stockage des mots de passe : La valeur de hachage du mot de passe ne révèle aucun détail du mot de passe, ce qui souligne l’importance de stocker les mots de passe hachés de manière sécurisée sur le serveur.
• Signatures : Ce sont les hachages des messages qui sont signés, et non le message entier.

Une procédure de hachage doit être déterministe : pour une valeur d'entrée donnée, elle doit toujours générer la même valeur de hachage. Autrement dit, elle doit être une fonction des données à hacher, au sens mathématique du terme. Cette exigence exclut les fonctions de hachage qui dépendent de paramètres variables externes, tels que les générateurs de nombres pseudo-aléatoires ou l'heure. Elle exclut également les fonctions qui dépendent de l' adresse mémoire de l'objet à hacher, car cette adresse peut changer pendant l'exécution (comme cela peut se produire sur les systèmes utilisant certaines méthodes de ramasse-miettes ), même si un nouveau hachage de l'élément est parfois possible.

Le déterminisme s'inscrit dans le contexte de la réutilisation de la fonction. Par exemple, Python ajoute la fonctionnalité suivante : les fonctions de hachage utilisent une graine aléatoire générée une seule fois, au démarrage du processus Python, en plus de l'entrée à hacher. La fonction de hachage Python ( SipHash ) reste valide lors d'une utilisation unique, mais si les valeurs sont enregistrées (par exemple, sur le disque), elles ne peuvent plus être considérées comme des valeurs de hachage valides, car la valeur aléatoire peut différer lors d'une exécution ultérieure.

Il est souvent souhaitable que la sortie d'une fonction de hachage ait une taille fixe (voir ci-dessous). Si, par exemple, la sortie est limitée à des valeurs entières de 32 bits, les valeurs de hachage peuvent servir d'index dans un tableau. Ce type de hachage est couramment utilisé pour accélérer les recherches de données. Produire une sortie de longueur fixe à partir d'une entrée de longueur variable peut être réalisé en divisant les données d'entrée en segments de taille spécifique. Les fonctions de hachage utilisées pour les recherches de données utilisent une expression arithmétique qui traite itérativement des segments de l'entrée (tels que les caractères d'une chaîne) pour produire la valeur de hachage.

Dans de nombreuses applications, l'intervalle des valeurs de hachage peut varier d'une exécution à l'autre ou évoluer au cours d'une même exécution (par exemple, lorsqu'il est nécessaire d'étendre une table de hachage). Dans ces cas, une fonction de hachage prenant deux paramètres est requise : les données d'entrée et le nombre de valeurs de hachage autorisées.

Une solution courante consiste à calculer une fonction de hachage fixe avec une très grande plage de valeurs (par exemple, de − 1 ), à diviser le résultat par et à utiliser le reste de la division . Si est lui-même une puissance de et − 1 , quelle que soit la valeur de rencontrée dans l'application. Selon la fonction, le reste peut n'être uniforme que pour certaines valeurs de , par exemple les nombres impairs ou premiers .

Lorsque la fonction de hachage est utilisée pour stocker des valeurs dans une table de hachage qui survit à l'exécution du programme, et que la table de hachage doit être agrandie ou réduite, on parle alors de table de hachage dynamique.

Il est souhaitable de disposer d'une fonction de hachage qui déplace le nombre minimal d'enregistrements lors du redimensionnement de la table. Il faut donc une fonction de hachage (où est la clé à hacher et le nombre de valeurs de hachage autorisées) telle que + 1) = H ( z , n ) avec une probabilité proche de + 1) .

Le hachage linéaire et le hachage en spirale sont des exemples de fonctions de hachage dynamiques qui s'exécutent en temps constant, mais qui assouplissent la propriété d'uniformité afin de minimiser les déplacements. Le hachage extensible utilise une fonction de hachage dynamique dont le calcul nécessite un espace mémoire proportionnel à et qui dépend des clés précédemment insérées. Plusieurs algorithmes préservant l'uniformité, mais dont le calcul de la valeur de ont été développés.

Une fonction de hachage avec un déplacement minimal est particulièrement utile dans les tables de hachage distribuées .

Dans certaines applications, les données d'entrée peuvent contenir des caractéristiques non pertinentes à des fins de comparaison. Par exemple, lors de la recherche d'un nom propre, il peut être souhaitable d'ignorer la distinction entre majuscules et minuscules. Pour de telles données, il est nécessaire d'utiliser une fonction de hachage compatible avec le critère d'équivalence des données : deux entrées considérées comme équivalentes doivent produire la même valeur de hachage. Ceci peut être réalisé en normalisant l'entrée avant de la hacher, par exemple en convertissant toutes les lettres en majuscules.

Si les données à hacher sont suffisamment petites, on peut utiliser les données elles-mêmes (réinterprétées comme un entier) comme valeur de hachage. Le coût de calcul de cette fonction de hachage d'identité est pratiquement nul. Cette fonction de hachage est parfaite , car elle associe à chaque entrée une valeur de hachage unique.

La notion de « suffisamment petit » dépend de la taille du type utilisé comme valeur de hachage. Par exemple, en Java , le code de hachage est un entier 32 bits. Ainsi, les objets entiers 32 bits Integeret à virgule flottante 32 bits Floatpeuvent utiliser directement cette valeur, contrairement aux entiers 64 bits Longet aux objets à virgule flottante 64 bits Double.

D'autres types de données peuvent également utiliser ce schéma de hachage. Par exemple, lors de la conversion de chaînes de caractères entre majuscules et minuscules , on peut utiliser l'encodage binaire de chaque caractère, interprété comme un entier, pour indexer une table qui donne la forme alternative de ce caractère (« A » pour « a », « 8 » pour « 8 », etc.). Si chaque caractère est stocké sur 8 bits (comme en ASCII étendu ou en ISO Latin 1 ), la table ne comporte que 2⁸ ⁼ 256 entrées ; dans le cas des caractères Unicode , la table en comporterait 17 × ^2¹⁶ =1 114 112 entrées.

La même technique peut être utilisée pour faire correspondre les codes pays à deux lettres comme « us » ou « za » aux noms de pays (26² ^{= 676 entrées de tableau),} les codes postaux à 5 chiffres comme 13083 aux noms de villes (100 000 entrées), etc. Les valeurs de données non valides (telles que le code pays « xx » ou le code postal 00000) peuvent être laissées non définies dans le tableau ou associées à une valeur « nulle » appropriée.

Si les clés sont uniformément ou suffisamment uniformément réparties dans l'espace des clés, de sorte que leurs valeurs soient essentiellement aléatoires, elles peuvent être considérées comme déjà « hachées ». Dans ce cas, n'importe quel nombre de bits de la clé peut être extrait et utilisé comme index dans la table de hachage. Par exemple, une fonction de hachage simple pourrait masquer les .

Un code de hachage par carrés moyens est produit en élevant au carré l'entrée et en extrayant un nombre approprié de chiffres ou de bits centraux. Par exemple, si l'entrée est123 456 789 et la taille de la table de hachage10 000 , puis en élevant la clé au carré, on obtient15 241 578 750 190 521 , le code de hachage est donc calculé à partir des quatre chiffres centraux du nombre à 17 chiffres (en ignorant le chiffre de poids fort) 8750. La méthode des carrés médians produit un code de hachage acceptable si la clé ne contient pas beaucoup de zéros en début ou en fin de chaîne. Il s'agit d'une variante du hachage multiplicatif, mais moins performante car une clé quelconque ne constitue pas un bon multiplicateur.

Une technique courante consiste à utiliser une fonction modulo sur la clé, en choisissant un diviseur K (mod M ) . La taille de la table est généralement une puissance de 2. Ceci donne une distribution dans 1} . Cette méthode donne de bons résultats pour un grand nombre d'ensembles de clés. Un inconvénient majeur du hachage par division est que la division nécessite plusieurs cycles sur la plupart des architectures modernes (y compris x86 ) et peut être 10 fois plus lente que la multiplication. Un autre inconvénient est qu'elle ne permet pas de séparer les clés groupées. Par exemple, les clés 123000, 456000, 789000, etc., modulo 1000, correspondent toutes à la même adresse. Cette technique fonctionne bien en pratique car de nombreux ensembles de clés sont déjà suffisamment aléatoires, et la probabilité qu'un ensemble de clés soit cyclique d'un grand nombre premier est faible.

Le codage algébrique est une variante de la méthode de hachage par division qui utilise la division par un polynôme modulo 2 au lieu d'un entier pour mapper bits. Dans cette approche, , et nous postulons un polynôme de degré m − 1 x m − 1 + ⋯ + ζ 0 . Une clé 1 … k 1 k 0 ) 2 peut être considérée comme le polynôme 1 x n − 1 + ⋯ + k 1 x + k 0 . Le reste, calculé par l'arithmétique polynomiale modulo 2, est 1</sub> x  m - 1 + … h 1 x + h 0  . Alors 1</sub> … h 1 h 0  ) 2  . Si est construit de manière à avoir bits sont garanties de ne pas entrer en collision.

, (ce dernier étant un diviseur de 1 ) et est construite à partir du fini . Knuth donne un exemple : en prenant obtient La démonstration est la suivante :

Soit , t } ⊆ S et S ∀ j ∈ S .

Définir∈ ⁿ GF(2 ^k ) et où les coefficients de sont calculés dans ce corps. Alors le degré de S | . Puisque ^{2 j} est une racine de chaque fois que ^j est une racine, il s'ensuit que les coefficients de satisfont = p _i , donc ils sont tous égaux à 0 ou 1. Si 1 x ^{n − 1} + ⋯ + r ₁ x + r ₀ est un polynôme non nul modulo 2 avec au plus n'est pas un multiple de modulo 2. Il s'ensuit que la fonction de hachage correspondante associera les clés ayant moins de , soit ( aK mod W ) / ( W / M ) ⌋ , qui produit une valeur de hachage dans , M − 1} . La valeur ; elle doit être grande aK mod 2^{^w} ) / (2 ^{^w − m} ) ⌋ . Ceci est particulier car l'arithmétique modulo </sup> est effectuée par défaut dans les langages de programmation bas niveau et la division entière par une puissance de 2 correspond simplement à un décalage à droite. Ainsi, en C , par exemple, cette fonction devient h_a(K ) = ⌊(aK mod 2^w) / (2^w − m)⌋.

fixés, cela se traduit par une simple multiplication d'entiers et un décalage à droite, ce qui en fait l'une des fonctions de hachage les plus rapides à calculer.

Le hachage multiplicatif est sujet à une « erreur courante » qui entraîne une mauvaise diffusion : les bits d’entrée de valeur élevée n’affectent pas les bits de sortie de valeur faible. Une transmutation sur l’entrée, qui décale vers le bas la plage des bits de poids fort conservés et les combine par XOR ou ADD à la clé avant l’étape de multiplication, corrige ce problème. La fonction résultante ressemble à :

Fibonacci est une forme de hachage multiplicatif dont le multiplicateur est , où (phi) le nombre d'or (environ 1,618). Ce multiplicateur a la propriété de répartir uniformément dans l'espace de la table les blocs de clés consécutives par rapport à n'importe quel bloc de bits de la clé. Les clés consécutives dans les bits de poids fort ou les bits de poids faible de la clé (ou d'un autre champ) sont relativement fréquentes. Les multiplicateurs pour différentes longueurs de mot sont :

• 16 : a = 9E37 ₁₆ =40 503 ₁₀
• 32 : a = ₁₆ =2 654 435 769 ₁₀
• 48 : a = 7F4B ₁₆ =173 961 102 589 771 ₁₀
• 64 : a = 7F4A 7C15 ₁₆ =11 400 714 819 323 198 485 ₁₀

L'exemple paradigmatique de la réduction par caractères consiste à additionner les valeurs entières de tous les caractères de la chaîne. Une meilleure approche consiste à multiplier le total du hachage par une constante, généralement un grand nombre premier, avant d'ajouter le caractère suivant, en ignorant les dépassements de capacité. L'utilisation du OU exclusif à la place de l'addition est également une alternative envisageable. L'opération finale serait un modulo, un masque ou une autre fonction permettant de réduire la valeur du mot à un index de la taille de la table. Le point faible de cette procédure est que des informations peuvent se concentrer dans les bits de poids fort ou de poids faible des octets ; cette concentration persiste dans le résultat du hachage et engendre davantage de collisions qu'un hachage aléatoire correct. Les codes d'octets ASCII, par exemple, ont un bit de poids fort à 0, et les chaînes imprimables n'utilisent ni le dernier code d'octet ni la plupart des 32 premiers. Par conséquent, les informations utilisant les codes d'octets restants se concentrent dans les bits restants de manière non évidente.

L'approche classique, appelée hachage PJW d'après les travaux de Peter J. Weinberger aux Bell Labs dans les années 1970, a été initialement conçue pour hacher les identifiants dans les tables de symboles du compilateur, comme indiqué dans le « Dragon Book » . Cette fonction de hachage décale les octets de 4 bits avant de les additionner. Lorsque le total atteint un nombre maximal d'octets, les 4 bits de poids fort sont décalés et, s'ils sont non nuls, réintégrés par un OU exclusif (XOR) dans l'octet de poids faible du total. On obtient ainsi un code de hachage de la taille d'un mot, auquel on peut appliquer un modulo ou une autre opération de réduction pour produire l'index de hachage final.

Aujourd'hui, notamment avec l'avènement des tailles de mots de 64 bits, un hachage de chaînes de longueur variable par blocs de mots beaucoup plus efficace est disponible.

Dans certaines applications, comme la recherche de sous-chaînes , on peut calculer une fonction de hachage pour chaque sous-chaîne de d' une chaîne caractères donnée , en parcourant la chaîne à l'aide d'une fenêtre de largeur caractères, où est un entier fixe et . La solution directe, qui consiste à extraire une telle sous-chaîne à chaque position de caractère dans le texte et à calculer séparément, nécessite un nombre d'opérations proportionnel à . Cependant, en choisissant judicieusement , on peut utiliser la technique du hachage glissant pour calculer tous ces hachages avec un effort proportionnel à où est le nombre d'occurrences de la sous-chaîne.

L'algorithme de ce type le plus courant est Rabin-Karp, dont la complexité est dans le meilleur et le meilleur cas, et de dans le pire des cas (il faut toutefois préciser que ce dernier cas est particulièrement problématique : la chaîne de caractères et la sous-chaîne sont toutes deux composées d'un seul caractère répété, comme ="AAAAAAAAAAA" » et ="AAA »). La fonction de hachage utilisée est généralement l' empreinte de Rabin , conçue pour éviter les collisions dans les chaînes de caractères de 8 bits, mais d'autres fonctions de hachage appropriées peuvent également être utilisées.