Cryptography Reference
In-Depth Information
Durch analoge Rechnungen findet man
p
(
D
U
)=
p
(
D
V
)=
σ
und
p
(
D
W
)=
τ
.
(
×
)
∩
=
{
(
)
}
Es gilt
0
K
D
Z
0,
z
, also
p
((
0
×
K
)
∩
D
Z
) =
ατ
=
p
(
0
×
K
)
·
p
(
D
Z
)
.
Daher sind die Ereignisse 0
K
und
D
Z
unabhängig.
In gleicher Weise zeigt man die Unabhängigkeit der verbleibenden Ereignisse
×
×
×
×
×
1
K
und
D
Z
,
0
K
und
D
W
,
1
K
und
D
W
,
0
K
und
D
V
,
1
×
K
und
D
V
,
0
×
K
und
D
U
,
1
×
K
und
D
U
.
Somit ist das Kryptosystem
S
=(
P
,
C
,
K
,
f
)
perfekt sicher.
2.3.2 Kennzeichnung perfekt sicherer Systeme
=
∅
Wir nehmen ab jetzt an, dass alle definierten Ereignisse
eine Wahrschein-
lichkeit
0 haben. Andernfalls kann man die Mengen
P
bzw.
K verkleinern
, d. h.,
man entfernt Elemente aus den Mengen
P
und
K
, die mit Wahrscheinlichkeit 0
ausgewählt werden. Als Konsequenz sind die Ereignisse
D
c
und
x
>
×
K
genau
dann unabhängig, wenn
(
∩
×
)=
(
)
·
(
×
)
⇔
(
|
×
)=
(
)
p
D
c
x
K
p
D
c
p
x
K
p
D
c
x
K
p
D
c
⇔
p
(
x
×
K
|
D
c
)=
p
(
x
×
K
)
.
Wir stellen nun fest, dass bei einem perfekt sicheren Kryptosystem zu jedem Klar-
text
N
C
N
und jedem Geheimtext
ein Schlüssel existiert, durch den der Klartext
in den Geheimtext
C
chiffriert wird.
Lemma 2.2
Es sei
S
=(
P
,
C
,
K
,
f
,
g
)
ein perfekt sicheres Kryptosystem. Dann gibt es zu jedem
∈
∈
∈
(
)=
(
)
→
x
P und c
C stets ein k
K mit f
x
,
k
c. Kurz: Die Abbildung f
x
,.
:
K
C
ist für jedes x
∈
P surjektiv. Insbesondere gilt
|
K
| ≥ |
C
| ≥ |
P
|
.
Beweis.
Es seien
x
∈
P
und
c
∈
C
.Da
S
perfekt sicher ist, sind die Ereignisse
x
×
K
und
D
c
unabhängig, das bedeutet
p
((
×
)
∩
)=
(
×
)
·
(
)
>
x
K
D
c
p
x
K
p
D
c
0.
(
×
)
∩
=
∅
∈
(
)
∈
(
×
)
∩
Folglich gilt
x
K
D
c
. Ist also
k
K
mit
x
,
k
x
K
D
c
, so gilt
f
(
x
,
k
)=
c
. Daher ist die Abbildung
f
(
x
,.
)
:
K
→
C
surjektiv, d. h.
|
K
| ≥ |
C
|
.
|
| ≥ |
|
Die Ungleichung
C
P
gilt nach der Definition eines Kryptosystems (vg
l.
Seite 9).
Aus diesem Lemma ergibt sich für einen Angreifer auf ein perfekt sicheres Sys-
tem, dass hinter einem Geheimtext
C
jeder mögliche Klartext
N
verborgen sein
kann.
Wir beweisen den Hauptsatz dieses Kapitels. Nach ihm muss in einem perfekt si-
cheren Kryptosystem die Wahrscheinlichkeitsverteilung auf dem Schlüsselraum
die Gleichverteilung sein.
