Suchen

Hash | Hashing

Redakteur: Gerald Viola

Unter Hashing versteht man die Konvertierung einer Zeichenkette in einen Wert mit einer typischerweise kürzeren festen Länge bzw. einen Schlüssel, der für die ursprüngliche Zeichenkette

Firma zum Thema

Unter Hashing versteht man die Konvertierung einer Zeichenkette in einen Wert mit einer typischerweise kürzeren festen Länge bzw. einen Schlüssel, der für die ursprüngliche Zeichenkette steht. Hashing wird zur Indizierung und zum Abrufen von Einträgen in einer Datenbank verwendet, weil die Suche anhand des kürzeren Hash-Schlüssels schneller als die Suche nach dem ursprünglichen Wert geht. Hashing wird auch in vielen Verschlüsselungsalgorithmen angewandt.

Als einfaches Beispiel für die Nutzung von Hashing in Datenbank, könnte eine Gruppe von Menschen wie folgt in einer Datenbank stehen:

Abernathy, Sara Epperdingle, Roscoe Moore, Wilfred Smith, David (und viele andere, alphabetische sortiert)

Jeder Name wäre der Datenbankschlüssel für die Daten der entsprechenden Person. Ein Datenbank-Suchmechanismus müsste zeichenweise alle Namen durchsuchen, bis der Treffer gefunden ist (oder alle anderen Einträge ausgeschlossen sind). Wenn jeder Name gehasht wird, könnte man (je nach Anzahl der Namen in der Datenbank) eine eindeutige, vierstellige Ziffer für jeden Namen generieren. Zum Beispiel:

7864 Abernathy, Sara 9802 Epperdingle, Roscoe 1990 Moore, Wilfred 8822 Smith, David (und so weiter)

Die Suche nach einem beliebigen Namen würde zunächst den Hash-Wert mithilfe der gleichen Hash-Funktion kalkulieren, die zum Speichern des Eintrags verwendet wurde, um dann Treffer für diesen Wert zu suchen. Es wäre generell viel schneller einen Treffer für eine vierstellige Zahl zu finden, wobei es für jede Stelle nur 10 Möglichkeiten gibt, als für einen Wert unbekannter Länge, bei dem es für jede Stelle 26 Möglichkeiten gibt.

Der Hashing-Algorithmus wird als Hash-Funktion bezeichnet (wobei dieser Begriff wahrscheinlich daher rührt, dass man sich das Hash-Ergebnis wie eine durcheinander gewürfelte Version des dargestellten Wertes vorstellen kann). Neben dem schnelleren Datenabruf wird Hashing auch für die Verschlüsselung und Entschlüsselung von digitalen Signaturen verwendet (die für die Authentifizierung der Absender und Empfänger einer Nachricht eingesetzt werden). Die digitale Signatur wird mithilfe der Hash-Funktion umgewandelt; daraufhin werden sowohl der Hash-Wert (auch Message-Digest genannt) und die Signatur als eigenständige Übertragungen zum Empfänger geschickt. Mit der gleichen Hash-Funktion wie der Absender, liest der Empfänger eine Message-Digest aus der Signatur und vergleichet diese mit dem eingehenden Message-Digest. Diese sollten gleich sein.

Die Hash-Funktion wird zum Indizieren des ursprünglichen Wertes oder Schlüssels und dann jedes Mal später angewandt, wenn die mit dem Wert oder Schlüssel zusammenhängenden Daten abzurufen sind. Daher ist Hashing immer eine irreversible Operation. Das Reverse-Engineering der Hash-Funktion durch Analyse der Hash-Werte ist überflüssig. In Wirklichkeit kann man eine ideale Hash-Funktion nicht durch eine solche Analyse erkennen. Eine gute Hash-Funktion generiert außerdem niemals den gleichen Hash-Wert für zwei unterschiedliche Eingaben. Wenn ja, spricht man von einer Kollision. Eine Hash-Funktion, die ein sehr niedriges Kollisionsrisiko mit sich bringt, ist vielleicht gerade noch akzeptabel.

Es folgen einige relativ einfache Hash-Funktionen, die benutzt worden sind:

  • Die Division/Restglied-Methode: Die Größe einiger Einträge in der Tabelle wird geschätzt. Diese Nummer wird dann als Divisor auf jeden ursprünglichen Wert oder Schlüssel angewandt, um einen Quotienten sowie ein Restglied zu ergeben. Das Restglied ist der Hash-Wert. (Da diese Methode dazu neigt, mehrere Kollisionen zu erzeugen, müsste ein Suchmechanismus eine Kollision erkennen und einen alternativen Suchmechanismus anbieten können.)
  • Faltung: Bei dieser Methode wird der ursprüngliche Wert (Zahlen in diesem Fall) in verschiedene Abschnitte geteilt; die Teile werden dann addiert und die letzten vier Stellen (oder eine beliebige andere Anzahl von Stellen, die auch funktioniert) wird als Hash-Wert oder Schlüssel genutzt.
  • Basiszahl-Transformation: Wo der Wert oder Schlüssel digital ist, kann die Zahlenbasis geändert werden, um eine andere Folge von Zahlen zu ergeben. (Beispielsweise kann man eine Dezimale in einen hexadezimalen numerischen Schlüssel umgewandelt werden.) Die Stellen höherer Ordnung könnten verworfen werden, um einen Hash-Wert mit einer Standardlänge zu ergeben.
  • Umstellung: Bei dieser Methode nimmt man den ursprünglichen Wert oder Schlüssel, beispielsweise Zahlen in den Position 3 bis 6, kehrt die Reihenfolge um und nutzt die Sequenz als Hashwert oder Schlüssel.

Eine Hash-Funktion, die für die Speicherung und das Abrufen in und von Datenbanken gut funktioniert, wird für kryptografische Zwecke oder zur Fehlererkennung unter Umständen nicht so gut funktionieren. In der Kryptografie gibt es einige bekannte Hash-Funktionen. Dazu gehören die Message-Digest-Hash-Funktionen MD2, MD4 und MD5 für die Konvertierung von digitalen Signaturen in kürzere Message-Digest genannte Werte sowie der Secure Hash-Algorithmus (SHA), ein Standardalgorithmus, der ein größeres (60-Bit) Message-Digest erstellt und damit MD4 ähnelt.

(ID:2020898)