Cryptography Reference
In-Depth Information
Eine Kompressionsfunktion ist im Wesentlichen eine beschränkte Hashfunktion:
Definition 8.4.1 (Kompressionsfunktion). Es seien
b, l >
0
.Eine
(
l,b
)
-Kompressions-
funktion
(
compression function
) ist eine Funktion
f
:
l
b
l
.Eine
{
0
,
1
}
×{
0
,
1
}
→{
0
,
1
}
l
+
b
l
.Dabei
solche Funktion wird auch aufgefasst als Funktion der Form
f
:
{
0
,
1
}
→{
0
,
1
}
nennt man
l
die
Kompressionslänge
und
b
die
Blocklänge
von
f
.
Eine
Kollision
von
f
ist ein Paar
(
x, x
)
l
+
b
l
+
b
, für das
x
=
x
und
∈{
0
,
1
}
×{
0
,
1
}
f
(
x
)=
f
(
x
)
gilt.
Ein erster offensichtlicher und naiver Ansatz, um eine Hashfunktion
h
aus einer
(
l,b
)
-
Kompressionsfunktion zu konstruieren, ist folgender. Wir nehmen dabei zunächst an,
dass die Länge der Eingabenachricht
x
durch
b
teilbar ist, also
x
b∗
gilt. Damit
∈{
0
,
1
}
kann man
x
in
b
-Blöcke zerlegen:
x
=
x
0
···
x
n−
1
für ein
n
≥
0
und
|
x
i
|
=
b
für alle
i<n
.
Zusätzlich wählt man einen Initialisierungsvektor
u ∈{
0
,
1
}
l
fest und berechnet dann
h
(
x
)=
f
(
f
(
···
f
(
f
(
u, x
0
)
,x
1
)
···
,x
n−
2
)
,x
n−
1
)
,
wobei im Fall
n
=0
der Hashwert
h
(
ε
)
auf
u
gesetzt wird. Dafür wollen wir eine Schreib-
weise einführen:
Definition 8.4.2. Es sei
f
eine
(
l,b
)
-Kompressionsfunktion. Dann ist die zugehörige
Iterationsfunktion
i
f
:
l
b∗
l
induktiv definiert durch:
{
0
,
1
}
×{
0
,
1
}
→{
0
,
1
}
i
f
(
u,
)=
u
l
,
für alle
u
∈{
0
,
1
}
i
f
(
u, xv
)=
f
(
i
f
(
u, x
)
,v
)
l
,
x
b∗
,
v
b
.
für alle
u
∈{
0
,
1
}
∈{
0
,
1
}
∈{
0
,
1
}
Die Verwendung von
i
f
(
)
als Hashfunktion ist zum einen problematisch, weil diese
Funktion nur auf Nachrichten angewendet werden kann, deren Länge ein Vielfaches der
Blocklänge ist. Zum anderen, und das ist der entscheidende Punkt, überträgt sich die Kol-
lisionsresistenz der Kompressionsfunktion nicht notwendigerweise auf die Hashfunktion
(siehe Aufgabe 8.6.6).
Das bereits erwähnte Merkle-Damgård-Prinzip löst beide Probleme. Diesem Konstruk-
tionsprinzip folgend geht man wie folgt vor: Ein beliebiger Bitvektor (bis zu einer ma-
ximalen Länge) wird durch »Auffüllen« mit zuätzlichen Bits auf eine durch
b
teilbare
Länge gebracht, wobei Informationen über die ursprüngliche Länge des Bitvektors in die-
sen Füllbits enthalten sind. Nach Anwendung dieser sogenannten Füllfunktion wird dann
die Iterationsfunktion angewendet. Die Füllfunktion sollte dabei MD-kompatibel sein:
·
,
·
Definition 8.4.3 (MD-kompatible Füllfunktion). Es seien
r
und
b
natürliche Zahlen mit
0
<r
<
2
r
b
+
heißt
MD-kompatible
(
r, b
)
-Füllfunktion
,
≤
b
. Eine Funktion
p
:
{
0
,
1
}
→{
0
,
1
}
falls die folgenden Bedingungen erfüllt sind:
1. Für jedes
x
<
2
r
ist
x
ein Präfix von
p
(
x
)
.
∈{
0
,
1
}
<
2
r
2. Für alle
x
0
,x
1
∈{
0
,
1
}
mit
|
x
0
|
=
|
x
1
|
gilt
|
p
(
x
0
)
|
=
|
p
(
x
1
)
|
.
<
2
r
mit
3. Für alle
x
0
,x
1
∈{
0
,
1
}
ist der Sux von
p
(
x
0
)
der Länge
b
verschieden vom Sux von
p
(
x
1
)
der Länge
b
.
|x
0
|
=
|x
1
|
