Bessere Hash-Funktionen

Kollisionen

Die Einwegfunktion  c(m) = 17*(w₁)² + 11*(w₂)² + 21*(w₃)² + 4*(w₄)² 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:

c_n(m) = 26*(26*(26*w₁ + w₂) + w₃) + w₄) 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