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.2 - Polyalphabetische Verschlüsselung - Die Verschlüsselungsmaschine Enigma

Geschrieben von Nina • Montag, 17. Juni 2013 • Kategorie: Mysteries lösen
Geocaching Mysteries lösen

Kapitel 6.2 -Polyalphabetische Verschlüsselung



Die Verschlüsselungsmaschine Enigma


Enigma_Verkehrshaus_Luzern.jpg: cropped by OS Die Enigma (vom griechischen Wort "ainigma" = Rätsel) ist der unangefochtene Star unter den Verschlüsselungsmaschinen des zweiten Weltkrieges. Nicht weil sie die Beste, sondern weil sie die mit Abstand bekanntest ist. Wobei sie wirklich gut und beinahe nicht zu knacken gewesen ist.

Rein technisch ist Enigma eine Rotor-Schlüsselmaschine, bei der jeder Buchstabe des Klartextes mit einem anderen Schlüsselalphabet verschlüsselt wird. Sie beherrscht also die polyalphabetische Substitution, die damit dank der maschineller Unterstützung ab ca. 1920 einfach und – theoretisch - für Jedermann sicher anwendbar war. Relativ sicher zumindest, sofern man bestimmte Regeln beachtete und auch nur, solange es noch keine Maschinen gab, die beim Entschlüsseln helfen.

Arthur Scherbius hat die Enigma erfunden. Etwa zeitgleich mit ihm sind in anderen Ländern ähnliche Geräte patentiert worden. Anfangs war sie für zivile Zwecke konzipiert worden. Da der erste Weltkrieg aber einen deutlichen Mangel an sicheren und dennoch einfach zu bedienenden Verschlüsselungsmethoden deutlich gemacht hatte, zeigte das Militär recht bald Interesse an den Geräten des Herrn Scherbius. Dieser konnte den Siegeszug seiner Erfindung leider gar nicht mehr genießen, er starb 1929 an den Folgen eines Verkehrsunfalls (mit einem Pferdefuhrwerk!). Dafür blieb es ihm auch erspart mitzuerleben, dass sein Baby eben doch nur FAST unknackbar gewesen ist. Letztlich schreiben viele Historiker, dass Enigma kriegsentscheidend gewesen ist. Vor allem des Umstandes wegen, dass in den letzten Kriegsjahren viele deutsche Funksprüche vom Feind mitgelesen werden konnten. Dank dem Geschick der Alliierten, was die Nutzung dieser Informationen anging, blieben die Deutschen bis zum Kriegsende von der Sicherheit ihrer Verschlüsselung überzeugt. Ein in meinen Augen sehr spannendes Stück Zeitgeschichte, was wohl auch den Reiz der Enigma als Rätselinhalt erklären dürfte.

Ein bisschen zur Technik

Es gab im Laufe der Jahre eine Fülle an Enigmas. Die bekanntesten (und beim Geocachen auch am häufigsten benutzten) sind die Enigma I, Enigma M3 und die Enigma M4. Die Zahlen drei und vier beziehen sich hier auch auf die Anzahl der Walzen, die sich mit jedem verschlüsselten Buchstaben um eine Position weiter drehen und jeweils eine neues Verschlüsselungsalphabet erzeugen. Die M4 war somit sicherer als ihre kleine Schwester mit nur drei Walzen und wurde bei der Marine zur Kommunikation mit den U-Booten benutzt.

<a class="serendipity_image_link"  href='/blog/uploads/400px-Enigma_beschriftet_cropped.jpg'><!-- s9ymdb:219 --><img class="serendipity_image_left" width="110" height="82"  src="/blog/uploads/400px-Enigma_beschriftet_cropped.serendipityThumb.jpg"  alt="" /></a> Neben den Walzen (austauschbar, bis zu 8 verschiedene normale plus Beta und Gamma als vierte Walze bei der M4) hatten die hier relevanten Enigmas noch eine Umkehrwalze (UKW-B oder C), außerdem eine Tastatur, ein Lampenfeld, was den ver-/bzw. entschlüsselten Buchstaben darstellte und ein Steckbrett, mit dem die Buchstaben noch einmal paarweise verwürfelt worden sind; wodurch die Sicherheit der Verschlüsselung noch einmal enorm verstärkt worden ist.

Die genaueren technischen Details spare ich mir hier, da es schon mehr als genug wirklich gute Erklärungen, Bau- und Schaltpläne sowie mathematische Betrachtungen zu Schlüsselstärken und Entschlüsselungsalgorithmen im großen, weiten Web gibt.

Ich helfe dafür hoffentlich in ausreichender Kürze dabei, mit den im (Geocaching-) Rätsel vorhandenen Informationen den verschlüsselten Text in Klartext zu übersetzen.

Die Enigma entschlüsseln nur echte Freaks „zu Fuß“, die letzten dürften es vor etwa 60 Jahren getan haben. Weniger tapfere Naturen bedienen sich heutzutage der dafür reichlich vorhandenen Software. Empfehlen kann ich den Download von Dirk Rijmenants hervorragender Enigma-Simulation . Ebenfalls empfehlenswert sind diese online-Varianten der Sternenhimmelsstürmer und Enigmaco. Und vermutlich viele weitere, die ich nicht näher kennengelernt habe.

Und wie geht das nun?

Enigma kann nur Großbuchstaben, keine Ziffern oder Satzzeichen verschlüsseln. Letztere wurden einfach durch ein X ersetzt, Ziffern ausgeschrieben. Eigennamen wurden üblicherweise verdoppelt und mit X umschlossen. Außerdem das „ch“ durch den Buchstaben Q ersetzt. Anschließend wurde der Text in Fünfergruppen dargestellt und nun verschlüsselt.

Dazu benötigte man den Tagesschlüssel, der die Grundstellung der Enigma beinhaltete. Also die Angabe, welche der Walzen benutzt wird (die sogenannte Walzenlage I, II, III, … sowie Gamma und Beta, falls es eine M4 war), welche Umkehrwalze (UKW-B oder -C), die Grundstellung des inneren Rings dieser Walzen (Ringstellung, Walzenstellung, entweder in Buchstabenwerten A=1, B=2,… oder in Buchstaben ausgedrückt), sowie die Buchstabenvertauschungen (Steckerverbindungen) vom Steckbrett.

Zum Entschlüsseln werdet ihr irgendwo diese Informationen finden, die seinerzeit in der Realität und heutzutage, wenn wir damit spielen, gerne auf Monatsblättern, von unten nach oben aufsteigend, dargestellt werden. Von unten nach oben, damit man den Schlüssel vom Vortag abscheiden und wegwerfen kann. Gedruckt wurden diese Blätter häufig auf Löschpapier, damit man sie bei Bedarf einfach vernichten kann.

Beispiel-Tagesschlüssel (Enigma I):



Es gab viele verschiedene Tagesschlüssel, je nach Anwendungsgebiet bzw. Empfängergruppe. Damit der Entschlüsselnde sich sicher sein konnte, dass die Nachricht für ihn bestimmt war und er sie in Klartext umwandeln konnte, gab es häufig beim Tagesschlüssel noch eine (ebenfalls täglich wechselnde) Kenngruppe. Diese wurde dann der verschlüsselten Nachricht unverschlüsselt vorne angestellt.

Das alles wirkt zwar schon ausreichend wirr, reichte als Sicherheit aber noch nicht, da mit dieser Methode eine große Anzahl von Funksprüchen eines Tages auf die gleiche Art verschlüsselt worden wären. Also musste der Verschlüsselnde sich häufig noch die äußere Walzenstellung (den Spruchschlüssel) selber ausdenken und ihn mit einer ebenfalls selbst ausgedachten Buchstabenfolge verschlüsseln.

Die Enigma stellte er dann (innen) in die Grundstellung des Tages laut Tagesschlüssel, wählt die drei (oder vier) Buchstaben des selbst ausgedachten Spruchschlüssels an den äußeren Walzenstellungen und tippte seine drei ausgedachten Buchstaben. Die Verschlüsselungsmaschine verschlüsselte diese und lieferte als Antwort drei andere Buchstaben. Dieser so verschlüsselte Spruchschlüssel wird zusammen mit der gewählten Grundstellung der Enigma Nachricht – unverschlüsselt – vorangestellt.

Eine korrekt verschlüsselte Enigma-Nachricht hatte im Kopf die Uhrzeit (als vierstellige Zahl, z.B. 1130 für halb zwölf Uhr), die Zeichenlänge des Funkspruches, die Grundstellung sowie den damit verschlüsselten Spruchschlüssel. Anschließend folgte die verschlüsselte Nachricht in Fünfergruppen, gegebenenfalls mit der vorangestellten dreistelligen Kenngruppe, die um zwei Füllbuchstaben zu einer üblichen Fünfergruppe aufgestockt worden ist.

Ein Beispiel zum Nachspielen und Verstehen

1. Verschlüsseln

Nimmt man als Beispiel den oberen Tag 29 und stellt die Enigma M3 auf folgende Grundstellung innen (der Bereich, der sich nur täglich einmal änderte):
UKW-C
Walzen Nummer I IV III
Ringestellung der Walzen 12 18 22
Steckerverbindungen CY EL FH GS IJ KQ MW PV RZ TU

Außen (der Bereich, den der Verschlüsselnde sich selber jedesmal neu ausdenken musste)
die Grundstellung PLR und tippt nun den ausgedachten Spruchschlüssel: NVD

Die Enigma gibt als Antwort ein WGT zurück.

Der somit als WGT verschlüsselten Spruchschlüssel wird dem Empfänger zusammen mit der zufällig gewählten Grundstellung PLR im Kopf des Nachricht mitgeteilt.

Verschlüsselt wird Text des Funkspruches dann mit dem gewählten Spruchschlüssel, hier also NVD, auf den die Walzen (außen) eingestellt und der Text eingegeben wird. In meinem Beispiel lautet dieser:

Hier wäre ich ohne Geocaching nie hingekommen!


Also in Enigma-Schreibweise:


HIERW AEREI CHOHN EGEOC ACHIN GNIEH INGEK OMMEN X


Verschlüsselt schaut er so aus:

JOPVV QKJZS FNXNJ RUMXT NLQGQ RPEPJ HTLGI SKWLT Z


Das ergäbe nun mit einem korrekten Schlüsselkopf folgenden Funkspruch:

2333 55 PLR WGT
YZUIX JOPVV QKJZS FNXNJ RUMXT NLQGQ RPEPJ HTLGI SKWLT Z


2. Entschlüsseln

Der Empfänger guckt nun zuerst ob er die Kenngruppe (irgendwo in den ersten 5 Buchstaben) in seinem Tagesschlüssel hat. ZUI gibt es dort, also kann er die Nachricht entschlüsseln. Er stellt die Enigma passend ein

C I IV III 12 18 22 CY EL FH GS IJ KQ MW PV RZ TU

und erhält den noch fehlenden Spruchschlüssel, in dem er die Walzen auf PLR stellt und WGT aus dem Kopf der Nachricht tippt. Die Enigma antwortet mit dem unverschlüsselten Spruchschlüssel NVD. Dieser (NVD) wird nun auf der (äußeren) Walzenlage eingestellt und der verschlüsselte Text (ohne die ersten fünf Zeichen mit der Kenngruppe) eingegeben.

JOPVV QKJZS FNXNJ RUMXT NLQGQ RPEPJ HTLGI SKWLT Z


Und schwuppdiwupp (*hüstel*) erhält man die unverschlüsselte Variante zurück:

HIERW AEREI CHOHN EGEOC ACHIN GNIEH INGEK OMMEN X


Und wer bis hier erstmal etwas verwirrt ist, kann sich beruhigt zurücklehnen: das geht wohl den meisten so. Am besten spielt man dies Szenario tatsächlich einfach einmal nach und tröstet sich anschließend mit dem Gedanken, dass viele Enigma-Caches gar nicht die komplizierte Variante mit einem verschlüsselten und im Kopf der Nachricht mitgesendeten Spruchschlüssel arbeiten, sondern sie verschlüsseln plump ihren Text und geben dann die ganzen Daten inklusive Grundstellung heraus. Da muss man dann nur die Enigma dementsprechend einstellen, den verschlüsselten Text hineinwerfen und erhält die entschlüsselte Nachricht zurück.

Ebenfalls einwerfen muss ich aber noch den Hinweis, dass sich im Laufe der (Kriegs-)Jahre der Umgang mit der Enigma, den Verschlüsselungen und ihren Regeln, gern auch abhängig von den jeweiligen Nutzergruppen und Enigmaversionen, geändert hat. Somit ist das hier dargestellte noch nicht ganz die einzige Wahrheit, aber, wenn man das Grundprinzip erstmal verstanden hat, ist der größte Schritt in Richtung Entschlüsselung sicher schon getan!

Nochmal, nochmal?

Wer jetzt noch etwas üben möchte, dem hab ich etwas vorbereitet ;) :

Tagesschlüssel Kriegsmarine, M4 vom 17.6.2013

UKW B
Walzenlage: Gamma, VIII, V, VI
Ringstellung: 15, 5, 16, 12
KENNGRUPPEN: liu aer vpu

AN BO DQ FS GT HU IV LY ER

Funkspruch

1141 183 ASDFJHGF
XAER QRHG REYX BXWB MTBY VDWF BGOB XWVW TPEX EKTZ ZLTC OFWS BQEJ UNLQ ZTMT ELIO FSHM HXHU WSZP EXHQ XMHN ZDJA ERZD WJBD DCJD UFLH WCQR EIXA PHPR QLAH OUAK VDEE FUCF YHGD PKPC GBRJ URXJ TIV

Viel Erfolg! :)

Zurück zum Inhaltsverzeichnis
gratis Counter by GOWEB