Cryptography Reference
In-Depth Information
UnterscheiderECB(
H
)
1.
Erzeuge Nachricht, die aus zwei gleichen Blöcken besteht.
x
=0
2
l
2.
Frage Nachricht an.
y
=
H
(
x
)
3.
Treffe Entscheidung anhand der Blöcke des Chiffretextes.
falls
y
[0
,l
)=
y
[
l,
2
l
)
,sogib
1
, sonst
0
zurück
Offensichtlich gilt
suc
RR
(UnterscheiderECB
,
ECB-
B
)=1
,
da in der Realwelt der erste und zweite
l
-Block von
y
immer identisch sind. In der
Zufallswelt ist das genau dann der Fall, wenn im ersten und zweiten Block der gleiche
Klartext gewählt wird. Die Wahrscheinlichkeit dafür ist
2
l
2
2
l
=
2
l
. Wir erhalten also:
)=
1
2
l
fail
RR
(UnterscheiderECB
,
ECB-
B
,
und damit,
1
2
l
adv
RR
(UnterscheiderECB
,
ECB-
B
)=1
−
.
Wir werden nun in den folgenden beiden Unterabschnitten die Beziehung zwischen
der FG- und der RR-Sicherheit studieren. Zunächst zeigen wir, dass man zu jedem guten
Angreifer (im FG-Ansatz) leicht einen guten Unterscheider (im RR-Ansatz) mit ver-
gleichbaren Ressourcen konstruieren kann. Wäre also ein symmetrisches Kryptoschema
bzgl. der FG-Sicherheit unsicher, dann wäre es auch bzgl. der RR-Sicherheit unsicher.
Mit anderen Worten, RR-Sicherheit implizit FG-Sicherheit. In Abschnitt 5.5.2 zeigen
wir, dass die Umkehrung auch gilt.
5.5.1
Von Angreifern zu Unterscheidern
Es sei im Folgenden
S
ein symmetrisches
l
-Kryptoschema. Es ist sehr leicht, aus einem
guten Angreifer
A
auf
(im RR-
Ansatz) zu konstruieren. Die Idee ist nämlich sehr ähnlich zu derjenigen im Beweis der
Sicherheit der R-CTR-Betriebsart (Abschnitt 5.4). Der Unterscheider muss lediglich das
Experiment
S
(im FG-Ansatz) einen guten Unterscheider
U
auf
S
E
A
(ohne Chiffrewahl) mit Hilfe der ihm übergebenen Chiffre simulieren.
Wenn der Unterscheider in der Realwelt arbeitet, dann wird genau das Experiment
E
A
simuliert. Ist
A
ein guter Angreifer auf
,dannwird
A
in diesem Experiment erfolgreich
sein. Läuft dagegen
U
in der Zufallswelt, so wird
A
, wie wir sehen werden, wenig Erfolg
im von
U
simulierten Experiment
S
E
A
haben. Also machen wir die Entscheidung des
Unterscheiders
U
davon abhängig, ob
A
in
E
A
erfolgreich ist oder nicht. Ist
A
erfolgreich,
dann wird der Unterscheider vermuten, dass er in der Realwelt läuft; ansonsten vermutet
der Unterscheider, in der Zufallswelt zu laufen.
