Cryptography Reference
In-Depth Information
Nun stellt sich natürlich die Frage, ob pseudozufällige Funktionen ein adäquates Mit-
tel sind, sichere Block-Kryptosysteme zu modellieren, schließlich sind Chiffren von Block-
Kryptosystemen Permutationen. Die Antwort ist glücklicherweise: Ja! Grob gesagt, wer-
den wir in diesem Abschnitt zeigen, dass ein Block-Kryptosystem genau dann eine pseu-
dozufällige Permutation ist, wenn es eine pseudozufällige Funktion ist. Wir können bei
der Modellierung sicherer Block-Kryptosysteme also beliebig zwischen pseudozufälligen
Permutationen und pseudozufälligen Funktionen hin- und herwechseln.
Bevor wir diese Äquivalenz zeigen, übertragen wir die Begriffe und Notationen aus
Abschnitt 4.7 auf (pseudo-)zufällige Funktionen. Dazu bezeichne
F
{
0
,
1
}
l
die Menge der
{
0
,
1
}
l
nach
{
0
,
1
}
l
und es sei
B
ein
l
-Block-Kryptosystem.
Funktionen von
F
{
0
,
1
}
l
. Das so erhaltene Experiment
zum
l
-Unterscheider
U
(und zum Block-Kryptosystem
Wir ersetzen nun
P
{
0
,
1
}
l
in Definition 4.7.2 durch
PRF
U
B
) bezeichnen wir mit
E
.Ba-
sierend auf diesem Experiment definieren wir das verkürzte Experiment
S
PRF
U
,denErfolg
suc
PRF
(
U,
)
analog zu den
entsprechenden Begriffen aus Abschnitt 4.7. Offensichtlich überträgt sich Lemma 4.7.1
auf die neuen Begriffe für Erfolg, Misserfolg und Vorteil.
Ähnlich wie nach Definition 4.7.2 beschrieben, ist es auch hier nützlich, sich vorzustel-
len, dass in
B
)
, den Misserfolg fail
PRF
(
U,
B
)
und den Vorteil adv
PRF
(
U,
B
PR
U
eine zufällige Funktion partiell und dynamisch bestimmt
wird, statt zu Anfang des (verkürzten) Experiments und vollständig: Sobald eine Ora-
kelanfrage gestellt wird, wird, falls der Klartext bisher noch nicht angefragt wurde, ein
Funktionswert bestimmt, indem zufällig, gleichverteilt ein Bitvektor aus
E
PRF
U
bzw.
S
l
gewählt
wird, sonst wird der für diesen Klartext gespeicherte Funktionswert zurückgeliefert. Der
entscheidende Unterschied zu Permutationen ist also, dass wir uns nicht darum kümmern
müssen, dass ein neu zu wählender Funktionswert vorher noch nicht verwendet wurde.
Genau diese Tatsache vereinfacht, wie wir sehen werden, den Umgang mit Funktionen
im Vergleich zu Permutationen.
Zur besseren Unterscheidung der Begriffe schreiben wir im Fall pseudozufälliger Permu-
tationen von nun an auch
{
0
,
1
}
PRP
U
PRP
U
E
,
S
,suc
PRP
(
U,B
)
,fail
PRP
(
U,B
)
und adv
PRP
(
U,B
)
statt einfach
)
, wie in Abschnitt 4.7.
Wir können nun die Äquivalenz der Sicherheitsbegriffe zeigen. Das folgende Lemma
wird auch
PRF/PRP-Switching Lemma
genannt.
E
U
,
S
U
, suc
(
U,
B
)
,fail
(
U,
B
)
bzw. adv
(
U,
B
0
,
l>
0
, mit
2
l
Lemma 4.8.1.
Es seien
q
ein
l
-Block-Kryptosystem und
U
ein
l
-Unterscheider, der maximal
q
Orakelanfragen stellt. Dann gilt
≥
≥
q
,
B
q ·
(
q −
1)
2
l
+1
|
adv
PRP
(
U,
B
)
−
adv
PRF
(
U,
B
)
|≤
.
Beweis.
Es seien
U
und
wie oben gegeben. Wir können annehmen, dass
U
genau
q
verschiedene
Klartexte anfragt. Ansonsten können wir leicht einen solchen Unterscheider
U
konstruieren:
U
simuliert
U
merkt sich allerdings alte Antworten und muss deshalb
niemals einen Klartext mehrfach anfragen. Stellt
U
weniger als
q
Anfragen, so stellt
U
einfach noch weitere Anfragen mit anderen Klartexten, so dass es am Ende genau
q
An-
fragen sind. Die für diese Anfragen erhaltenen Antworten werden ignoriert. Offensichtlich
gilt adv
PRP
(
U
,B
)=
adv
PRP
(
U,B
)
und adv
PRF
(
U
,B
)=
adv
PRF
(
U,B
)
. Wir nehmen
deshalb im Folgenden an, dass
U
genau
q
verschiedene Klartexte anfragt.
B
