Koinzidenzindex

Einführung

Der Koinzidenzindex (auch Friedmansche Koinzidenzindex oder auch Kappa-Test) ist ein Werkzeug der Kryptoanalyse und gibt die Wahrscheinlichkeit an, mit der zwei zufällig aus einer Nachricht ausgelesen Buchstaben übereinstimmen. Diese ist für verschiedene Sprachen unterschiedlich und von der Häufigkeitsverteilung der Buchstaben innerhalb der Sprache abhängig.

Der Koinzidenzindex für ausgewählte Sprachen ist (Quelle: http://kryptografie.de):

Berechnung

Man geht von einer beliebigen Buchstabenfolge der Länge N aus. Weiter bezeichnet man mit n₁ die Anzahl der a's, mit n₂ die Anzahl der b's,... und mit n₂₆ die Anzahl der z's (Quelle: Kryptologie:Albrecht Beutelspacher Springer-Verlag 2014 S. 40 ff). Als nächstes bestimmt die Anzahl der Paare, bei dem beide Buchstaben gleich a sind. Es wird nicht verlangt, dass es sich um Bigramme, also um aufeinander folgende Buchstaben handelt. Für die Auswahl des ersten a's gibt es genau n₁ Möglichkeiten. Für die Auswahl des zweiten a's dann noch n₁-1 Möglichkeiten. Da es auf die Reihenfolge der Buchstaben nicht ankommt, ist die Anzahl der gesuchten Paare gleich n₁*(n₁-1)/2. Also ist die Anzahl der Paare, bei dem beide Buchstaben gleich sind, d.h. bei denen beide gleich a oder beide gleich b ... oder beide gleich z sind, gleich

G = n₁*(n₁-1)/2 + n₂*(n₂-1)/2 + ... + n₂₆*(n₂₆-1)/2.

Die Chance, ein Paar aus gleichen Buchstaben zu erwischen, nennt man Anzahl der günstigen Fälle. Insgesamt gilt:

"Anzahl der günstigsten Fälle durch Anzahl der möglichen Fälle"

Nun bestimmt man noch ganz allgemein alle möglichen Fälle zwei Zeichen aus dem Text auszuwählen. Ein beliebiges Zeichen kann mit N-1 Elementen kombiniert werden. Also mit allen Zeichen außer sich selbst. Auch hier spielt die Reihenfolge keine Rolle, so dass für die Anzahl der möglichen Fälle gilt:

M = N*(N-1)/2.

"Anzahl der günstigsten Fälle durch Anzahl der möglichen Fälle" ergibt mathematisch ausgedrückt:

IC = G/M

IC ist der (Friedmansche) Koinzidenzindex und entspricht der Formel von Laplace.

Beispiel

Als Beispiel dient uns der Anfang des Märchens Rotkäppchen der Gebrüder Grimm (Quelle: http://kryptografie.de/kryptografie/kryptoanalyse/koinzidenzindex.htm):

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 sich ein IC von 0,068.

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

Page updated

Google Sites

Report abuse