Cryptography Reference
In-Depth Information
schreiben:
)=Prob
S
A
=1
−
Prob
S
A
=1
adv
(
A,
H
b
=1
b
=0
=Prob
{
S
{
S
1
,
0
=1
}−
Prob
0
,
0
=1
}
{
S
{
S
=Prob
1
,
0
=1
}−
Prob
1
,
1
=1
}
+
(6.6.5)
Prob
{
S
{
S
1
,
1
=1
}−
Prob
0
,
1
=1
}
+
{
S
{
S
Prob
0
,
1
=1
}−
Prob
0
,
0
=1
}
.
Wir werden nun die drei Differenzen auf der rechten Seite der Gleichung (6.6.5) durch
den Vorteil von zu konstruierenden Angreifern auf
S
a
bzw.
S
s
abschätzen, was dann
insgesamt (6.6.4) liefern wird.
Schauen wir uns zunächst die erste Differenz
{
S
{
S
Prob
1
,
0
=1
}−
Prob
1
,
1
=1
}
(6.6.6)
S
S
an. In den verkürzten Experimenten
passiert fast das Gleiche. Erst
wenn
A
sein Angebot
(
z
0
,z
1
)
unterbreitet, gibt es einen Unterschied: In
1
,
0
und
1
,
1
S
1
,
0
wird
S
(
E
a
(
k
0
,k
)
,E
s
(
z
1
,k
0
))
zurückgeben, wohingegen in
der Chiffretext
(
E
a
(
k
1
,k
)
,
E
s
(
z
1
,k
0
))
zurürckgeben wird. Die beiden Chiffretexte unterscheiden sich also ledig-
lich darin, dass bei dem einen
k
0
und bei dem anderen
k
1
mit dem asymmetrischen
Chiffrieralgorithmus
E
a
verschlüsselt wird. Damit sollten sich die Wahrscheinlichkeiten
Prob
{
S
1
,
0
=1
}
1
,
1
und
Prob
{
S
1
,
1
=1
}
aber kaum unterscheiden, denn sonst könnte
man einen Angreifer
A
0
auf
S
a
konstruieren, der gut zwischen der Verschlüsselung von
k
0
und
k
1
unterscheiden könnte. Wir wollen
A
0
nun angeben und werden leicht einsehen,
dass der Vorteil von
A
0
genau der in (6.6.6) angegebenen Differenz entspricht.
Der Angreifer
A
0
=(
S
AF
0
,
AG
0
)
auf
S
a
simuliert im Wesentlichen
b
=1
,bisauf
die Chiffrewahl. Genauer arbeitet
A
0
wie folgt:
A
0
(
k
):
AF
0
(
k
)
:
1.
Simuliere
AF
.
(
z
0
,z
1
)=
(
k
)
.
2.
Bestimme zwei zufällige symmetrische Schlüssel.
k
0
=
flip
(
K
s
)
;
k
1
=
flip
(
K
s
)
3.
Sende Angebot.
sende
(
k
1
,k
0
)
AG
0
(
k,y
)
:
4.
Berechne asymmetrische und symmetrische Chiffretexte.
y
sk
=
y
y
pt
=
E
s
(
z
1
,k
0
)
5.
Setze Simulation von
A
fort.
setze Simulation von
A
mit
AF
AG
(
k,
(
y
sk
,y
pt
))
fort.
S
S
a
S
Man sieht nun leicht, dass sich
A
0
b
=1
exakt wie
1
,
0
verhält. Entsprechendes gilt