Cryptography Reference
In-Depth Information
4.4 Einwegfunktionen und Hashfunktionen
Etwas salopp ausgedrückt, werden wir eine Funktion
f
, für die
b
=
f
(
a
)
einfach
f
−
1
∈
(
{
}
)
auszuwerten ist, aber für die
a
schwer
zu bestimmen ist, eine
Ein-
wegfunktion
nennen. Die Existenz von echten
Einwegfunktionen
hängt eng mit der
Frage zusammen, ob die Komplexitätsklassen
P
und
NP
verschieden sind. Da
diese Frage offen ist, werden wir zur Existenz von Einwegfunktionen nur Vermu-
tungen anstellen können.
Im Folgenden werden wir gelegentlich feststellen, eine Funktion sei in
P
oder
NP
. Das soll bedeuten, dass es einen Algorithmus zur Auswertung von
f
gibt,
der in der entsprechenden Klasse liegt. In vielen - gerade für diesen Abschnitt
wichtigen - Fällen, hängt das von der Art ab, wie
f
beschrieben ist.
b
4.4.1 Einwegfunktionen
Es seien
A
und
B
Mengen. Eine Abbildung
f
:
A
→
B
heißt
Einwegfunktion
,
wenn gilt:
(E1)
f
∈
P
und
f
lässt sich tatsächlich effizient berechnen;
∈
∈
(
)=
(E2) Das Problem
Π
„
zu b
B bestimme a
A mit f
a
b
“, d. h. finde ein
Element in
f
−
1
(
)
∈
b
, ist für die meisten
b
B
nicht effizient lösbar. Im besten
nicht in
P
.
Man beachte, dass das Problem
Fall ist
Π
Π
wegen der ersten Bedingung in
NP
liegt.
Beispiel
Wir betrachten die Menge
I
k
2
k
−
1
,2
k
=[
−
]
∩
N
1
der
k
-Bit Zahlen. Die Multipli-
kationsabbildung
I
k
×
→
N
I
k
ab
kann effizient ausgeführt werden (siehe Lemma 4.3). Daher ist (E1) erfüllt. Es
scheitert aber (E2) an der Formulierung
für die meisten
. Für kryptografische An-
wendungen sind die Ergebnisse zu häufig faktorisierbar.
Schränken wir diese Abbildung aber ein, indem wir nur
k
-Bit Primzahlen zulas-
sen, also Elemente der Menge
(
a
,
b
)
→
P
k
:
=
{
p
∈
I
k
;
p
prim
}
, so erhalten wir:
P
k
×
P
k
→
N
(
)
→
a
,
b
ab
Diese Abbildung ist nach allem, was wir heute wissen, vermutlich eine Einweg-
funktion. Auf dieser Einwegfunktion basiert das bekannte RSA-Verfahren.
Bemerkung
Die Sicherheit von AES besagt im Wesentlichen, dass AES eine Einwegfunktion
in beiden Argumenten ist.
