Cryptography Reference
In-Depth Information
Satz 2.3
(Shannon)
Es sei
S
=(
)
ein Kryptosystem mit den Wahrscheinlichkeitsfunktionen p
P
auf P, p
K
auf K und p auf P
P
,
C
,
K
,
f
,
g
×
K mit p
(
x
,
k
)=
p
P
(
x
)
·
p
K
(
k
)
. Weiter gelte
|
=
|
|
=
|
|
K
C
P
|
.
S
Das Kryptosystem
ist genau dann perfekt sicher, wenn:
1
(
)
∈
(
)=
(
×
)=
i
Für jedes k
K gilt p
K
k
p
P
k
und
|
K
|
(
)
∈
(
)
→
ii
für jedes x
P ist die Abbildung f
x
,.
:
K
C bijektiv.
Beweis.
⇒
: Das System
S
sei perfekt sicher. Nach Lemma 2.2 ist die Abbildung
(
)
→
∈
|
|
=
|
|
f
x
,.
:
K
C
für jedes
x
P
surjektiv und wegen
K
C
auch bijektiv,
somit gilt (ii). Wir zeigen nun (i).
Es sei
c
∈
(
)
→
C
fest gewählt. Da die Abbildung
f
x
,.
:
K
C
bijektiv ist, existiert
zu jedem
x
∈
P
genau ein
α
(
x
)
∈
K
mit
f
(
x
,
α
(
x
)) =
c
. Damit ist eine Abbildung
→
→ α
(
)
α
:
P
K
,
x
x
definiert, und es gilt
∩
(
×
)=
{
(
α
(
))
}
D
c
x
K
x
,
x
.
Wir zeigen
α
(
P
)=
K
: Angenommen,
α
ist nicht surjektiv. Dann ist
α
wegen
|
K
|
=
auch nicht injektiv. Es seien
x
,
x
∈
x
, mit
k
:
x
)
=
=
α
(
)=
α
(
|
P
|
P
,
x
x
gewählt.
x
,
k
(
)=
(
)
S
Es folgt
f
ein
Kryptosystem ist (man beachte, dass nach Definition eines Kryptosystems die
Abbildung
f
x
,
k
f
, im Widerspruch zur Voraussetzung, wonach
(
)
→
α
(
)=
.,
k
:
P
C
injektiv ist, siehe Seite 9). Somit gilt
P
K
.
Wir nutzen nun aus, dass die Ereignisse
x
P
, unabhängig sind
und beachten die Definition der bedingten Wahrscheinlichkeit:
×
K
und
D
c
,
x
∈
(
∩
(
×
))
(
α
(
))
(
)
·
(
α
(
))
p
D
c
x
K
p
x
,
x
p
P
x
p
K
x
p
(
D
c
)=
p
(
D
c
|
x
×
K
)=
=
)
=
p
(
x
×
K
)
p
(
x
×
K
p
P
(
x
)
=
(
α
(
))
p
K
x
.
Für jedes
x
∈
P
gilt somit
p
K
(
α
(
x
)) =
p
(
D
c
)
, wobei
c
unser festgewähltes Ele-
(
α
(
))
ment aus
C
ist. Der Wert
p
K
x
, das ist die Wahrscheinlichkeit, den Schlüssel
α
(
K
,
haben wir gezeigt, dass jeder Schlüssel mit derselben Wahrscheinlichkeit auftritt.
Es folgt die Behauptung (i):
x
)
∈
K
zu wählen, ist also nicht von
x
abhängig. Da
α
surjektiv ist,
α
(
P
)=
1
p
K
(
k
)=
p
(
P
×
k
)=
für alle
k
∈
K
.
|
K
|
⇐
(
)
→
: Wegen der Bijektivität der Abbildung
f
x
,.
:
K
C
können wir die Schreib-
weise
α
(
x
)
aus dem ersten Teil des Beweises mit derselben Bedeutung benutzen.
∈
Für ein
x
P
ergibt sich wie eben
(
α
(
))
p
x
,
x
1
p
(
D
c
|
x
×
K
)=
)
=
p
K
(
α
(
x
)) =
.
p
(
x
×
K
|
K
|
