Cryptography Reference
In-Depth Information
In vielen kryptografischen Anwendungen sind die Mengen
P
und
C
speziell ge-
wählt: Wir erinnern an die Menge aller Wörter über dem Alphabet
A
(in der
Praxis ist
A
oft gleich
Z
2
) aus Abschnitt 1.4, die wir mit
A
∗
bezeichnet haben.
A
n
benutzt. Bei sol-
chen Hashfunktionen wird also ein Datensatz beliebiger Länge auf einen Daten-
satz der festen Länge
n
komprimiert
. Ein typischer Wert für
n
aus der Praxis ist
n
werden dann häufig Hashfunktionen
h
:
A
∗
→
∈
N
Mit
n
160, oder größer.
Die Kollisionsresistenz stellt sicher, dass der sogenannte
Hashwert
h
=
(
)
unfälsch-
bar mit
x
verbunden ist. Man spricht manchmal auch von einem (kryptografi-
schen)
Fingerabdruck
. Wie der Fingerabdruck eines Menschen diesen fast sicher
identifizieren kann, soll der Hashwert den Datensatz
x
identifizieren.
x
4.4.3 Einwegfunktionen mit Hintertürchen
Auch die Idee, Einwegfunktionen mit Hintertürchen zu definieren, stammt von
Diffie und Hellman [9]. Sie haben damit die moderne Kryptologie begründet.
Es seien
A
und
B
Mengen. Eine Abbildung
f
→
B
heißt
Trapdoor-
Einwegfunktion
oder
Einwegfunktion mit Hintertürchen
, wenn gilt:
:
A
(H1)
f
ist invertierbar.
f
,
f
−
1
(
)
(H2) Das Paar
ist leicht zu erzeugen.
(H3) Es gibt eine Beschreibung von
f
, in der
f
eine Einwegfunktion ist.
P
, genauer: Es gibt einen Algorithmus, mit dem
f
−
1
effizient berech-
net werden kann.
f
−
1
∈
(H4)
Beispiele werden wir hierzu nicht geben. In Kapitel 7 wird gezeigt, dass das RSA-
Verfahren auf einer Einwegfunktion mit Hintertürchen basiert, die algorithmisch
äquivalent zur Faktorisierung ist (siehe auch das Beispiel auf Seite 76).
Weitere Kandidaten für Einwegfunktionen mit Hintertürchen ergeben sich aus
dem diskreten Logarithumsproblem, wie es in Kapitel 10 beschrieben ist.
4.4.4 Anwendungen
Die Beobachtung von Diffie und Hellman [9] war, dass aus Einwegfunktionenmit
Hintertürchen asymmetrische Verschlüsselungs- und Signaturschemata konstru-
iert werden können: Jeder Teilnehmer
T
eines Netzwerks erzeugt sich ein Paar
(
f
T
,
f
−
1
von Trapdoor-Einwegfunktionen und veröffentlicht
f
T
in der Beschrei-
bung gemäß (H3).
)
T
