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 3 - Zahlen, Zahlen, Zahlen (3) - Binärcodes

Geschrieben von Nina • Freitag, 4. Januar 2013 • Kategorie: Mysteries lösen
Geocaching Mysteries lösen

Kapitel 3.3 Binärcodes

Beim Mystery Enträtseln begegnen einem ziemlich häufig Nullen und Eisen. Oder etwas, was verschlüsselt auf zwei Zustände herunter gebrochen werden kann: zwei verschiedene Farben oder Töne, etwas ist wahr oder falsch, etwas ist da oder weg, lang oder kurz. Oder zum Beispiel GroSsBucHstaben, wo sie nich hingehören (GroSsBucHstaben könnte, wenn das Großgeschriebene die 1 symbolisiert, die Binärzahl 100101001000000 ergeben).

Und dann steht man vor den Nullen und Einsen, die keineswegs immer nur Dualzahlen sein müssen. Das Beispiel oben ergäbe immerhin eine 19008, was da, wo ich wohne, eine schlüssige Nordkoordinate ergibt- wenn man sich vorn noch ein 52° herandenkt und nach der 19 einen Punkt setzt. Die Verschlüsselung kann aber auch an einem anderen Binär-Code erfolgt sein, als dem der Dualzahlen. Ich bemühe mich hier, einige der üblicheren Binärcodes vorzustellen.

Hilfreich bei der Suche nach dem passenden Binärcode, ist die Länge der Binärzahl. Ist sie 5 Stellen lang, oder durch 5 teilbar, könnte sie Baudot bzw. Baudot -Murray-Code sein (ITA-1 und ITA-2, bzw. CCITT-2) . Dieser stammt aus der Zeit der Telegraphie und ist im Original geteilt in einen Bereich mit 2 Bits und einen mit 3 Bits. Hiermit lassen sich Zahlen und Buchstaben, sowie einige Sonderzeichen darstellen, Häufig finden sich in den Listings derartiger Caches Bilder von Lochstreifen, die Baudot-Code darstellen. Die größte Schwierigkeit hier ist es, herauszufinden, von welcher Seite des Lochstreifens gelesen wird und welcher Baudot/ITA benutzt worden ist.

Nicht so richtig Nullen und Einsen, sondern die Buchstaben A und B benutzte der Herr Bacon für seine Bacon-Chiffre . Er hat einfach jedem Buchstaben im Alphabet einen fünfstelligen Code, bestehend aus den beiden Buchstaben A und B, zugewiesen. Das Wort Mysterie in Bacon-Chiffre lautet demnach: ababb babba baaab baaba aabaa baaaa babba
Diese Codierung kann durchaus unauffällig im Text versteckt sein. Man könnte, auch wenn es etwas Mühe kostet, einen Text zusammenschreiben, bei dem die vorhandenen Buchstaben A und B Bacons Chiffre ergeben. Oder wieder die Groß- und kLeinSchReibUNG benutzen, und den GROSSGESCHRIEBENEN Buchstaben zum Beispiel das A zuweisen, den kleinen das B. Die Buchstaben könnten auch teilweise fett oder kursiv geschrieben werden, um die zwei Zustände, hier a oder b darzustellen. Möglichkeiten gibt es genug, und Mystery-Owner auch trickreich genug, beinahe unendlich viele davon zu erfinden ;) .

ASCII ist wohl der bekannteste Vertreter der binär-Codes, von den Dualzahlen mal abgesehen. Die "American Standard Code for Information Interchange" ist eine von Computern benutzte 7-Bit-Zeichenkodierung, die schon 1963 als Standard veröffentlich wurde. Sie kann 128 Zeichen darstellen (das lateinische Alphabet, arabische Ziffern, einige Satzzeichen) und wird von einer unzähligen Masse von Geräten und Programmen verstanden und unterstützt. Das überzählige achte Bit (ein Ascii-Zeichen wird üblicherweise in einem Byte gespeichert, hätte also Platz für acht Bits) wird entweder als Prüfziffer missbraucht, oder um länderspezifische ASCII-Zeichensätze darzustellen. Die deutschen Umlaute zum Beispiel. Mit dem ASCII-Zeichensatz kann man hervorragend Caches verschlüsseln, zumal man ihn nicht nur direkt in binär, sondern auch in HEX oder Oktal darstellen kann.

BCD (Binary Coded Decimal ) ist ein weiterer, bekannter Binär-Code. Es gibt ihn als 4- und als 6-Bit-Code. Der 4er ist ein 8-4-2-1-Code. Also ein nummerischer Code, dessen Wertigkeit dem bekannten Dualsystem entspricht. Es lassen sich Ziffern von 0-9 darstellen. Theoretisch könnte man 16 statt 10 Dezimalzahlen mit einem derartigen "Halbbyte" darstellen, man hat sich aber drauf geeinigt, dass man derartiges per BCD nicht tut. Ein Byte sind ja 8 Bits, also 8 Stellen, der 4-Bit-BCD-Code ist somit ein halbes Byte lang. Man nennt dieses Halbbyte auch Nibble. Diesem bin ich bei einem Nachtcache tatsächlich schon begegnet.

BCD gibt es auch als 6-Bit-Code . Dieser kann neben Ziffern auch Buchstaben und einige Sonderzeichen darstellen.

Der BCD-Zählcode ist 10 Bits lang, wobei jedes Bit die Wertigkeit 1 im Dezimalsystem hat. Man bekommt die gesuchte Zahl durch plumpes addieren der Einsen. Dieses simple addieren der Einsen, anstatt kompliziert nach Codierungen zu suchen, ist etwas, was man beim Mystery-Entschlüsseln auch mal probieren könnte.

Selten aber möglich ist auch der 1-aus-n-Code, bei dem es 10 bits gibt, von denen 9 immer 0 sind und die 1 als Zähler dient. Steht sie auf der 7. Position von rechts (0001000000 ), steht sie für eine dezimale 6, steht sie auf der 2. Position von rechts (0000000010), ist sie Eins wert, ganz rechts (0000000001) ist es eine dezimale Null.

Weitere 4-Bit-Sonderformen: der Aiken-Code, bei dem die vierte Stelle von links nicht 8 wert ist, wie bei 4-Bit-BCD, sondern 2. Es ist also ein 2-4-2-1-Code. Oder der Gray-Code http://de.wikipedia.org/wiki/Gray-Code, den es auch als 2-Bit, 3-Bit, 4-Bit, 5-Bit und 6-Bit-Code gibt. Er zeichnet sich dadurch aus, das benachbarte Codewörter sich nur in einer einzigen dualen Ziffer unterscheiden und ist entwickelt worden, um Ablesefehler zu minimieren.

Braille, die Blindenschrift mit den kleinen Punkten, ist ebenfalls binär, also hat zwei Zustände. Es gibt 'nen Hubbel oder es gibt keinen Hubbel. Hiermit haben mich schon mehrere Mysteries geärgert, weil ich viel zu spät und von all den Computercodierungen geblendet auf das im Format 3-hoch-2-breit geguckt hab um an das Braille-System zu denken.

Morse ist auch ein Kandidat, der eigentlich nicht so wirklich und dann wieder doch binären Codes. Es gibt zwei Zustände, nur heißen die bei Morse eigentlich lang und kurz, Punkt und Strich. Prinzipiell ist es hier aber das gleiche, irgendwo finden wir die binäre Verschlüsselung und der Schlüssel hierzu könnte das Morsealphabet sein. Allerdings hat Morse einen gravierenden Nachteil, der beim Erkennen helfen könnte: die einzelnen Zeichen sind unterschiedlich lang. Häufig benutzte Buchstaben, wie zum Beispiel das E haben kurze Morsezeichen (ein . ), lange Morsezeichen haben fünf Striche und Punkte (Sonderzeichen oft sogar sechs). Um Morse sicher übersetzen zu können, benötigt die verschlüsselte Botschaft Leerzeichen zwischen den einzelnen Zeichen. Ziffern hingegen sind bei Morse immer fünf Morsezeichen lang und dank ihres symmetrischen Aufbaus sogar relativ leicht zu erlernen.





Zurück zum Inhaltsverzeichnis
Weiter: Kapitel 3.4 - Malen von Zahlen


gratis Counter by GOWEB