Brechen der Autokey Chiffre

Um dieses kryptoanalytische Verfahren anzuwenden, muss man sich sicher sein, dass das Chiffrat mit Autokey verschlüsselt ist. Sind Sie nicht sicher, dass es sich um eine Autokey-Chiffre handelt, sollten Sie zuerst die Art der Chiffre bestimmen und überprüfen, ob die Charakteristika zutreffen. Sonst betreiben Sie ggf. unnötigen Aufwand an einem anderen Verschlüsselungsverfahren.

Brechen der Variante "Chiffrat anhängen"

Da diese Variante des Autokey einfacher zu brechen ist, wollen wir mit dieser Variante beginnen. Wie bei der Autokey Chiffre nachzulesen, wird hier der Schlüssel nicht wie bei Vigenere wiederholt, sondern es wird dem Schlüssel das gerade entstehende Chiffrat angehängt: Klartext: treffenamfreitagumzweiundzwanziguhrambekanntentreffpunkt Schlüssel: berlinUVVQNRHVHVEVPOHBYHOKLJSURJHJFTZPBQWTLQFAWGYJJNPXCO Chiffrat: UVVQNRHVHVEVPOHBYHOKLJSURJHJFTZPBQWTLQFAWGYJJNPXCOOCJKMH Wir machen uns den Umstand zunutze, dass ab einer bestimmten Position das Chiffrat gleich dem Schlüssel ist und dies liegt uns ja praktischerweise schon vor. Es bleibt nur noch herauszufinden, welche Position das genau ist. Aber das ist keine große Schwierigkeit. Wir nehmen einfach die Schlüssellänge 3 an und entschlüsseln das Chiffrat mit Vigenere ab Position 4 mit dem Chiffrat als Schlüssel. Wir fahren solange fort, bis sich ein lesbarer Text ergibt. UVVQNRHVHVEVPOHBYHOKLJSURJHJFTZPBQWTLQFAWGYJJNPXCOOCJKMH <-- Chiffrat 3 xxxUVVQNRHVHVEVPOHBYHOKLJSURJHJFTZPBQWTLQFAWGYJJNPXCOOCJ ...WSWRIQOJOUKMMKANMEVIJIRNSWMQKIRHSVUMPGBYNDPGOPZRAVWKY 4 xxxxUVVQNRHVHVEVPOHBYHOKLJSURJHJFTZPBQWTLQFAWGYJJNPXCOOC ....TWMFUEXAITDGJTHJNCEKGAPPOKSGWXXEKAJHLQTJNHROTBZFHWYF 5 xxxxxUVVQNRHVHVEVPOHBYHOKLJSURJHJFTZPBQWTLQFAWGYJJNPXCOO .....XMARINOUHMXDSADKLLGHYYRLCQISLDUWPPEDVIEJRJZTFBNMIYT 6 xxxxxxUVVQNRHVHVEVPOHBYHOKLJSURJHJFTZPBQWTLQFAWGYJJNPXCO ......NAMFREITAGUMZWEIUNDZWANZIGUHRAMBEKANNTENTREFFPUNKT ^-- Original-Schlüssellänge und Schlüssel für Vigenere-Test Damit haben wir bereits den Großteil des Klartextes entziffert (in diesem Fall genügen die Informationen) und wissen, dass der Original-Schlüssel 6 Zeichen lang ist. Wenn wir ein paar verdächtige Kandidaten für Schlüssel haben, die in der Länge passen, können wir sie ausprobieren und so evtl. mit etwas Glück auch die ersten sechs Buchstaben ermitteln.

Nach diesem Test sollte klar geworden sein, wie unsicher diese Autokey-Variante in Wahrheit ist. Manch einer mag ein sichereres Gefühl bei der Verschlüsselung haben, weil sie komplizierter in der Durchführung ist als die andere Variante und sich der Schlüssel nur Buchstabe für Buchstabe aus dem Chiffrat ergänzt, aber das ist ein fataler Trugschluss.

Brechen der Variante "Klartext anhängen"

Bei dieser Variante bekommen wir den Schlüssel nicht auf dem Silbertablett serviert, denn hier wird der Schlüssel durch den Klartext selbst erweitert.

Brechen mit bekanntem Klartextteil (Known-Plaintext-Attack)

1 2 3 4 5 12345678901234567890123456789012345678901234567890123456 Klartext: treffenamfreitagumzweiundzwanziguhrambekanntentreffpunkt Schlüssel: berlintreffenamfreitagumzweiundzwanziguhrambekanntentref Chiffrat: UVVQNRGRQKWIVTMLLQHPEOOZCVAIHMLFQHEZUHYRRNZUIXTERYJCNEOY Für dieses Beispiel wollen wir annehmen, dass wir wissen, dass es bei der Nachricht um ein Treffen handelt und das dieses, wie üblicherweise, zwischen 20:00 Uhr und Mitternacht stattfinden wird. Wir nehmen also den Klartextteil "ZWANZIGUHR" als Klartext an, der für diese Uhrzeiten vorkommen muss.

Da wir wissen, dass der Klartext bei Autokey Schlüsselbestandteil ist, wissen wir auch, dass der Klartextteil "ZWANZIGUHR" als Schlüssel verwandt wurde und wenn wir das Chiffrat damit an alle Positionen beginnend entschlüsseln, muss irgendwann ein lesbares Dechiffrat auftauchen.

Wir wenden das schon beim Brechen der Vigenere Chiffre mithilfe eines bekannten Klartextteils vorgestellte Verfahren an.

Nach Eingabe von Chiffrat und dem Klartextteil "ZWANZIGUHR" in das dort vorgestellte Hilfstool erhalten wir folgende Liste: ... 024: AGVNJZGRYZ 025: DZAVIEFLJQ 026: WEIUNDZWAN 027: BMHZMXKNXI 028: JLMYGIBKSD ... "WEIUNDZWAN" an Position 26 ist ein Stückchen lesbarer Klartext, das wir notieren. Hier beginnt also unser Schlüssel ZWANZIGUHR 1 2 3 4 5 12345678901234567890123456789012345678901234567890123456 Chiffrat: UVVQNRGRQKWIVTMLLQHPEOOZCVAIHMLFQHEZUHYRRNZUIXTERYJCNEOY Dechiff.: ZWANZIGUHR Wir haben damit auch den neuen Klartextteil (und somit auch Schlüsselteil) WEIUNDZWAN erhalten, mit dem wir das Verfahren wiederholen können: ... 018: UDHKBLAGVN 019: LLWUBWDZAV 020: TAGUMZWEIU 021: IKGFPSBMHZ 022: SKRIIXJLMY 023: SVUBNFIQLS 024: DYNGVENPFD 025: GRSOUJMJQU 026: ZWANZIGUHR 027: EEZSYCRLEM 028: MDERSNIIZH ... Wir erhalten den neuen Klartextteil TAGUMZWEIU 1 2 3 4 5 12345678901234567890123456789012345678901234567890123456 Chiffrat: UVVQNRGRQKWIVTMLLQHPEOOZCVAIHMLFQHEZUHYRRNZUIXTERYJCNEOY Dechiff.: ZWANZIGUHR WEIUNDZWAN Wir fahren mit dem Verfahren fort und finden noch 1 2 3 4 5 12345678901234567890123456789012345678901234567890123456 Chiffrat: UVVQNRGRQKWIVTMLLQHPEOOZCVAIHMLFQHEZUHYRRNZUIXTERYJCNEOY Dechiff.: ZWANZIGUHR WEIUNDZWAN TAGUMZWEIU AMFREITAGU REFFENAMFR ERLINTREFF <Schlüssel><---- Klartext -------------------- ... --> Auffällig ist hier die jeweilige Verschiebung um 6 Zeichen. Das ist unsere Original-Schlüssellänge. Das Original-Schlüssellänge steht also an Pos. 1 bis 6. Die nachfolgenden 6 Zeichen sind damit verschlüsselt worden. Wenn wir nun mit diesen (TREFFE) suchen erhalten wir: 001: BERLIN BERLIN ist also unser Schlüsselwort und wir können damit das Autokey-Chiffrat komplett dechiffrieren.

Brechen ohne bekanntem Klartextteil (Ciphertext-Only-Attack)

Hier wollen wir ein etwas längeres Chiffrat als Beispiel nehmen, da es bei dieser Methode auf die Häufigkeitsverteilung ankommt, die erst bei längeren Texte genau wird. Klartext: ZURWINTERSZEITALSEINMALEINTIEFERSCHNEELAGMUSSTEEINARMERJUNGEHINAUSGEHENUNDHOLZAUFEINEMSCHLITTENHOLEN WIEERESNUNZUSAMMENGESUCHTUNDAUFGELADENHATTEWOLLTEERWEILERSOERFRORENWARNOCHNICHTNACHHAUSGEHENSONDERNE RSTFEUERANMACHENUNDSICHEINBISSCHENWAERMENDASCHARRTEERDENSCHNEEWEGUNDWIEERSODENERDBODENAUFRAEUMTEFAND EREINENKLEINENGOLDENENSCHLUESSELNUNGLAUBTEERWODERSCHLUESSELWAEREMUESSTEAUCHDASSCHLOSSDAZUSEINGRUBIND ERERDEUNDFANDEINEISERNESKAESTCHENWENNDERSCHLUESSELNURPASSTDACHTEERESSINDGEWISSKOSTBARESACHENINDEMKAE STCHENERSUCHTEABERESWARKEINSCHLUESSELLOCHDAENDLICHENTDECKTEEREINSABERSOKLEINDASSMANESKAUMSEHENKONNTE ERPROBIERTEUNDDERSCHLUESSELPASSTEGLUECKLICHDADREHTEEREINMALHERUMUNDNUNMUESSENWIRWARTENBISERVOLLENDSA UFGESCHLOSSENUNDDENDECKELAUFGEMACHTHATDANNWERDENWIRERFAHRENWASFUERWUNDERBARESACHENINDEMKAESTCHENLAGEN Schlüssel: GRIMM Chiffrat: FLZIUMNVNAMXMKSKWMBNXSPMVZTTINRKAGMRVWNHTQYDSZQYAFTVQMEJLZKVQCAGYZORHYFARKLBFMDBTPHNYRWKUPULVLYPHEIA DWPIEAARYEDMFUZLYFGQEYPNXMHFHNZTHLUIKRSAWXRDOEEXASCHXMPVNWWPVWJCVVSNOIRBYHEVQJAAIEOANUUNLHYFYSUHRJBR UWKSILWKFRGETHRZUPKWVWUHAVDPWAPIMFOCLVZANHREGUDRJVLEIUXRWTKRRWYLTYRZAOYRUOWHIEWFGFBHVQBIIVNEORKEJUZW IWEVQIEOTRMAOYKWYHRTSYVGUPHWUZPFRMFKWNOOZPELXHHIIOQKPLWUZPFASWVPIUIJWFYEMUAHAMUJKLGKUKLNMKHIMAJYJVTU YSMEGILRUIEHQHNNRLWMERMKORRWLMHIFPGURQAVFPKPLWUZPFRMJTLFMKSAUZMHETLLWMEHYWEVVYOKALTKFWLBCYIFIPKIZSNH WFMHIFXTZYPLKWUDLKISXEIOWENJMLTHWUZPFPGULOLSPKOIGUHYBFLGXMHITOBRWRFMEKOLPVABNLWAZDNWKWAHQKOHYZCSURGO SECKSFZTIHFCRUWILFFKPLWUZPFTSKWETGDMXGQWCGJNLLTLKTHVVLBRQRPPRDUXBRUHGHZXRMFQHAAJANNBVJBZLIEWWDPVIRDL YSJWSWMRSKULYIFVHRHQHFOROEWPKPMUHNXTAVKTUNPHRQRJAZUIEBIYVVSWHJJHAROZHHVNVNUIJBCYIFIPKIZSNHWFMHIFECNIA Als erstes gilt es, die Schlüssellänge zu bestimmen. Für den ersten Überblick führen wir einen Kappa-Test auf das Chiffrat aus: 1: 4,249% 2: 4,214% 3: 4,163% 4: 4,182% 5: 4,5% 6: 4,308% 7: 4,261% 8: 4,17% 9: 4,038% 10: 4,396% 11: 4,147% 12: 4,284% 13: 4,263% 14: 4,255% 15: 4,506% 16: 4,193% 17: 4,16% 18: 4,082% 19: 4,243% 20: 4,172% 21: 4,096% 22: 4,172% 23: 4,33% 24: 4,36% 25: 4,282% Die Kappa-Werte sind alle sehr ähnlich. Es gibt keinen Ausschlag irgendwo. Das liegt daran, dass durch die Fortschreibung des Schlüssels durch den Klartext immer wieder andere Buchstabenkombinationen entstehen, die via Vigenere verknüpft werden.

Was aber wäre, wenn wir eine Autokey-Entschlüsselung an der Position beginnen lassen würden, die dem Schlüsselwort folgt? Dann würde der (verschlüsselte) Usprungsklartext auf die aus diesen Buchstaben resultierendem Chiffrat treffen und wir würden den verschiebenden (und verschleiernden) Teil herausrechnen. Damit wäre dann wieder eine natürliche Häufigkeitsverteilung gegeben und der Kappa-Test müsste anschlagen.

Wir müssen also nur der Reihe nach durchprobieren. Beginnen wir mit der Annahme der Länge 3 und demnach AAA, mit dem wir unser Chiffrat Autokey-dechiffrieren: Schlüssel: AAA (3) Dechiffrat: FLZDJNKMAQAXWKVOMRNBGFOGQLNDXAONASZRDXWEWUUHYFJAVWTAUTEPSVVDVHXLRCDAFVFVWFQFAWYBXRGQHLGDJJRCMUWDNIF... Kappa-Test 1: 3,845% 2: 3,904% 3: 3,775% 4: 3,942% 5: 3,799% 6: 3,839% 7: 3,878% 8: 3,883% 9: 3,805% 10: 3,837% 11: 3,772% 12: 3,89% 13: 3,888% 14: 3,821% 15: 4,06% 16: 3,939% 17: 3,918% 18: 3,817% 19: 3,888% 20: 3,8% 21: 4,039% 22: 3,753% 23: 3,896% 24: 3,807% 25: 3,75% Schlüssel: AAAA (4) Dechiffrat: FLZIPBONYZYKOLUAIBHNPRIZGILUCFGQYBGBXVHGWVRXWEZBEBUUMLKPZOAGROAAHLORANRJRXUSOPJJFAYETRYGBYWFUNCKNRGQ... Kappa-Test 1: 3,836% 2: 3,825% 3: 3,838% 4: 3,821% 5: 3,772% 6: 3,771% 7: 3,769% 8: 3,849% 9: 3,847% 10: 3,745% 11: 3,873% 12: 3,695% 13: 3,761% 14: 3,773% 15: 3,847% 16: 3,849% 17: 3,794% 18: 4,032% 19: 3,699% 20: 3,819% 21: 3,918% 22: 3,793% 23: 4,038% 24: 3,773% 25: 3,845% max. 4,038% bei Intervall 23 Schlüssel: AAAAA (5) Dechiffrat: FLZIUHCWFGFVQFMFBWWBSRTQUHCASTKIAOTHNWZOMDCEENNWWBGIUQDDDFUSNZVMGMPWVSTLVPTIUROILVQZQGBUVZOKBQZBXDSB... Kappa-Test 1: 4,071% 2: 4,287% 3: 3,989% 4: 4,218% 5: 5,893% 6: 4,124% 7: 3,94% 8: 4,26% 9: 3,91% 10: 8,266% 11: 4,048% 12: 4,198% 13: 3,963% 14: 4,21% 15: 5,504% 16: 4,22% 17: 4,028% 18: 4,168% 19: 4,072% 20: 8,117% 21: 3,555% 22: 4,214% 23: 3,845% 24: 4,417% 25: 5,817% max. 8,266% bei Intervall 10 Hier haben wir einen deutlichen Ausschlag bei der Schlüssellänge 10. Unsere getestete Schlüssellänge ist aber 5. Wieso ist der Kappa-Ausschlag bei der doppelten Schlüssellänge? Wenn wir den Klartext mit dem Dechiffrat vergleichen ZURWINTERSZEITALSEINMALEINTIEFERSCHNEELAGMUSSTEEINARMERJUNGEHINAUSGEHENUNDHOLZAUFEINEMSCHLITTENHOLEN Klartext FLZIUHCWFGFVQFMFBWWBSRTQUHCASTKIAOTHNWZOMDCEENNWWBGIUQDDDFUSNZVMGMPWVSTLVPTIUROILVQZQGBUVZOKBQZBXDSB Dechiffrat (Pseudo-Klartext) UJSOOGRIMMUJSOOGRIMMUJSOOGRIMMUJSOOGRIMMUJSOOGRIMMUJSOOGRIMMUJSOOGRIMMUJSOOGRIMMUJSOOGRIMMUJSOOGRIMM Vigenere-Dechiffrat wird es klar: Durch das "Herausrechnen" des AAAAA-Autokeys wurde unser Chiffrat zum Pseudoklartexttext, der einer Vigenere Chiffre gleichgestellt ist mit dem zehnstelligen Schlüssel "UJSOOGRIMM", der sich ständig wiederholt.

Unseren Pseudoklartext können wir nun also genauso behandeln und knacken wie eine Vigenere-Verschlüsselung mit der Schlüssellänge 10.

Code / Chiffre online dekodieren / entschlüsseln bzw. kodieren / verschlüsseln (DeCoder / Encoder / Solver-Tool)

Für die Hilfsfunktion geben die das Chiffrat bitte in das Eingabe- und den Klartextteil in das Schlüsselfeld ein.



Quellen, Literaturverweise und weiterführende Links

Gaines, Helen Fouché: Cryptanalysis, Dover Verlag New York 1956, S. 113