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) |
||
| (7 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 3: | Zeile 3: | ||
Der Koinzidenzindex für ausgewählte Sprachen ist (Quelle: http://kryptografie.de): | Der Koinzidenzindex für ausgewählte Sprachen ist (Quelle: http://kryptografie.de): | ||
[[Datei:Koinzedenzindex Länder.png|mini]] | |||
== 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 16: | ||
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 33: | Zeile 34: | ||
''Eine Zählung der einzelnen Buchstaben ergibt sich ein IC von 0,068.'' | |||
* Summe (31.306):Dies ist das Ergebnis der Addition aller Werte aus der rechten Spalte. In der [[Kryptoanalyse|Kryptoanalyse]] wird dieser Wert benötigt, um den Koinzidenzindex zu berechnen. Er gibt an, wie viele Paare identischer Buchstaben man in diesem speziellen Text bilden könnte. | |||
* Textlänge (676):Dies ist die Gesamtzahl der Buchstaben im untersuchten Text (die Summe der mittleren Spalte. | |||
* 456.300:Dies ist das Ergebnis der Rechnung N *(N - 1), also 676 *675. Dies ist die Gesamtzahl aller theoretisch möglichen Buchstabenpaare im Text. Dieser Wert ist der Nenner für die Berechnung des IC. | |||
* IC (= 0,06861):Dies steht für den Koinzidenzindex (Index of Coincidence). Er wird berechnet, indem man die obere Summe durch das Produkt der Textlänge teilt: 31.306/456.300 = 0,06861 | |||
* Interpretation dieses Wertes: Ein Wert von ca. 0,068 ist typisch für die deutsche Sprache (oder andere natürliche Sprachen wie Englisch).Wäre der Text zufällig verschlüsselt (z. B. mit einer Vigenère-Chiffre und einem langen Schlüssel), läge der Wert deutlich niedriger (nahe 0,038).Dieser hohe Wert deutet also darauf hin, dass es sich entweder um einen Klartext oder eine einfache monoalphabetische Substitution (wie Cäsar) handelt. | |||
Bst. | |||
{| class="wikitable" style="text-align: right;" | |||
! Bst. !! Anzahl n<sub>i</sub> bzw. N !! n<sub>i</sub> * (n<sub>i</sub> - 1) | |||
|- | |||
| style="text-align: left;" | A: || 48 || 2256 | |||
|- | |||
| style="text-align: left;" | B: || 11 || 110 | |||
|- | |||
| style="text-align: left;" | C: || 24 || 552 | |||
|- | |||
| style="text-align: left;" | D: || 35 || 1190 | |||
|- | |||
| style="text-align: left;" | E: || 91 || 8190 | |||
|- | |||
| style="text-align: left;" | F: || 4 || 12 | |||
|- | |||
| style="text-align: left;" | G: || 16 || 240 | |||
|- | |||
| style="text-align: left;" | H: || 39 || 1482 | |||
|- | |||
| style="text-align: left;" | I: || 46 || 2070 | |||
|- | |||
| style="text-align: left;" | J: || 1 || 0 | |||
|- | |||
| style="text-align: left;" | K: || 15 || 210 | |||
|- | |||
| style="text-align: left;" | L: || 23 || 506 | |||
|- | |||
| style="text-align: left;" | M: || 27 || 702 | |||
|- | |||
| style="text-align: left;" | N: || 63 || 3906 | |||
|- | |||
| style="text-align: left;" | O: || 20 || 380 | |||
|- | |||
| style="text-align: left;" | P: || 7 || 42 | |||
|- | |||
| style="text-align: left;" | R: || 37 || 1332 | |||
|- | |||
| style="text-align: left;" | S: || 71 || 4970 | |||
|- | |||
| style="text-align: left;" | T: || 42 || 1722 | |||
|- | |||
| style="text-align: left;" | U: || 36 || 1260 | |||
|- | |||
| style="text-align: left;" | V: || 4 || 12 | |||
|- | |||
| style="text-align: left;" | W: || 13 || 156 | |||
|- | |||
| style="text-align: left;" | Z: || 3 || 6 | |||
|- style="border-top: 2px solid black;" | |||