Ninas Schmierblo(g)ck

Konservierungsmittel...

Geocaching Mysteries lösen - 6.3 Vigenère entschlüsseln

Geschrieben von Nina • Freitag, 13. März 2015 • Kategorie: Mysteries lösen
Geocaching Mysteries lösen

Kapitel 6.3 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, siehe zum Beispiel hier), 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 (Kasiski-Online-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.

Praktisch untersuchen kann man dies z.B. hier (Dank Java-Sicherheitseinstellungen könnte es einfacher sein, das Script herunterzuladen und lokal zu starten. Das Java-Script stammt nicht von mir, daher auf eigene Gefahr. ). Wenn ihr mögt, startet dieses Script und gebt oben folgenden Geheimtext ein:

Rensi ssm Evoimzk nek cvoisdlxtx. Zforzkeouuhko Mxmwmhxm lklmdr nixrix Ttf jüb ebmix Pxbldaz. Keocadvvivg. Nodxq Xkg brx novg ileg fixan rs oigdv. Ydxq mct wzw xuk ais mbq wy, wxhp oigd qoigdv lebcix svgakrsdr Uamyix smzixdbf zyn ehrus tm qsr onvlebqixnm?

Es erscheint im unteren Fenster ein Balkendiagramm. Interessant für die Schlüssellänge sind jetzt die längeren Balken, die sich mit einem gemeinsamen Teiler wiederholen. Im Beispiel wirkt die 5 sehr aufdringlich, da sich bei 5, 10, 15, 20 u.s.w. die höchsten Balken zeigen. Klicken wir nun auf den Balken mit der 5, setzen also testweise die Schlüssellänge auf 5, können wir mit den fünf "Strichen" unter "Schlüssel bestimmen" passende Buchstaben "raten".

Es erscheint ein neues Balkendiagramm mit möglichen Schlüsselbuchstaben, die zu dieser Schlüsselstelle passen. Sticht einer davon besonders durch seine Länge heraus, ist die Wahrscheinlichkeit, dass es sich um den gesuchten handelt, besonders groß. Klicken wir nun auf das wahrscheinliche "K", erscheint im rechten Fenster unter dem Geheimtext an jeder fünften Stelle eine Entschlüsselung auf "K". Sieht erst mal nach normalen, deutschen Buchstaben aus, also weiter. Beim zweiten Schlüsselbuchstabe ist das "A" am wahrscheinlichsten, beim 3. das "T". Jetzt lässt sich der Klartext fast schon erraten. Der Schlüssel aber auch. Und auch wenn das Tool Leer- und Satzzeichen unterschlägt, lässt sich nun lesen, dass ich diesen Blogbeitrag an einem Freitag, den 13. geschrieben habe.

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 n-gramm-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 .

Ü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.

Zurück zum Inhaltsverzeichnis


Geocaching Mysteries lösen - Kapitel 6 - Verschlüsselungen - Geheimtexte manuell entschlüsseln

Geschrieben von Nina • Montag, 1. April 2013 • Kategorie: Mysteries lösen
Geocaching Mysteries lösen

Kapitel 6.1.2 - Verschlüsselungen - Geheimtexte manuell entschlüsseln


Einfache, monoalphabetische Verschlüsselungen, bei dem jedem Buchstaben des Alphabets einfach ein anderer Buchstabe, ein anderes Zeichen oder eine Zahlenkette zugewiesen wird, lassen sich in relativ kurzer Zeit Mithilfe von Zettel, Papier und einer Tabelle für Buchstabenhäufigkeiten der jeweiligen Sprache sowie ein wenig Zeit entschlüsseln.

Grundsätzlich gilt: je länger der Geheimtext ist, um so einfacher ist es, ihm über Buchstabenhäufigkeiten, Worthäufigkeiten, Wortendungen und sprachliches Geschick auf die Schliche zu kommen.

Hierfür muss man als erstes die Zeichen des Geheimtextes zählen und nach Häufigkeit sortieren. Hat man (je nach Textlänge) etwa 20-27 unterschiedliche Zeichen, hat man mit ziemlicher Sicherheit ein einfach verschlüsseltes Alphabet (26 Zeichen) plus Leerzeichen und möglicherweise noch ein oder zwei Interpunktionszeichen (Punkt, Komma und für die Geocacher vielleicht noch ein Gradzeichen). Sind es ungefähr 55 Zeichen, ist möglicherweise Groß- und Kleinschreibung verwendet worden, gegebenenfalls auch deutsche Umlaute. Kommen noch etwa 10 Zeichen oben drauf, könnten sich auch noch Ziffern im Text befinden.

Natürlich gibt es im Internet willige Helfer, die einem das Zählen und Sortieren und in vielen Fällen sogar noch das Entschlüsseln abnehmen. Eine Häufigkeitsverteilung kann man sehr hübsch bei cryptool-online und kas-bc.de erledigen lassen.

Auf der Cryptool-Seite findet sich, wie auch im Wikipedia-Artikel, die Tabelle mit Buchstabenhäufigkeiten der deutschen und englischen Sprache. Ebenfalls findet sich dort das „Häufigkeitsgebirge“, was sehr hilfreich ist, wenn man Rotations-Chiffren optisch erkennen möchte. Also die Form von Buchstabenverschlüsselungen, bei denen das Alphabet nur um x Stellen verschoben wird. Bei Caesar und seinem Code waren es 3 (aus einem "A" wird ein "C", aus einem "B" ein "D", ...), heute wird sehr häufig die 13 benutzt (ROT13), was den Charme hat, daß man mit einem weiteren Sprung um 13 Zeichen im Alphabet wieder beim Ausgangstext angekommen ist. Entschlüsseln und Verschlüsseln sind somit auf gleichem Wege möglich. Wobei zu betonen ist, daß eine Rotationschiffre keineswegs eine irgend geartete Verschlüsselung ist, also nie benutzt werden sollte, um wirklich geheimzuhaltende Informationen zu verschleiern. Es ist eher eine Spielerei, bei der ein Text nicht sofort lesbar ist.

Ergibt die Zeichenverteilung ähnliche „Ausschläge“, wie die Buchstabenverteilung in den Tabellen? Es sollten ein bis zwei Zeichen sehr häufig vorkommen, das Leerzeichen (sofern es überhaupt verschlüsselt worden ist) ist üblicherweise das häufigste Zeichen. Auf dieses kann aber auch verzichtet werden, dannsinddieWörternurnichtmehrsoleichtlesbar. Dem Leerzeichen dicht auf den Fersen ist der Buchstaben „E“, der ungefähr 17% der Buchstaben in durchschnittlichen Deutschen Texten besetzt.

Sogar in meiner sehr kleinen Beispielverschlüsselung stimmt die relative Häufigkeit des „E“s.

Der Geheimtext:

tuxjlaktlfckokotyfckojxkobokxlaktl


hat zwar nur 12 verschiedene Buchstaben, das liegt aber daran, dass er so kurz geraten ist. Der häufigste Buchstabe ist das „K“ mit ungefähr 20%. Nehmen wir an, dass dies das E ist, haben wir vielleicht schon ein Fünftel des Geheimtextes entschlüsselt und vor allem ein Ansatzpunkt für sprachliches Geschick und typische Buchstabenverbindungen oder Wortendungen.

So gibt es neben den Tabellen für die Buchstabenhäufigkeiten auch welche mit den häufigsten Buchstabenendungen. Hier führen: „en, em, es, el und er, st, ing, sam, bar, lich, ung, heit, keit“.

Auch interessant sind die häufigsten Bigramme, also zusammen auftretende Buchstabenpaare: „en, er, ch, ck, (wobei c alleine fast nie vorkommt), te, de, nd, ei, ie, in, es“. Und Trigramme (die drei am Häufigsten aufeinander folgenden Buchstaben): „ein, ich, nde, die, und, der, che, end, gen, sch“.

Einen weiteren Blick sollte man auf die im Deutschen am Häufigsten verwendeten Wörter werfen. Diese Hitliste führen „der, die, und, in, den, von, zu, das, mit, sich, des, auf, für, ist und im“ an. Für Geocacher verändert sich diese Hitliste vermutlich ein wenig, wodurch die Wörter „Nord, Ost, Grad, Cache, Koordinaten, Dose, suchen, Versteck“ sowie die ausgeschriebenen Ziffern: „eins, zwei, drei, vier, fuenf/fünf, sechs, sieben, acht, neun und null“ weiter nach oben rutschen.

Übrigens gibt es im Deutschen eigentlich keine Ein-Buchstaben-Wörter – was deutsche von englischen Texten stark unterscheidet.

Zum manuellen Entschlüsseln einfacher Geheimtexte nutze ich einen Texteditor (das kostenlose Notepad++). Genauso gut funktioniert ein beliebiges Textverarbeitungsprogramm, wobei als Schriftart eine gewählt werden muss, deren Buchstaben feste Breiten haben (zum Beispiel Courier New oder monospace). So lassen sich Geheimtext und der Entschlüsselungsversuch direkt untereinander platzieren.

Im Beispiel von eben:

tuxjlaktlfckokotyfckojxkobokxlaktl


Davon ausgehend, daß der Text ohne Leerzeichen verschlüsselt worden ist (da es nur einen sehr häufigen Buchstaben gibt) und der häufigste tatsächlich das „E“ ist, schreibe ich diese Erkenntnis unter den Geheimtext.



Lesbar ist das leider noch nicht. Aber vielleicht funktioniert hier ja das, was schon vielen historischen Geheimtexten das Genick gebrochen hat: vielleicht kann man hier ja raten, wie der Text anfängt, oder welche Wörter drin enthalten sind. Noch im zweiten Weltkrieg sind viele, eigentlich fast sichere Chiffres geknackt worden, weil typische Grußfloskeln, die immer gleichen Phrasen und leicht zu erratende Wörter verwendet worden sind.

In unserem Fall, einem für Geocaching typischen Verschlüsselung, gehen wir mal davon aus, dass es sich hierbei um eine Koordinatenangabe handelt. Diese beginnt üblicherweise mit Nord oder N. Das „T“, der erste Buchstabe des Geheimtextes macht 12% von diesem aus, was mit der üblichen statistischen Häufigkeit von etwa 10% vom „N“ gut zusammen passt. Probieren wir es aus:




Naja, wirklich lesbar ist es noch nicht, also weiter. Aber wie? Man könnte jetzt weitere Buchstaben raten. Das zweit häufigste im Geheimtext ist ein „O“, an dritter Stelle steht das „L“. Nehmen wir die Buchstabenhäufigkeitstabellen, sind die Buchstaben E N I S R und A am Häufigsten. Somit dürfte O und L einer von denen sein. Da „E“ und „N“ vermutlich schon gefunden wurden, fehlt ja nur noch I, S, R und A.

Man könnte auch Wörter raten. Fängt der Geheimtext wirklich mit Nord an? Dann wäre das „U“ um Geheimtext ein „O“ und noch hilfreicher wäre das „X“, welches im Geheimtext gleich drei Mal vor kommt, und einem „R“ entspräche.

Der Text endet mit en und einem weiteren, noch unbekannten Buchstaben. Was könnte hier eine plausible Endung sein? Ist es eine ausgeschriebene Ziffer? Welche endet denn mit en und einem weiteren Buchstaben? Dann wäre fuenf oder fünf ein passender Kandidat. Hat der Verschlüsseler die ue-Schreibweise gewählt um keine deutschen Umlaute zu chiffrieren, müsste, wenn es wirklich die fuenf ist, der fünfte Buchstabe von hinten dem letzten entsprechen. Bingo! „laktl“ sind die letzten fünf Buchstaben. Und das bedeutet mit Sicherheit „fuenf“.

Wir könnten aber auch den Ansatz des Häufigkeitsgebirges wählen. Falls es sich bei dem Geheimtext nur um eine ROT-Verschiebung (Alphabetsverschiebung um x Stellen) handelt, sollten Auffälligkeiten hier vielleicht sogar mit so wenigen Buchstaben schon sichtbar sein.

Häufigkeitsgebirge - Quelle: cryptool-online.de


Und tatsächlich, die großen Balken scheinen sich in ähnlichem Abstand oben und unten zu wiederholen. Der E, I und N im normalen Alphabet könnten den Balken K, O und T im Geheimtext entsprechen. Dieses „Häufigkeitsgebirge“ wäre wesentlich aussagekräftiger, wäre der Geheimtext länger. Aber auch bei dem kurzen Schnipsel könnte es reichen und wir sehen eine Verschiebung um 6 Buchstaben. Dies ist auch der Vorschlag, den cryptool-online uns hier machen würde, wenn wir auf den passenden Knopf "ROT-Check" klicken würden.

Und eigentlich hätte man dies schon ein paar Schritte vorher ausprobieren können, da der Buchstabe „E“ (im Geheimtext „K“) und „N“ (im Geheimtext „T“) ja schon erraten worden sind. Beide sind um 6 Buchstaben verschoben, somit kann man immerhin schon hoffen, dass alle Buchstaben um 6 verschoben worden sind.

Aber egal welchen Weg wir wählen, mit ein bisschen Übung braucht es nur Minuten, um aus dem Geheimtext

tuxjlaktlfckokotyfckojxkobokxlaktl

den Originaltext

nordfuenfzweieinszweidreivierfuenf


zu erhalten.

Auch wenn das Alphabet komplett verwürfelt worden sind (anstatt um x Stellen zu verschieben), dauert die Entschlüsselung nur etwas länger. Hilfreich ist immer der einfache Ansatz, über Häufigkeitsanalysen das Leerzeichen und das „E“ zu identifizieren. In längeren Texten ist auch immer nach Punkt und Komma zu suchen, die nie an einem Wortanfang stehen aber immer von einem Leerzeichen verfolgt werden. Als nächstes sollte man versuchen, die kurzen Wörter zu entschlüsseln (der, die, das, und, in, im, ...) und nach identischen Textpassagen suchen, die gleiche Worte oder gleiche Wortteile bedeuten. Gleiche Geheimtextzeichen hintereinander sind auch ein schöner Ansatzpunkt, da im Deutschen nur bestimmte Buchstaben doppelt auftauchen und diese oft von gleichen oder ähnlichen Buchstaben umschlossen werden. Doppelte Konsonanten haben immer Vokale, doppelte Vokale immer Konsonanten um sich herum. Und natürlich sollte man immer nach typischen Grußformeln ("Lieber Cacher, …") und Abschiedworten ("Viel Spaß bei der Suche") schauen.

Funktioniert der Ansatz mit der Häufigkeitsanalyse nicht, sticht also kein Zeichen des Geheimtextes auffällig hinaus, dann ist es keine monoalphabetische Verschlüsselung sondern möglicherweise eine wiederholte Buchstabenverschiebung, bei der alle x Zeichen das Schlüsselalphabet gewechselt worden ist. Auch das lässt sich mit etwas Mühe per Hand entschlüsseln, ist aber definitiv schon wesentlich anstrengender. Wichtig ist hier über gleiche Geheimtextstellen herauszufinden, nach wie vielen Buchstaben das Alphabet - und wie oft - wechselt.

Ein weiterführender Link für das Decodieren von Geheimtexten mittels einer Tabellenkalkulation und dem Umrechnen und Vergleichen von Ascii-Werten findet sich auf dem Mathebord.

Zurück zum Inhaltsverzeichnis
Zurück zum vorherigen Artikel - Monoalphabetische Substitution
gratis Counter by GOWEB