codieren

Material für den Informatikunterricht

Verschlüsseln mit Caesar und Vigenère, asymmetrischer Schlüssel mit RSA

Zunächst ein paar Grundbegriffe

Klartext → der unverschlüsselte oder eben entschlüsselte Text in einer natürlichen Sprache. Herauszubekommen, in welcher Sprache der Klartext formuliert wurde, ist schon sozusagen die halbe Miete, denn dann kann ich verschlüsselte Buchstabenhäufigkeiten suchen. Hinweise zu Buchstabenhäufigkeiten gibt u.a. die Universität in Mainz, der häufigste deutsche Buchstabe ist das e, gefolgt vom n. Um diese Angriffsfläche zu meiden, haben die USA im Pazifik-Krieg gegen Japan so genannte Codetalkers der Navaho-Indianer eingesetzt, das verstand nun wirklich niemand sonst. Im Klartext sind alle Standardformulierungen am Anfang und Schluss (Anrede, Grußformel) zu vermeiden - siehe Beispiel (was mag wohl SIMUT heißen?). Oder: Die deutschen U-Boote bekamen im 2. Weltkrieg immer Geheimbotschaften, in denen am Anfang das Wort "WETTER" vorkam; als das den Engländern auffiel, war ein ziemlich großes Tor offen, auch bei täglich wechselndem Schlüssel.
chiffrieren → verschlüsseln. Üblicherweise wird der Klartext nur in Großbuchstaben geschrieben, Umlaute werden mit Vokal + E umgeschrieben, Wortabstände werden gelöscht und statt dessen die gesamte Botschaft in Gruppen von je fünf Buchstaben oder allgemein Zeichen geschrieben - auch in Gruppen von fünf Bits (dazu ein Beispiel unten). Ebenso werden Zeilenwechsel und Satzzeichen gelöscht. Der Grund: Die Beibehaltung der natürlichen Wortgruppen führt bei englischem Text sofort zur Vermutung, dass einzelne Buchstaben ein I oder A bedeuten könnten. Ein Text, der mit zwei verschlüsselten Wörtern beginnt und dann einen Zeilenwechsel enthält, gerät sofort in den Verdacht, da eine Anrede zu enthalten, siehe oben das Textbeispiel. Die einfachste Art der Verschlüsselung ist die Caesar-Verschlüsselung (dazu hier ein Beispiel), schon härter ist die Vigenère-Verschlüsselung (hier der gleiche Klartext wie bei Caesar, jetzt mit Vigenère verschlüsselt). Verschlüsselt wird heute, indem den Buchstaben Zahlenwerte zugewiesen werden - und zwar aus der ASCII-Tabelle. Da hat A den Dezimalwert 65, B entspricht 66 usw. Oder man geht gleich auf die binäre Ebene (dazu mehr bei RSA).
dechiffrieren → die Auflösung des Geheimtextes in Klartext. Auf meiner Netzfläche werden Verfahren zum Chiffrieren und Dechiffrieren in Excel, Winlogo und Word vorgestellt. Ein umgangssprachlicher, hier gebräuchlicher Ausdruck, ist knacken. Um einen Geheimtext bzw. dessen Schlüssel zu knacken, benutzt man heute mathematische Methoden, Statistiken zur Häufigkeitsanalyse (siehe hier Methoden mit Excel) und das gute alte Ausspionieren des Schlüssels, unter anderem auch mittels social engeneering, siehe hier zum Schlüssel: Ich erkundige mich, welche Urlaube und Hobbys der Versender des Geheimtextes hat, wie seine Frau und sein Hund heißen, Postleitzahlen, Hochzeitsdatum usw.
Bigramme → Gruppen von zwei Buchstaben. Sollte ich - bei unterstelltem Klartext in deutsch - ein C entschlüsselt haben, dann kann ich testen, ob das Zeichen dahinter vielleicht ein H ist. Das häufigste deutsche Bigramm ist EN. Eine Liste stellt die Uni Mainz.
Schlüssel → heute üblicherweise eine Zeichenfolge oder ein Umrechnungsverfahren, um den Klartext in Geheimtext zu verwandeln, also um zu chiffrieren. In der Vergangenheit wurden statt dessen auch mechanische Mittel benutzt, Walzen mit Buchstabnen o.ä.; die berühmteste Maschine dieser Art war die Enigma. Ein Geheimtext mit einem Schlüssel, der so lang ist wie der Klartext, ist praktisch nicht mehr zu knacken - außer man fängt den Schlüssel selbst ab (dazu unten mehr). Der Schlüssel sollte nicht trivial sein, also nicht "12345" oder "Schalke". Der Schlüssel eines Hackers war "ducati"; er war Motorradfan und schwärmte auf seiner Homepage von dieser italienischen Maschine...
Code; der Ausdruck hat leider zwei völlig unterschiedliche Bedeutungen: 1.) Schlüssel, also das Mittel zur Verschlüsselung, 2.) die verschlüsselte Botschaft selbst, also der Geheimtext.

Textdateien verarbeiten

Texte mit einem Word-Makro (ein Programm innerhalb von Word; siehe bei Vigenère) zu codieren, verlangt keine besondere Vorbereitung auf der Textseite.

Texte in Excel zu codieren oder zu knacken, verlangt ihre Aufarbeitung als Tabelle. Dazu muss ich in Word mit Suchen und Ersetzen nach jedem Buchstaben ein Tab-Zeichen einfügen. Das geht so:

Ich benutze beim Suchen und Ersetzen in Word so genannte Platzhalter; das sind nichts anderes als Variablen. Damit Word nach Platzhaltern sucht, muss ich "Mit Mustervergleich" wählen ("Muster" soll wohl auch Variable heißen).
Mit Suchen und Ersetzen wird jedes Zeichen (Symbol Fragezeichen) gesucht und dann das Gesuchte (also jedes Zeichen; Symbol ^&) mit einem Tab (Symbol ^t) ergänzt.
Den neuen Text mit Absatzmarken in Blöcke von etwa je 30 Zeichen einteilen (viel mehr kann Word nicht zu Spalten umformen).
Dann diese Blöcke umwandeln in Tabellen.
Einfügen in Excel
Chiffrieren oder dechiffrieren.

Logo ist kein Textverarbeitungsprogramm. Aber Dateien speichern und lesen kann es schon - mit ein paar Verrenkungen. Die erste Verrenkung besteht darin, dass die Textblöcke (das können Wörter oder ganze Absätze sein) durch ordentlichen Zeilenwechsel mit der Returntaste voneinander getrennt sein müssen. Dann programmiert man beispielsweise Folgendes:

LADELISTE "beispiel" "Laufwerk:\Pfad...\Dateiname.txt"
WH ANZAHL :beispiel [DR ER :beispiel DR " " SETZE "beispiel" OE :beispiel]

Ergebnis ist der Text, in diesem Fall fortlaufend, aber statt der Zeilenwechsel mit Leerzeichen. Damit könnte man dann die Verschlüsselung betreiben...

Ver- und entschlüsseln ohne Schlüsselübergabe

Eines der Kryptographie-Probleme ist auch bei dem längsten und kompliziertesten Schlüssel, dass der Partner ja diesen Schlüssel haben muss, um wieder Klartext lesen zu können. Dazu gibt es zunächst einen Ausweg, der bei den Vorüberlegungen zur public-key-Technik gefunden wurde (in der heutigen Anwendung geht das Ganze ohne doppeltes Hin und Her - durch einen mathematischen Trick). Man kann diesen Ausweg schön mit dem Word-Codierungs-Makro nachstellen:

Schritt: Alice verschlüsselt ihren Klartext mit ihrem Schlüssel, den nur sie und sonst niemand hat und kennt.
Schritt: Sie schickt diesen Geheimtext an Bob.
Schritt: Bob kann diesen Geheimtext nicht lesen. Er verschlüsselt diesen Geheimtext ein zweites Mal - und zwar mit seinem, nur ihm exklusiv bekannten Schlüssel.
Schritt: Bob schickt diesen nun doppelt verschlüsselten Geheimtext zurück an Alice.
Schritt: Alice entschlüsselt diesen Geheimtext mit ihrem Exklusiv-Schlüssel. Ergebnis ist ein Text, den sie nicht lesen kann (das braucht sie auch nicht, sie kennt ja den Klartext). Aber ihren Schlüssel hat sie aus dem Text entfernt.
Schritt: Alice schickt diesen Geheimtext zurück an Bob.
Schritt: Bob entschlüsselt den Geheimtext mit seinem Schlüssel. Er enthält den gewünschten Klartext.

Ergebnis: Geheimtextübermittlung ohne Schlüsselübergabe. Die Sache hat natürlich einen Haken: Wenn der Spion die verschiedenen Varianten abfängt (Schritte 2, 4 und 6) und sozusagen die Differenzen errechnet, dann hat er auch den oder auf die Dauer beide Schlüssel ...Das Problem ist aber bei RSA gelöst.

Schwächen im Klartext - Entschlüsselung durch Sprachanalyse

Die Enigma-Maschine der Nazis im 2. Weltkrieg wurde unter anderem auch deshalb geknackt, weil irgendwann herauskam, dass die damit verschlüsselten Botschaften an die deutschen U-Boote anfangs immer irgendwo das Wort "Wetter" enthielten. - Allgemein kann man folgende Schwächen auflisten, die es erleichtern, einen Schlüssel zu finden

Worte wie im Klartext trennen: Das erleichtert die Suche nach zweibuchstabigen Worten, von denen es im Deutschen nicht unendlich viele gibt; im Englischen suche ich dann natürlich nach "I".
Absatztrennungen; so finde ich eventuell Datumsangaben zu Beginn, Anreden am Anfang und Namen am Ende.
Standartexte zu Beginn und am Ende: "Liebe", "Hallo", "...Gruß/Grüße" sind also tabu.
Zahlen als Zahlen zu verschlüsseln ist ganz tabu, vor allem nicht am Anfang das Datum als eigene Zeile rechtsbündig. Dann ist für den Spion schon fast alles klar.

Eine Methode der Entschlüsselung, auch wenn ich den Schlüssel gar nicht kenne, ist die Sprachanalyse (linguistische Verfahren). Hier ein Beispiel. Ein Rauschgift-Fahnder hat folgenden Geheimtext abgefangen:
OOO1O OO1OO 1OOOO 1O1OO OO111 1OOO1 111OO O1111 OO111 1O111 1O11O O1OOO 1O11O OOOO1 1O11O O1OO1 OO111 OO1OO O1OO1 1O11O 1OO11 O11O1 1OO11 O11O1 O1OO1 1O1O1 OOO1O O111O 11O11 OO1OO 111O1 11OO1 O1OOO OO111 11O11 O1111 OO11O 11OO1 OO111 O
Er lässt sich aber nicht entmutigen und er weiß auch einiges:
- Geheimtext wird oft in Blöcken von fünf Bits gruppiert, so auch hier.
- Es handelt sich dabei um Binärcode für Buchstaben.
- Dahinter steht in diesem Fall ein Klartext in deutscher Sprache.
- Im Klartext geht es um einen Millionenauftrag der Dealer.
Indem der Rauschgift-Fahnder die Fünferblöcke in Blöcke von sieben Bits umgruppiert, die dem ASCII-Code von Großbuchstaben entsprechen - warum sieben Bits? - entdeckt er folgende Bitfolge zweimal hintereinander: O11O11O (hier im Fettdruck). Die sachlich korrekte Gruppierung der Bits sieht nämlich so aus:

1)  O.OO1.OOO
2)  1.OO1.OOO
3)  O.1O1.OOO
4)  O.111.1OO
5)  O.111.1OO
6)  O.111.1OO
7)  1.111.O11
8)  1.1O1.1OO
9)  1.OOO.1O1
10) 1.OOO.OO1
11) 1.O11.OO1
12) O.O1O.O11
13) 1.OO1.OOO
14) 1.OO1.1O1
15) 1.O1O.O11  =  I
16) O.11O.11O  = L
17) O.11O.11O  = L
18) 1.O1O.O11  = I
19) O.1O1.OOO
20) 1.OO1.11O  ?
21) 1.1O1.1OO  ?
22) 1.OO1.11O  ?
23) 1.11O.O1O
24) 1.OOO.OO1
25) 1.111.O11
26) O.111.1OO
27) 1.1O1.1OO  ?
28) 1.OO1.11O  ?

Wenn die Zeichenfolge (7 Bits) in der Mitte des Textes zweimal gleich ist, dann kann das in diesem Fall LL von "Million" sein. Wenn sich die 7 Bits davor und danach auch gleichen, dann könnten die beiden Blöcke jeweils das I sein, also in der Tat "Million". Wenn zwei Zeichen nach dem zweiten I eine Bitfolge vorkommt, die zwei Blöcke danach wieder vorkommt, dann würde N passen: "Millionen". Damit hätte ich dazwischen auch das E. Um wieviel Millionen geht es? Jedenfalls nicht um ein Zahlwort, das i und e enthält, denn in den Blöcken davor kommen I und E nicht vor. Also bleibt da nur das Zahlwort "acht". Damit hätte ich auch ein T. Der Text bis dahin: _TO____E_ACHTMILLIONEN_A__EN
Bis jetzt hat der Fahnder den Schlüssel überhaupt nicht benutzt, nicht gekannt, nicht geknackt. Er hat trotzdem schon einiges herausbekommen.