Cryptography Reference
In-Depth Information
Außerdem erhalten wir wegen
D
c
=
{
(
x
,
α
(
x
))
;
x
∈
P
}
:
1
1
)=
x
∈
P
p
(
x
,
α
(
x
)) =
x
∈
P
p
P
(
x
)
·
p
K
(
α
(
x
)) =
|
x
∈
P
p
P
(
x
)=
(
p
D
c
.
|
K
|
K
|
Damit ist
p
(
D
c
|
x
×
K
)=
p
(
D
c
)
gezeigt, und
D
c
und
x
×
K
sind für jedes
c
∈
C
und
x
∈
K
unabhängig. Daher ist das System
S
perfekt sicher.
Beispiel
Das One-Time-Pad, das wir zum Beginn des Kapitels beschrieben haben, ist ein
perfekt sicheres Kryptosystem. Und die Vigenère-Chiffre ist genau dann perfekt
sicher, wenn
(
k
)=
(
x
)
gilt und die Schlüssel gleichverteilt gewählt werden.
Bemerkung
Das Beispiel auf Seite 29 zeigt, dass die Voraussetzung
nicht weggelas-
sen werden kann, sie kann aber abgeschwächt werden (siehe Aufgabe 2.4).
|
C
|
=
|
P
|
Aufgaben
2.1
Ein
Palindrom
ist ein String, der von vorn und von hinten gelesen gleich
bleibt, z. B.
otto
,
stets
. Wie groß ist die Wahrscheinlichkeit bei zufälliger Wahl
ein Palindrom unter den Strings der Länge
n
über einem Alphabet
A
zu ziehen?
2.2 Das Geburtstagsparadoxon
≤
(a) Wählt man aus einer
m
-elementigen Menge
M
mit Zurücklegen
k
m
Ele-
mente, so ist die Wahrscheinlichkeit
p
m
,
k
dafür, dass die
k
Elemente alle von-
einander verschieden sind, gleich
1
.
−
1
i
=
0
k
i
m
p
m
,
k
=
−
(b) Zeigen Sie:
exp
,
k
(
k
−
1
)
≈
−
p
m
,
k
2
m
falls
k
viel kleiner ist als
m
(
Hinweis:
Benutzen Sie log
(
1
−
x
)
≈−
x
.)
1.2
√
m
, falls
p
m
,
k
=
1
≈
(c)
2
gilt.
(d) Wie viele Personen sollten sich in einem Raum aufhalten, damit die Wahr-
scheinlichkeit, dass zwei am selben Tag Geburtstag haben, etwa
Zeigen Sie, dass
k
1
2
ist.
Diese überraschend kleine Zahl ist für den Namen verantwortlich.
2.3
Folgern Sie, unter Verwendung der Bezeichnungen aus Abschnitt 2.3, direkt
aus der Definition, dass
p
(
x
×
K
)=
p
P
(
x
)
und
p
(
P
×
k
)=
p
K
(
k
)
gilt.
2.4
Zeigen Sie, dass im Satz von Shannon die Voraussetzung
|
C
|
=
|
P
|
abge-
|
| <
|
|
schwächt werden kann zu
C
2
P
.
2.5
Zeigen Sie, dass in einem perfekt sicheren Kryptosystem
(
P
,
C
,
K
,
f
,
g
)
jeder
Geheimtext mit derselben Wahrscheinlichkeit auftritt.
