Für die Berechnung einer digitalen Signatur für ein beliebig langes Dokument m wird das Dokument zunächst mithilfe einer Hashfunktion h auf wenige Bits (z.B. 160) "eingedampft". Der Hashwert h(m) stellt eine Art "Fingerabdruck" des Dokuments dar, mit der gewünschten Eigenschaft, dass unterschiedliche Dokumente auch unterschiedliche Fingerabdrücke haben. Theoretisch ist dies natürlich nicht zu gewährleisten, denn es gibt unendlich viele Bitfolgen beliebiger Länge (Dokumente), aber nur 2160 Bitfolgen der Länge 160. In der Praxis aber gibt es sehr viel weniger als 2160 tatsächliche Dokumente, sodass es unwahrscheinlich ist, dass zwei tatsächliche Dokumente denselben Fingerabdruck haben.
Sei A ein Alphabet Sei ferner A* die Menge aller Wörter über A und An die Menge aller Wörter der Länge n über A.
Definition: Eine Hashfunktion ist eine Abbildung
h : A* → An
die ein beliebig langes Wort x über A auf ein Wort h(x) fester Länge n über A abbildet.
Das Wort x wird in diesem Zusammenhang auch als Dokument bezeichnet, der Funktionswert h(x) als der Hashwert des Dokuments.
Da es unendlich viele Wörter in A* gibt, aber nur endlich viele in An, ist eine Hashfunktion niemals injektiv, d.h. es gibt immer Wörter x, y ∈ A* mit x ≠ y, aber h(x) = h(y).
Definition: Sei h eine Hashfunktion. Ein Paar (x, y) mit x ≠ y, aber h(x) = h(y) wird als Kollision bezeichnet.
Beispiel: Sei A = {0, ..., 9}. Die Menge A* besteht also aus allen endlichen Ziffernfolgen. Die Hashfunktion h : A* → A3 ist definiert durch
h(x) = die letzten drei Ziffern von 000x
Der Hashwert eines Wortes x besteht also einfach aus den letzten drei Ziffern von x, wobei gegebenenfalls führende Nullen ergänzt werden, wenn x aus weniger als drei Ziffern besteht.
Somit gilt also beispielsweise
h(526350482645) = 645 und
h(27) = 027
Das Paar (27, 678027) ist eine Kollision, denn die Hashwerte von 27 und von 678027 sind gleich.
Für kryptografische Anwendungen werden kollisionssichere Hashfunktionen benötigt. Die Hashfunktion aus dem obigen Beispiel ist dafür nicht geeignet.
Definition: Eine Hashfunktion h wird als schwach kollisionssicher bezeichnet, wenn es praktisch undurchführbar ist, zu einem gegebenen Wort x eine Kollision (x, y) zu finden.
Beispiel: Sei h die Hashfunktion aus dem obigen Beispiel. Gegeben sei x = 17364 mit dem Hashwert 364. Die Hashfunktion h wäre schwach kollisionssicher, wenn es schwer wäre, eine andere Ziffernfolge y mit dem gleichen Hashwert 364 zu finden.
Tatsächlich aber ist eine solche Ziffernfolge y sehr leicht zu finden; z.B. erfüllt stets y = 0x, hier also y = 017364, die Bedingungen x ≠ y aber h(x) = h(y).
Die Hashfunktion h aus dem obigen Beispiel ist also nicht schwach kollisionssicher.
Theoretisch ist es auch bei jeder anderen Hashfunktion h sehr leicht, zu einem gegebenen Wort x eine Kollision zu finden, falls eine solche existiert. Man erzeugt einfach der Reihe nach alle Wörter y ∈ A* und prüft, ob h(x) = h(y) ist.
Eine Hashfunktion kann also nur dann schwach kollisionssicher sein, wenn die Anzahl der Wörter y, die ausprobiert werden müssen, so groß ist, dass dieses Verfahren zu lange dauert. Hierzu muss insbesondere der Hashwert genügend lang sein, z.B. 160 Bit.
Die Lösung eines Problems wird als praktisch undurchführbar (engl.: infeasible) bezeichnet, wenn kein Verfahren bekannt ist, das wesentlich schneller ist als das Ausprobieren aller Möglichkeiten.
Definition: Eine Hashfunktion h wird als kollisionssicher bezeichnet, wenn es praktisch undurchführbar ist, eine beliebige Kollision (x, y) zu finden.
Lemma: Jede kollisionssichere Hashfunktion ist auch schwach kollisionssicher.
Es ist schwerer, zu einem bestimmten Wort x eine Kollision (x, y) zu finden als irgendeine beliebige Kollision (x', y') zu finden. Hier besteht ein Zusammenhang zu dem sogenannten Geburtstagsparadoxon: Es ist ziemlich unwahrscheinlich, dass in einem Raum mit 23 Personen jemand (y) am selben Tag wie Sie (x) Geburtstag hat. Der Geburtstag spielt hier die Rolle des Hashwertes, d.h. wenn x und y am selben Tag Geburtstag haben, gilt h(x) = h(y). Aber es ist sehr wahrscheinlich, nämlich mehr als 50%, dass sich überhaupt zwei Personen x' und y' dort befinden, die an einem beliebigen Tag h(x') = h(y') beide Geburtstag haben.
In der Praxis allerdings kommen Kollisionen weitaus seltener vor als es zunächst scheint. Denn Hashwerte werden nur von tatsächlich vorhandenen Dokumenten berechnet, und es gibt sehr viel weniger tatsächlich vorhandene Dokumente als mögliche Hashwerte, jedenfalls wenn die Länge n der Hashwerte groß genug ist, z.B. n = 160 Bit.
[Bu 00] J.A. Buchmann: Introduction to Cryptography. Springer (2000)
[Wät 04] D. Wätjen: Kryptographie. Spektrum (2004)
Weiter mit: [up]