Kryptografie

Kryptografische Hashfunktion

 aufwärts

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 "Finger­abdruck" des Dokuments dar, mit der gewünschten Eigenschaft, dass unter­schiedliche Dokumente auch unter­schiedliche Finger­abdrücke haben. Theoretisch ist dies natürlich nicht zu gewähr­leisten, 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 unwahr­scheinlich ist, dass zwei tatsächliche Dokumente denselben Finger­abdruck haben.

Hashfunktion

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 : APfeil nach rechts 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 Funktions­wert 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 Element 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 Ziffern­folgen. Die Hashfunktion h : APfeil nach rechts 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 gegebenen­falls führende Nullen ergänzt werden, wenn x aus weniger als drei Ziffern besteht.

Somit gilt also beispiels­weise

h(526350482645)  =  645   und
h(27)  =  027

Das Paar (27, 678027) ist eine Kollision, denn die Hashwerte von 27 und von 678027 sind gleich.

Kollisionssicherheit

Für krypto­grafische Anwendungen werden kollisions­sichere Hash­funktionen benötigt. Die Hashfunktion aus dem obigen Beispiel ist dafür nicht geeignet.

Definition:  Eine Hashfunktion h wird als schwach kollisions­sicher bezeichnet, wenn es praktisch undurch­führ­bar 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 kollisions­sicher, 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 kollisions­sicher.

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 Element A* und prüft, ob h(x) = h(y) ist.

Eine Hashfunktion kann also nur dann schwach kollisions­sicher 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 undurch­führ­bar (engl.: infeasible) bezeichnet, wenn kein Verfahren bekannt ist, das wesentlich schneller ist als das Ausprobieren aller Möglich­keiten.

Definition:  Eine Hashfunktion h wird als kollisions­sicher bezeichnet, wenn es praktisch undurch­führ­bar ist, eine beliebige Kollision (x, y) zu finden.

Lemma:  Jede kollisions­sichere Hashfunktion ist auch schwach kollisions­sicher.

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 Geburtstags­paradoxon: Es ist ziemlich unwahr­scheinlich, 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 wahr­scheinlich, 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.

Literatur

[Bu 00]J.A. Buchmann: Introduction to Cryptography. Springer (2000)
[Wät 04]D. Wätjen: Kryptographie. Spektrum (2004)

 

Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 08.03.2010   Updated: 08.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik