Vigenère knacken

Steht dieselbe Klartextfolge (z. B. ein häufiges Wort) zweimal im Text und beginnt beide Male an derselben Stelle des periodisch wiederholten Schlüsselworts, wird sie mit denselben Verschiebungen verschlüsselt und ergibt dieselbe Geheimtextfolge. Der Abstand ist dann ein Vielfaches der Schlüssellänge.

Der einzige gemeinsame Teiler größer als 1 ist 5: \(\operatorname{ggT}(100, 35, 95, 75, 15) = 5\). Die Schlüssellänge teilt alle Abstände, also ist sie vermutlich 5 (die Länge 1 hieße Caesar; dann müsste die Auszählung eine deutliche E-Spitze zeigen, die ein Vigenère-Text nicht hat).

Zwei zufällige Dreierfolgen stimmen mit einer Wahrscheinlichkeit von etwa \(1 : 26^3 = 1 : 17\,576\) überein. In 219 Buchstaben gibt es 217 Dreierfolgen und damit \(\binom{217}{2} = 23\,436\) Paare — man erwartet also rund eine zufällige Dreierwiederholung. FLJ könnte Zufall sein (ihr Abstand 15 passt hier aber zu 5).

Eine zufällige Übereinstimmung von 13 Buchstaben ist dagegen praktisch ausgeschlossen (\(26^{13} \approx 2{,}5 \cdot 10^{18}\) Möglichkeiten). Sie stammt fast sicher von einer gleichen Klartextfolge unter gleicher Schlüsselposition; ihr Abstand 35 ist daher ein verlässlicher Hinweis.

Teiltexte 1–4 (häufigster Buchstabe ↔ E): J → F, Y → U, G → C, L → H. Probe mit dem zweithäufigsten Buchstaben: S − F = N, N − U = T, V − C = T, S bzw. Y − H = L bzw. R — häufige Buchstaben, die Zuordnung ist plausibel.

Teiltext 5 ist nicht eindeutig: A und J kommen gleich oft vor, und E muss nicht der häufigste Buchstabe sein. Test der Kandidaten:

Nur S liefert durchweg häufige deutsche Buchstaben (E selbst ist hier nur viermal vertreten — bei 43 Buchstaben ein Zufallseffekt). Zusammen mit dem Hinweis „Tiername“ ergibt sich das Schlüsselwort FUCHS; der entschlüsselte Text beginnt mit „DER SCHATZ LIEGT UNTER DER ALTEN EICHE …“.

def haeufigster(text):
    anzahl = [0] * 26
    for c in text:
        anzahl[ord(c) - 65] += 1
    # Nummer des häufigsten Buchstabens
    return anzahl.index(max(anzahl))

def schluessel_finden(geheimtext, n):
    wort = ""
    for i in range(n):
        teiltext = ""
        # jeder n-te Buchstabe ab Position i
        for j in range(i, len(geheimtext), n):
            teiltext = teiltext + geheimtext[j]
        # häufigster Buchstabe ↔ E (Nummer 4)
        k = (haeufigster(teiltext) - 4) % 26
        wort = wort + chr(k + 65)
    return wort

Mit dem Geheimtext und \(n = 5\) liefert die Funktion "FUCHW": Bei Gleichstand gibt index den ersten Treffer (A) zurück. Ein vollständiger Entwurf benennt diese Schwäche, z. B. mit dem Vorschlag, bei Gleichstand mehrere Kandidaten zurückzugeben oder die Teiltexte mit der ganzen deutschen Häufigkeitsverteilung zu vergleichen. Kürzere Lösungen mit Slicing geheimtext[i::n] sind gleichwertig.

Schnitzeljagd: Der Schlüssel ist ein kurzes, sinnvolles Wort; bei 219 Buchstaben hat jeder Teiltext über 40 Buchstaben. Kasiski-Test und spaltenweise Häufigkeitsanalyse führen mit Papier und Bleistift in unter einer Stunde zum Ziel. Für ein Spiel ist das angemessen — als Schutz geheimer Daten ist es unsicher.

Zufälliger Schlüssel so lang wie der Text, einmal verwendet (One-Time-Pad): Es gibt keine Periode, also keine systematischen Wiederholungen, und jeder „Teiltext“ besteht nur aus einem Buchstaben. Zu einem Geheimtext passt jeder gleich lange Klartext mit einem passenden Schlüssel — das Verfahren ist beweisbar sicher. Der Preis: Der Schlüssel ist so groß wie die Nachricht und muss vorher sicher übergeben werden; bei Wiederverwendung bricht die Sicherheit zusammen. Vollständig ist eine Bewertung, die beide Fälle an denselben Kriterien misst.