Koinzedenzindex: Unterschied zwischen den Versionen
Thomas (Diskussion | Beiträge) Die Seite wurde neu angelegt: „== 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 Sprache…“ |
Thomas (Diskussion | Beiträge) |
||
| Zeile 5: | Zeile 5: | ||
== Berechnung == | == Berechnung == | ||
Man geht von einer beliebigen Buchstabenfolge der Länge N aus. Weiter bezeichnet man mit n1 die Anzahl der a's, mit n2 die Anzahl der b's,... und mit n26 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 n1 Möglichkeiten. Für die Auswahl des zweiten a's dann noch n1-1 Möglichkeiten. Da es auf die Reihenfolge der Buchstaben nicht ankommt, ist die Anzahl der gesuchten Paare gleich n< | Man geht von einer beliebigen Buchstabenfolge der Länge N aus. Weiter bezeichnet man mit n1 die Anzahl der a's, mit n2 die Anzahl der b's,... und mit n26 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 n1 Möglichkeiten. Für die Auswahl des zweiten a's dann noch n1-1 Möglichkeiten. Da es auf die Reihenfolge der Buchstaben nicht ankommt, ist die Anzahl der gesuchten Paare gleich n<sub>1</sub>*(n<sub>1</sub>-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 = n1*( | G = n1*(n<sub>1</sub>-1)/2 + n2*(n<sub>2</sub>-1)/2 + ... + n<sub>26</sub> *(n<sub>26</sub>-1)/2. | ||
Die Chance, ein Paar aus gleichen Buchstaben zu erwischen, nennt man Anzahl der günstigen Fälle. Insgesamt gilt: | Die Chance, ein Paar aus gleichen Buchstaben zu erwischen, nennt man Anzahl der günstigen Fälle. Insgesamt gilt: | ||
| Zeile 15: | Zeile 15: | ||
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: | 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. | '''M = N*(N-1)/2.''' | ||
"Anzahl der günstigsten Fälle durch Anzahl der möglichen Fälle" ergibt mathematisch ausgedrückt: | '''''"Anzahl der günstigsten Fälle durch Anzahl der möglichen Fälle"''''' ergibt mathematisch ausgedrückt: | ||
IC = G/M | '''IC = G/M''' | ||
IC ist der (Friedmansche) Koinzidenzindex und entspricht der Formel von Laplace. | IC ist der (Friedmansche) Koinzidenzindex und entspricht der Formel von Laplace. | ||
Beispiel | == Beispiel == | ||
Als Beispiel dient uns der Anfang des Märchens Rotkäppchen der Gebrüder Grimm (Quelle: http://kryptografie.de/kryptografie/kryptoanalyse/koinzidenzindex.htm): | Als Beispiel dient uns der Anfang des Märchens Rotkäppchen der Gebrüder Grimm (Quelle: http://kryptografie.de/kryptografie/kryptoanalyse/koinzidenzindex.htm): | ||
| Zeile 31: | Zeile 31: | ||
ESWAREINMALEINKLEINESSUESSESMAEDCHENDASHATTEJEDERMANNLIEBDERSIENURAN SAHAMALLERLIEBSTENABERIHREGROSSMUTTERDIEWUSSTEGARNICHTWASSIEALLESDEM KINDEGEBENSOLLTEEINMALSCHENKTESIEIHMEINKAEPPCHENVONROTEMSAMTUNDWEILI HMDASSOWOHLSTANDUNDESNICHTSANDERSMEHRTRAGENWOLLTEHIESSESNURDASROTKAE PPCHENEINESTAGESSPRACHSEINEMUTTERZUIHMKOMMROTKAEPPCHENDAHASTDUEINSTU ECKKUCHENUNDEINEFLASCHEWEINBRINGDASDERGROSSMUTTERHINAUSSIEISTKRANKUN DSCHWACHUNDWIRDSICHDARANLABENMACHDICHAUFBEVORESHEISSWIRDUNDWENNDUHIN AUSKOMMSTSOGEHHUEBSCHSITTSAMUNDLAUFNICHTVOMWEGEABSONSTFAELLSTDUUNDZE RBRICHSTDASGLASUNDDIEGROSSMUTTERHATNICHTSUNDWENNDUINIHRESTUBEKOMMSTS OVERGISSNICHTGUTENMORGENZUSAGENUNDGUCKNICHTERSTINALLENECKENHERUM | ESWAREINMALEINKLEINESSUESSESMAEDCHENDASHATTEJEDERMANNLIEBDERSIENURAN SAHAMALLERLIEBSTENABERIHREGROSSMUTTERDIEWUSSTEGARNICHTWASSIEALLESDEM KINDEGEBENSOLLTEEINMALSCHENKTESIEIHMEINKAEPPCHENVONROTEMSAMTUNDWEILI HMDASSOWOHLSTANDUNDESNICHTSANDERSMEHRTRAGENWOLLTEHIESSESNURDASROTKAE PPCHENEINESTAGESSPRACHSEINEMUTTERZUIHMKOMMROTKAEPPCHENDAHASTDUEINSTU ECKKUCHENUNDEINEFLASCHEWEINBRINGDASDERGROSSMUTTERHINAUSSIEISTKRANKUN DSCHWACHUNDWIRDSICHDARANLABENMACHDICHAUFBEVORESHEISSWIRDUNDWENNDUHIN AUSKOMMSTSOGEHHUEBSCHSITTSAMUNDLAUFNICHTVOMWEGEABSONSTFAELLSTDUUNDZE RBRICHSTDASGLASUNDDIEGROSSMUTTERHATNICHTSUNDWENNDUINIHRESTUBEKOMMSTS OVERGISSNICHTGUTENMORGENZUSAGENUNDGUCKNICHTERSTINALLENECKENHERUM | ||