i
i
“main 2013/4/10 15:19 page 58 #70
i
i
i
i
i
i
58 Kryptographie
Als Verbesserungen zur monoalphabetischen Substitution ergibt sich zum einen eine
gleichmäßigere Verteilung der Symbole und zum anderen existieren keine verräte-
rischen Doppellaute mehr.
Dieses Verfahren galt lange Zeit als unangreifbar, weil die Häufigkeitsanalyse
nicht (direkt) anwendbar ist. Aber man hat das Problem, dass gleiche Textstellen
gleich verschlüsselt wer den, wenn der Abstand zwischen diesen ein ganzzahliges
Vielfaches der Schlüssellänge
d ist. Darum bemühen wir noch einmal das Beispiel
von gerade eben, um das Problem zu verdeutlichen.
guzrjuwdygtqzvpeogsrvgsryhpoobekkrpyozdvkoe
iufebubpgkuchkglqjhslxhphtatqahpvtccwnslvzoyg
hmyrxhspgwyexoyfngpykbekrwxekodwywohyvzrztcrs
hshrsqwkmprlhshjslwngshgrlekswltsquuaekkhchk
hsuuirkzvpvnceioteblspwuie
Hier sieht man, dass das häufige Wort the in der vorletzt en Zeile zweimal mit hsh
verschlüsselt wurde.
Wenn wir nun von der Annahme ausgehen, dass die Schlüssellänge oder Viel-
fache davon bekannt ist, dann können wir das Vigenère-Verfahren folgendermaßen
knacken: Sei also die Schlüssellänge oder ein Vielfaches davon bekannt und hier mit
d bezeichnet. Wir führen die Häufigkeitsanaly se pro Spalte aus, d. h. wir notieren uns
Spalten und schreiben in jede Spalte
i alle verschlüsselten Symbole, deren Position
kongruent
i modulo d sind. Nun sind alle Zeichen in einer Spalte gleich verschlüssel t
und wir können jede einzelne Spalte angreifen und entschlüsseln mit Brute-Force,
Häufigkeitsanalyse oder ähnlichem.
Um uns vor dieser Art des Angriffs zu schützen, sollten wir als erste Maßnahme
die Schlüssellänge d geheim halten. Tatsächlich gibt es weitere und relativ einfache
Methoden, eine Häufigkeitsanalyse zu erschweren. Eine solche Möglichkeit bietet die
verlustfreie Datenkompression (häufig auch als Quellencodierung bezeichnet). Da hier-
durch Redundanzen im Text eliminiert werden, wirkt ein komprimierter Text wie ein
Zufallsstring; insbesondere haben alle Symbole in etwa dieselbe Häufigkeit.
2.4 Häufigkeitsanalyse und Koinzidenzindex
Wir haben die Häufigkeitsanalyse ber eits als Verfahren kennen gelernt, mit dem man
z. B. die monoalphabetische Substitution brechen kann. Hier erweitern wir diese Me-
thode. Wir haben schon gesehen, wie man mit Hilfe einer Häufigkeitsanalyse das
Vi genère-Verfahren brechen kann, wenn die Schlüssellänge oder ein Vielfaches da-
von bekannt ist. Der Angriff mittels Koinzidenz-Index dient nun gerade dazu, ein
Vielfaches der Schlüssellänge zu ermitteln. Seien
x = x
1
···x
n
und x
= x
1
···x
n
i
i
main”—2013/4/10—15:19—page59—#71
i
i
i
i
i
i
Häufigkeitsanalyse und Koinzidenzindex 59
zwei Texte der Länge n über dem Alphabet Σ.IhrKoinzidenz-Index κ(x,x
) ist defi-
niert als
κ(x,x
) =
1
n
n
i=1
δ(x
i
,x
i
)
Hierbei bezeichnet δ das sogenannte Kronecker-Delta (nach Leopold Kronecker, 1823–
1891):
δ(u, v) =
1
falls u = v
0
sonst
Der Koinzidenz-Index misst die relative ufigkeit für das Zusammentreffen gleicher
Buchstaben bei übereinandergelegten Texten
x und x
. Wenn wir also annehmen,
dass
x und x
aus einem gleichv e rteilten Zufallsexperiment entstanden sind, dann
folgt daraus
E[κ] =
1
N
; hierbei bezeichnet E den Erwartungswert und N =|Σ|
die Alphabetgröße. Wenn die Buchstaben nicht gleichverteilt sind, dann wächst die
Wahrscheinlichkeit für eine Übereinstimmung. Daher gilt für Zufallstexte über einer
beliebigen Verteilung der Buchstaben die Abschätzung
1
N
E[κ] 1
Konkret erhalten wir dann bei einem Alphabet mit N = 26 bei einer Gleichvertei-
lung der Buchstaben den Wert
E[κ] = 3,8%. Experimente mit natürlichsprachlichen
Texten über derselben Sprache haben mit
E[κ] 7% einen deutlich höheren Erwar-
tung swert als im Zufallsexperiment oben ergeben. Wichtig bei Substitutionschiffren
ist aber vor allem, dass der Koinzidenz-Index zweier Texte sich bei gleicher Verschlüs-
selung nicht ändert:
κ(x,x
) = κ(c(x),c(x
))
Dies wollen wir uns nun zu Nutze machen, um d zu bestimmen. Sei also der Ge-
heimtext
y gegeben. Dann bestimmen wir zunächst für k N den Wert κ
k
= κ(y,
σ
k
(y)), wobei hier σ
k
(y) die zyklische Verschiebung von y um k Zeichen nach
links ist. Wenn nun eines dieser
k ein Vielfaches von d ist, so ist κ
k
Koinzidenz zwei-
er gleich verschlüsselter natürlicher Texte . Damit ist zu erwarten, dass
κ
k
im Bereich
von
7% liegt. Ist dies nicht der Fall, so liegt der Wert darunter. Dies wollen wir uns in
einem Beispiel verdeutlichen.
Der Text aus The Gold Bug“ hat die Läng e
n = 203.Wenny die Vigenére-
Verschlüsselung dieses Texts mit dem Geheimwort
gold ist, dann gilt:
k 1234 5678910111213
n · κ
k
6 11 5 17 13 7 4 17 9 9 10 24 6

Get Diskrete algebraische Methoden now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.