11  Die Vigenère-Verschlüsselung brechen

TippNotebook interaktiv ausführen

Die entscheidende Schwäche der Vigenère-Verschlüsselung wurde Mitte des 19. Jahrhunderts von zwei Männern unabhängig voneinander entdeckt. Einer von ihnen war Charles Babbage, ein britischer Universalgelehrter. Er entdeckte die Schwachstelle, um eine Wette zu gewinnen. Der andere war Friedrich Wilhelm Kasiski, ein pensionierter Major der preußischen Armee, der nach seiner Pensionierung seine Zeit mit Schreiben verbrachte. Die Methode zum Brechen der Vigenère-Verschlüsselung ist nach dem preußischen Major Kasiski benannt.

11.1 Die Kasiski-Methode – Zusammenfassung

Die Kasiski-Methode ist eine Technik zum Brechen der Vigenère-Verschlüsselung, bei der wiederholte Muster im Geheimtext ausgenutzt werden. So funktioniert sie:

11.1.1 Grundprinzip

Wenn dieselbe Klartextsequenz mit demselben Teil des Schlüssels verschlüsselt wird, entstehen identische Geheimtextsequenzen. Indem wir diese Wiederholungen finden, können wir die Schlüssellänge bestimmen.

11.1.2 Schritt-für-Schritt-Anleitung

1. Wiederholte Sequenzen finden
   • Den Geheimtext nach identischen Sequenzen von 3+ Zeichen durchsuchen.
   • Die Positionen aufzeichnen, an denen diese Sequenzen auftreten.
2. Abstände berechnen
   • Den Abstand zwischen wiederholten Sequenzen messen.
   • Die Schlüssellänge muss ein Teiler dieser Abstände sein.
3. Schlüssellänge bestimmen
   • Den größten gemeinsamen Teiler (ggT) aller Abstände finden.
   • Oder nach dem häufigsten gemeinsamen Teiler suchen.
   • Dies ergibt die wahrscheinliche Schlüssellänge.
4. Häufigkeitsanalyse
   • Den Geheimtext basierend auf der Schlüssellänge in Gruppen aufteilen.
   • Jede Gruppe wurde mit demselben Schlüsselzeichen verschlüsselt.
   • Eine Häufigkeitsanalyse auf jede Gruppe separat anwenden.
   • Die Buchstabenhäufigkeiten mit den erwarteten Mustern der Sprache abgleichen.

11.1.3 Beispiel

Wenn „THE“ mehrmals im Klartext an Positionen erscheint, an denen sich der Schlüssel wiederholt, sind die entsprechenden Geheimtextsequenzen identisch. Wenn diese Sequenzen 10 Positionen voneinander entfernt sind, ist die Schlüssellänge wahrscheinlich ein Teiler von 10 (1, 2, 5 oder 10).

Für ein konstruiertes Beispiel, wenn der Klartext „the codes in the word and the message“ lautet und der Schlüssel „crypt“ ist, erhalten wir den folgenden Geheimtext.

p: t h e c o d e s i n t h e w o r d a n d t h e m
k: c r y p t c r y p t c r y p t c r y p t c r y p
c: V Y C r h f v q x g V Y C l h t u y c w V Y C b

Beachten Sie, dass das Geheimtextmuster VYC dreimal im Geheimtext vorkommt und jedes Mal ein Abstand von 10 Buchstaben zwischen dem Anfang eines VYC und dem nächsten liegt. Dies geschieht, weil dasselbe Klartextmuster, „the“, jedes Mal auf denselben Teil des Schlüssels, „cry“, trifft, was zum selben Geheimtext führt. Die Wiederholung des Schlüsselworts ist hier die Schwachstelle. Die Duplikate im Geheimtext sind alle 10 Buchstaben voneinander entfernt. Babbage und Kasiski schlussfolgerten, dass dies bedeutet, dass die Länge des Schlüssels ein Teiler von 10 ist. Die Teiler von 10 sind 10, 5 und 2. Man könnte argumentieren, dass ein Schlüssel der Länge 2 zu kurz ist, um viel Sicherheit zu bieten, sodass ein Schlüssel der Länge 5 oder 10 wahrscheinlicher ist. Ein Schlüssel der Länge 10 hätte in einem so kurzen Geheimtext wahrscheinlich nicht so viele Wiederholungen, daher wird der Kryptoanalytiker seine Arbeit mit einer angenommenen Schlüssellänge von 5 beginnen.

Eine Schlüssellänge von 5 bedeutet, dass der 1., 6., 11., 16. usw. Buchstabe alle mit demselben Schlüsselbuchstaben und somit mit demselben Alphabet aus der Vigenère-Tabelle verschlüsselt werden. In ähnlicher Weise werden der 2., 7., 12., 17. usw. Buchstabe alle mit dem nächsten Schlüsselalphabet verschlüsselt. Wenn wir also das Kryptogramm in 5 Buchstabengruppen aufteilen, haben wir 5 monoalphabetische Substitutions-Geheimtexte. Wir können dann eine Häufigkeitsanalyse jeder Gruppe durchführen und jede Gruppe separat lösen. Und in einem standardmäßig verschobenen Alphabet wie in der normalen Vigenère-Tabelle haben wir, wenn wir einen einzigen Geheimtext-Alphabetbuchstaben finden können, das gesamte Alphabet.¹

11.1.4 Warum es funktioniert

Die Schwäche der Vigenère-Verschlüsselung liegt in der Wiederholung des Schlüssels. Sobald die Schlüssellänge bekannt ist, wird die Verschlüsselung zu mehreren einfachen Caesar-Verschlüsselungen, die mittels Häufigkeitsanalyse gebrochen werden können.

---

1. Dooley, John F. History of Cryptography and Cryptanalysis: Codes, Ciphers, and Their Algorithms. History of Computing. Cham: Springer International Publishing, 2024. https://doi.org/10.1007/978-3-031-67485-3. S. 76.