Cryptography Reference
In-Depth Information
zu schicken. Das Spiel ist für Eva gewonnen, wenn
b
=
b
gilt, sie also das Bit
b
richtig
geraten/bestimmt hat. Gibt es eine Angreiferin Eva (mit beschränkten Ressourcen), für
die die Wahrscheinlichkeit, das Spiel zu gewinnen, »nicht gering« ist, dann bezeichnen
wir das Kryptoschema als unsicher.
Dieses Spiel spiegelt zum einen das erwähnte Bedrohungsszenarium wider: Eva darf
sich beliebige Klartexte verschlüsseln lassen (Angriff mit Klartextwahl). Wir werden zu-
dem annehmen, dass die Eva im Spiel zur Verfügung stehenden Ressourcen (Laufzeit,
Anzahl Orakelanfragen) beschränkt sind.
Zum anderen fasst das Spiel auch das beschriebene Sicherheitsziel: Würde Eva (im
Rahmen ihrer Rechenkapazität) aus einem Chiffretext Informationen über den zugehö-
rigen Klartext gewinnen können, dann könnte sie
z
0
und
z
1
so konstruieren, dass sie
feststellen könnte, ob
z
0
oder
z
1
von Charlie verschlüsselt wurde. Sie könnte also das Bit
b
bestimmen und das Spiel gewinnen, zumindest mit einer gewissen Erfolgswahrschein-
lichkeit. Wie gesagt, erlauben wir, dass der Chiffretext Informationen über die Länge des
Klartextes preisgibt. Aus diesem Grund verlangen wir im Spiel, dass die beiden Ange-
botshälften,
z
0
und
z
1
, die gleiche Länge haben. Ansonsten könnte Eva leicht zwischen
der Verschlüsselung von
z
0
und derjenigen von
z
1
unterscheiden, indem sie die beiden
Angebotshälften so wählt, dass sie verschiedene Längen haben.
Im Hinblick auf Szenarium 3 kann man das Spiel auch wie folgt interpretieren: Unter
einem Angebot
(
z
0
,z
1
)
kann man sich vorstellen, dass Eva weiß, dass Alice
z
0
oder
z
1
an Bob schicken möchte (Eva hat
z
0
und
z
1
sogar selbst bestimmt). Eva weiß aber nicht,
welchen der beiden Klartexte Alice nun tatsächlich an Bob schickt. Es ist Evas Aufgabe,
dies anhand des von Alice gesendeten Chiffretextes herauszufinden. Dabei darf sie sogar
alle anderen Klartexte, die Alice an Bob schickt, selbst bestimmen. Insbesondere dürfen
unter diesen Klartexten auch
z
0
und
z
1
sein, d. h., Eva kann bestimmen, dass Alice
z
0
und/oder
z
1
mehrfach sendet. Trotzdem sollte Eva nicht in der Lage sein, zu entschei-
den, welche Angebotshälfte Alice nach Unterbreitung des Angebots,
(
z
0
,z
1
)
, tatsächlich
an Bob geschickt hat. Dies modelliert, dass, wie gefordert, das mehrfache Senden dessel-
ben Klartextes verborgen bleibt. Die Tatsache, dass Eva im Spiel alle Chiffretexte sieht,
modelliert, dass sie den Kommunikationskanal zwischen Alice und Bob abhören kann.
Bevor wir das Spiel präziser fassen, legen wir in der folgenden Definition fest, dass Eva
als Algorithmus modelliert wird.
Definition 5.3.1 (Angreifer). Es sei
l>
0
.Ein
l
-Angreifer
oder einfach
Angreifer
(adversary)
A
auf symmetrische
l
-Kryptoschemen ist ein zufallsgesteuerter Algorithmus
A
(
H
:
l∗
}
∗
):
{
0
,
1
}
→{
0
,
1
{
0
,
1
}
, der von der Form
(
AF
,
AG
)
,
(5.3.1)
AF
AG
ist. Dabei bezeichnet
ein Algorithmenstück, das
Finder (find)
genannt wird, und
ein Algorithmenstück, das
Rater (guess)
genannt wird. Der Finder
AF
gibt am Ende ein
l∗
, von Klartexten gleicher Länge aus (d. h.,
Paar
(
z
0
,z
1
)
,
z
0
,z
1
∈{
0
,
1
}
|
z
0
|
=
|
z
1
|
),
das
Angebot
mit
linker
bzw.
rechter Angebotshälfte
. Der Rater
AG
erwartet zunächst
}
∗
, und gibt am Ende ein Bit
b
,die
Vermutung
von
ein Argument, die
Probe
y
∈{
0
,
1
A
aus. Sowohl
erwarten als Argument das Verschlüsselungsorakel
H
,
an das sie beliebige Anfragen stellen dürfen. In einem Lauf von
A
, im Rahmen eines
AF
als auch
AG
