Kryptoanalyse
Das neue Thema, nämlich die Kryptoanalyse, teile ich in 2 Themen auf, die ziemlich zusammenhängend sind.Denn der Kasiski-Test kann nicht wirklich gut erklärt werden, wenn wir keine Häufigkeitsanalyse durchführen können. Man könnte sagen: Der Kasiski-Test hat eine Häufigkeitsanalyse (Delegation, auch wenn Java-Begriffe hier wohl nicht ganz funktionieren, möchte doch jeder Begriff, der mir einfällt, genannt werden).
Nun denn, der Test beschäftigt sich mit einem mathematischen Ansatz, Texte zu entschlüsseln, die mit Vigenere verschlüsselt sind.
Die Idee dahinter hatte ein gleichnamiger Erfinder, der Kryptoanalytiker für Preußen im 19. Jahrhundert war.
Ein Beispiel, um dies zu verdeutlichen:
Text: Fliegen fliegen Fliegen hinterher. Dabei fliegen fliegende Fliegen fliegenden Flügeln der Fliegen hinterher.
Schlüssel: Hai
Verschlüsselter Text: Mlqlgmu nsimnev Ftpeoln oivaezoez. Lhbmp nsimnev ftpeolnll Nsimnev ftpeolnlln Mlünetu llr Mlqlgmu ppnblrplr.
Jetzt suchen wir identische Buchstabenfolgen. Die finden wir:
"Mlqlgmu nsimnev ftpeoln" kommt zweimal im Text vor. Der Abstand zwischen diesen beträgt 9 Zeichen.
Wir gehen hierbei davon aus, dass es kein Zufall ist, dass zweimal die selbe Zeichenfolge vorkommt. Ein Zufall wäre zum Beispiel:
Imon mag Pflanzen.
aaaa aaa thdnaaaa
Imon mag Imonzen
Dies wäre ein hochgradig unwahrscheinlicher Zufall, da hierbei Zeichenfolge des Schlüssels in 1 bestimmten Kombination zusammentreffen würden.
Zurück zum Abstand von 9 Zeichen. Dieser Abstand sagt uns, dass der Schlüssel entweder 3 oder 9 Zeichen lang ist, da dies die einzigen Teiler von 9 sind.
Mlqlgmu nsimnev Ftpeoln oivaezoez. Lhbmp nsimnev ftpeolnll Nsimnev ftpeolnlln Mlünetu llr Mlqlgmu ppnblrplr.
Diesmal beträgt der Abstand 6 Zeichen. Da 9 kein Teiler für 6 ist, bleibt nur noch die Möglichkeit, dass der Schlüssel 3 Zeichen lang sein muss.
Zugegeben: Ich habe das Beispiel so konstruiert, dass es einfach für eine Erklärung ist. Um so später Rückschlüsse zu ziehen, ist es aber besser, wenn die Texte relativ lang werden, da mein Beispiel schon durch den Zufall hätte verfälscht sein können.
So, jetzt haben wir die Länge des Schlüssels. Und dann?
Wir wissen, dass jeder n-te Buchstabe (in diesem Fall jeder dritte) mit dem selben Vigenere-Alphabet verschlüsselt wird. Somit lässt sich nun die sogenannte Häufigkeitsanalyse anwenden:
WAS IST DAS?
Mit der Häufigkeitsanalyse zählen wir im Prinzip das Vorkommen eines bestimmten Buchstaben in einem Alphabet. Wenn bspw. das "e", das praktisch jeder etwa fünfte Buchstabe eines Textes sein muss, kaum vorkommt, dafür aber sich das "x" aufdrängt mit einer ähnlichen Statistik - dann wissen wir, dass dieser durch diesen ersetzt worden ist.
Diese ergibt für unseren kryptischen Text:
(("a" 1) ("b" 2) ("c" 1) ("d" 0) ("e" 9) ("f" 3) ("g" 2) ("h" 1) ("i" 4) ("j" 0) ("k" 0) ("l" 17) ("m" 9) ("n" 12) ("o" 5) ("p" 7) ("q" 2) ("r" 3) ("s" 3) ("t" 4) ("u" 3) ("v" 4) ("w" 0) ("x" 0) ("y" 0) ("z" 2))
Das L drängt sich auf - kann es sein? Kann es sein, dass sich das e als dieses ausgibt?
Wir wissen jedenfalls, dass wenn die l's in 3er Abständen vorkommen, dies wahrscheinlich ist. Aber testen wir es. Undzwar auf die RICHTIGE Art und Weise. Das was ich gerade getan habe, funktioniert nur, wenn auf jeden Buchstaben das selbe Alphabet angewendet worden wäre (siehe Caesar). Da dies nicht der Fall ist...
->
Wir machen aus unserem Krypto-Gedöns:
"Mlqlgmu nsimnev Ftpeoln oivaezoez. Lhbmp nsimnev ftpeolnll Nsimnev ftpeolnlln Mlünetu llr Mlqlgmu ppnblrplr"
FOLGENDES:
mluietooaolmsnfennmvplllelmlunrr
Ich habe folgendes gemacht:
- Großbuchstaben wurden entfernt
- Leerzeichen wurden entfernt
- Alle Buchstaben, die nicht 1+n*3 sind, wurden entfernt. So blieb nur jeder dritte Buchstabe.
(("a" 1) ("b" 0) ("c" 0) ("d" 0) ("e" 3) ("f" 1) ("g" 0) ("h" 0) ("i" 1) ("j" 0) ("k" 0) ("l" 7) ("m" 4) ("n" 4) ("o" 3) ("p" 1) ("q" 0) ("r" 2) ("s" 1) ("t" 1) ("u" 2) ("v" 1) ("w" 0) ("x" 0) ("y" 0) ("z" 0))
L kommt am häufigsten vor. Wir gehen davon aus, dass es somit für "e" steht.
Laut Vigenear Tabelle kommt ein "L" für "E" nur, wenn der Schlüssel "H" ist.
Somit ist der Schlüssel HXX.
Diese beiden X stehen nicht für den Buchstaben X, sondern für Unbekannte. Wir verfahren weiter.
Diesmal verbleiben nur: 2 + n*3
Wir machen aus unserem Krypto-Gedöns:
"Mlqlgmu nsimnev Ftpeoln oivaezoez. Lhbmp nsimnev ftpeolnll Nsimnev ftpeolnlln Mlünetu llr Mlqlgmu ppnblrplr"
FOLGENDES:
lgnmvplieehpietolsnfennütllgpbp
Das Ü ignorieren wir, da ich die Vigenear Verschlüsselung mit einer Website gemacht habe, die scheinbar weiter zählt.
Herauskommt:
(("a" 0) ("b" 1) ("c" 0) ("d" 0) ("e" 4) ("f" 1) ("g" 2) ("h" 1) ("i" 2) ("j" 0) ("k" 0) ("l" 5) ("m" 1) ("n" 4) ("o" 1) ("p" 4) ("q" 0) ("r" 0) ("s" 1) ("t" 2) ("u" 0) ("v" 1) ("w" 0) ("x" 0) ("y" 0) ("z" 0))
Wahrscheinlichkeiten sind auch nur Wahrscheinlichkeiten! Tatsächlich ist der Schlüssel hier A, auch wenn sich das H wieder aufdrängt, indem "L" oft vorkommt. Dies ist Zufall. Die zweithäufigste Häufigkeit, nämlich 4 für n und e, trifft zu. In diesem Fall ist es e. Da e für e steht, kann der Schlüssel hier nur a geheißen haben.
Ich fasse zusammen: die Häufigkeitsanalyse hat von mir ein Beispiel bekommen, das Nutzen und Probleme dargestellt hat. Dem Problem wären wir allerdings mit einem langen Text entgangen, aber nicht jeder Text ist nun einmal lang. Was will man machen...
Ich erkläre dann nochmal den Code zur Häufigkeitsanalyse per se:
(define snashimon '(("a" 0) ("b" 0) ("c" 0) ("d" 0) ("e" 0) ("f" 0) ("g" 0) ("h" 0) ("i" 0) ("j" 0) ("k" 0) ("l" 0) ("m" 0) ("n" 0) ("o" 0) ("p" 0) ("q" 0) ("r" 0) ("s" 0) ("t" 0) ("u" 0) ("v" 0) ("w" 0) ("x" 0) ("y" 0) ("z" 0)))
(define (start text)
(analytiko (string->list text) snashimon))
(define (analytiko text alphabet)
(cond ((null? text) alphabet)
((equal? (first text) #\space) (analytiko (rest text) alphabet))
(else (analytiko (rest text) (counter (first text) alphabet)))))
(define (counter elem alphabet)
(cond ((equal? (first(string->list (first(first alphabet)))) elem) (append (list(cons (first(first alphabet)) (list (+ 1 (first(rest(first alphabet))))))) (rest alphabet)))
(else (cons (first alphabet) (counter elem (rest alphabet))) )
)
)
Die Liste Snashimon entnahm ich dem Video, dass Frau Kück bereitgestellt hat.
Der REst ist ziemlcih einfach: Der Text wird zu einer verarbeitbaren Liste verarbeitet, Leertasten werden gestrichen, und die einzelnen Nullen in Snashimon werden je nach Bedarf bearbeitet.