Cryptography Reference
In-Depth Information
Lemma 1.2
Der Friedman'sche Koinzidenzindex I
(
)
=
···
x
n
gibt die Wahr-
scheinlichkeit dafür an, dass bei zufälliger Wahl zweier Buchstaben x
i
,
x
j
,i
x
für einen String x
x
1
=
j, aus dem
String x diese beiden Buchstaben gleich sind.
Beweis.
Die Anzahl der ungeordneten Paare
x
i
,
x
j
mit
i
=
j
und
x
i
=
x
j
=
a
ist
gleich
h
a
2
h
a
(
h
a
−
1
)
=
,
2
=
und die Anzahl aller ungeordneten Paare
x
i
,
x
j
mit
i
j
ist
n
2
(
−
)
n
n
1
=
.
2
Damit ergibt sich wegen
h
a
2
(
)
1
)=
∑
a
)
∑
a
(
)
=
(
−
)
I
x
h
a
h
a
1
n
2
(
−
(
n
n
1
∈
Z
q
∈
Z
q
die Behauptung.
Wir bestimmen nun den Koinzidenzindex für einen deutschen
Durchschnittstext
und für einen Text, bei dem alle Buchstaben gleich oft vorkommen. Dazu stellen
wir vorab fest: Es sei
x
Z
q
. Angenom-
men, wir kennen die Wahrscheinlichkeit
p
a
, mit der wir den Buchstaben
a
in
x
bei zufälliger Wahl ziehen. Dann ist die Zahl
=
x
1
···
x
n
ein String über dem Alphabet
∑
a
∈
Z
q
p
a
in etwa die Wahrschein-
lichkeit dafür, dass wir bei zufälliger Wahl von zwei Buchstaben im Text
x
zwei
gleiche Buchstaben ziehen, d. h.
)
≈
∑
i
p
i
(
I
x
.
∈
Z
26
Da man bei einem deutschen
Durchschnittstext
natürlich die Wahrscheinlichkei-
ten
p
a
,
p
b
,
p
c
, . . . für die 26 Buchstaben des Alphabets kennt (vgl. die Grafik auf
Seite 5), erhält man so leicht den Koinzidenzindex
I
D
für einen solchen Text. Es
gilt
≈
I
D
0.0762 .
Und nun nehmen wir an, dass die Buchstaben in dem Text
x
=
x
1
···
x
n
alle
1
q
=
∈
Z
q
. Im Fall
q
=
gleichverteilt sind, d. h.
p
a
für alle
a
26 erhalten wir für
einen solchen Text mit
gleichverteilten
Buchstaben den Index
≈
I
G
0.0385 .
Man bedenke, dass man bei der (polyalphabetischen) Vigenère-Chiffre eine sol-
che Gleichverteilung aller Buchstaben im Geheimtext als idealisiertes Ziel hat.
