Cryptography Reference
In-Depth Information
l
.
d
(
y,k
)=
y
⊕
k,
für alle
x, k, y
∈{
0
,
1
}
(3.2.14)
Zum Beispiel ergibt sich für
l
=5
und
k
= 10100
,dass
01000
der Chiffretext zu
11100
ist.
Offensichtlich handelt es sich tatsächlich um ein Kryptosystem. Denn es gilt
(
x
⊕
k
)
⊕
k
=
x⊕
(
k ⊕k
)=
x⊕
0
l
=
x
für alle
x, k ∈{
0
,
1
}
l
, womit die Dechiffrierbedingung erfüllt
l
, was zeigt, dass (3.2.4) gilt.
Die wesentliche Frage, die wir nun stellen sollten, ist natürlich, ob die bisher kennenge-
lernten Kryptosysteme sicher sind und was dies überhaupt bedeuten könnte. Beschränken
wir uns zunächst einmal auf den Fall
l
=1
für das Vernamsystem, in dem nur ein ein-
zelnes Bit übertragen wird. Nehmen wir weiterhin an, Eva kenne alle Bestandteile des
Kryptosystems abgesehen von dem geheimen Schlüssel
k
. Dann kann Eva aus der Beob-
achtung eines einzelnen Chiffretextes
y
nichts über den Klartext schließen, was sie nicht
auch schon vorher gewusst hätte: Wenn sie den Chiffretext
y
=0
beobachtet, kann der
Klartext aus ihrer Sicht
0
oder
1
sein, denn Eva weiß nicht, ob der Schlüssel
k
gleich
0
oder
1
verwendet wurde. Wenn Eva den Chiffretext
y
=1
beobachtet, dann sind aus Evas
Sicht ebenfalls beide Klartexte möglich. (Natürlich gewinnt sie durch die Beobachtung
des Chiffretextes die Erkenntnis, dass überhaupt eine Nachricht verschickt wurde. Diese
Tatsache zu verbergen, ist Gegenstand der sogenannten
Steganographie
, die in diesem
Buch allerdings nicht behandelt wird.)
Wir werden diese Überlegung zu einer Definition erheben:
0
l
für alle
x
ist. Außerdem gilt
x
=
x
⊕
∈{
0
,
1
}
Definition 3.2.2 (possibilistisch sicher). Ein Kryptosystem
heißt
possibilistisch si-
cher (possibilistically secure),
wenn es zu jedem Chiffretext
y
und zu jedem Klartext
x
einen Schlüssel
k
gibt, so dass
e
(
x, k
)=
y
gilt.
S
Dies kann auch anders formuliert werden:
Bemerkung
3.2.1
.
Es sei
S
ein Kryptosystem. Dann sind die folgenden Aussagen äqui-
valent:
a
.
ist possibilistisch sicher.
b
. Für jedes
x ∈ X
gilt Bild
(
e
(
x, ·
)) =
Y
.
S
Wir können nun sofort erkennen, dass das Kryptosystem aus (3.2.1)
nicht
possibilis-
tisch sicher ist, denn wenn Eva
C
beobachtet, muss
b
der Klartext sein. Es gibt zu
a
und
C
keinen Schlüssel
k
mit
e
(
a
,k
)=
C
.
Wie sieht es nun mit den Vernam-Kryptosystemen aus?
Proposition 3.2.1 (Sicherheit der Vernamsysteme).
Für jedes
l>
0
ist das Vernamsys-
tem der Länge
l
possibilistisch sicher.
Beweis.
Es seien
x, y ∈{
0
,
1
}
l
beliebig. Wir müssen zeigen, dass es ein
k ∈{
0
,
1
}
l
gibt,
so dass
e
(
x, k
)=
y
gilt. Dies ist aber der Fall, wenn wir
k
=
x
⊕
y
setzen, denn dann gi
lt
y
=0
l
e
(
x, k
)=
x
⊕
(
x
⊕
y
)=(
x
⊕
x
)
⊕
⊕
y
=
y
.
Wir betrachten ein weiteres Beispiel.
