Cryptography Reference
In-Depth Information
Anwendung: Schlüsselaustausch.
Gegeben sei ein Kryptosystem
(
P
,
P
,
K
,
f
,
g
)
(
)
→
∈
bei dem
f
y
,.
:
K
P
für jedes
y
P
eine Einwegfunktion ist. Außerdem
setzen wir voraus, dass
f
k
1
und
f
k
2
für alle
k
1
,
k
2
∈
K
vertauschbar sind, dass also
gilt
f
k
1
◦
f
k
2
=
f
k
2
◦
f
k
1
.
Wir wählen ein festes
x
P
, das öffentlich zugänglich ist. Zwei Teilnehmer
T
1
und
T
2
bestimmen einen gemeinsamen geheimen Schlüssel
∈
κ
wie folgt:
∈
=
(
)
T
1
wählt
k
1
K
und publiziert
y
1
:
f
x
,
k
1
.
∈
=
(
)
T
2
wählt
k
2
K
und publiziert
y
2
:
f
x
,
k
2
.
κ
=
(
)=
(
)
Es ist
der gemeinsame geheime Schlüssel, wobei
T
1
die erste,
T
2
die zweite Rechnung ausführen kann.
:
f
y
2
,
k
1
f
y
1
,
k
2
Unsere Voraussetzung stellt sicher, dass es nicht möglich ist,
κ
aus
y
1
oder
y
2
zu
berechnen.
Diese Idee geht auf Diffie und Hellman [9] zurück. Sie haben auch ein konkretes
Verfahren beschrieben, das in Kapitel 9 zu finden ist. Dort werden einige Feinhei-
ten diskutiert, die wir hier der Einfachheit halber unterschlagen haben.
4.4.2 Hashfunktionen
Hashfunktionen - im Deutschen auch
Streuwertfunktionen
genannt - sollen evtl.
sehr große Datenmengen auf einen kleinen, aber typischen Datensatz komprimie-
ren. Sie werden in der Kryptologie häufig eingesetzt, etwa bei Signaturschemata
und auch bei symmetrischen Authentifikationssystemen, wie sie im folgenden
Kapitel beschrieben werden.
Es seien
P
,
C
Mengen mit
|
>
|
. Dabei darf
P
unendlich sein,
C
wird endlich
vorausgesetzt. Wir nennen eine Einwegfunktion
h
:
P
|
P
C
|
C
eine
Hashfunktion
.
Genauer müsste man Einweg-Hashfunktion sagen, aber wir sind nur an Einweg-
funktionen interessiert.
→
Bemerkung
Für andere Anwendungen, wie etwa die Indizierung in Datenbanken, werden
durchaus auch Hashfunktionen ohne Einwegeigenschaft benutzt.
Eine Hashfunktion
h
heißt
kollisionsresistent
, wenn es keinen effizienten Algo-
rithmus gibt, mit dem
x
,
y
)
gilt. Häufig wird die Kollisionsresistenz in die Definition der Hashfunktion mit
aufgenommen.
Es gibt noch eine schwächere Form der Kollisionsresistenz: Zu vorgegebenem
x
∈
P
gefunden werden können, für die
h
(
x
)=
h
(
y
∈
P
gibt es keinen effizienten Algorithmus, der
y
∈
P
findet mit
h
(
y
)=
h
(
x
)
.
|
>
|
|
∈
N
Wegen
|
P
C
kann die Abbildung
h
nicht injektiv sein. Daher
gibt
es
- im Allgemeinen sogar sehr viele! Verlangt ist nur, dass es
schwer sein muss, solche zu
finden
.
x
,
y
mit
h
(
x
)=
h
(
y
)
