Grundlagen

Hashfunktion

Eine Hashfunktion (auch Streuwertfunktion) ist eine Abbildung, die eine große Eingabemenge (die Schlüssel) auf eine kleinere Zielmenge (die Hashwerte) abbildet.
Eine „gute“ Hashfunktion liefert dabei für die (erwarteten) Eingabedaten Werte so, dass zwei unterschiedliche Eingaben auch zu unterschiedlichen Ausgabewerten führen.
Ein Hashwert wird deshalb auch als englisch Fingerprint bezeichnet, da er eine nahezu eindeutige Kennzeichnung einer größeren Datenmenge darstellt.

Eine sog. Kollision tritt dann auf, wenn unterschiedlichen Eingabedaten derselbe Hashwert zugeordnet wird.
Da die Menge der möglichen Hashwerte meist kleiner ist als die der möglichen Eingaben, sind solche Kollisionen dann prinzipiell unvermeidlich.
Eine gute Hashfunktion zeichnet sich dadurch aus, dass sie für die Eingaben, für die sie entworfen wurde, möglichst wenige Kollisionen erzeugt.

Hashfunktionen haben verschiedene Anwendungsfelder. Dabei lassen sich drei große Gebiete unterteilen:

Datenbanken
- In der Datenspeicherung kann ein Hashwert verwendet werden, um die Speicherstelle der angefragten Daten zu berechnen (z. B. Hashtabelle).
Prüfsummen
- Bei Prüfsummen verwendet man Hashwerte, um Übertragungsfehler zu erkennen.
Kryptologie
- In der Kryptologie werden spezielle kryptologische Hashfunktionen verwendet, bei denen zusätzlich gefordert wird, dass es praktisch unmöglich ist, Kollisionen absichtlich zu finden.

Eine kryptologische Hashfunktion oder kryptographische Hashfunktion ist eine spezielle Form der Hashfunktion, welche kollisionsresistent sein sollte und nach Definition immer eine Einwegfunktion ist.
Kryptologische Hashfunktionen werden in schlüssellose und schlüsselabhängige eingeteilt.

Bei der Merkle-Damgård-Konstruktion wird die eingegebene Nachricht M zuerst in Blöcke fester Länge geteilt
Der letzte Block wird mit zusätzlichen Bits aufgefüllt, so dass die Eingabelänge ein ganzzahliges Vielfaches der Blocklänge beträgt.
Die Funktion hat als Input einen Nachrichtenblock und den Wert des letzten Hashberechnung(ausser beim ersten Block).
Der Output entspricht dem Wert der neuen Hashberechnung.
Der Hashwert der gesamten Nachricht ist der Hashwert des letzten Blocks:

{\begin{aligned}H\left(0\right)&=IV\\H\left(i\right)&=f\left(M\left(i\right),H\left(i-1\right)\right),\qquad i=1,2,\dotsc ,t\\h\left(M\right)&=H(t)\end{aligned}}

IV bezeichnet einen festen Startwert (initial value).