Chi-Quadrat-Test
| Kategorisierung: | Kryptoanalyse Klassisch / Substitution / polyalphabetisch |
| Siehe auch: | Kasiski-Test, Kappa-Test, Chi-Quadrat-Test |
| 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
JUKVM XTXQW JEBSE VSXHR WAEDM XTBDJ ORLBL XEXKE QMNRW DEXHR KRFDV TUGFI RIGZY CGXGI XUGCL YLSZY PEBMI WSVGP STMDR ROEDR GIXDV OSGTR JULZQ WEGFI CUVGX ENWZY PGXKE NEGGE DTXVS VLMDI BWXHP ORLNI BFKNV ONPZV XOVGR SCASR KCAGE ESZDL ONLNR NEKMI BSMEI EEKZR WAVGI XUGCW SCADM XBBRW MHXMA KEKLI XDTRG RAKQX OEKCI XSVGR OEPDK ENWVM OEKRS NEGDV NBHCI XANEV KENLX OFTMH ORXHR ONDKI SNXMK YLWDR ONLBL VUXRW OLGTR QLTTF DEXQA YDXQW MHETI CSXKA KEKDQ EELRX OANBL NALRG RLHRW NASTW OIGFV EBBMH ORXQH OUGCJ KNWDM XEBRI BNXRO KELSG REGVI XNWDV CCAKY OSLDP XUKOE CSMCE MHMDI BELRM XDZDA SSLJS CTUZV OSTBL ONBMH OMDZI CTVGI XEKRY MHMDE LEKDW GAKJI SNLBL VUXRW OLENG RDTDR NLBBL ONMCI MKMDI BEBMW KBXQW YKEDM XDTRW WAGDW UANLW OHXMO YNGSI ORIQS LIXQX OUGCH ORLBL VUXRW OLIZW CTXFP EEVJP SCACE NRXGX OEKDM XMTKL ORNLY XDGTR WUXRW ONPHV GAKSI XBBRI BVHKP ONWRE EFZDW MHENW CEGTR NDXMH OCDDP KUYFI WAVGX RAMCE XNPDV NEGVM BEKEE RRXMA KSYTI BWNMH ORUZV OSTBL ONBMH OMDZI CTVGI XLTFI X
(Leerzeichen dienen lediglich der Lesbarkeit)
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