Chi-Quadrat-Test

Kategorisierung:Kryptoanalyse Klassisch / Substitution / polyalphabetisch
Herkunft / Verwendung: Chi-Quadrat ist eine statistische Größe und spiegelt folgende sprachliche Eigenschaft eines Textes wider: Inwieweit entspricht die in einem Text beobachtete Verteilung der Buchstaben der erwarteten Verteilung?

Der Chi-Quadrat-Test sollte bitte nicht mit dem Chi-Test verwechselt werden. Die Chi-Quadrat-Test ist kein spezieller für die Kryptoanalyse entworfener Test, sondern ein allgemein mathematisch-statistischer. Der Chi-Test ist speziell für die Kryptoanalyse entworfen worden und entspricht dem Kappa-Test. Der ursprünglich von William Friedman eingeführte Buchstabe Kappa (κ) für das Ergebnis des Ursprungsverfahren wurden von Solomon Kullback in Chi (χ) geändert, als er das Verfahren verfeinerte.

Der Chi-Quadrat-Test (χ2-Test) wird normalerweise in der mathematischen Statistik verwendet, kann aber unter kryptoanalytischen Gesichtspunkten angewandt werden, wenn man Chi-Quadrat für mehrere Einzelalphabete einer polyalphabetischen Substitution ausrechnet und miteinander vergleicht. Das Einzelalphabet* mit der wahrscheinlichsten Schlüssellänge weist normalerweise den höchsten Chi-Quadrat-Wert auf.

Es sollte aber beachtet werden, dass die Auswertung für kurze Chiffrate (kleiner Schlüssellänge * 20) ungenau wird und dann nicht mehr geeignet ist.


* Ein Einzelalphabet ist die Zusammenfassung der Buchstaben des Klartextes, die mit dem selben Schlüsselbuchstaben verschlüsselt worden sind. Verschlüsselt wurde der 1. Klartextbuchstabe mit dem 1. Schlüsselbuchstaben, der 2. Klartextbuchstabe mit dem 2. Schlüsselbuchstaben usw. - und bei beispielweise eine Schlüssellänge von 5 - dr 6. Klartextbuchstaben wieder mit dem 1. Schlüsselbuchstaben, weil ein kurzer Schlüssel wiederholt wird.

Beschreibung des Verfahrens

Um die Schlüssellänge zu bestimmen, versucht man die einzelnen Buchstaben des Chiffrats so zusammenfassen, wie sie im ursprünglichen Text vorkamen. Man weiß vom Vigenere Chiffre, dass der Schlüssel wiederholt und dass mit dem 1. Buchstaben des Schlüssels der 1. Klartextbuchstabe, der (1+Schlüssellänge). Klartextbuchstabe, der. (1+Schlüssellänge*2). Klartextbuchstabe usw. verschlüsselt wurde.

Beispielsweise für die Länge 5 ergäben sich 5 monoalphabetische Substitutionen, jeweils mit dem Schlüsselbuchstabe Si verschlüsselt, die die Klartextbuchstaben Ki enthalten:

S1: K1, K6, K11, K16, ...
S2: K2, K7, K12, K17, ...
S3: K3, K8, K13, K18, ...
S4: K4, K9, K14, K19, ...
S5: K5, K10, K15, K20, ...

Diese Buchstaben aus monoalphabetischen Substitution unterliegen aber den gleichen statistischen Eigenschaften wie die ursprüngliche Sprache, da nur die Buchstaben ausgetauscht wurden, ihre Häufigkeitsverteilung ist gleich geblieben.

Man muss also nur die potentiellen Schlüssellängen durchprobieren, jeweils Chi-Quadrat errechnen und die Werte miteinander vergleichen.

Beispiel

JUKVMXTXQWJEBSEVSXHRWAEDMXTBDJORLBLXEXKEQMNRWDEXHRKRFDVTUGFIRIGZYCGXGIXUGCLYLSZYP EBMIWSVGPSTMDRROEDRGIXDVOSGTRJULZQWEGFICUVGXENWZYPGXKENEGGEDTXVSVLMDIBWXHPORLNIBF KNVONPZVXOVGRSCASRKCAGEESZDLONLNRNEKMIBSMEIEEKZRWAVGIXUGCWSCADMXBBRWMHXMAKEKLIXDT RGRAKQXOEKCIXSVGROEPDKENWVMOEKRSNEGDVNBHCIXANEVKENLXOFTMHORXHRONDKISNXMKYLWDRONLB LVUXRWOLGTRQLTTFDEXQAYDXQWMHETICSXKAKEKDQEELRXOANBLNALRGRLHRWNASTWOIGFVEBBMHORXQH OUGCJKNWDMXEBRIBNXROKELSGREGVIXNWDVCCAKYOSLDPXUKOECSMCEMHMDIBELRMXDZDASSLJSCTUZVO STBLONBMHOMDZICTVGIXEKRYMHMDELEKDWGAKJISNLBLVUXRWOLENGRDTDRNLBBLONMCIMKMDIBEBMWKB XQWYKEDMXDTRWWAGDWUANLWOHXMOYNGSIORIQSLIXQXOUGCHORLBLVUXRWOLIZWCTXFPEEVJPSCACENRX GXOEKDMXMTKLORNLYXDGTRWUXRWONPHVGAKSIXBBRIBVHKPONWREEFZDWMHENWCEGTRNDXMHOCDDPKUYF IWAVGXRAMCEXNPDVNEGVMBEKEERRXMAKSYTIBWNMHORUZVOSTBLONBMHOMDZICTVGIXLTFIX 2: 96,3 3: 66,8 4: 57,8 5: 205,1 6: 44,3 7: 39,8 8: 42,9 9: 41,8 10: 115,9 11: 37,3 12: 34,5 13: 33,9 14: 32,9 15: 81,6 16: 36,3 17: 31,3 18: 31,2 19: 33,7 20: 68,3 21: 26,4 22: 28,9 23: 30,8 24: 29,9 25: 56,7 max. 205,1 bei Intervall 5

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

Erklärung des Chi-Quadrat-Test bei MatehGuru.com