Cäsar im Quadrat
Historische Kryptografie: Vigenère-Chiffre in Python programmiert
Verbotene Romanzen, Komplotte oder Botschaften im Krieg: Um Geheimnisse vor neugierigen Dritten zu schützen, verwendete man vor gut 400 Jahren nicht selten die Vigenère-Chiffre. Wir haben sie uns angeschaut und in Python nachprogrammiert.
Der Kurier hetzt das Pferd vom Schlachtfeld weg, aus der Ferne hallt das Grollen von Kanonen. Der oberste General muss diese Nachricht sofort erhalten. Damit Fremde die Botschaft nicht verstehen, wurde sie kodiert. Wohlbehütet steckt die wertvolle Fracht zusammengefaltet in der Brusttasche. Die Tür fliegt auf, an der Schwelle steht der Kurier mit der Botschaft in der Hand, am Tisch blicken die Generäle auf, in der Mitte – Napoleon.
Dieses von uns erfundene Szenario mag so passiert sein oder auch nicht. Für fast 300 Jahre war die Vigenère-Chiffre ein beliebter Kandidat bei der sicheren Übermittlung von Botschaften. Sie kam bei Kriegen zum Einsatz, bei Mordkomplotts oder auch unter heimlichen Liebespaaren. Da die Chiffre komplett ohne Mathematik auskommt und kein spezielles Vorwissen benötigt, war sie besonders einfach durchzuführen.
Im Zeitalter der Computer spielt die Chiffre keine Rolle mehr, aber sie hat im Laufe der Jahrhunderte ihre Spuren hinterlassen und wichtige Entwicklungen in der Kryptografie angestoßen. Grund genug, um sie sich genauer anzuschauen und sie in Python nachzuprogrammieren.
Das alte Rom
Doch bevor wir auf den Code eingehen, drehen wir die Zeit noch weiter zurück: Julius Cäsar regiert das Römische Reich. Moment, ist das denn nicht viel zu weit? Ganz und gar nicht, denn die Grundlage der Vigenère-Chiffre ist die Cäsar-Chiffre. Das nach ihm benannte Verfahren benutzte Cäsar damals, um Militärnachrichten zu kodieren. Dazu schrieb er seine Botschaft nieder und verschob jeden der Buchstaben seines Klartextes um drei Buchstaben im Alphabet weiter – für die Botschaft HALLO lautet der Geheimtext KDOOR.
Eine heute immer noch (nicht zur Sicherung von Systemen) verwendete Variante der Cäsar-Chiffre ist „Rot13“. Wie es vielleicht der Name schon vermuten lässt, werden die einzelnen Buchstaben um 13 Plätze im Alphabet verschoben. Sie können sich das Alphabet als einen Kreis vorstellen: Beim Verschieben der Buchstaben rotiert dieser und wenn man bei Z angekommen ist, fängt man einfach bei A wieder an. Diverse Foren benutzen Rot13 beispielsweise, um Spoiler zu maskieren – echte „Profis“ nehmen Rot26.
Die Cäsar-Chiffre gehört genauso wie die Vigenère-Chiffre zu den sogenannten Substitutions-Chiffren, die Buchstaben des Klartextes nach einem bestimmten Schema gegen andere Zeichen austauschen. Eine Alternative ist die Transposition: Hier vertauscht der Absender die Buchstaben miteinander, ersetzt aber keine davon. Ein Beispiel dafür wäre die Doppelwürfel-Chiffre, die wir schon in [1] vorgestellt haben.
Trotz der Einfachheit der Cäsar-Chiffre war sie lange Stand der Technik. Dabei ist das Verfahren nicht wirklich sicher: Ein Angreifer muss nur probeweise die ersten paar Buchstaben des Geheimtextes verschieben und schauen, ob etwas Brauchbares herauskommt – im schlimmsten Falle tut er dies 26 Mal. Wie man am Beispiel KDOOR erkennt, kann der Angreifer nach doppelt hintereinander stehenden Buchstaben Ausschau halten und mit geschicktem Probieren noch schneller das Wort und damit die Verschiebung erraten.
Diese Schwäche war Kryptologen durchaus bewusst: Um 1460 schlug der Mathematiker Leon Battista Alberti vor, nicht eine Cäsar-Chiffre zu benutzen, sondern zwei unterschiedliche. So zum Beispiel kann man den ersten Buchstaben um sieben Positionen verschieben, den zweiten um 16, den danach wieder um sieben und so weiter.
Die Ideen Albertis entwickelten andere Personen weiter, bis 1585 schließlich der französische Kryptograf Blaise de Vigenère Ansätze des Benediktinerabts Johannes Trithemius und des Gelehrten Battista della Porta zusammenführte, um die heute bekannte Vigenère-Chiffre zu erfinden.
Kodierungsfreuden
Die Vigenère-Chiffre verwendet 26 Verschiebungen. Um wie viele Positionen im Alphabet ein Buchstabe des Klartextes verschoben wird, regelt ein vorher vereinbartes Schlüsselwort. Das macht die händische Kodierung ein wenig aufwendiger, weswegen Vigenère zusätzlich das Vigenère-Quadrat erfand (siehe Infografik unten). Oben stehen die Buchstaben des Klartextes, links die des Schlüssels. Nun kann man einfach die Buchstaben des Geheimtextes ablesen. Wie genau das funktioniert, sehen Sie bei der Kodierung des Beispielsatzes „DAS IST EIN LANGER BEISPIELTEXT“ mit dem Schlüsselwort CTMAGAZIN.
Als Erstes schreibt ein Absender das Schlüsselwort wiederholend unter dem Klartext bis ans Ende der Nachricht auf:
DAS IST EIN LANGER BEISPIELTEXT CTM AGA ZIN CTMAGA ZINCTMAGAZIN
Im nächsten Schritt zieht er das Vigenère-Quadrat zurate und liest die einzelnen Buchstaben ab: Oben auf der Zeile geht er für den ersten Buchstaben von D aus nach unten, bis er auf die Spalte von C (linke Seite) trifft, das wäre der Buchstabe F. Für A und T kommt T heraus und so weiter. Das Ergebnis der Kodierung sieht wie folgt aus:
DAS IST EIN LANGER BEISPIELTEXT CTM AGA ZIN CTMAGA ZINCTMAGAZIN FTE IYT DQA NTZGKR AMVUIUERTDFG
Doch warum ändert sich beim vierten oder sechsten Buchstaben nichts? Das liegt daran, dass zu den 26 möglichen Verschiebungen auch keine Verschiebung gehört. Ersichtlich wird das, wenn Sie das Alphabet von null aus abzählen und den Buchstaben Zahlen zuweisen: Heraus kommen A als 0, B als 1, C gleich 2 und so weiter. Taucht nun ein A im Schlüsselwort auf, dann wird der Buchstabe des Klartextes um 0 Plätze verschoben. Ein B im Schlüsselwort verschiebt den Buchstaben des Klartextes um 1, E um 4 und Z um 25. Würde das Schlüsselwort AAAAA... lauten, dann wäre vom Text nichts verschleiert worden.
Für die Dekodierung schreibt der Empfänger zuerst wieder das Schlüsselwort unter den Geheimtext. Danach nimmt er das Vigenère-Quadrat und schaut auf der linken Spalte nach den ersten Buchstaben des Schlüsselwortes (C) und sucht in der Zeile nach dem Buchstaben des Geheimtextes (F). Sobald er ihn gefunden hat, zieht er eine imaginäre Linie nach oben zum Klartext: Es ist D. Den gleichen Prozess wiederholt er für die gesamte Nachricht:
FTE IYT DQA NTZGKR AMVUIUERTDFG CTM AGA ZIN CTMAGA ZINCTMAGAZIN DAS IST EIN LANGER BEISPIELTEXT
Obwohl die Vigenère-Chiffre ständig die Cäsar-Chiffre anwendet, ist dieses System weitaus schwerer zu durchschauen, denn aufgrund der mehrfach verschobenen Cäsar-Chiffre unterscheiden sich identische Buchstaben später im Geheimtext. Der Buchstabe E steht viermal im Klartext, im Geheimtext wird er aber je nach Position zu D, K, M und E. Das macht einen Angriff schwieriger, aber nicht unmöglich. Mehr dazu in einem weiteren Artikel.
Nutzung des Programms
Damit Sie nicht mühselig Buchstabe für Buchstabe im Vigenère-Quadrat zusammensuchen müssen, haben wir ein kurzes Python-Programm geschrieben, mit dem Sie sowohl kodieren als auch dekodieren können. Das Programm finden Sie im GitHub-Repository unter ct.de/yvkq. Falls Sie noch Python zur Ausführung des Programms benötigen, erfahren Sie in dem kostenfreien Artikel [2], wie Sie die Programmiersprache auf Ihrem jeweiligen System nachinstallieren.
Wir haben das Programm so konstruiert, dass Sie es bequem über die Kommandozeile bedienen können. Sie nutzen es wie folgt:
python3 vigenere.py [d/e] <text> <key>
e steht für kodieren (encrypt) und d für dekodieren (decrypt). Danach folgt der zu bearbeitende Text und das Schlüsselwort. Achten Sie auf die öffnenden und schließenden Gänsefüßchen um den Text, wenn Sie Leerzeichen oder Satzzeichen benutzen. Machen Sie sich keine Sorgen über die Sonderzeichen, diese sortiert das Programm für Sie aus.
Folgender Befehl kodiert eine Nachricht:
python3 vigenere.py e "Lorem ipsum dolor sit" CTMAGAZIN
Herauskommt der Geheimtext NHDESIOAHOWALURRQG, den Sie mit dem Befehl
python3 vigenere.py d NHDESIOAHOWALURRQG CTMAGAZIN
wieder in den Klartext umwandeln können: LOREMIPSUMDOLORSIT.
Funktionsweise
vigenere.py ist zwar insgesamt knapp über 50 Zeilen lang, aber das meiste sind Vorkehrungen, um die Argumente von der Kommandozeile zu verarbeiten oder um sicherzustellen, dass keine Sonderzeichen den Kodierungsprozess ruinieren. Wie Sie weitere Zeichen verwenden können, lesen Sie in dem Kasten „Modifikation“ auf dieser Seite unten. Die Logik der Chiffre umfasst gerade mal 15 Zeilen (siehe Codekasten auf Seite 156).
Die Methode process bekommt zwei Parameter: mode enthält die Information, ob kodiert oder dekodiert werden soll und text den Inhalt der zu verarbeitenden Nachricht. In der ersten Zeile schmeißt sie dann alle Zeichen heraus, die nicht zu den 26 vorgegebenen Buchstaben des Alphabets gehören. Außerdem vereinheitlicht sie den text, indem sie alles zu Großbuchstaben umwandelt (text.upper()).
Das Herzstück der Methode ist die for-Schleife, die jeden Buchstaben von text durchgeht. Im Unterschied zur manuellen Kodierung und Dekodierung, berechnet das Programm ad hoc welcher Buchstabe herauskommt, indem es die Position der Buchstaben im Alphabet beziehungsweise im Schlüssel, angefangen bei 0, zu Zahlen umwandelt (key_value und text_value). Anschließend addiert oder subtrahiert es beide Werte und rechnet das Ergebnis modulo 26 (len(self.abc)). Die Modulo-Operation stellt sicher, dass wieder vorne beim Alphabet angefangen wird, sollte zum Beispiel nach großen Verschiebungen eine Position größer 26 entstehen.
Zu guter Letzt baut die Methode den ausgebenden Klar- oder Geheimtext zusammen result += self.abc[value]. Fertig ist die Vigenère-Chiffre.
Sehr viele Möglichkeiten
Da die Vigenère-Chiffre aus der recht schwachen Cäsar-Chiffre besteht, stellt sich die Frage, wie sicher sie denn tatsächlich ist. Für eine einfache Cäsar-Chiffre, bestehend aus Großbuchstaben, gibt es 26 Möglichkeiten. Für zwei Cäsar-Chiffren, sprich einem Schlüsselwort mit 2 Buchstaben wie CT, sind es schon 26 · 26 = 676 mögliche Kombinationen. Ein Schlüsselwort mit zwölf Buchstaben erhöht die Anzahl bereits auf 95.428.956.661.682.176. Je länger also das Schlüsselwort, desto schwerer wird es, die Chiffre zu knacken.
Die Vigenère-Chiffre galt daher als außerordentlich sicher, so sicher sogar, dass sie den Beinamen „le chiffre indéchiffrable“ erhielt – die unknackbare Chiffre. Und wie bei so vielen Dingen, die als unsinkbar, unknackbar oder unzerstörbar gelten, braucht es einen Eisberg oder nur jemanden mit genügend Einsatzwillen, um das Gegenteil zu beweisen. Auch wenn es 300 Jahre dauerte, bis das Schicksal der Chiffre besiegelt war. Wie sie schließlich gebrochen wurde, lesen Sie in einer der nächsten Ausgaben. (wid@ct.de)
Python-Programm im GitHub-Repository: ct.de/yvkq