Cryptography Reference
In-Depth Information
Die Behauptung ergibt sich nun durch Auflösen nach suc
(
U,
B
)
−
fail
(
U,
B
)
und d
er
Definition von adv
(
U,B
)
.
Wir wollen uns ein erstes einfaches Beispiel für einen Unterscheider und dessen Vorteil
ansehen.
Beispiel 4.7.1 (Unterscheider auf Vernamsystem). Es sei
l>
0
.Wirbetrachtenden
l
-Unterscheider, der wie folgt gegeben ist (siehe unten für weitere Erklärung):
l
-Vernamunterscheider(
F
)
1.
Stelle Vermutung über verwendeten Schlüssel an
k
=
F
(0
l
)
2.
Erfrage Chiffretext für anderen Klartext
y
=
F
(1
l
)
3.
Gib Vermutung aus
falls
1
l
⊕
k
=
y
,danngib
1
aus, sonst
0
Es bezeichne
B
das in Beispiel 3.2.2 eingeführte Vernamsystem der Länge
l
≥
1
.Wir
kürzen im Folgenden
l
-
Vernamunterscheider
mit
U
ab.
Der Unterscheider
U
bestimmt in 1. den Schlüssel unter der Annahme, dass die über-
gebene Chiffre
F
eine Vernamchiffre ist. Dann überprüft er, ob die Anwendung von
F
auf
1
l
mit der Verschlüsselung von
1
l
unter dem hypothetischen Schlüssel übereinstimmt.
Ist dies der Fall, vermutet der Unterscheider, dass er sich in der Realwelt befindet, also
F
tatsächlich eine Vernamchiffre ist; ansonsten vermutet er, dass er sich in der Zufallswelt
befindet,
F
also eine Substitutionschiffre ist.
Wir schätzen nun den Erfolg und Misserfolg von
U
bzgl.
B
ab, um den Vorteil von
U
zu bestimmen.
Man sieht leicht, dass, wenn
U
in der Realwelt läuft, also
F
eine Vernamchiffre ist,
U
immer
1
ausgeben wird. Wir erhalten also für den Erfolg von
U
:
suc
(
U,B
)=Prob
S
U
b
=1
=1
=1
.
Um den Misserfolg von
U
abschätzen zu können, müssen wir uns überlegen, mit welcher
Wahrscheinlichkeit
U
das Bit
1
ausgibt, obwohl
U
in der Zufallswelt läuft, in der
U
eine zufällig gewählte Permutation
F
als Orakel erhält. Der Unterscheider gibt nur
1
aus, falls
1
l
⊕ k
=
y
gilt, also
1
l
⊕ F
(0
l
)=
F
(1
l
)
. Es gilt also die Wahrscheinlichkeit
Prob
1
l
F
(0
l
)=
F
(1
l
)
zu bestimmen, wobei, wie in Abschnitt 4.6.2 besprochen,
F
als Zufallsvariable über der Menge der Läufe von
⊕
S
U
aufgefasst werden kann. Als
solche liefert
F
offensichtlich eine zufällig gewählte Permutation aus der Menge
b
=0
P
{
0
,
1
}
l
.
Wir erhalten deshalb:
Prob
1
l
F
(0
l
)=
F
(1
l
)
=
x∈{
0
,
1
}
l
Prob
1
l
F
(0
l
)=
F
(1
l
)
,F
(0
l
)=
x
⊕
⊕
=
x∈{
0
,
1
}
l
Prob
1
l
F
(0
l
)=
x
·
F
(0
l
)=
F
(1
l
)
⊕
|
Prob
F
(0
l
)=
x
