Koinzidenzindex (Kappa)

Kategorisierung:	Klassisch / Substitution / polyalphabetisch
Siehe auch:	Shannon Entropie, Kappa-Test
Herkunft / Verwendung:	Der Koinzidenzindex ("Kappa", engl: Index of coincidence, Abkürzung: IC) gibt die Wahrscheinlichkeit an, mit der zwei zufällig aus einem Text herausgegriffene Buchstaben übereinstimmen. Dieser ist für unterschiedliche Sprachen verschieden und ist von der Häufigkeitsverteilung der Buchstaben innerhalb der Sprache abhängig. Man erhält ihn durch eine statistische Auswertung der Buchstaben eines Textes. Mit ihm können verschlüsselte Text auf sprachliche Eigenschaften untersucht werden. Die Methode wurde von William Friedman entwickelt und 1922 in The index of coincidence and its applications in cryptography (zu deutsch: "Der Koinzidenzindex und seine Anwendungen in der Kryptografie") veröffentlicht. Anhand des Koinzidenzindexes kann man darauf schließen, ob ein Chiffretext aus monoalphabetischer oder polyalphabetischer Substitution stammt. Da es bei der monoalphabetischen Substitution nur ein Schlüsselalphabet gibt, werden die Buchstaben im Prinzip nur untereinander ausgetauscht. Die Häufigkeitsverteilung der einzelnen Buchstaben untereinander bleibt gleich. Wenn z. B. ein 'E' durch ein 'X' ausgetauscht wird, dann wird das 'X' im Chiffrat ebenfalls der häufigste Buchstabe sein. Mit der Häufigkeitsverteilung bleibt auch der Koinzidenzindex gleich. Entspricht der Koinzidenzindex eines Chiffrats also annähernd dem einer natürlichen Sprache, ist die Substitution monoalphabetisch und es kann ggf. sogar auf die verwendete Sprache zurückgeschlossen werden. Enthält die monoalphabetische Chiffre außer der Substitution auch eine Transposition, so hat das im Übrigen keinen Einfluss auf den Koinzidenzindex, da hier nur die Positionen der Buchstaben vertauscht werden. Eine einfache Transposition hat niemals eine Auswirkung auf den Koinzidenzindex. Entspricht der Koinzidenzindex eines Chiffrats aber mehr dem Koinzidenzindex eines gleichverteilten Buchstabensalates, dann ist von einer polyalphabetischen Substitution auszugehen, denn diese wurde ja gerade dazu ersonnen, die ursprüngliche Häufigkeitsverteilung zu verschleiern. Der Koinzidenzindex findet weiterhin Anwendung im Friedman Test und dem Kappa-Test. Dort werden die Koinzidenzindexes jeweils testweise für die Gruppen von Buchstaben berechnet, wie sie bei einer bestimmten Schlüssellänge gruppiert werden. Bei der richtigen Schlüssellänge sollte der Kappa-Wert (der Koinzidenzindex) der höchsten sein und dem Koinzidenzindex einer natürlichen Sprache entsprechen. So kann auf die vermutliche Schlüssellänge zurückgeschlossen werden.

Beschreibung des Verfahrens

Vereinfacht gesagt pickt man sich zwei zufällige Buchstaben aus einem Chiffrat heraus und schaut, ob diese übereinstimmen (koexistieren). Das macht man über alle Buchstaben und erhält einen statistischen Wert, eben den Koinzidenzindex.

Der Koinzidenzindex wird ermittelt, indem man die jeweiligen Anzahlen n_i der unterschiedlichen Buchstaben in einem Chiffrat zählt. Das heißt, es wird gezählt, wie oft das 'A', das 'B' usw. in einem verschlüsselten Text vorkommt. Die Wahrscheinlichkeit berechnet sich nach dem Muster Anzahl der zutreffenden Fälle geteilt durch die Anzahl der möglichen Fälle. Die Anzahlen werden also mit den Anzahlen minus 1 multipliziert und für alle Buchstaben aufsummiert. Anschließend wird die Summe dividiert durch die Textlänge N multipliziert mit der Textlänge minus 1:



oder anders ausgedrückt für ein Alphabet von A bis Z:

IC = ( (Anz("A") * Anz("A")-1) + (Anz("B") * Anz("B")-1) + ... + (Anz("Z") * Anz("Z")-1) ) / (Len($text) * (Len($text)-1) )

Der Koinzidenzindex für einen Text mit nur einem, immer gleichen Buchstaben (z. B. "AAAAAAAAAAAAAAAAAAAAAAAAAA") wird 1, also 100% sein. Weil jeder herausgepickte erste Buchstabe mit jedem herausgepickten zweiten Buchstabe übereinstimmt.

Der Koinzidenzindex für einen Text, dessen Grundlage die 26 Buchstaben des Alphabets sind und der nur unterschiedliche Buchstaben enthält (also "ABCDEFGHIJKLMNOPQRSTUVWXYZ") wird 0 sein, weil kein herausgepickter erster Buchstabe mit keinem herausgepickten zweiten Buchstabe übereinstimmt.

Der Koinzidenzindex für einen Text, dessen Grundlage die 26 Buchstaben des Alphabets sind und der alle Buchstaben des Alphabets in gleicher Anzahl enthält (z. B: "ABCDEFGHIJKLMNOPQRSTUVWXYZ" x-mal hintereinander) wird 1/26 oder 3.85% sein, weil es für jeden herausgepickten ersten Buchstaben 26 Alternativen für den zweiten herausgepickten Buchstaben gibt.

Der Koinzidenzindex für ausgewählte Sprachen ist:

Sprache	Koinzidenzindex	in Prozent
malaysisch	0.085	8,5%
französisch	0.078	7,8%
hebräisch	0.077	7,7%
japanisch	0.077	7,7%
deutsch	0.076	7,6%
italienisch	0.076	7,6%
arabisch	0.076	7,6%
spanisch	0.075	7,5%
portugiesisch	0.075	7,5%
finnisch	0.074	7,4%
dänisch	0.070	7.0%
esperanto	0.069	6,9%
griechisch	0.069	6,9%
norwegisch	0.069	6,9%
englisch	0.065	6,5%
serbisch	0.064	6,4%
schwedisch	0.063	6,3%
polnisch	0.061	6,1%
russisch	0.053	5,3%
tschechisch	0.051	5,1%
gleichverteilt ("starke" Chiffre)	0.0385	3,85%

Das heißt also, dass es für einen deutschen Text etwa doppelt so wahrscheinlich ist (7,6%), dass zwei zufällig ausgewählte Buchstaben aus einem Text übereinstimmen wie in einem Text mit gleichverteilten Buchstaben (3,85%), der entstehen würde, hätte man einen Wüfel mit 26 Seiten und würden damit einen Text rein zufällig auswürfeln. Und wie er z. B. in einem chiffrierten Text aus polyalphabetischer Substitution (etwa der Vigenere Chiffre) oder mit Anwendung von Homophonen stammen könnte. Im Grunde alle Verfahren, die zum Zweck haben, die spezifische Häufigkeitsverteilung einer Sprache aufheben. Eben weil dies historisch betrachtet ein sehr beliebter Angriffsvektor auf einen chiffrierten Text ist.

Am Koinzidenzindex kann man erkennen, ob es sich um eine monoalphabetische oder polyalphabetische Substitution handelt, denn im ersten Fall würde der Index gleich bleiben, also der eingesetzen Sprache entsprechen und im zweiten Fall eher zu 3,85% (Gleichverteilung) tendieren. Außerdem kann er Aufschlüsse zur eingesetzten Sprache geben, allerdings nur bei langen Texten, weil die Differenz zwischen dem deutschen und englischen Index doch eher marginal ist.

Der Koinzidenzindex ist Grundlage für den Kappa-Test und den Friedman Test, mit dem sich die Länge des verwendeten Schlüssels z. B. einer Vigenere Chiffre bestimmen lässt.

Aber auch bei der Kryptoanalyse anderen Verfahren kann der Koinzidenzindex hilfreich sein, etwa bei der Dechiffrierung eines Geheimtextes einer Enigma. Ein Enigma-Chiffrat wird im Ausgangszustand einen Koinzidenzindex nahe 0.0385 haben. Auch mit irgendeiner (falschen) Einstellung der vielfältigen Enigma-Optionen (Walzenstellungen, Steckbrett etc.) wird dieser Wert so bleiben, wenn man versucht, das Ursprungschiffrat damit zu dechiffrieren. Wenn man allerdings eine oder mehrere der Optionen richtig eingestellt hat, dann wird sich der Koinzidenzindex des Entschlüsselungsversuchs dem der natürlichen Ausgangssprache des Klartextes annähern. Das zwar nur jedesmal minimal, aber in vielen Fällen doch noch erkennbar. Behält man die "guten" Optionen bei und probiert die vermeintlich falschen weiter durch, nähert man sich immer näher der Lösung an, die aus allen richtigen Optionen besteht. Und hat schlussendlich das Chiffrat geknackt.

Beispiele

Als Beispiel dient uns der Anfang des Märchens Rotkäppchen der Gebrüder Grimm:

Es war einmal ein kleines süßes Mädchen, das hatte jedermann lieb, der sie nur ansah, am allerliebsten aber ihre Großmutter, die wusste gar nicht, was sie alles dem Kinde geben sollte. Einmal schenkte sie ihm ein Käppchen von rotem Samt, und weil ihm das so wohl stand, und es nichts anders mehr tragen wollte, hieß es nur das Rotkäppchen. Eines Tages sprach seine Mutter zu ihm: "Komm, Rotkäppchen, da hast du ein Stück Kuchen und eine Flasche Wein, bring das der Großmutter hinaus; sie ist krank und schwach und wird sich daran laben. Mach dich auf, bevor es heiß wird, und wenn du hinauskommst, so geh hübsch sittsam und lauf nicht vom Wege ab, sonst fällst du und zerbrichst das Glas, und die Großmutter hat nichts. Und wenn du in ihre Stube kommst, so vergiss nicht guten Morgen zu sagen und guck nicht erst in allen Ecken herum!"

Bereinigt um Leer- und Satzzeichen und mit ersetzen Umlauten ergibt dies ESWAREINMALEINKLEINESSUESSESMAEDCHENDASHATTEJEDERMANNLIEBDERSIENURANSAHAMALLERLIEBSTENABERIHREGROSSMUTTERDIEWUSSTEGARNICHTWASSIEALLESDEMKINDEGEBENSOLLTEEINMALSCHENKTESIEIHMEINKAEPPCHENVONROTEMSAMTUNDWEILIHMDASSOWOHLSTANDUNDESNICHTSANDERSMEHRTRAGENWOLLTEHIESSESNURDASROTKAEPPCHENEINESTAGESSPRACHSEINEMUTTERZUIHMKOMMROTKAEPPCHENDAHASTDUEINSTUECKKUCHENUNDEINEFLASCHEWEINBRINGDASDERGROSSMUTTERHINAUSSIEISTKRANKUNDSCHWACHUNDWIRDSICHDARANLABENMACHDICHAUFBEVORESHEISSWIRDUNDWENNDUHINAUSKOMMSTSOGEHHUEBSCHSITTSAMUNDLAUFNICHTVOMWEGEABSONSTFAELLSTDUUNDZERBRICHSTDASGLASUNDDIEGROSSMUTTERHATNICHTSUNDWENNDUINIHRESTUBEKOMMSTSOVERGISSNICHTGUTENMORGENZUSAGENUNDGUCKNICHTERSTINALLENECKENHERUM Eine Zählung der einzelnen Buchstaben ergibt folgendes Bild:

Bst.	Anzahl ni bzw. N	x*(x-1)
A:	48	2256
B:	11	110
C:	24	552
D:	35	1190
E:	91	8190
F:	4	12
G:	16	240
H:	39	1482
I:	46	2070
J:	1	0
K:	15	210
L:	23	506
M:	27	702
N:	63	3906
O:	20	380
P:	7	42
R:	37	1332
S:	71	4970
T:	42	1722
U:	36	1260
V:	4	12
W:	13	156
Z:	3	6
Summe:		31306
Textlänge:	676	456300
IC:		= 0,06861

Bei einem noch längeren Text würde sich der Koinzidenzindex noch mehr der 0,076 für die deutsche Sprache angleichen.

Würde man eine Transpositions-Chiffre wie etwa die Skytale auf den Märchentext anwenden und damit die Buchstaben durcheinander wirblen, dann hätte das keinen Einfluss auf den Koinzidenzindex, den die Buchstaben bleiben ja gleich und sind nur an anderer Stelle. Die Wahrscheinlichkeit, dass zwei zufällig herausgepickte Buchstaben überstimmten, bliebe exakt gleich.

Und auch bei einer monoalphabetischen Substitution, bei der man zum Beispiel alle A zu einem X und all X zu seinem P und alle P zu einem C etc. machen würde, bliebe der Koinzidenzindex und die Wahrscheinlichkeit, dass zwei zufällig herausgepickte Buchstaben überstimmten, exakt gleich. Es ist ja egal, ob ich das A mit allen anderen As vergleiche oder alle Xs miteinander, wenn am Ende die Summen aller Buchstaben aufaddiert werden.

Code / Chiffre online dekodieren / entschlüsseln bzw. kodieren / verschlüsseln (DeCoder / Encoder / Solver-Tool)

Vorher etwas mit dem Vigenere Chiffre verschlüsseln.

Quellen, Literaturverweise und weiterführende Links