Cryptography Reference
In-Depth Information
Betrachten wir dazu nochmals Beispiel 4.6.6, wobei wir nun die Programmzeile
y
3
=
B
(
Parameter
)
durch
y
3
=
B
(
O
(
·
))
ersetzen. Dabei bezeichnet
O
ein Orakel, das wir als
durch einen zufallsgesteuerten Algorithmus realisiert annehmen und an das der ebenfalls
zufallsgesteuerte Algorithmus
B
maximal
q
Anfragen stellt. Ist die Laufzeit von
O
in
jedem Aufruf durch
t
O
beschränkt, dann hat der zugehörige Produktraum zum betrach-
teten Pseudocode die folgende Form:
Ω
prod
A
l
1
l
2
t
B
t
O
t
O
=
{
0
,
1
}×{
0
,
1
}
×{
0
,
1
}
×{
0
,
1
}
×{
0
,
1
}
×···×{
0
,
1
}
.
q
-
fach
Steht
O
(
·
)
im obigen Beispiel für eine Funktion (oder einen deterministischen Algorith-
mus), dann werden im Produktraum zu
A
natürlich keine Zufallskomponenten für
O
(
·
)
vorgesehen.
4.7
Algorithmische Sicherheit von Block-Kryptosystemen
Nachdem wir uns schon mehrere Block-Kryptosysteme angesehen haben, wollen wir uns
nun der Frage zuwenden, was es bedeutet, dass ein Block-Kryptosystem sicher ist, natür-
lich unter der Annahme, dass es in Szenarium 2 verwendet wird.
Zuerst einmal wollen wir uns überlegen, unter welchen Umständen wir ein Kryptosys-
tem als unsicher ansehen wollen. Dazu sind gemäß der Abschnitte 2.3 und 2.4 zwei Dinge
zu klären: die Sicherheitsziele und die Bedrohungsszenarien.
Zunächst wenden wir uns den Bedrohungsszenarien zu. Gemäß Szenarium 2 gehen wir
von
Angriffen mit Klartextwahl
aus (siehe auch Abschnitt 2.4.1). Eva hat also Zugriff auf
die Verschlüsselungsmaschinerie und kann sich Klartexte ihrer Wahl verschlüsseln lassen.
Dabei gehen wir, gemäß Abschnitt 2.4.2, davon aus, dass Eva nur eine feste, beschränkte
Anzahl von Rechenoperationen durchführen kann (
konkrete Sicherheit
).
Betrachten wir nun die Sicherheitsziele, also die Frage, inwieweit die zu übermitteln-
den Klartexte gegen Aufdeckung geschützt werden müssen/können. Wir hatten uns dazu
in Abschnitt 4.1 bereits überlegt, dass Substitutionskryptosysteme diesbezüglich »opti-
mal« sind: Wenn Eva von
N
Klartexten
N
0
Klartexte abgefragt hat und Alice dann einen
(neuen) Chiffretext zu einem neuen Klartext sendet, dann weiß Eva natürlich, dass der
zum Chiffretext gehörende Klartext nicht einer der
N
0
abgefragten Klartexte sein kann,
aber ansonsten ist jeder der anderen
N − N
0
Klartexte möglich. Die Information, die
Eva über den neuen Klartext erhält, ist also minimal. Das Problem mit Substitutions-
kryptosystemen ist nur, dass sie, wie wir uns bereits überlegt haben, völlig unpraktikabel
sind. Allerdings können sie dazu dienen, die Sicherheit von Block-Kryptosystemen zu de-
finieren. Die Idee ist denkbar einfach. Wenn jeder ressourcenbeschränkte Angreifer nicht
oder nur mit verschwindend geringer Wahrscheinlichkeit unterscheiden kann, ob er mit
dem eigentlichen Block-Kryptosystem interagiert oder mit dem Substitutionskryptosys-
tem, dann ist das Block-Kryptosystem (fast) so sicher wie das Substitutionskryptosystem,
bietet also etwa das gleiche Maß an Sicherheit.
Den erwähnten Angreifer werden wir ab jetzt als »Unterscheider« bezeichnen, da seine
Aufgabe sein wird, zwischen dem eigentlichen Block-Kryptosystem und dem Substituti-
onskryptosystem zu unterscheiden.
