Cryptography Reference
In-Depth Information
Prob
{
E
bit
=1
}≥
3
/
4
gelten. Schätzen Sie den Vorteil von
U
analog zu Beispiel 4.7.2
ab.
Hinweis: Um den Misserfolg von
U
abzuschätzen, betrachten Sie das Ereignis
Q
,dass
in einem Lauf von
S
wie in Beispiel 4.7.2 definiert ist) weder
x
noch
x
von
O
abgefragt wurde, wobei
x
denindiesemLaufvon
U
gewählten Klartext bezeichnet;
formal ist
Q
die Menge solcher Läufe. Zeigen Sie nun, mit ähnlicher Argumentation
wie in Beispiel 4.7.2, dass
P
rob
S
(wobei
{
S
=1
=
2
gilt. Bestimmen Sie des Weiteren die
|
Q
}
Wahrscheinlichkeit
Prob
Q
für das Auftreten des Gegenereignisses von
Q
.
Aufgabe
4.9.20 (zufallsgesteuertes Orakel für erstes Bit)
.
Erweitern Sie die Argumentati-
on aus Aufgabe 4.9.19 für den Fall, dass der Algorithmus zur Bestimmung des ersten Bits
des Klartextes zufallsgesteuert ist. Betrachten Sie auch den Fall, dass der Algorithmus
höchstens
10
(statt nur eine) Anfrage stellt.
Aufgabe
4.9.21 (zufallsgesteuertes Orakel für den Schlüssel)
.
Konstruieren Sie analog zu
Aufgabe 4.9.20 einen möglichst guten Unterscheider auf ein Block-Kryptosystem unter
der Annahme, dass ein zufallsgesteuerter Algorithmus gegeben ist, der mit Wahrschein-
lichkeit
≥
3
/
4
nach höchstens
10
Anfragen den verwendeten Schlüssel bestimmen kann.
Schätzen Sie den Vorteil Ihres Unterscheiders ab und beweisen Sie Ihre Aussage.
Aufgabe
4.9.22 (zufallsgesteuertes Orakel für die Anzahl der Einsen)
.
Konstruieren Sie
analog zu den vorherigen Aufgaben einen möglichst guten Unterscheider auf ein Block-
Kryptosystem unter der Annahme, dass ein zufallsgesteuerter Algorithmus gegeben ist,
der mit Wahrscheinlichkeit
3
/
4
zu einem gegebenen Chiffretext nach höchstens
10
Anfragen die Anzahl der Einsen im Klartext bestimmen kann. Schätzen Sie den Vorteil
Ihres Unterscheiders ab und beweisen Sie Ihre Aussage.
Aufgabe
4.9.23 (Größe des Programmcodes)
.
Damit unsere Sicherheitsdefinitionen Sinn
ergeben, haben wir festgelegt, dass die Laufzeit eines Algorithmus die Summe aus der
eigentlichen Laufzeit (Anzahl ausgeführter Operationen) und der Programmlänge ist. In
dieser Aufgabe wollen wir untersuchen, was passiert, wenn die Programmlänge unbe-
schränkt ist, d. h. die Laufzeit eines Algorithmus lediglich durch die Anzahl ausgeführter
Operationen definiert ist.
Es sei
≥
s
. Wir nehmen an,
B
ein
l
-Block-Kryptosystem mit Schlüsselraum
K
⊆{
0
,
1
}
l
dass für alle paarweise verschiedenen Klartexte
x
0
,...,x
9
∈{
0
,
1
}
und alle paarweise
l
verschiedenen Chiffretexte
y
0
,...,y
9
∈{
0
,
1
}
gilt, dass es höchstens einen Schlüssel
k
K
gibt mit
E
(
x
0
,k
)=
y
0
,...,E
(
x
9
,k
)=
y
9
.
a) Begründen Sie, dass für praktische Block-Kryptosysteme, z. B. AES, die obige An-
nahme sinnvoll ist.
b) Konstruieren Sie einen guten Unterscheider
U
, der eine feste Anzahl von Anfragen
an das Orakel stellt und dessen Laufzeit, gemessen in der Anzahl ausgeführter Ope-
rationen (und ohne die Größe des Programmcodes zu berücksichtigen),
O
(
l
+
s
)
ist.
Schätzen Sie den Vorteil von
U
bezüglich
∈
B
geeignet ab und bestimmen Sie die
Programmlänge von
U
.
Aufgabe
4.9.24 (Funktionen statt Permutationen)
.
Beweisen Sie Aussage (4.8.3).
Hinweis: Stellen Sie sich dazu
S
PRP
U
0
und
S
PRF
U
0
als Algorithmen vor, die nicht
am Anfang
F
=
flip
(
P
{
0
,
1
}
l
)
bzw.
F
=
flip
(
F
{
0
,
1
}
l
)
berechnet, sondern stattdessen
y
i
=
