Häufigkeitsanalyse bei homophoner Verschlüsselung

Hallo Menschen und Hobby-Kryptologen,

ich finde gerade etwas Zeit, mich den Programmen zu widmen, die ich das Semester über immer vor mir hergeschoben habe. Momentan bastle ich an einem Programm, das die Kryptoanalyse verschlüsselter Texte erleichtern soll.

Wer jetzt schon das Interesse verloren hat, kann den Thread schließen, es wird nicht mehr interessanter ich will das nur kurz etwas ausführen, damit mein Anliegen deutlich wird.

Homophone Verschlüsselung: http://de.wikipedia.org/wiki/Homophone_Verschl%C3%BCsselung Ein Substitutionsverfahren, wo ein Symbol aus dem Klartext durch mehrere verschiedene Symbole ersetzt werden kann, d.h. der Klartext "TEXT" könnte zu "ABCD" verschlüsselt werden, wobei sowohl "A" als auch "D" dem Klartextsymbol "T" entsprechen. Zweck der Mehrfachbelegung ist, eine Häufigkeitsanalyse zu erschweren. Da im geschriebenen Text unterschiedliche Buchstaben unterschiedlich häufig vorkommen (das "e" im Deutschen z.B. sehr oft, "y" so gut wie nie), lässt sich durch Abzählen der Vorkommen von Zeichen eines verschlüsselten Textes ungefähr abschätzen, welches Zeichen das sein wird. Um das zu erschweren, verwendet man für häufig im Klartext vorkommende Zeichen mehrere Zeichen im verschlüsselten Text, um die Häufigkeiten anzugleichen.

So, die homophone Verschlüsselung hat aber, vor allem, wenn auf dem Papier durchgeführt, einen großen Schwachpunkt: die unterschiedlichen Ersetzungszeichen für ein Klartextzeichen werden oft in gleichbleibender Reihenfolge verwendet. Ein Beispiel:

"DASISTEINTOLLERTEST"

kann dann z.B. werden zu

"XXXXXAXXXQXXXXXAXXQ"

wichtig sind hierbei nur die T-Ersetzungen. In dem Beispiel hätte man jetzt für das Klartext-T die Ersetzungen A und Q gewählt und die immer der Reihe nach abgehandelt.

Je nach Länge des Textes ergeben sich dadurch gut erkennbare Muster, weil im verschlüsselten Text z.B. immer zwischen zwei As genau ein Q steht, aber beliebig viele Ns oder Ps oder Ws. Damit weiß ich zwar noch nicht, wofür ein A oder ein Q ursprünglich stand, aber ich weiß, dass diese beiden mit einiger Sicherheit das gleiche Zeichen ersetzen. Ich habe für mein Programm also ein paar Methoden geschrieben, wo ich recht gut hervorheben kann, welche Zeichen derart zusammenhängen.

So, das ist die erste Information, die ich habe. Die zweite Information ist eine Häufigkeitstabelle der Buchstaben A-Z im Schriftenglisch, damit man das auch vergleichen kann später.

Warum ich den Thread hier schreibe ist, dass mir irgendwie die zündende Idee fehlt, wie ich jetzt vom einen aufs andere komme, und ich hoffe, dass hier jemand schon mal was ähnliches gemacht hat oder in Statistik aufgeweckter ist als ich oder einfach so einen Rat weiß. Also ich suche ein (Näherungs-)Verfahren, das mir anhand der Ähnlichkeit zwischen den Zeichen sowie der Häufigkeitstabelle eine Wahrscheinlichkeit angibt, mit der das jeweilige Ersetzungszeichen ein bestimmter Buchstabe ist, also

(Ersetzungszeichen, Buchstabe des Alphabets A-Z) -> [weird magic] -> (0..1).

Um im Beispiel zu bleiben, sollte möglichst (Q, T) = 1 und (Q, F) = 0 sein.

In der Theorie klingt Häufigkeitsanalyse so einfach, dass es nirgends wirklich detailliert ausgeführt wird, wie man rechnen muss, damit man auf brauchbare Ergebnisse kommt. Ich brauche ja irgendwie die Wahrscheinlichkeit, dass "dieses und jenes" Zeichen zusammengehören UND dann die Ähnlichkeit dieser zusammenhängender Zeichen zur Häufigkeit desjenigen Buchstaben aus der Häufigkeitstabelle. :confused:

Ich würde mich sehr freuen, wenn jemand hier ein paar Ideen einstreuen könnte

Gruß und weiterhin schöne Ferien

mOfl

Hey, danke für die Antwort! An CrypTool habe ich gar nicht mehr gedacht. Leider kann mir das aber auch nicht weiterhelfen, weil das nur die einfache Frequenzanalyse kennt. Da die Frequenzanalyse für homophone Verschlüsselung ja schon recht spezifisch und dazu noch wenig interessant ist, glaube ich nicht, dass es da schon irgendwo eine fertige Lösung gibt, wo ich spickeln kann. Naja, mein Kopf raucht weiter, hoffentlich komme ich irgendwann drauf. Ich hatte beinahe schon gedacht, dieses Gefühl des Nichtweiterkommens, obwohl man weiß, dass die Lösung recht simpel sein muss, hätte ich mit der Statistikprüfung damals hinter mir gelassen... :sudern:

Danke für die Antwort! Du hast natürlich Recht mit dem, was du sagst, vielleicht habe ich mich nicht klar genug ausgedrückt. Ich weiß _nicht_, dass A und Q zu T gehören, sondern nur, dass A und Q (wahrscheinlich) zusammengehören. Ich hab ja die Information aus dem (Beispiel-)Klartext nicht mehr, nur den verschlüsselten Text. Was mir fehlt und woran ich tüftle ist genau dieser Schritt, wie ich von "A und Q sind sehr ähnlich" und "T hat im Schriftenglisch die Wahrscheinlichkeit 7 %" auf "A und Q sind wahrscheinlich T" komme. Wie du schon richtig sagst, ist der Sinn der homophonen Verschlüsselung das Angleichen der Wahrscheinlichkeiten der verwendeten Symbole, z.B. alle auf 1 %. Dazu werden dann natürlich auch mehr als 26 Substitutionssymbole gebraucht, das mit dem A und Q war nur ein Beispiel, das so natürlich nicht funktionieren würde, weil ich nicht mehr von den Buchstaben in die Buchstaben abbilden kann.

In meinem Programm werden auch noch andere Methoden zur Analyse verwendet, z.B. eine Trigramm-Analyse und ein Wörterbuchvergleich, weil man vor allem bei einer regelmäßigen Verwendung der unterschiedlichen Ersetzungszeichen für einen Buchstaben da schon klare Muster erkennen und dann bestimmte Buchstaben sehr gewichten kann. Nur möchte ich vorher noch die offensichtliche Ähnlichkeit einiger Ersetzungszeichen zueinander ausnutzen, damit der Rest schneller zum Ziel führt.

Ja, ich verstehe, was du meinst. Im Prinzip hast du damit auch recht, nur klappt das für meine Beispieltexte nicht wirklich. Das liegt aber wohl nicht am Verfahren an sich, sondern an der Kürze der Texte. Häufige Buchstaben kann ich relativ gut zuordnen, aber seltene gehen überhaupt nicht, weil die Häufigkeitswerte des Textes einfach gar nicht mit den erwarteten Häufigkeiten im Schriftenglisch übereinstimmen. Zudem ist mir vorher nicht aufgefallen, dass meine Ähnlichkeitsfunktion für die seltenen Zeichen natürlich nicht stimmt. Wenn j, q und x genau einmal im Klartext vorkommen, dann ist das im ersten Post genannte Kriterium ja erfüllt, dass zwischen je zwei Ersetzungen von j genau eine Ersetzung von q und eine von x kommt, mit dem Ergebnis, dass j, q und x als der gleiche Klartextbuchstabe gesehen werden. Damit wird dann ohnehin nach einer falschen Gesamthäufigkeit gesucht, aber ich glaube, um das Problem kümmere ich mich jetzt nicht weiter, weil dadurch nur die seltensten Zeichen falsch interpretiert werden, das kann ich verschmerzen. Die Trigramm-Analyse und der Wörterbuchvergleich haben ohnehin eine gewisse Fehlertoleranz, die das dann auffangen sollte.

Vielen Dank für dein Input! Wenn man sich in ein Problem vergräbt, erkennt man manchmal die einfachsten Lösungen nicht mehr...