Koinzidenzindex

Kategorisierung:Klassisch / Substitution / polyalphabetisch
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. Diese 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 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.

Entspricht der Koinzidenzindex eines Chiffrats aber mehr dem Koinzidenzindex eines gleichverteilten Textes, 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.

Beschreibung des Verfahrens

Der Koinzidenzindex wird ermittelt, indem man die jeweiligen Anzahlen ni 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 ausgewählte Sprachen ist:

SpracheKoinzidenzindexin Prozent
deutsch0.0767,6%
französisch0.0787,8%
italienisch0.0767,6%
spanisch0.0757,5%
englisch0.0656,5%
schwedisch0.0636,3%
russisch0.0535,3%
gleichverteilt ("starke" Chiffre)0.03853,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%), wie er z. B. in einem chiffrierten Text aus polyalphabetischer Substitution (etwa der Vigenere Chiffre) oder mit Anwendung von Homophonen stammen könnte.

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 Index 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.

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 ESWAREINMALEINKLEINESSUESSESMAEDCHENDASHATTEJEDERMANNLIEBDERSIENURAN SAHAMALLERLIEBSTENABERIHREGROSSMUTTERDIEWUSSTEGARNICHTWASSIEALLESDEM KINDEGEBENSOLLTEEINMALSCHENKTESIEIHMEINKAEPPCHENVONROTEMSAMTUNDWEILI HMDASSOWOHLSTANDUNDESNICHTSANDERSMEHRTRAGENWOLLTEHIESSESNURDASROTKAE PPCHENEINESTAGESSPRACHSEINEMUTTERZUIHMKOMMROTKAEPPCHENDAHASTDUEINSTU ECKKUCHENUNDEINEFLASCHEWEINBRINGDASDERGROSSMUTTERHINAUSSIEISTKRANKUN DSCHWACHUNDWIRDSICHDARANLABENMACHDICHAUFBEVORESHEISSWIRDUNDWENNDUHIN AUSKOMMSTSOGEHHUEBSCHSITTSAMUNDLAUFNICHTVOMWEGEABSONSTFAELLSTDUUNDZE RBRICHSTDASGLASUNDDIEGROSSMUTTERHATNICHTSUNDWENNDUINIHRESTUBEKOMMSTS OVERGISSNICHTGUTENMORGENZUSAGENUNDGUCKNICHTERSTINALLENECKENHERUM 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.

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

Franke, Herbert W.: Die geheime Nachricht, Umschau Verlag 1982, S. 76
Bauer, Friedrich L.: Entzifferte Geheimnisse, Springer Verlag 1995, S. 247
Beutelspacher, Neumann und Schwarzpaul: Kryptografie in Theorie und Praxis, Vieweg Verlag 2005, S. 17
Ertel, Wolfgang: Angewandte Kryptographie, Hanser Verlag 2012, S. 43
Fumy, Walter und Rieß, Hans Peter: Kryptographie: Entwurf, Einsatz und Analyse..., Oldenbourg Verlag 1988, S. 58
Kahn, David: The Codebreakers - The Story of Secret Writing, Macmillan Verlag 1968, S. 377
Wobst, Reinhard: Abenteuer Kryptologie, Addison-Wesley-Verlag 2001, S. 90