Cryptography Reference
In-Depth Information
8
Kryptographische Hashfunktionen
8.1
Einführung
Bevor wir in den nächsten Kapiteln auf symmetrische Authentifizierungsverfahren und
digitale Signaturen eingehen, führen wir in diesem Kapitel kryptographische Hashfunk-
tionen ein, da sie eine wichtige Rolle bei der Konstruktion dieser kryptographischen
Primitive spielen. Kryptographische Hashfunktionen nehmen auch darüber hinaus einen
wichtigen Platz in der Kryptographie ein.
Unabhängig von der Anwendung kryptographischer Hashfunktionen für die Nachrich-
tenauthentifizierung wollen wir diese Funktionen durch das folgende Szenarium motivie-
ren:
Szenarium 6.
Alice möchte eine große Datenmenge vorübergehend in einen unsicheren,
von Eva kontrollierten Bereich auslagern. Beim Zurückholen der Daten möchte Alice
überprüfen, ob die Daten während des Aufenthalts in dem unsicheren Bereich von Eva
verändert wurden.
Wie würde Alice hier vorgehen? Sie würde eine kurze »Prüfsumme« der auszulagern-
den Daten erstellen, die charakteristisch für ihre Daten ist, und diese in ihrem sicheren
Bereich ablegen. Beim Zurückholen der Daten würde sie dann eine Prüfsumme für die
zurückgeholten Daten berechnen und mit der abgelegten Prüfsumme vergleichen. Falls
beide Prüfsummen übereinstimmen, würde sie die Daten als gültig betrachten und nutzen,
andernfalls würde sie diese als verändert ansehen und damit als ungültig verwerfen.
In der Regel spricht man in diesem Zusammenhang allerdings nicht von »Prüfsum-
men«, sondern nutzt den Anglizismus
Hashwert
(
to hash
=
zerkleinern). Die Vorschrift,
die einem Bitvektor einen Hashwert zuordnet, wird
kryptographische Hashfunktion
ge-
nannt, wobei wir das Attribut
kryptographisch
ab sofort fallen lassen. Es dient dazu, die
betrachteten Funktionen abzugrenzen von den Hashfunktionen, die man im Bereich der
Datenstrukturen studiert. Da diese hier aber keine Rolle spielen, besteht keine Gefahr
der Verwechslung.
Formal wollen wir eine Hashfunktion wie folgt definieren.
l
}
∗
. Eine Funk-
Definition 8.1.1 (Hashfunktion). Es seien
l>
0
und
{
0
,
1
}
⊂
D
⊆{
0
,
1
}
≤L
für
L>l>
0
,sonennenwir
h
eine
(
L, l
)
-beschränkte Hashfunktion
oder einfach
beschränkte
Hashfunktion
.Für
D
=
{
0
,
1
}
∗
heißt
h
unbeschränkte
l
-Hashfunktion
oder einfach
unbe-
schränkte Hashfunktion
.DieZahl
l
ist die
Hashbreite
. Der Bitvektor
h
(
x
)
wird
Hashwert
von
x
genannt.
l
tion
h
:
D
→{
0
,
1
}
heißt
Hashfunktion mit Definitionsbereich
D
.Ist
D
=
{
0
,
1
Es sei bemerkt, dass man in der Praxis an Hashfunktionen interessiert ist, die sich
sehr ezient berechnen lassen, nämlich in linearer Zeit in der Länge der Eingabe.
