Was genau ist Hash?

38

Ich habe gehört, dass das Wort "Hash" in verschiedenen Kontexten (alle innerhalb der Computerwelt) mit unterschiedlichen Bedeutungen verwendet wird. In dem Buch Learn Python the Hard Way heißt es beispielsweise im Kapitel über Wörterbücher : "Python nennt sie" Diktate. "Andere Sprachen nennen sie" Hashes "." Sind es also Hashes-Wörterbücher? "

Die andere gebräuchliche Verwendung des Wortes bezieht sich auf die Verschlüsselung. Ich habe auch Leute gehört (& gelesen), die das Wort "Hash" als eine bestimmte Funktion innerhalb der High-Level-Programmierung verwendeten.

Also, was genau ist das?

Kann irgendjemand (mit der Zeit und wer kennt sich aus) freundlich erklären, warum "Hash (oder Hashes)" so eine Sache sind?

gracedlamb
quelle
8
Wikipedia bietet detaillierte Artikel zu Hash-Tabellen und kryptografischen Hash-Funktionen . Wonach suchst du, nicht in denen?
David Richerby
1
Sie listen bereits mehrere Verwendungen des Begriffs "Hash" auf, und es gibt noch mehr. Also, wie genau erwarten Sie eine Antwort auf "Was genau ist das?"
Raphael
4
"Hashes" in diesem Sinne ist eine Abkürzung für "Hash-Tabellen", z. B. Tabellen, die Hashes zur Organisation von Schlüsseln verwenden. Es ist so, als würde man Benzin "Gas" nennen - Sie erwarten nicht, dass "Gas" gasförmig ist oder dass Gase benzinähnliche Eigenschaften haben, oder? Dies passiert die ganze Zeit mit der Sprache - insbesondere Kürzungen sind sehr häufige Quellen für Wortüberschneidungen.
Luaan
1
"Es gibt keine Definition für dieses Wort - niemand weiß, was Hash ist." - The Devil's Dictionary
jpmc26
In Bezug auf die verschiedenen Gedankengänge, was eine Hash-Funktion ist: Eine Hash-Funktion ist nur eine Funktion mit einer Reihe von Eigenschaften, aber es ist nicht die Definition, die relevant ist, sondern die Eigenschaften, die wir haben möchten - die wir daraus ableiten, wie wir wollen die funktion nutzen - das ist relevant. Da wir damit schnell auf Inhalte zugreifen möchten, möchten wir, dass diese effizient berechenbar sind. Da wir keinen unendlichen Platz zur Verfügung haben, wollen wir, dass die Codomäne endlich ist. Da wir Kollisionen so gut wie möglich vermeiden wollen, möchten wir, dass die Hash-Funktion die Hashes gleichmäßig verteilt.
G. Bach

Antworten:

44

Der Wikipedia-Artikel über Hash-Funktionen ist sehr gut, aber ich werde hier mein Einverständnis geben.


Was ist ein Hash?

"Hash" ist wirklich ein weiter Begriff mit unterschiedlichen formalen Bedeutungen in unterschiedlichen Kontexten. Es gibt keine perfekte Antwort auf Ihre Frage. Ich werde das allgemeine Grundkonzept erläutern und einige der gebräuchlichsten Verwendungen des Begriffs erwähnen.

Ein "Hash" ist eine Funktion , die als Hash-Funktion bezeichnet wird und als Eingabeobjekte eine Zeichenfolge oder Zahl ausgibt. Die Eingabeobjekte sind normalerweise Mitglieder grundlegender Datentypen wie Zeichenfolgen, Ganzzahlen oder größerer Datentypen, die aus anderen Objekten wie benutzerdefinierten Strukturen bestehen. Die Ausgabe ist normalerweise eine Zahl oder eine Zeichenfolge. Das Substantiv "Hash" bezieht sich oft auf diese Ausgabe. Das Verb "Hash" bedeutet oft "eine Hash-Funktion anwenden". Die wichtigsten Eigenschaften, die eine Hash-Funktion haben sollte, sind:h

  1. Es sollte einfach zu berechnen sein und
  2. Die Ausgänge sollten relativ klein sein.

Beispiel:

Angenommen, wir möchten Hash-Zahlen im Bereich von 0 bis 999.999.999 bis zu Zahlen zwischen 0 und 99 verwenden. Eine einfache Hash-Funktion kann .h(x)=xmod100

Gemeinsame zusätzliche Eigenschaften:

Je nach Anwendungsfall möchten wir, dass die Hash-Funktion zusätzliche Eigenschaften erfüllt. Hier sind einige übliche zusätzliche Eigenschaften:

  1. Einheitlichkeit : Oft möchten wir, dass die Hashes von Objekten unterschiedlich sind. Außerdem möchten wir, dass die Hashes "ausgebreitet" werden. Wenn ich einige Objekte in 100 Buckets hacken möchte (die Ausgabe meiner Hash-Funktion ist also eine Zahl von 0-99), dann hoffe ich normalerweise, dass ungefähr 1/100 Objekte in Bucket 0 landen, ungefähr 1/100 in Eimer 1 und so weiter.

  2. Widerstand gegen kryptografische Kollisionen : Manchmal wird dies sogar noch weiter vorangetrieben. In der Kryptografie möchte ich möglicherweise eine Hash-Funktion, sodass es für einen Gegner rechnerisch schwierig ist, zwei verschiedene Eingänge zu finden, die demselben Ausgang zugeordnet sind.

  3. Komprimierung : Ich möchte häufig willkürlich große Eingaben in eine Ausgabe mit konstanter Größe oder eine feste Anzahl von Buckets zerlegen.

  4. Determinismus : Möglicherweise möchte ich eine Hash-Funktion, deren Ausgabe sich zwischen den Durchläufen nicht ändert, dh die Ausgabe der Hash-Funktion für dasselbe Objekt bleibt immer gleich. Dies scheint im Widerspruch zur obigen Gleichförmigkeit zu stehen, aber eine Lösung besteht darin, die Hash-Funktion zufällig einmal auszuwählen und nicht zwischen den Durchläufen zu ändern.


Einige Anwendungen

Eine häufige Anwendung sind Datenstrukturen wie eine Hash-Tabelle, mit denen Wörterbücher implementiert werden können. Hier ordnen Sie Speicher zu, beispielsweise 100 "Buckets". Wenn Sie dann aufgefordert werden, ein (Schlüssel-, Wert-) Paar im Wörterbuch zu speichern, haben Sie den Schlüssel in eine Zahl von 0 bis 99 gehasht und das Paar im entsprechenden Bucket gespeichert. Wenn Sie dann aufgefordert werden, einen Schlüssel nachzuschlagen, wird der Schlüssel mit derselben Hash-Funktion in eine Zahl von 0 bis 99 gehasht und in diesem Bucket überprüft, ob sich der Schlüssel dort befindet. In diesem Fall geben Sie den Wert zurück.

Beachten Sie, dass Sie Wörterbücher auch auf andere Weise implementieren können, z. B. mit einem binären Suchbaum (wenn Ihre Objekte vergleichbar sind).

Eine weitere praktische Anwendung sind Prüfsummen, mit denen überprüft werden kann, ob zwei Dateien identisch sind (z. B. wurde die Datei gegenüber der vorherigen Version nicht beschädigt). Da es sehr unwahrscheinlich ist, dass Hash-Funktionen zwei Eingaben derselben Ausgabe zuordnen, berechnen und speichern Sie einen Hash der ersten Datei, der normalerweise als Zeichenfolge dargestellt wird. Dieser Hash ist sehr klein, vielleicht nur ein paar Dutzend ASCII-Zeichen. Wenn Sie dann die zweite Datei erhalten, prüfen Sie, ob die Ausgabe identisch ist. In diesem Fall handelt es sich mit ziemlicher Sicherheit Byte für Byte um dieselbe Datei.

Eine andere Anwendung ist die Kryptographie, bei der es schwierig sein sollte, diese Hashes zu "invertieren" - das heißt, angesichts der Ausgabe und der Hash-Funktion sollte es schwierig sein, die Eingaben zu ermitteln, die zu dieser Ausgabe geführt haben. Eine Verwendung davon ist für Kennwörter: Anstatt das Kennwort selbst zu speichern, speichern Sie einen kryptografischen Hash des Kennworts (möglicherweise mit einigen anderen Bestandteilen). Wenn ein Benutzer ein Kennwort eingibt, berechnen Sie seinen Hash und überprüfen, ob er mit dem richtigen Hash übereinstimmt. Wenn ja, sagen Sie, dass das Passwort korrekt ist. (Jetzt hat auch jemand, der den auf dem Server gespeicherten Hash nachsehen und herausfinden kann, nicht so leicht die Möglichkeit, sich als Benutzer auszugeben.) Bei dieser Anwendung ist die Ausgabe möglicherweise genauso lang oder länger als die Eingabe, da Die Eingabe ist so kurz.

usul
quelle
1
Nette Erklärung, aber ich bin nicht einverstanden mit "sehr unwahrscheinlich". Siehe: programmers.stackexchange.com/questions/49550/... : Kollision tun auftreten, und manchmal überraschend oft.
Olivier Dulac
8
Beachten Sie auch, dass der Begriff "Hash" im Zusammenhang mit der Verschlüsselung sehr stark eine "Einweg" -Operation impliziert, die in der Praxis nicht einfach rückgängig gemacht werden kann. Wenn es leicht rückgängig gemacht werden kann, nennt man es "Verschlüsselung". Aus diesem Grund werden Sie von den Mitarbeitern von Security.SE angewiesen, die Passwörter Ihrer Kunden immer zu hacken und niemals zu verschlüsseln.
Ixrec
4
Ein Hash, der sich nicht "ausbreitet", ist immer noch ein Hash, nur vielleicht nicht sehr gut für Ihre Anwendung.
Hören Sie auf, Monica am
1
Klar, das sind alles gute Punkte.
usul
10

Eine Hash-Funktion ist eine Funktion, die eine Eingabe entgegennimmt und einen Wert fester Größe erzeugt. Beispielsweise könnten Sie eine Hash-Funktion haben stringHash, die eine stringbeliebige Länge akzeptiert und eine 32-Bit-Ganzzahl erzeugt.

Typischerweise ist es richtig zu sagen, dass die Ausgabe einer Hash-Funktion ein Hash ist (auch bekannt als Hash-Wert oder Hash-Summe). Manchmal wird die Funktion jedoch als Hash bezeichnet . Dies ist technisch inkorrekt, wird jedoch normalerweise übersehen, da allgemein (im Kontext) davon ausgegangen wird, dass die Person die Hash-Funktion gemeint hat .

Die typische Verwendung einer Hash-Funktion ist die Implementierung einer Hash-Tabelle . Eine Hash-Tabelle ist eine Datenstruktur, die Werte mit anderen Werten verknüpft, die normalerweise als Schlüssel bezeichnet werden. Hierzu wird eine Hash-Funktion für den Schlüssel verwendet, um einen Hash-Wert mit fester Größe zu erstellen, mit dem die gespeicherten Daten schnell nachgeschlagen werden können. Ich werde nicht im Detail darauf eingehen, wie es das macht, aber die wichtigste Tatsache hier ist, dass es eine Hash-Tabelle heißt, weil es auf einer Hash-Funktion beruht , um Hash-Werte (Hashes) zu erzeugen .

Hier kommt ein Teil der Verwirrung ins Spiel, weil einige Leute (wieder etwas falsch) eine Hash-Tabelle als Hash bezeichnen. Wie in anderen Antworten angegeben, bezieht sich die Implementierung einer Hash-Tabelle in einer bestimmten Sprache manchmal auf die Hash-Tabelle als Hash (insbesondere Perl tut dies, obwohl ich erwarte, dass dies auch in anderen Sprachen der Fall ist). Andere Sprachen beziehen sich auf die Implementierung einer Hash-Tabelle als Wörterbuch. Python ist eine dieser Sprachen, aber aufgrund der Verankerung in der jeweiligen Sprache verkürzen viele Python-Benutzer den Begriff Wörterbuch, um ihn zu diktieren.

Während sich die korrekte Verwendung des Begriffs Hash auf den von einer Hash-Funktion erzeugten Hash-Wert bezieht, wird der Begriff manchmal auch informell verwendet, um auf Hash-Funktionen und Hash-Tabellen zu verweisen , was zu Verwirrung führt.

Pharap
quelle
2
Ich bin nicht sicher, ob es wirklich falsch ist , eine Hash-Tabelle oder eine Hash-Funktion als "Hash" zu bezeichnen (es scheint nicht schlimmer zu sein, als beispielsweise "Washington" für "die Vereinigten Staaten" zu verwenden, wie in " Washington begrüßte Chinas Erklärung vorsichtig "). Aber ich stimme zu, dass es verwirrend ist und es gut ist, dass Sie in Ihrer Antwort darüber sehr klar sind.
David Richerby
1
@DavidRicherby Formal würde ich sagen, dass die Arbeit "Hash" undefiniert ist. "Hash-Funktion", "Hash-Wert", "Hash-Tabelle" und "Hash einer Zeichenfolge" haben alle präzise mathematische Definitionen, aber "Hash" ist mehrdeutig. Ebenso weiß ich, was Sie mit "Washington" meinen, aber Ihr Satz ist immer noch sinnvoll, wenn ich "Washington" so interpretiere, dass er "George Washington" oder "Denzel Washington" bedeutet, und nicht "Die Stadt Washington", was sehr informell ist an die Bundesregierung verweisen. Fazit: Achten Sie darauf, "zu wissen, was Sie meinen" nicht für eine strenge formale Definition zu verwechseln.
Mike Ounsworth
@DavidRicherby Das ist keine wirklich äquivalente Analogie. Die Unrichtigkeit ist umstritten, die Informalität jedoch nicht.
Pharap
2

Eine Hash-Funktion ist im Großen und Ganzen jede Funktion, bei der das Bild kleiner als die Domäne ist . Die Ausgabe einer solchen Funktion f(x)kann als "der Hash von x" bezeichnet werden.

In der Informatik begegnen wir normalerweise zwei Anwendungen von Hash-Funktionen.

Die erste Möglichkeit betrifft Datenstrukturen wie Hash-Tabellen , in denen die Schlüsseldomäne (z. B. 32-Bit-Ganzzahlen oder Zeichenfolgen beliebiger Länge) einem Array-Index (z. B. Ganzzahl zwischen 0 und 100) zugeordnet werden soll. Ziel ist es, die Leistung der Datenstruktur zu maximieren. Eigenschaften der Hash-Funktion, die typischerweise wünschenswert sind, sind Einfachheit und gleichmäßige Ausgabeverteilung.

Perl nennt seinen eingebauten assoziativen Array-Typ "Hash" , was hier für Verwirrung zu sorgen scheint. Ich kenne keine anderen Sprachen, die dies tun. Die Datenstruktur kann lose als Hash-Funktion selbst gesehen werden (wobei die Domäne der aktuelle Satz von Schlüsseln ist), ist aber auch als Hash-Tabelle implementiert.

Die zweite dient der Kryptografie : Nachrichtenauthentifizierung, Kennwort- / Signaturüberprüfung usw. Die Domäne besteht normalerweise aus beliebigen Byte-Zeichenfolgen. Hier geht es um Sicherheit - was manchmal eine absichtlich geringe Leistung bedeutet -, wo nützliche Eigenschaften Kollision und Beständigkeit vor dem Bild sind.

Hör auf, Monica zu schaden
quelle
Und ich habe immer noch Einwände gegen Ihren ersten Satz, da beim Hashing von 32-stelligen Passwörtern mit SHA-512 der Eingabebereich tatsächlich kleiner als der Ausgabebereich ist. Wenn Hash-Funktionen miteinander verkettet werden, sind Domäne und Bereich identisch. Die Größe des Eingabebereichs spielt keine Rolle. Die Antwort von Pharap hat die richtige Definition: "Eine Hash-Funktion ist jede Funktion mit einer Ausgabe mit fester Länge". Das ist es, das ist alles, was du brauchst, alle anderen Bedingungen, von denen du sprichst, sind davon impliziert.
Mike Ounsworth
@MikeOunsworth, aber die Domäne von SHA-512 sind binäre Zeichenfolgen beliebiger Länge. Ich nehme an, ich könnte Pharaps-Formulierungen stehlen, aber ich habe versucht, die Bedingungen zum Nutzen des OP explizit zu machen. Ich bin mir nicht sicher, ob "von fester Länge" notwendig oder eindeutig definiert ist.
Hören Sie auf, Monica am
@OrangeDog Ok, aber ich kann SHA-512 in eine aufgerufene Funktion einschließen, MikesHash()die Zeichenfolgen der Länge 12 akzeptiert und sie an SHA-512 übergibt und die Ausgabe zurückgibt. Ich bin mir ziemlich sicher, dass dies MikesHash()immer noch der Definition einer Hash-Funktion entspricht. (In der Praxis haben Sie recht, die von uns verwendeten Hash-Funktionen akzeptieren Eingaben beliebiger Länge, aber ich glaube nicht, dass etwas nicht zu einer Hash-Funktion wird, wenn dies nicht der Fall ist.)
Mike Ounsworth
@ MikeOunsworth Ebenso kann ich es so umbrechen, dass die Ausgabe abgeschnitten oder aufgefüllt wird, wenn die Msb eine Eins ist. Die Ausgabe ist nicht mehr von fester Länge, aber ist es immer noch eine Hash-Funktion?
Hören Sie auf, Monica am
@OrangeDog würde ich nein sagen. Mein aller Punkt war, dass eine Hash-Funktion auf eine Ausgabe mit fester Größe abgebildet werden muss, aber die Eingabegröße ist irrelevant. Wir sind sehr weit vom Thema entfernt. Ihre Antwort hat gute Sachen drin, seien Sie nur vorsichtig mit Ihrer formalen Definition ;-)
Mike Ounsworth
0

Große Frage Basil Ajith,

Hier ist meine Perspektive, was ein Hash für etwas ist, an dem ich heute arbeite.

*

Verwenden Sie die Prüfsumme, um sicherzustellen, dass der Tarball mit der Download-Seite übereinstimmt

*

Bildbeschreibung hier eingeben Zieht den Auditorenhut an, ich meine Zaubererrobe

Hash ist ein Wert / string / whatever / label. Stellen Sie sicher, dass er auf Ihrem Computer mit der Quelle eines Downloads identisch ist.

Jesse MacDougall
quelle
3
Dies ist nur eine Verwendung für einen Hash. Es gibt viele andere Verwendungen.
Yuval Filmus
Willkommen auf der Seite! Die Verwendung von kryptografischen Hashes als Prüfsummen wird bereits von der akzeptierten Antwort abgedeckt, sodass Ihre Antwort nichts Neues hinzufügt und dabei viel Platz auf dem Bildschirm beansprucht.
David Richerby
-1

Ich werde versuchen, nur eine kurze Zusammenfassung dessen hinzuzufügen, was andere sagen.

Hash-Funktion

Es gibt eine spezielle Art von Funktionen, die als Hash-Funktionen bezeichnet werden.

"SHA256 ist eine bekannte Hash-Funktion, die kryptografisch sicher ist"

Drei Hauptanwendungen sind * Hash-Tabellen, * Prüfsummen (Datenintegritätsprüfungen, z. B. in Festplatten oder ADSL-Protokollen) * und Kryptografie (verschiedene Formen der kryptografischen Authentifizierung, einschließlich, aber nicht beschränkt auf digitale Signaturen und sichere Speicherung von Passwörtern).

Hash-tabelle

Hash-Tabelle ist eine Datenstruktur für die schnelle Suche. Intern werden Hash-Funktionen verwendet, daher der Name.

"Datenbanken verwenden Hash-Tabellen und Suchbäume intern, um die Ausführung von Suchanfragen zu beschleunigen"

Hash

  1. Ein abstrakter Dictionary-Datentyp

"Hash" ist der offizielle Name der in Perl integrierten Wörterbücher. Sie sind intern Hash-Tabellen, daher der Name. Msgstr "Diese Unterroutine akzeptiert einen Hash als erstes Argument". Diese Tage können für jedes assoziative Array verwendet werden, nicht unbedingt für eine Hash-Tabelle.

  1. Ergebnis der Anwendung einer Hash-Funktion auf eine Eingabe

Msgstr "MD5 - Hashes der .iso - Images werden bereitgestellt, um ihre Integrität nach dem Download zu überprüfen".

nponeccop
quelle