Material für den Informatikunterricht
Verschlüsseln mit Caesar und Vigenère
Die Funktion TASTE
Was mit der Funktion TASTE zurückgegeben wird, wird in Winlogo 2.0 ganz ungefragt in Großbuchstaben verwandelt. Es gibt in Winlogo 2.0 nicht mehr wie im guten alten DOS-LOGO den Befehl GROSSKLEIN. Eine weitere Besonderheit ist, dass TASTE die Leertaste und die Returntaste ignoriert. Um also aus einer Rekursion herauszukommen, die permanent die einzelne Tasteneingabe liest, muss man ein anderes Sonderzeichen der Tastatur nehmen, z.B. "#". - Aber eben in Winlogo 2.0 dessen "groß" geschriebene Version, d.h. ANSI 191, also "¿".
Damit kann man dann allmählich zu einem einfachen Codierungsprogramm kommen:
Die Caesar-Verschlüsselung
Dies ist eine sehr schlichte Kinder-Verschlüsselung, wo einfach das gesamte Alphabet um einen festen Wert, z.B. um fünf Buchstaben, verschoben wird. - Aber schon da erhebt sich die Frage: Wie stelle ich es programmiertechnisch an, dass nach z wieder mit a weitercodiert wird?
PR start
;* ##### Startprozedur #####
;* LS
TEXTBILD ;* eventuell auskommentieren
SETZE "schlüssel" EINGABEFENSTER "Bitte eine Zahl bis 26 eingeben."
SETZE "schlüssel" ER :schlüssel
DZ "Beenden nur mit der Raute-Taste."
DZ [ ]
caesar
DZ [ ]
DR "Der Text wurde mit " DR :schlüssel DZ " verschlüsselt."
TB
ENDE
PR caesar
;* ##### (c) Kraus 11/2008 #####
SETZE "a" TASTE
WENN :a = "¿" DANN RK ;* "¿" für Winlogo 2.0, "#" für 1.0
SETZE "b" ASCII :a
;* DZ [] DR "Buchstabe " DR :a DR " = ANSI " DZ :b ;* Test
SETZE "b" :b - 65
;* kreisförmiger Durchlauf von A bis Z mit REST
SETZE "c" REST (:b + :schlüssel) 26 ;* 26 Buchstaben
SETZE "c" :c + 65
DR ZEICHEN :c
caesar
ENDE
Zunächst werden die über TASTE eingegebenen Großbuchstaben (siehe oben!) in ANSI-Werte verwandelt, die hier noch ASCII heißen.
Die Funktion REST
Dann wird der Wert für A auf Null heruntergerechnet, der Wert für B auf 1, C = 3 usw. bis Z = 25; das sind alle 26 Zeichen, die hier ausschließlich für die Codierung benutzt werden. Der Witz ist die anschließende Modulo-Rechnung, in Logo REST genannt. REST gibt zurück, was nach einer Division als Ergebnis ohne Dezimalzahlen übrigbleibt. Also REST von 12 durch 7 gleich 5, REST von 12 durch 6 gleich Null, REST von 12 durch 13 gleich 12! Wozu ist das gut? Die Modulo-Rechnung sorgt für einen kreisförmigen Datendurchlauf - wie bei einer Uhr. REST 13 12 = 1, REST 20 12 = 8 usw. Beim maximalen Wert geht es wieder von vorne los, oder genauer: Wenn Dividend = Divisor, dann ist der Rest = Null. Damit kann man programmieren, dass die Codierung nach Z wieder bei A anfängt.
Und die Codierung selbst?
Die 26 Buchstaben von A bis Z haben die ANSI-Werte von A = 65 bis Z = 90. Die harte Nuss, die zu knacken war, lautet: Wie heißt die Modulo-Formel, wenn die verschlüsselten Werte kreisförmig nicht wieder bei Null anfangen sollen (der ANSI-Wert von Null ist jedenfalls kein Buchstabe), sondern immer zwischen 65 (= A) und 90 (= Z) kreisen sollen?
Die Lösung geschieht in 2 Schritten: SETZE "c" REST (:b + :schlüssel) 26 und dieses Ergebnis, das ja einen ANSI-Wert von Null bis 25 ergeben wird, also weit unter A = 65, wird dann auf die Basis von A = 65 gehoben: SETZE "c" :c + 65. Am besten überprüft man den Stand der Programmierung nicht mit einem lustigen Text, sondern ganz dröge mit dem Schlüssel 3 und der Eingabe von A B C U V W X Y Z. Das muss dann als D E F X Y Z A B C verschlüsselt werden.
Frage: Wie entschlüsselt man denn eine so verschlüsselte Botschaft? Material dazu liefert Mystery-Twister; am besten kopiert man sich dort rechts das "Programmiererinterface".
Hinweise zu Buchstabenhäufigkeiten gibt es hier.
Die Vigenère-Verschlüsselung
Das nächste wäre dann die Vigenère-Verschlüsselung
Man hat nicht nur ein Element als Schlüssel wie bei der Caesar-Verschlüsselung, sondern einen, der aus vielen Elementen besteht, die immer wieder durchlaufen werden. Beim Schlüssel aus den vier Elementen "4712" kann ein e mit i (= + 4 Stellen) mit l (= + 7 Stellen), mit f oder mit g verschlüsselt werden. Der Klartext "LIEBE ELTERN" wird dann nicht wie bei Caesar mit einer Verschiebung von + 5 zu "QNJGJ JQYJWS", wo man immerhin die vielen J als auffällig erkennt. Sondern mit dem Schlüssel "4712" wird daraus "PPFDI LMVIYO". Da sieht es mit dem häufigsten Buchstaben schon schwieriger aus. Beispielsweise wird aus L und I am Textanfang beide Male P, aber einmal L + 4 = P und einmal I + 7 = P.
Die Programmierung der Verschlüsselung mit der Vigenère-Technik in Logo hat natürlich seine Probleme:
- Bei der Eingabe des mehrstelligen Schlüssels müssen die einzelnen Elemente durch ein Leerzeichen getrennt werden, nur dann werden sie von Logo als Elemente erkannt. Der ganze Schlüssel ist eine Liste.
- Die Länge dieser Liste y wird gemessen und als Wert der Variable lang gespeichert.
- Logo durchläuft mit "index" als Zähler nacheinander die Elemente des Schlüssels. Wenn der gesamte Schlüssel durchlaufen worden ist, dann wird wieder dessen erstes Element genommen. Diesen kreisförmigen Lauf besorgt wieder einmal die Modulo-Rechnung mit REST: Es geht dann mit dem Schlüssel wieder von vorne los, wenn das Element, das den gleichen Wert wie die Länge des Schlüssels hat, benutzt worden ist - und das ganz ohne WENN - DANN - SONST, nämlich so: SETZE "index" REST :index :lang .
- Zur Umrechnung von Buchstaben in den ASCII-/ANSI-Code, zur Benutzung von REST und zur rekursiven Tastenbenutzung siehe oben Caesar.
- Wie decodiert man so etwas? Zunächst muss natürlich im Anfang von PR start der Befehl LS auskommentiert werden. Dann wird es ganz einfach: Ich gebe als Schlüssel die Negativzahlen der Verschlüsselung ein oder die Subtraktion von 26. Damit tippe ich noch einmal den Geheimtext ein - und siehe da: Alles erscheint wieder im Klartext.
PR start ;* ######### Startprozedur ################## ;* ######### (c) Michael Kraus 12/2008 ##### ;* #### Kontakt: www.michael-kraus.info #### ;* LS ;* eventuell auskommentieren TEXTBILD ;* eventuell auskommentieren SETZE "y" [] ;* Schlüssel-Liste leeren für Wiederholung SETZE "y" EINGABEFENSTER "Zahlen als Schlüssel eingeben. Trennen mit Leertaste" SETZE "lang" ANZAHL :y ;* Länge des Schlüssels SETZE "index" 0 ;* Zähler für die Elemente des Schlüssels DZ [ ] DZ "Bitte jetzt den Klartext eingeben. Beenden nur mit der Raute-Taste." DZ [ ] vigenere DZ [ ] DR "Der Text wurde mit " DR :y DZ " verschlüsselt." TB ENDE PR vigenere ;* ##### (c) Kraus 11/2008 ##### SETZE "a" TASTE WENN :a = "¿" DANN RK ;* "¿" für Winlogo 2.0, "#" für 1.0 SETZE "b" ASCII :a SETZE "b" :b - 65 ;* DR "Buchstabe " DR :a DR " = ANSI " DZ :b ;* Test SETZE "index" :index + 1 ;* DZ [] DR "Verschlüsselung jetzt mit " DZ ELEMENT :index :y ;* Test ;* kreisförmiger Durchlauf von A bis Z SETZE "c" REST (:b + ELEMENT :index :y) 26 ;* 26 Buchstaben SETZE "c" :c + 65 ;* anheben auf ASCII-Niveau DR ZEICHEN :c ;* Buchstaben aus ASCII ;* kreisförmiger Durchlauf des Schlüssels SETZE "index" REST :index :lang vigenere ENDE
Ein Word-Makro
Ernsthaft kann man mit diesem Logo-Programm natürlich keinen Blumentopf gewinnen - mit dem Word-Makro schon eher. Es arbeitet mit Vigenère. Wie baut man es ein?
- Den Code "codieren.txt" markieren, in den Arbeitsspeicher kopieren. Übrigens: Alles nach einem Apostroph oder nach "Rem" ist ein Kommentar.
- In Word anklicken: Extras → Makro → Makros; hier den Name "codieren" eingeben, dann Klick auf Erstellen. Es wird in Editor etwa Folgendes erstellt:
- Dies wäre Anfang und Ende eines Makros und einiger Kommentarzeilen. Dies alles löschen und den kopierten Code einfügen (Strg V).
- Klick auf Datei → normal speichern.
Klick auf Datei → schließen und zurück zu Word - Klick auf Extras → Anpassen; auf der Karte "Befehle" in "Kategorie" wählen: "Makros", rechts den Eintrag finden "TemplateProject.NewMacros.codieren" (oder ähnlich). Diese Zeile mit gedrückter linker Maustaste hinauf in die Zeile mit den Schaltflächen (Icons) schieben, dort loslassen.
- Rechtsklick darauf; anklicken "Standard", anklicken "Schaltflächensymbol ändern", dann aus der Symboltafel den Schlüssel anklicken. "Anpassen" schließen.
- Man könnte jetzt noch eine Beschreibung erfinden: → Extras → Makro → Makros; unten in der Beschreibung etwas formulieren, z.B. "codiert oder decodiert eine Datei", dann → Abbrechen.
- Ein paar Zeilen sinnvollen Text in ein neues Dokument schreiben. Die Makro-Schaltfläche, also den Schlüssel anklicken und entsprechend verfahren.
- Die Makro-Schaltfläche entfernen? → Extras → Anpassen; Schaltfläche mit gedrückter linker Maustaste irgendwohin auf das geöffnete Feld "Befehle" ziehen, loslassen. Den Makro aus "Normal.dot" (oder wo sonst er ist) entfernen? → Extras → Anpassen → Makro → Makros; dort "codieren" markieren und → Löschen.
- Welchen Schlüssel benutzt man denn nun? Als Schlüssel funktionieren hier nur Zahlen! Man nehme einen möglichst langen Schlüssel (mehr als 5 Stellen!) und benutze am Anfang und Ende des Textes keine Standardformulierungen wie "Liebe..." oder "Hallo...", denn darauf wird als Erstes geprüft, um den Code zu knacken. Den Schlüssel muss man einander telefonisch oder auf anderem Wege mitteilen.
Sub codieren() ' ' codieren Makro ' Makro erstellt am ... ' End Sub
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 in 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.
Textdateien verarbeiten
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...
© Michael Kraus, ab September 2008