Unter Hashverfahren versteht man Such- und Speicherverfahren.
Pfiffigerweise werden die Speicheradressen aus den Daten (Schlüsseln) selbst berechnet, so daß aufwendige Suchverfahren entfallen können. Die Suchzeiten sind trotzdem erstaunlich gut: bei 90%-iger Ausnutzung des Speichers muß im Durchschnitt selbst mit der schlechtesten Methode mit nur 2,56 Zugriffen (theoretisch) bzw. 5,5 Zugriffen (praktisch) gerechnet werden, um einen Datensatz bzw. eine freie Speicheradresse zu finden.
Das Kernstück des Hashings ist die Hashfunktion. Man definiert eine Hashfunktion H als Abbildung von der Menge K aller Schlüssel in die Menge A der Adressen des Adreßraumes:
H : K ---> A
Dabei muß auf K eine Ordnungsrelation definiert sein; im Normalfall stellt das aber keine Schwierigkeit dar.
Soll nun ein Schlüssel s in eine Datenbank eingetragen werden, so berechnet man mit Hilfe von H die entsprechende Speicheradresse H(k) für den Schlüssel k . Es liegt nahe, daß in der Hashfunktion H die Größe des benutzten Speicherbereichs eingehen muß, da sonst Adressen berechnet werden könnten, die außerhalb des benutzten Adreßbereichs liegen. Wenn als Adressen die Zahlen 0 bis n-1 zur Verfügung stehen, ist die naheliegendste Version einer Hashfunktion daher
H(k) = ord (k) MOD n
Damit liegen die Adressen alle gleichverteilt im Adreßraum. In diesem Falle ist H sehr einfach zu berechnen, vor allem, wenn n eine Potenz von 2 ist. Einen äußerst ungünstigen Fall stellen Schlüssel aus Buchstabenfolgen dar; Worte, die sich am Anfang nur in wenigen Stellen unterscheiden, werden mit hoher Wahrscheinlichkeit auf gleiche Adressen abgebildet. In diesem Falle sollte für n eine Primzahl gewählt werden. Desweiteren nehme man nicht die Anfangsbuchstaben, sondern Zeichen aus der Mitte bzw. vom Ende der Zeichenketten; das liefert bessere Ergebnisse.
Ein Beispiel:
Als Ordnungsfunktion wird die ASCII-Tabelle benutzt. Für den Schlüssel 'e' berechnet sich dann die Adresse:
H('e') = ord ('e') MOD 5
= 101 MOD 5 = 1
Der Schlüssel 'e' wird also unter der Speicheradresse 1 abgelegt.
Im allgemeinen sind die Daten im Adreßraum an kein festes Muster gebunden. Das ist nicht nur tolerabel, sondern man wünscht geradezu, daß die Verteilung möglichst zufällig und damit gleichmäßig geschieht. Das versucht man durch Hashfunktionen zu erreichen, die stochastisch arbeiten. Um mit Niklaus Wirth (dem Vater von PASCAL) zu sprechen:
Spätestens hier wird klar, daß ein grundsätzliches Problem zu erörtern ist. Die Menge der möglichen Schlüsselwerte ist in der Regel im Vergleich zur Menge der vorhandenen Speicheradressen sehr groß. Die Funktion H ist also nicht eindeutig. In Datenbankanwendungen folgt daraus das Problem, wie man freie Speicherplätze findet. Bei kryptologischen Anwendungen ist es wichtiger, daß einerseits keine zwei Mengen von Eingabedaten denselben Tabellenzustand erzeugen und andrerseits, daß keine Menge von Eingabedaten aus dem zugehörigen Tabellenzustand zurückgewonnen werden kann. In diesem Fall spricht man von Einweg-Hashfunktionen (oneway hashfunction).
Die Nachteile solchen Vorgehens ergeben sich aus dem gerade Erarbeiteten: Zunächst ist die Größe des Adreßraumes statisch, sie muß vorher festgelegt werden. Vor allem bei der Anwendung in Datenbanken setzt das voraus, daß man von Anfang an weiß, wieviele Datensätze bearbeitet werden. Die Erfahrung lehrt, daß dies in den meisten Fällen nicht möglich ist. Zudem darf der Adreßraum nicht zu 100% belegt werden, da sich die Suchzeiten bei hoher Auslastung schnell signifikant verschlechtern. Eine Belegung von maximal 80% gilt als Obergrenze.
Der nächste Punkt ist, daß die Daten in völlig ungeordneter Form vorliegen. Das darf ohne weitere Vorbereitung auch nicht geändert werden. Andernfalls kann kaum ein Eintrag mehr gefunden werden, da die meisten sonst nicht mehr an den Adressen zu finden sind, die ihnen durch die Hashfunktion H zugewiesen wurden. Schließlich ist es aufwendig, Datensätze zu löschen, wie wir gleich sehen werden.
Die große Frage, welche Funktionen zum Hashing eingesetzt werden können, ist noch aufwendiger zu beantworten. Es gibt mehr oder weniger komplizierte Verfahren zum Finden von Hashfunktionen. Und ob die gefundene Funktion dann auch noch den strengen Anforderungen standhält, ist ebenfalls nicht so einfach nachprüfbar; selbst bei den anerkannten Funktionen (z.B. MD4, MD5) liest man stets den Hinweis auf Abhängigkeit von weiteren Analysen [16].
Wenn man das Hashverfahren zur Herstellung einer Datenbank benutzt, sind die ersten Fragen, die man stellt: Können zwei Schlüssel auf dieselbe Adresse fallen? Und wenn ja, wie reagiert man in diesem Falle?
Beinahe selbstverständlich ist die Antwort auf die erste Frage: Ja. In einer Datenbank ist das natürlich fatal, und so benötigt man Verfahren, die solche Kollisionen zu behandeln in der Lage sind. Verschiedene Methoden sind in der Literatur beschrieben. Beispielsweise löst man das Kollisionsproblem durch "direkte Verkettung" [13]. Man schreibt alle Eintragungen k mit identischem H(k) in eine verkettete Liste. Die kann entweder im benutzten Adreßraum direkt liegen, oder es wird ein "Überlaufbereich" dafür angelegt. Obwohl sehr effektiv, müssen in diesem Falle zusätzliche Listen geführt werden und jeder Eintrag muß Platz für einen Zeiger aufweisen, der in den entsprechenden Überlaufbereich zeigt, in dem die kollidierenden Elemente gesammelt werden.
Eine andere Lösung ist die "offene Adressierung" [13]. Ist eine Adresse besetzt und droht dadurch eine Kollision, wird einfach der restliche Adreßraum nach freien Plätzen abgesucht (Die Eigenschaft "frei" muß definiert und der Adreßraum damit initialisiert werden). Der Suchalgorithmus sieht im Prinzip so aus (Pseudo-PASCAL):
h := H(k) ;
i := 0 ;
repeat
if a [h].key = k then
"element gefunden"
else
if a [h].key = "frei" then
"element nicht in der tabelle"
else
begin
i := i + 1;
h := H(k) + G(i);
end
until "gefunden, nicht in tabelle oder tabelle voll";
Die Funktion G ist im einfachsten Falle die Identität:
G(i) = i
Hierbei kann es jedoch zur "Clusterbildung" kommen - verschiedene Einträge ballen sich um einige wenige Adressen herum. Doch das will man ja gerade verhindern. Beispielsweise sucht man sich eine Funktion G, die ihrerseits wieder Werte ergibt, die sich gleichmäßig auf den Adreßraum verteilen. Weil das zu aufwendig werden kann, werden in der Praxis Kompromisse gesucht, die einfach (also schnell) zu berechnen sind (wie der Fall der Identität) und gleichzeitig eine annehmbare Verteilung erreichen. Ein solcher Kompromiß ist die quadratische Funktion
G(i) = i * i (quadratisches Sondieren)
Natürlich werden bei dieser Methode nicht alle Plätze durchsucht, aber man kann durch die Wahl der Größe n des benutzten Adreßraumes (dabei ist n eine Primzahl) dafür sorgen, daß mindestens n/2 Adressen durchsucht werden.
Wie oben schon angedeutet, können Tabellen, die mit Hashverfahren aufgebaut wurden, nicht (direkt) sortiert werden. Das wäre beispielsweise aber die Voraussetzung für eine alphabetische Ausgabe. Wenn trotzdem Sortieren erforderlich ist, kann man jedoch mit Hilfe von zusätzlichen Indextabellen, wie sie ja auch durchaus üblich sind, diesen Nachteil schnell ausgleichen.
Sehr schwierig wird es, wenn Einträge gelöscht werden sollen. Man darf nicht einfach Einträge löschen, d.h. die entsprechenden Adressen wieder als frei markieren, denn sonst funktioniert der Suchvorgang nicht mehr in allen Fällen - ein freier Speicherplatz war ja eines der Abbruchkriterien (s.o.). Wird ein Datensatz wirklich gelöscht, so bricht die Suche eventuell schon an dieser Stelle ab, obwohl weitergesucht werden müßte.
Auch hier kann man relativ leicht abhelfen, indem man in jedem Eintrag eine zusätzliche Eigenschaft einbaut, in die der Status "gelöscht" oder "aktiv" eingetragen wird (logisches Löschen), was jedoch zusätzlichen Speicherplatz kostet. Wenn die Anzahl der als gelöscht markierten Datensätze einen gewissen Prozentsatz übersteigt, kann der aktive Anteil in eine leere Tabelle kopiert werden (natürlich unter Benutzung derselben Hashfunktion).
Die Tatsache, daß mit dem Hashverfahren aufgebaute Tabellen stochastisch verteilt sind, möchte man sich in der Kryptologie gezielt zunutze machen. Bei kryptologischen Anwendungen möchte man ja gerade die Quellinformation (Klartext) verschleiern, damit Unbefugte keine Möglichkeit haben, Manipulationen vorzunehmen.
Um einen Fingerabdruck herzustellen, wird wie folgt vorgegangen:
Die Hashfunktion muß die schon angedeuteten Eigenschaften besitzen:
Natürlich ist es äußerst schwierig, gute Hashfunktionen zu finden. Vor allem Punkt 1 ist praktisch nicht zu erfüllen, deswegen muß die Wahrscheinlichkeit, daß das doch vorkommen kann, äußerst klein sein. Vor allem Hashfunktionen für kryptologische Anwendungen müssen solchen außerordentlichen strengen Prüfungen standhalten, da sie sonst wertlos sind.
Die ideale Hashfunktion vermeidet jegliche Kollision. Jeder Schlüssel bildet dann auf eine andere Adresse ab. Da das die Bijektivität oder zumindest die Injektivität der Funktion H bedeutet, setzt das notwendig voraus, daß die Anzahl der benutzten Daten vor der Festlegung der Hashfunktion feststehen und es mindestens so viele Adressen wie Schlüssel gibt - eine unrealistische Annahme. Solche Hashfunktionen werden auch "perfekt" genannt.
Man gibt sich deswegen schon mit "minimal perfekten Hashfunktionen" (MPHF) zufrieden. Es handelt sich dabei um Hashfunktionen, die mit einer gewissen Wahrscheinlichkeit perfekt sind. Knuth hat 1973 gezeigt, daß es nur eine perfekte Hashfunktion unter 10 Millionen gibt, welche die 31 häufigsten Worte der englischen Sprache auf 41 Adressen verteilt.
Man kann zeigen, daß es MPHFen gibt (Jeschke, 1981):
Dann ist der folgende Algorithmus eine MPHF:
for ( i = 1; i <: m; i++ ) A [k[i]] = i
Das Array A definiert H, zugelassene Schlüssel werden in die Menge der Adressen {0,.., m - 1} abgebildet, andere Schlüssel auf "ERROR". Dadurch wird eine MPHF definiert - auch wenn das Array A fast leer ist (bei m << N ). Praktisch ist diese Erkenntnis jedoch von keinerlei Nutzen, denn es wird zuviel Platz vergeudet.
Es gibt verschiedene Verfahren, MPFHs zu berechnen, von denen die einfachste darin besteht, eine Klasse von Funktionen auszuwählen, die bekanntermaßen eine Anzahl von MPFHs enthält und dann nach diesen zu suchen, indem man den Parametern, die die Klasse definieren, verschiedene Werte zuweist. Weitere Einzelheiten sowie die Beschreibung eines kompletten Algorithmus zur Berechnung der MPFH mit C-Sourcecode kann man in [14] nachlesen.
Von den in der Kryptologie bekanntesten Funktionen seien hier nur zwei genannt: der "Secure Hash Standard", den die NIST 1992 definiert hat, und MD5, die von Ron Rivest (einem der Entwickler des RSA-Verfahrens) kurze Zeit später als RFC 1321 (Request for Comments) definiert und im Usenet/Internet publiziert wurde (s. C-Quelltext) [D].
MD5 hat zudem weite Verbreitung gefunden, da es unter anderem in