Quel est exactement (et précisément) est "hash?"

J'ai entendu le mot "hash" utilisé dans différents contextes (tous dans le monde de l'informatique) avec différentes significations. Par exemple, dans le livre Apprendre Python à la dure, dans le chapitre consacré aux dictionnaires, il est dit "Python les appelle" dicts. "D'autres langues les appellent" hachages "." Alors, les dictionnaires sont-ils des hachages?

L'autre usage courant du mot concerne le cryptage. J'ai aussi entendu (et lu) des gens utiliser le mot "hash" comme fonction spécifique dans la programmation de haut niveau.

Alors, c'est quoi exactement?

Quelqu'un peut-il (avec le temps et qui est compétent) bien vouloir expliquer les détails de "hash (ou hash)?"

L'article de Wikipedia sur les fonctions de hachage est très bon, mais je vais donner ici mon point de vue.

Qu'est-ce qu'un hash?

"Hash" est vraiment un terme large avec différentes significations formelles dans différents contextes. Il n'y a pas une seule réponse parfaite à votre question. Je vais expliquer le concept général sous-jacent et mentionner quelques-unes des utilisations les plus courantes du terme.

Un "hachage" est une fonction appelée fonction de hachage qui prend comme objets d'entrée et génère une chaîne ou un nombre. Les objets d'entrée sont généralement des membres de types de données de base tels que des chaînes, des entiers ou de plus grands composés d'autres objets tels que des structures définies par l'utilisateur. La sortie est généralement un nombre ou une chaîne. Le nom "hash" fait souvent référence à cette sortie. Le verbe "hash" signifie souvent "appliquer une fonction de hachage". Les principales propriétés qu'une fonction de hachage devrait avoir sont:$h$

1. Il devrait être facile de calculer et
2. Les sorties devraient être relativement petites.

Exemple:

Supposons que nous voulions hacher des nombres compris entre 0 et 999 999 999 et compris entre 0 et 99. Une simple fonction de hachage peut être .$h(x) = x \mod 100$

Propriétés supplémentaires communes:

Selon le cas d'utilisation, nous pouvons souhaiter que la fonction de hachage satisfasse des propriétés supplémentaires. Voici quelques propriétés supplémentaires communes:

1. Uniformité : Souvent, nous souhaitons que les objets de hachage soient distincts. De plus, nous voudrons peut-être que les hachages soient "dispersés". Si je veux diviser des objets en 100 compartiments (la sortie de ma fonction de hachage est donc un nombre compris entre 0 et 99), j'espère qu'environ 1/100 des objets atterriront dans le compartiment 0, environ 1/100 dans seau 1, et ainsi de suite.

2. Résistance aux collisions cryptographiques : parfois, cela va encore plus loin. Par exemple, en cryptographie, je peux souhaiter une fonction de hachage telle qu'il est difficile, d'un point de vue calcul, à un adversaire de trouver deux entrées différentes mappant vers la même sortie.

3. Compression : je souhaite souvent réduire de façon arbitraire des entrées volumineuses en une sortie de taille constante ou un nombre fixe de compartiments.

4. Déterminisme : il se peut que je veuille une fonction de hachage dont la sortie ne change pas entre les exécutions, c’est-à-dire que la sortie de la fonction de hachage sur le même objet restera toujours la même. Cela peut sembler en contradiction avec l'uniformité ci-dessus, mais une solution consiste à choisir la fonction de hachage de manière aléatoire une fois, et à ne pas la modifier entre les exécutions.

Quelques applications

Une application courante est dans les structures de données telles qu'une table de hachage, qui permettent d'implémenter des dictionnaires. Ici, vous allouez de la mémoire, par exemple 100 "compartiments"; puis, lorsqu'on vous demande de stocker une paire (clé, valeur) dans le dictionnaire, vous écrivez la clé dans un nombre compris entre 0 et 99, puis vous stockez la paire dans le compartiment correspondant en mémoire. Ensuite, lorsque vous êtes invité à rechercher une clé, vous la divisez en un nombre compris entre 0 et 99 avec la même fonction de hachage, puis vérifiez ce compartiment pour voir si cette clé est présente. Si c'est le cas, vous retournez sa valeur.

Notez que vous pouvez également implémenter les dictionnaires d'une autre manière, par exemple avec un arbre de recherche binaire (si vos objets sont comparables).

Une autre application pratique est la somme de contrôle, qui permet de vérifier que deux fichiers sont identiques (par exemple, le fichier n'était pas corrompu depuis sa version précédente). Comme il est très peu probable que les fonctions de hachage mappent deux entrées sur la même sortie, vous calculez et stockez un hachage du premier fichier, généralement représenté par une chaîne. Ce hachage est très petit, peut-être seulement quelques dizaines de caractères ASCII. Ensuite, lorsque vous obtenez le deuxième fichier, vous le hachez et vérifiez que le résultat est le même. Si c'est le cas, il s'agit presque certainement du même fichier, octet par octet.

Une autre application est la cryptographie, où ces hachages devraient être difficiles à "inverser" - c’est-à-dire que, compte tenu de la sortie et de la fonction de hachage, il devrait être difficile, d’un point de vue calcul, de déterminer l’entrée ou les entrées ayant conduit à cette sortie. Une des utilisations de ceci est pour les mots de passe: Au lieu de stocker le mot de passe lui-même, vous stockez un hachage cryptographique du mot de passe (peut-être avec quelques autres ingrédients). Ensuite, lorsqu'un utilisateur entre un mot de passe, vous calculez son hachage et vérifiez qu'il correspond au hachage correct; Si c'est le cas, vous dites que le mot de passe est correct. (Maintenant, même quelqu'un qui peut rechercher et trouver le hachage enregistré sur le serveur n'a pas la facilité de prétendre être l'utilisateur.) Cette application peut être un cas où la sortie est aussi longue ou plus longue que l'entrée, car l'entrée est si courte.

Une fonction de hachage est une fonction qui prend une entrée et produit une valeur de taille fixe. Par exemple, vous pourriez avoir une fonction de hachage stringHashqui accepte unstring longueur quelconque et génère un entier de 32 bits.

En règle générale, il est correct de dire que la sortie d'une fonction de hachage est un hachage (également appelée valeur de hachage ou somme de hachage). Cependant, parfois, les gens se réfèrent à la fonction elle-même comme un hachage . Ceci est techniquement incorrect, mais généralement négligé car il est généralement compris (dans le contexte) que la personne voulait dire fonction de hachage .

L'utilisation typique d'une fonction de hachage consiste à implémenter une table de hachage . Une table de hachage est une structure de données qui associe des valeurs à d'autres valeurs généralement appelées clés. Pour ce faire, il utilise une fonction de hachage sur la clé pour produire une valeur de hachage de taille fixe qu’elle peut utiliser pour rechercher rapidement les données qu’elle stocke. Je n'entrerai pas dans les détails pour savoir comment cela fonctionne, mais le fait clé ici est qu'il s'appelle une table de hachage car elle repose sur une fonction de hachage pour produire des valeurs de hachage (hachages).

C’est là que la confusion règne, parce que certaines personnes (encore une fois, quelque peu incorrectement) se réfèrent à une table de hachage comme à un hachage. Comme indiqué dans d'autres réponses, la mise en oeuvre d'une table de hachage dans une langue donnée fait référence à la table de hachage en tant que hachage (notamment Perl, bien que d'autres langues le soient aussi). D'autres langues choisissent de se référer à leur implémentation d'une table de hachage sous forme de dictionnaire. Python est l’une de ces langues mais, en raison de l’enracinement de leur langue, de nombreux utilisateurs de Python raccourcissent le terme dictionnaire en "dict".

Ainsi, si l’utilisation correcte du terme hash consiste à faire référence à la valeur de hachage produite par une fonction de hachage , les utilisateurs utilisent parfois aussi le terme de manière informelle pour désigner des fonctions de hachage et des tables de hachage , ce qui crée de la confusion.

Une fonction de hachage est en gros toute fonction où l'image est plus petite que le domaine . La sortie d'une telle fonction f(x)peut être appelée "le hachage de x".

En informatique, nous rencontrons généralement deux applications des fonctions de hachage.

La première concerne les structures de données telles que les tables de hachage , dans lesquelles nous voulons mapper le domaine de clé (par exemple des entiers 32 bits ou des chaînes de longueur arbitraire) à un index de tableau (par exemple un entier compris entre 0 et 100). Le but ici est de maximiser les performances de la structure de données; Les propriétés de la fonction de hachage qui sont généralement souhaitables sont la simplicité et la distribution uniforme de la sortie.

Perl appelle son type de tableau associatif intégré un "hachage" , ce qui semble être la cause de votre confusion ici. Je ne connais aucune autre langue qui le fasse. En gros, la structure de données peut être vue comme une fonction de hachage elle-même (où le domaine est l'ensemble de clés actuel), mais est également implémentée comme une table de hachage.

La seconde concerne la cryptographie : authentification de message, vérification du mot de passe / signature, etc. Le domaine est généralement constitué de chaînes d'octets arbitraires. Nous nous intéressons ici à la sécurité - ce qui signifie parfois des performances délibérément basses -, où les propriétés utiles sont la résistance aux collisions et à la résistance avant image.

Grande question, Basil Ajith,

Voici ma perspective de ce qu'est un hash pour quelque chose sur lequel je travaille aujourd'hui.

*

Utilisez la somme de contrôle pour vérifier que l'archive a été conforme à la page de téléchargement.

*

Met le chapeau d'auditeur, je veux dire la robe sorcière

hash est une valeur / chaîne / quel que soit / label, assurez-vous qu'il est identique sur votre ordinateur que la source du téléchargement.

J'essaierai simplement d'ajouter un bref résumé de ce que disent les autres.

Fonction de hachage

Il existe un type spécial de fonctions appelées fonctions de hachage.

"SHA256 est une fonction de hachage bien connue qui est sécurisée par cryptographie"

Les trois applications principales sont * les tables de hachage, * les totaux de contrôle (vérifications de l'intégrité des données, par exemple dans les disques durs ou les protocoles ADSL), * et la cryptographie (diverses formes d'authentification cryptographique, notamment les signatures numériques et le stockage sécurisé des mots de passe).

Table de hachage

La table de hachage est une structure de données pour la recherche rapide. Il utilise les fonctions de hachage en interne, d'où son nom.

"Les bases de données utilisent des tables de hachage et des arbres de recherche en interne pour accélérer l'exécution des demandes de recherche"

Hacher

1. un type de données abstrait de dictionnaire

"Hash" est le nom officiel des dictionnaires intégrés à Perl. Ce sont des tables de hachage en interne, d'où le nom. "Ce sous-programme accepte un hachage comme premier argument". Ces jours peuvent être utilisés pour n’importe quel tableau associatif, pas nécessairement une table de hachage.

2. résultat de l'application d'une fonction de hachage à une entrée

"Les hachages MD5 des images .iso sont fournis pour vérifier leur intégrité après le téléchargement".