Cryptography Reference
In-Depth Information
2. Aus einer Kollision für
f
lässt sich leicht eine Kollision für
f
bestimmen und umge-
kehrt.
3. Die Funktion
f
ist nicht viel schwerer zu berechnen als
f
.
Aufgabe
8.6.7 (Merkle-Damgård für unbeschränkte Hashfunktionen I)
.
In Abschnitt 8.4
haben wir das Merkle-Damgård-Prinzip kennengelernt, nachdem aus einer Kompressions-
funktion und einer passenden Füllfunktion eine Familie von beschränkten Hashfunktionen
konstruiert werden kann. Hier wollen wir, den Arbeiten von Merkle und Damgård folgend,
ein Prinzip kennenlernen, das eine Familie von
unbeschränkten
Hashfunktionen liefert. Es
sei eine
(
l,b
)
-Kompressionsfunktion
f
:
{
0
,
1
}
l
mit
b ≥
2
gegeben. Aus
f
wer-
de eine unbeschränkte
l
-Hashfunktion MD1
f
durch folgenden Algorithmus definiert:
MD
1
f
(
x
:
l
+
b
→{
0
,
1
}
}
∗
):
l
{
0
,
1
{
0
,
1
}
1.
Fülle Nachricht auf.
d
=
|
x
|
mod (
b
−
1)
y
=
x·
0
b−
1
−d
·
(
d
)
b−
1
2
(
Beachte:
|y|
=
n
(
b −
1)
für ein
n ≥
2
)
2.
Zerlege
y
in Blöcke der Länge
b
−
1
.
y
0
· ...·y
n−
1
=
y
mit
|y
i
|
=
b −
1
für
i<n
3.
Iteriere Kompressionsfunktion.
z
0
=0
l
+1
·
y
0
g
0
=
f
(
z
0
)
für
i
=0
bis
n
2
z
i
+1
=
g
i
·
1
·y
i
+1
g
i
+1
=
f
(
z
i
+1
)
4.
Gib Hashwert zurück.
gib
g
n−
1
zurück
Beweisen Sie, dass MD1
f
eine kollisionsresistente Hashfunktion ist, wenn die zugrunde
liegende Kompressionsfunktion
f
kollisionsresistent ist. Zeigen Sie dazu, wie man aus
einer Kollision für MD1
f
ezient eine Kollision für
f
konstruieren kann.
Aufgabe
8.6.8 (Merkle-Damgård für unbeschränkte Hashfunktionen II)
.
Wir wollen eine
zweite Möglichkeit, die ebenfalls auf Merkle und Damgård zurückgeht, studieren, wie aus
einer Kompressionsfunktion eine unbeschränkte Hashfunktion gewonnen werden kann. Es
sei eine
(
l,
1)
-Kompressionsfunktion
f
gegeben. Nun wird mit einer Expansionsfunktion
e
:
−
}
∗
→{
}
∗
gearbeitet. Diese ist definiert durch:
{
0
,
1
0
,
1
e
(
x
)=11
·
α
(
x
(0))
·
...
·
α
(
x
(
|
x
|−
1))
,
wobei
α
:
{
0
,
1
}→{
0
,
1
}
∗
definiert ist durch
α
(0) = 0
und
α
(1) = 01
.Aus
f
werde eine
unbeschränkte
l
-Hashfunktion MD2
f
durch folgenden Algorithmus definiert:
MD
2
f
(
x
:
{
0
,
1
}
∗
):
{
0
,
1
}
l
1.
Expandiere Nachricht.
y
=
e
(
x
)
2.
Iteriere Kompressionsfunktion.
g
0
=
f
(0
l
y
(0))
für
i
=0
bis
·
|y|−
2
g
i
+1
=
f
(
g
i
·
y
(
i
+1))
