3. Häufigkeitsanalyse Caesar-Chiffre

Häufigkeitsanalyse Caesar-Chiffre

  • W

    Hallo zusammen,

    ich möchte einen mit der Vigenere-Verschlüsselung (http://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher) verschlüsselten Ciphertext knacken. Mein Programm ermittelt zuerst die Schlüssellänge und teilt den Text so in mehrere monoalphabetische Probleme (jeweils Caesar-Verschlüsselungen) auf. Und die möchte ich mit einer Häufigkeitsanalyse knacken. Die Sprache des Textes kenne ich.

    Mein Problem ist jetzt: Wie kann ich meinem Programm beibringen, die richtige Verschiebung zu finden? Die statistischen Werte sind ja nur eine Tendenz. Der Text der einzelnen Caesar-Verschlüsselungen hat jeweils ca. 100 Buchstaben.

    ZB:
    "wirklich": Der tatsächliche statistische Wert, "berechnet": die berechnete Häufigkeit im vorliegenden Text. 'Q' ist demnach sehr wahrscheinlich 'E', beim nächsten Buchstaben wird's schon kniffliger. 'E', 'K' und 'Y' haben eine sehr ähnliche Wahrscheinlichkeit und die Buchstaben danach auch.

    A wirklich: 8.167, A berechnet: 1.08696
B wirklich: 1.492, B berechnet: 3.26087
C wirklich: 2.782, C berechnet: 3.26087
D wirklich: 4.253, D berechnet: 4.34783
E wirklich: 12.702, E berechnet: 11.9565
F wirklich: 2.228, F berechnet: 2.17391
G wirklich: 2.015, G berechnet: 0
H wirklich: 6.094, H berechnet: 4.34783
I wirklich: 6.699, I berechnet: 6.52174
J wirklich: 0.153, J berechnet: 7.6087
K wirklich: 0.772, K berechnet: 10.8696
L wirklich: 4.025, L berechnet: 1.08696
M wirklich: 2.406, M berechnet: 4.34783
N wirklich: 6.749, N berechnet: 0
O wirklich: 7.507, O berechnet: 3.26087
P wirklich: 1.929, P berechnet: 0
Q wirklich: 0.095, Q berechnet: 14.1304
R wirklich: 5.987, R berechnet: 1.08696
S wirklich: 6.327, S berechnet: 1.08696
T wirklich: 9.056, T berechnet: 3.26087
U wirklich: 2.758, U berechnet: 0
V wirklich: 0.978, V berechnet: 3.26087
W wirklich: 2.36, W berechnet: 1.08696
X wirklich: 0.15, X berechnet: 1.08696
Y wirklich: 1.974, Y berechnet: 10.8696
Z wirklich: 0.074, Z berechnet: 0

    Liebe Grüße,
    WurzelAusZwei

    0
  • V

    Ja, 'Q' wird wohl zu 'E' sein entschlüsselt werden.
    Aber hey, das ist ein Cäsar-Unterproblem sagst Du.
    Dann muss auch 'R' zu 'F' werden und 'S' zu 'G' und so weiter.

    Ich suche nicht nur den häufigsten Buchstaben beider Histogramme, sondern vergleiche für jeden Schlüssel mein ganzes Berechnet-Histogramm mit dem ganzen Wirklich-Histogramm, und wähle den besten Schlüssel mit als Maß zum Beispiel Summe der Quadrate der Differenzen der relativen Häufigkeiten.

    0
  • W

    Hey volkard,

    volkard schrieb:

    Ja, 'Q' wird wohl zu 'E' sein entschlüsselt werden.
    Aber hey, das ist ein Cäsar-Unterproblem sagst Du.
    Dann muss auch 'R' zu 'F' werden und 'S' zu 'G' und so weiter.

    Ja, bei Vigenère gibt es ein Codewort, das solange aneinandergereiht wird, bis der ganze Text abgedeckt ist. Und der jeweilige Buchstabe bestimmt dann, mit welchem Alphabet der Buchstabe des Plaintextes verschlüsselt wird. ZB: Codewort "ich", Plaintext: "heuteisteskalt". Dann wird 'h' mit dem Alphabet i-h verschlüsselt, 'e' mit Alphabet c-b, 'u' mit h-g, 't' mit i-h usw. Hier ist die Länge des Codeworts 3, daher weiß man, dass 1., 4., 7., 10., ... Buchstabe mit dem selben Alphabet verschüsselt sind, was mehrere Caesar-Verschlüsselungen ergibt.

    volkard schrieb:

    Ich suche nicht nur den häufigsten Buchstaben beider Histogramme, sondern vergleiche für jeden Schlüssel mein ganzes Berechnet-Histogramm mit dem ganzen Wirklich-Histogramm, und wähle den besten Schlüssel mit als Maß zum Beispiel Summe der Quadrate der Differenzen der relativen Häufigkeiten.

    Das klingt gut. 🙂 Frage nebenbei: Ändert das Quadrat etwas?

    Liebe Grüße,
    WurzelAusZwei

    0
  • W

    WurzelAusZwei schrieb:

    Das klingt gut. 🙂 Frage nebenbei: Ändert das Quadrat etwas?

    Blöde Frage von mir, natürlich will man negative Differenzen umgehen. Danke, so werde ich es machen!

    0

  • Man will auch grössere Werte stärker gewichten.
    Wenns nur um die negativen Werte ginge, würde man einfach den Absolutwert nehmen.

    0
  • V

    Das mit dem Vorzeichen ist ein netter Nebeneffekt. Vor allem will man besonders große Fehler überprortional einfließen lassen.

    Buchstabe Wirklich Gemessen Abstand Fehlerquadrat
    N 0.09 0.06 0.03 0.09 //Teuer!
    C 0.03 0.04 0.01 0.01
    G 0.03 0.04 0.01 0.01
    Q 0.02 0.03 0.01 0.01
    Summe der Abstände: 0.06
    Summe der Fehlerquadrate: 0.12 //schlecht

    Buchstabe Wirklich Gemessen Abstand Fehlerquadrat
    N 0.09 0.07 0.02 0.04
    C 0.03 0.02 0.01 0.01
    G 0.03 0.04 0.01 0.01
    Q 0.02 0.04 0.02 0.04
    Summe der Abstände: auch 0.06!
    Summe der Fehlerquadrate: 0.10 //ein wenig besser

    Buchstabe Wirklich Gemessen Abstand Fehlerquadrat
    N 0.09 0.06 0.03 0.09 //Teuer!
    C 0.03 0.03 0.00 0.00
    G 0.03 0.03 0.00 0.00
    Q 0.02 0.05 0.03 0.09 //Teuer!
    Summe der Abstände: auch wieder 0.06
    Summe der Fehlerquadrate: 0.18 //kathastrophal

    Die Methode mit der Summe der Fehlerquadrate ist also recht gutmütig gegenüber leichtem Rauschen, schlägt aber unerbittlich zu, wenn Du zum Beispiel sauviele 'q' oder echt wenige 'e' im dechiffrierten Text findest.

    0
  • W

    Ahhh, klar!

    Das funktioniert so tadellos und der mit Vigenère verschlüsselte Text ist bereits geknackt. 👍

    0
Anmelden zum Antworten