Direkt zur Hauptnavigation springen Direkt zum Inhalt springen Jump to sub navigation

Bessere Hash-Funktionen

Bessere Hash-Funktionen

Bessere Hash-Funktionen

Kollisionen

Die Einwegfunktion  c(m) = 17*(w1)2 + 11*(w2)2 + 21*(w3)2 + 4*(w4)2 für unsere vier-Buchstaben-langen Zeichenketten ist offensichtlich nicht geeignet für den "Münzwurf per E-Mail". Das liegt daran, dass es mehrere unterschiedliche Zeichenketten gibt, die den gleichen Code ergeben. So etwas nennt man eine Kollision.

Gute Hash-Funktionen haben möglichst keine Kollisionen und "streuen" ihre Werte unregelmäßig im ganzen Wertebereich.


Eine bessere Hash-Funktion

Von dem berühmten Informatiker Donald E. Knuth stammt die Idee zu einer wirklich guten Hash-Funktion. Für unser Beispiel würde man sie so bilden:

cn(m) = 26*(26*(26*w1 + w2) + w3) + w4) mod n

Dabei muss allerdings der Modul n "gut" gewählt werden, günstig sind größere Primzahlen.

Wie können Alice und Bob mit dieser Funktion ihre Entscheidung treffen?



MD5-Hash

Hashing - 34. Algorithmus der Woche

http://de.wikipedia.org/wiki/Message-Digest_Algorithm_5

Redaktionell verantwortlich: