Cryptography Reference
In-Depth Information
Bemerkung
Wie in Aufgabe 1.5 gezeigt werden soll, gilt
∑
a
∈
Z
q
p
a
≥
1
q
; und Gleichheit gilt
hierbei genau dann, wenn
p
a
=
p
b
für alle
a
,
b
∈
Z
q
, d. h. wenn eine Gleichver-
teilung der Buchstaben herrscht.
Bei monoalphabetischer Chiffrierung bleibt der Index
I
vor und nach der Ver-
schlüsselung offenbar unverändert. Daher ist
I
ein Indikator dafür, ob mo-
noalphabetisch oder polyalphabetisch verschlüsselt wurde. Bei polyalphabeti-
scher Verschlüsselung wird
I
(
x
)
(
x
)
nämlich kleiner, sofern die Schlüsselbuchstaben
gleichverteilt gewählt wurden.
Für die folgende Betrachtung nehmen wir an, dass
x
ein mit der Vigenère-Chiffre
verschlüsselter deutscher Text sei. Die Schlüssellänge, die wir näherungsweise
bestimmen wollen, sei
können wir
mit der oben angegebenen Formel bestimmen, es sind hierbei nur die Häufigkei-
ten der einzelnen Buchstaben zu ermitteln.
Nun ermitteln wir den Friedman'schen Koinzidenzindex
I
. Den Friedman'schen Koinzidenzindex
I
(
x
)
(
)
x
zu dem Geheim-
text
C
=
x
1
···
x
n
erneut, aber näherungsweise und in Abhängigkeit von der
(
)
Länge
des Schlüsselworts. Die näherungsweise Formel für
I
x
, die wir erhal-
ten, können wir nach
auflösen. Daraus gewinnen wir eine Näherung für
.
Der Übersicht wegen stellen wir uns vor, der Text sei in ein
-spaltiges Schema
eingetragen.
x
1
x
2
...
x
x
x
...
x
2
+
1
+
2
.
.
.
.
x
r
+
1
...
x
n
Es liegt dann in jeder Spalte eine Caesar-Chiffrierung vor. Damit ist der Koinzi-
denzindex in jeder Spalte in etwa der Index eines (durchschnittlichen) deutsch-
sprachigen Textes:
I
(
x
k
,
x
k
+
,
x
k
+
2
,...
)
≈
I
D
.
Die Wahrscheinlichkeit, in zwei verschiedenen Spalten ein Paar aus gleichen
Buchstaben zu wählen, ist in etwa
I
G
(hierbei nehmen wir an, dass das Schlüs-
selwort
hinreichend zufällig
und
groß genug ist, sodass also über die Spalten
verteilt in etwa eine Gleichverteilung der Buchstaben besteht).
Wir bestimmen nun den Koinzidenzindex. Dazu ist die Wahrscheinlichkeit zu
bestimmen, dass man bei zufälliger Wahl von zwei Buchstaben
x
i
,
x
j
,
i
=
j
, aus
dem Geheimtext
x
j
auswählt. Um
diese Wahrscheinlichkeit zu bestimmen, ermitteln wir zunächst, wie viele Buch-
stabenpaare es im Geheimtext bei der obigen Anordnung gibt.
Wenn wir zwei Buchstaben
x
i
und
x
j
zufällig wählen, dann liegen beide Buch-
staben
x
i
und
x
j
entweder in ein und derselben Spalte oder sie liegen in zwei
verschiedenen Spalten.
C
=
x
1
···
x
n
zwei gleiche Buchstaben
x
i
=
