Kappa-Test

Kategorisierung:Kryptoanalyse Klassisch / Substitution / polyalphabetisch
Herkunft / Verwendung: Grundlage für diesen Test ist der Koinzidenzindex (auch häufig bezeichnet mit dem griechischen Buchstaben Kappa), der angibt, wie hoch die Wahrscheinlichkeit ist, dass zwei zufällig aus einem Text gegriffene Buchstaben übereinstimmen.

Der Test wird zur Schlüssellängebestimmung von Chiffraten aus polyalphabetischen Substitutions Chiffren benutzt. Chiffre also, die den 1. Klartextbuchstaben mit dem 1. Schlüsselbuchstaben, den 2. Klartextbuchstaben mit dem 2. Schlüsselbuchstaben usw. - und bei beispielweise eine Schlüssellänge von 5 - den 6. Klartextbuchstaben wieder mit dem 1. Schlüsselbuchstaben chiffriert, weil ein kurzer Schlüssel wiederholt wird.

Wäre der Schlüssel genausolang wie der Klartext und würde sich nicht wiederholen, würde es sich um eine Chiffre handeln, in der ein sich stetig ändernder Schlüsselstrom verwendet wird. Beispiele dafür sind die Autokey Chiffre (hier wird der Klartext als Schlüsselerweiterung benutzt) und die sichere One-Time-Pad Chiffre (hier wird als Schlüsselstrom eine Zufallsfolge benutzt). In diesem Fällen kann der Kappa-Test nicht bei der Schlüssellängenfindung helfen.

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 dem gleichen Koinzidenzindex 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, bis man bei einer Schlüssellänge den Koinzidenzindex nahe der ursprünglichen Sprache erhält, die anderen Schlüssellängen sollten eher gegen Gleichverteilung (Koinzidenzindex von 3,85%) tendieren.

Zur Veranschaulichung ein Beispiel:

Der Klartext "zurwinterszeitalseinmaleintieferschneelagmussteeinarmerjungehinausgehenundholzaufeinemschlittenholen" mit dem Koinzidenzindex 7,596% wird mit dem Kennwort 'Katze' per Vigenere verschlüsselt zu: jukvmxtxqwjebsevsxhrwaedmxtbdjorlblxexkeqmnrwdexhrkrfdvtugfirigzycgxgixugclylszypebmiwsvgpstmdrroedr Nun sortiert man die Buchstaben für die einzelnen Schlüssellängen (SL) zurück. Man erhält jeweils SL zurücksortierte Texte: SL=2: ju kv mx tx qw je bs ev sx hr wa ed mx tb dj or lb lx ex ke qm nr wd ex hr kr fd vt ug fi ri gz yc gx gi xu gc ly ls zy pe bm iw sv gp st md rr oe dr jkmtqjbeshwemtdollekqnwehkfvufrgyggxgllzpbisgsmrod uvxxwesvxradxbjrbxxemrdxrrdtgiizcxiucysyemwvptdrer SL=3: juk vmx txq wje bse vsx hrw aed mxt bdj orl blx exk eqm nrw dex hrk rfd vtu gfi rig zyc gxg ixu gcl yls zyp ebm iws vgp stm drr oed r jvtwbvhambobeendhrvgrzgigyzeivsdor umxjssrexdrlxqrerftfiyxxclybwgtre kxqeexwdtjlxkmwxkduigcgulspmspmrd SL=4: jukv mxtx qwje bsev sxhr waed mxtb djor lblx exke qmnr wdex hrkr fdvt ugfi rigz ycgx gixu gcly lszy pebm iwsv gpst mdrr oedr jmqbswmdleqwhfurygglpigmo uxwsxaxjbxmdrdgicicsewpde ktjehetolknekvfggxlzbssrd vxevrdbrxerxrtizxuyymvtrr SL=5: jukvm xtxqw jebse vsxhr waedm xtbdj orlbl xexke qmnrw dexhr krfdv tugfi rigzy cgxgi xugcl ylszy pebmi wsvgp stmdr roedr jxjvwxoxqdktrcxypwsr utesatremeruigulesto kxbxeblxnxfggxgsbvme vqshddbkrhdfzgczmgdd mwermjlewrviyilyiprr usw. Für jede Schlüssellänge berechnet man aus den jeweiligen Texte den Durchschnittswert der Koinzidenzindexes. 1: 4,14% 2: 4,735% 3: 4,523% 4: 5% 5: 7,052% 6: 5,082% 7: 4,406% 8: 4,895% 9: 3,401% 10: 7,556% 11: 4,445% 12: 4,828% 13: 2,656% 14: 5,527% 15: 7,175% 16: 4,702% 17: 4,706% 18: 2,778% 19: 1,404% ... Wie man sieht, stechen einige Werte heraus, die alles Vielfache von 5 sind. Somit ist die wahrscheinliche Schlüssellänge 5.

Da die Buchstabenfolge aus dem Klartext durch die Chiffrierung in soviele Abschnitte zerrissen wurde, wie der Schlüssel lang ist, stimmt der Durchschnittwert der pro Abschnitt errechneten Koinzidenzindexes nicht genau mit dem ursprünglichen Koinzidenzindexes des (gesamten) Klartextes überein. Die Indexwerte gleichen sich aber mit zunehmender Textlänge an.

Noch eleganter läßt sich die Schlüssellänge mit dem Friedman Test ermitteln.

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

Franke, Herbert W.: Die geheime Nachricht, Umschau Verlag 1982, S. 75
Bauer, Friedrich L.: Entzifferte Geheimnisse, Springer Verlag 1995, S. 258