Cryptography Reference
In-Depth Information
=
x∈{
0
,
1
}
l
Prob
1
l
F
(0
l
)=
x
·
1
2
l
x
=
F
(1
l
)
⊕
|
1
1
2
l
(1
=
1
·
2
l
−
x∈{
0
,
1
}
l
1
=
,
2
l
−
1
wobei (
1
) leicht aus der Beobachtung folgt, dass unter der Bedingung, dass
F
(0
l
)=
x
gilt,
F
(1
l
)
nur noch
2
l
1
mögliche Werte annehmen kann, da
F
eine Permutation liefert.
Für den Misserfolg von
U
erhalten wir demnach:
−
)=Prob
S
U
=1
fail
(
U,
B
b
=0
1
=
.
2
l
−
1
Insgesamt folgt für den Vorteil von
U
also:
adv
(
U,
B
)=
suc
(
U,
B
)
−
fail
(
U,
B
)
1
=1
−
.
2
l
−
1
Für übliche Werte von
l
,z.B.,
l
= 128
,ist
1
2
l
−
1
praktisch
0
. Wir haben also einen
sehr guten, zudem ezienten Unterscheider gefunden. Das Vernamsystem lässt sich also
leicht von einem Substitutionskryptosystem unterscheiden und ist deshalb als unsicher
anzusehen.
Wir wollen noch ein weiteres Beispiel betrachten, das zeigt, wie man aus einem Al-
gorithmus, der Chiffretexten Klartexteigenschaften ansieht, einen erfolgreichen Unter-
scheider konstruieren kann. In diesem Beispiel werden wir zudem eine Beweistechnik
kennenlernen, die uns später in ähnlicher Form häufig begegnen wird.
Beispiel 4.7.2 (Unterscheider basierend auf Orakel für erstes Bit). Wir nehmen an, dass
es zu einem
l
-Block-Kryptosystem
mit Schlüsselraum
K
einen deterministischen Algo-
rithmus
O
mit fester, beschränkter Laufzeit
t
gibt, der zu jedem Chiffretext sagen kann,
ob der zugehörige Klartext mit
0
oder
1
beginnt. Wir nehmen an, dass dies dem Algo-
rithmus gelingt, ohne Zugriff auf ein Verschlüsselungsorakel zu haben; in Aufgabe 4.9.19
wird diese Annahme aufgehoben. Genauer nehmen wir an, dass
O
bei Eingabe eines
Chiffretextes
y
=
F
(
x
)
das erste Bit von
x
mit einer Wahrscheinlichkeit
B
3
/
4
richtig
bestimmt, gemittelt über alle Klartexte und Schlüssel. Für das folgende Experiment
≥
E
bit
,
bei dem
x
(0)
das erste Bit von
x
bezeichnet, gilt also
Prob
{
E
bit
=1
}≥
3
/
4
.
E
bit
:
}
k
=
flip
(
K
)
;
F
=
E
(
{
0
,
1
·
,k
)
x
=
flip
(
l
)
y
=
F
(
x
)
