Cryptography Reference
In-Depth Information
In Worten:
P
x
ist die Wahrscheinlichkeitsfunktion auf den Chiffretexten, die man durch
Beobachten der Chiffretexte erhält, wenn man den festen Klartext
x
mit einem zufäl-
lig gewählten Schlüssel verschlüsselt; man rechnet schnell nach, dass es sich tatsächlich
um eine Wahrscheinlichkeitsverteilung handelt (siehe Aufgabe 3.7.7). Offensichtlich gilt
P
x
(
y
)=
P
(
y
|
x
)
für jeden aktiven Klartext
x
∈
X
P
X
und jedes
y
∈
Y
. Im Gegensatz zu
x
)
ist allerdings
P
x
(
y
)
auch für passive Klartexte definiert, was Definition (3.4.14)
motiviert.
Aus den obigen Überlegungen ergibt sich nun leicht folgender Satz.
P
(
y
|
Satz 3.4.1 (Charakterisierung informationstheoretische Sicherheit).
Es sei
V
=
S
[
P
K
]
ein KSV. Dann sind die folgenden Aussagen äquivalent:
a
. Das Kryptosystem
V
ist informationstheoretisch sicher.
b
. Das Kryptosystem
ist informationstheoretisch sicher bzgl. einer Klartextverteilung
mit ausschließlich aktiven Klartexten.
c
.Esgilt
P
x
=
P
x
V
für alle
x, x
∈
X
.
3.4.3
Gleichverteilung auf dem Schlüsselraum und possibilistische
Sicherheit
In diesem Abschnitt werden wir den Zusammenhang zwischen possibilistischer und infor-
mationstheoretischer Sicherheit untersuchen. Dabei werden wir zudem die besondere Be-
deutung der Gleichverteilung auf dem Schlüsselraum klären, auf die wir in Abschnitt 3.4.1
gestoßen sind.
Wir zeigen zunächst, dass informationstheoretische Sicherheit possibilistische Sicher-
heit impliziert.
Proposition 3.4.3.
Es sei
V
=
S
[
P
K
]
ein Kryptosystem mit Schlüsselverteilung, das
informationstheoretisch sicher ist. Dann ist
S
possibilistisch sicher und es gilt
|
K
|≥
|Y |≥|X|
.
Beweis.
Wir beweisen zuerst, dass
S
possibilistisch sicher ist. Da
V
informationstheo-
retisch sicher ist, ist
informationstheoretisch sicher bzgl. einer Klartextverteilung
P
X
mit nur aktiven Klartexten.
Es seien nun
x
V
X
und
k
0
∈ K
mit
e
(
x
0
,k
0
)=
y
.Dawir
P
X
(
x
0
)=
P
(
x
0
)
>
0
und
P
(
k
0
)
>
0
annehmen,
erhalten wir
P
(
y
)
>
0
. Aus Proposition 3.4.2 ergibt sich dann aber
0
<P
(
y
)=
P
(
y
∈
X
und
y
∈
Y
.Da
S
ein Kryptosystem ist, existieren
x
0
∈
|
x
)=
k
:
y
=
e
(
x,k
)
P
(
k
)
. Es muss also ein
k
∈
K
geben mit
e
(
x, k
)=
y
.Alsoist
S
possibilistisch sicher.
Die Ungleichung folgt nun aus Proposition 3.2.3.
Damit ist also im Fall der informationstheoretisch sicheren Kryptosysteme die gleiche
untere Schranke für die Anzahl der Schlüssel wirksam, wie wir sie von den possibilistisch
sicheren Kryptosystemen kennen: Um informationstheoretische Sicherheit garantieren zu
können, muss man so viele Schlüssel wie Klartexte benutzen! Insbesondere folgt
s
≥
l
im Fall
X
=
{
0
,
1
}
s
. Schlüssel müssen also im Durchschnitt mindestens
so lang sein wie Klartexte. Dies ist häufig nicht praktikabel. Wie allerdings bereits in
l
und
K
=
{
0
,
1
}
