02 Vigenère entschlüsseln

Der französische Diplomat und Kryptograph Blaise de Vigenère entwickelte im 16. Jahrhundert eine für lange Zeiten unknackbare, polyalphabetische Verschlüsselung. Im Gegensatz zur monoalphabetischen bedient sie sich nicht eines einzelnen Schlüsselalphabetes, dem man mit Hilfe von Häufigkeitsanalysen schnell auf die Schliche kommt, sondern er benutzte für jeden Buchstaben des zu verschlüsselnden Textes ein eigenes. Hierfür verschob er das Alphabet um jeweils eine bestimmte Zahl (wie Ceasar um 3 und Rot13 um 13 Buchstaben verschiebt). Der hierfür verwendeter Verschiebeschlüssel ist dann das Schlüsselwort, mit dem der Kryptotext im Anschluss wieder entschlüsselt werden kann.

Am anschaulichsten lässt sich dieses Verfahren mit dem Vigenère -Quadrat verdeutlichen, welches alle 25 möglichen Verschiebungen darstellt:

Der erste Buchstabe des Klartextes “Scheibenwelt” – (R.I.P. Sir Terry Pratchett!) – ist ein S (obere gelbe Zeile im Bild) und wird mit dem ersten Buchstaben des Schlüssels “Terry”, also dem T, verschlüsselt (gelbe, linke Spalte im Bild), also das Alphabet um 19 Buchstaben verschoben (A=0) und landet auf dem L. Der zweite Buchstabe ist ein C und wird mit dem Schlüsselbuchstaben E zu einem G, …

Häufigkeitsanalysen laufen nun ins Leere, da die einzelnen Buchstaben jeweils nicht mehr mit dem gleichen ersetzt werden. Aber sicher ist die Vigenère-Verschlüsselung trotzdem nicht.

Je kürzer der Schlüssel und je länger der Klartext ist, um so einfacher wird es, den Code zu brechen. Da ein normaler Text, egal in welcher Sprache, bestimmte sich wiederholende Buchstabenfolgen hat (Bi- und Trigramme), steigt mit der Länge des Klartextes die Wahrscheinlichkeit, dass derartige Buchstabenfolgen mit den gleichen Schlüsselbuchstaben verschlüsselt wurden und sich der Kryptotext ähnelt. Hat man so eine Wiederholung von Bi- oder Trigrammen entdeckt, kann man daraus die Schlüssellänge ermittelt (ein Teiler der Entfernung zwischen den gleichen Buchstabenfolgen). Und nun mit dem Wissen um die Länge des Schlüsselwortes den Kryptotext Stück für Stück verschieben. Dieser Ansatz wurde einem seiner Entdecker nach Kasiski-Test getauft (KasiskiOnline-Tool).

Noch etwas theoretischer ist der Friedman-Test, dessen Algorithmus mit Wahrscheinlichkeiten, dass zwei zufällige Buchstaben gleich sind, Größenordnung der Schlüssellänge zu berechnen versucht.

Ebenfalls mit der Wahrscheinlichkeit arbeitet die Korrelationsfunktion. Zählt man die Buchstaben im Kryptotext und vergleicht sie mit der Buchstabenhäufigkeit der normalen Sprache, lässt sich mit einem genügend langen Text die Verschiebung anzeigen. Die Korrelationsfunktion besitzt bei der Verschiebung ein Maximum, bei der sich die zu vergleichenden Verteilungen am besten decken. Womit sich auch die Schlüssellänge bei genügend langen Texten gut ablesen lässt.

Fertig für alle Geocaching-Vigenère -Rätsel? Naja, eigentlich noch nicht ganz, es gibt noch mehr hübsche Lösungsansätze. Ist das Schlüsselwort ein echtes Wort aus dem Wörterbuch, lässt sich die ngramm-Analyse anwenden, die unter anderem auch bei Cryptoool-online implementiert ist. Hier wird mit wahrscheinlichen Bi- oder Trigrammen am Wortanfang gearbeitet, mit denen man Rückschlüsse auf den Schlüssel ziehen kann, in dem man wahrscheinliche Buchstabenkombinationen im Klartext findet.

Ähnlich aber weniger theoretisch funktionieren die Ansätze, bei denen man Teile des Schlüssels oder des Klartextes zu glauben kennt. Dabei ist es egal, welchen der beiden Ansätze man nutzen kann – man legt in jedem Fall das zu erwartende Wort/Wortteil (Nord, Ost, Cache, suchen, zweiundfuenfzig, der GC-Code oder der Ownername) über den Kryptotext und verschiebt um die jeweiligen Buchstaben vorwärts und rückwärts im Alphabet. Wer möchte und fähig dazu ist, kann das sicher schnell in Excel nachprogrammieren. Es ist aber dank Internet gar nicht nötig. f00l.de, nik kaanan und viele andere haben uns mit ihren Scripten diese Arbeit schon erleichtert. Wer sich weniger Mühe geben möchte, kann es auch mit einem Klick erst mal bei smurfoncrack probieren. Oder bei crypt-online, wo es auch Häufigkeits- und n-gramm-Analysen sowie ein Autokorrelationstool gibt. Ein simples aber manchmal auch funktionierendes Cracktool bietet die geocachingtoolbox an .

Und natürlich darf der GC Wizard nicht fehlen. In der Rubrik “Allgemeine Codelöser” gibt es auch einen Vigenère-Knacker. 😉

Übrigens hat der Herr Vigenère eine Verbesserung dieser Methode entwickelt, die aber nie dessen Bekanntheit erlangte, obwohl sie wesentlich sicherer gegen Analysen wie die hier beschriebenen ist.

Die Autokey-Verschlüsselung arbeitet ebenfalls mit einem Schlüsselwort und damit wie der hier beschriebenen Vigenère -Schlüssel, aber am Ende des Schlüssels wird für die Ver- und Entschlüsselung der Klartext angehängt. Somit ist die Schlüssellänge so lang wie der Kryptotext und wesentlich schwieriger zu knacken.