Hashfunktionen Teil 2: Anwendungsmöglichkeiten und Beispiele
Nachdem der erste Teil des Artikels vorgestellt hat, was eine Hashfunktion genau ist, geht der zweite Teil nun auf die wichtigsten Anwendungsmöglichkeiten ein. Zum Abschluss stellt er ein Beispiel für eine häufig verwendete Hashfunktion vor.
Anwendungsmöglichkeiten für die Hashfunktion
In den folgenden Abschnitten erfahren Sie, welche Anwendungsmöglichkeiten eine Hashfunktion bietet. Diese Liste ist jedoch nicht vollständig. Darüber hinaus zeichnen sich Hashfunktionen noch durch viele weitere Einsatzbereiche aus.
Prüfsummen
Prüfsummen kommen bei der Übermittlung von digitalen Dokumenten zum Einsatz – beispielsweise über das Internet. Hierbei wird vor dem Versand eine Hashfunktion auf die gesamten Inhalte des Dokuments angewendet. Das Ergebnis wird als Prüfsumme bezeichnet und an das Ende des Dokuments angehängt. Der Empfänger kann nun die gleiche Hashfunktion auf die erhaltenen Inhalte anwenden. Stimmt das Ergebnis mit der Prüfsumme überein, ist davon auszugehen, dass das Dokument ohne Fehler übermittelt wurde. Stimmt der Wert nicht mit der Prüfsumme überein, bedeutet das, dass ein Fehler aufgetreten ist. In diesem Fall ist es notwendig, eine erneute Übermittlung anzufordern.
Datenbanken
Viele Datenbanksysteme verwenden Hashtabellen, um Werte in einer Datenbank zu suchen. Insbesondere bei umfangreichen Daten wäre eine Suche nach dem eigentlichen Wert sehr aufwendig. Deshalb erstellt die Software Hashtabellen. So kann das Verwaltungssystem bei der Suche nach einem Wert zunächst den Hashwert überprüfen. Erst wenn es dabei eine Übereinstimmung gefunden hat, ruft es die tatsächlichen Daten ab. Das kann die Zugriffszeiten stark reduzieren.
Passwortabfrage
Viele Systeme verwenden Hashfunktionen für die Speicherung von Passwörtern. Statt das Passwort als Klartext in der Datenbank abzulegen, nehmen sie lediglich dessen Hashwert auf. Wenn der Anwender dann sein Passwort eingibt, berechnet das System den Hashwert und vergleicht diesen mit dem Eintrag in der Passwort-Datenbank. Stimmen die Werte überein, wird der Zugriff genehmigt. Das erhöht die Sicherheit, da ein Angreifer, der Zugriff auf die Passwort-Datenbank erhält, aus diesen Informationen nicht auf die tatsächlichen Werte schließen kann. Dabei handelt es sich im Übrigen nicht um eine Verschlüsselung. Die Hashfunktion erlaubt es lediglich, aus dem Ausgangswert den Hash Wert zu berechnen. Umgekehrt ist es jedoch nicht möglich, aus dem Hash den Wert des ursprünglichen Eintrags zu ermitteln. Es ist daher keine Entschlüsselung des Codes möglich.
Hashfunktion für Blockchains
Von großer Bedeutung ist die Hashfunktion auch bei Blockchains. Hierbei wird der bestehenden Blockchain bei jeder neuen Transaktion ein weiterer Block angehängt. Um Manipulationen zu verhindern, enthält der neue Block stets den Hashwert der bestehenden Kette. Wenn es dabei zu einer Veränderung kommen sollte, wird dies sofort offensichtlich, da die Inhalte zu einem anderen Hashwert führen als demjenigen, der im nachfolgenden Block gespeichert ist.
Bildquelle:
https://upload.wikimedia.org/wikipedia/commons/thumb/5/55/Bitcoin_Block_Data.svg/320px-Bitcoin_Block_Data.svg.png
Bloomfilter
Ein Bloomfilter kommt zum Einsatz, um bestimmte Informationen aus großen Datenmengen effizient zu speichern. Dieser funktioniert ähnlich wie das oben vorgestellte Beispiel der Auswahl eines Schülers für einen Vortrag. Der Bloomfilter erlaubt es, ausgewählte Informationen zuverlässig zu überprüfen. Zu anderen Details lassen sich hingegen keine genauen Aussagen treffen. Im Gegensatz zum oben dargestellten Beispiel arbeitet der Bloomfilter jedoch normalerweise mit mehreren Hashfunktionen, um einen möglichst geringen Speicherplatz bei minimalem Informationsverlust zu gewährleisten.
Ein Beispiel für eine wichtige Hashfunktion
Ein Beispiel für eine recht einfache Hashfunktion, die aber in der Praxis von großer Bedeutung ist, ist die Divisionsrestfunktion. Diese kommt häufig für Hashtabellen zum Einsatz. Sie ist wie folgt definiert:
h(k) = k mod m
Der Begriff mod steht hierbei für das Modulo – also den Rest der ganzzahligen Division. Die Variable m bezeichnet die Größe der Hashtabelle. Die Variable k steht wiederum für den Wert eines Dokuments. Dabei wird für jedes einzelne Zeichen, das darin vorkommt, dessen ASCII-Code ermittelt. Diese Werte werden dann addiert. Aufgrund der unzähligen Kombinationsformen in längeren Dokumenten ist es sehr unwahrscheinlich, dass hierbei der gleiche Wert mehrfach auftritt. Über das Modulo wird die Wertemenge so begrenzt, dass sie perfekt zur Größe der verwendeten Hashtabelle passt.
Um dies zu zeigen, wollen wir den Hashwert für den Text „Hallo!“ berechnen. Dabei gehen wir von einer Tabellengröße von 32 aus. Zunächst suchen wir die ASCII-Werte für die einzelnen Zeichen heraus:
H 72
a 97
l 108
o 111
! 33
Daraus bilden wir nun die Summe, wobei wir den Wert für den Buchstaben l selbstverständlich doppelt berechnen müssen. Daraus ergibt sich die folgende Summe: 529. Wenn wir daraus das Modulo berechnen, erhalten wir den Wert 17. Daher wird das Dokument mit dem entsprechenden Inhalt an Position 17 der Hashtabelle eingetragen.
Fazit: Hashfunktionen spielen in der Informatik eine wichtige Rolle
Hashfunktionen haben in der Informatik eine große Bedeutung. Damit lassen sich Manipulationen oder Übertragungsfehler ermitteln. Außerdem ist es mit Hashfunktionen möglich, den Speicherplatz für eine Datenmenge stark zu reduzieren – allerdings nur unter Inkaufnahme eines erheblichen Informationsverlusts. Hashfunktionen erlauben es zwar nicht, den ursprünglichen Inhalt aus dem Wert zu berechnen. Wenn Sie diese passend auswählen, können Sie damit jedoch einzelne relevante Informationen zu den ursprünglichen Werten effizient speichern oder die Korrektheit des Inhalts eines Dokuments überprüfen.
