SECOM

SECOM ist ein Verschlüsselungsalgorithmus, der auf dem berühmten russischen VIC Cipher aus den 1950er Jahren basiert. Er soll, wie auch der Pontifex/Solitaire-Algorithmus aus dem Buch Cryptonomicon, vor allem zwei Kriterien erfüllen:

  • Unkompliziertes Design: Die einzelnen Schritte sollen ohne Hilfe von z.B. Computern durchführbar sein. Zum Ver- und Entschlüsseln werden ausschließlich Materialien benötigt, die gut verfügbar sind und zudem den Anwender nicht verdächtig machen. Für SECOM wird ausschließlich Papier und Bleistift benötigt. (Soitaire benötigt zudem noch ein Kartdendeck als Schlüsselgenerator.)
  • Hohe Sicherheit: Obwohl auf die Rechenkapazitäten von Computern verzichtet wird, sollte die Sicherheit sehr hoch sein. (Immerhin wurde etwa der VIC Cipher von Geheimagenten im Feldeinsatz verwendet, bevor später allgemein zu One Time Pads übergegangen wurde.)

Im Gegensatz zu Solitaire erscheint mir SECOM einfacher in der Durchführung und im Schlüsselaustausch (Solitaire benötigt immerhin ein ganzes, speziell sortiertes Kartendeck als Schlüssel). Die Sicherheit beider Algorithmen wage ich dagegen nicht zu beurteilen.

Im unteren Teil dieser Seite wird eine von mir entwickelte Implementierung dieses Algorithmus vorgestellt: wxSECOM (Quicklinks: Features & Screenshots, Download, Quellcode).

Eine detaillierte Beschreibung des Algorithmus findet sich auf der Website des Kryptologen Dirk Rijmenants.

Aufbau

Der Algorithmus lässt sich grob in vier Komponenten unterteilen:

  1. Schlüsselerzeugung
  2. Substitution
  3. Erste Transposition
  4. Zweite Transposition

Auf Basis dieser Unterteilung soll der Algorithmus im Folgenden kurz erläutert werden. Zur Veranschaulichung wird der Klartext „RV TOMORROW AT 1400PM TO COMPLETE TRANSACTION USE DEADDROP AS USUAL“ mit dem Schlüsselsatz „MAKE NEW FRIENDS BUT KEEP THE OLD“ verschlüsselt.

Zur Veranschaulichung werden Leerzeichen im Klartext als × dargestellt:

Anmerkung: Dieses Beispiel entspricht dem auf der offiziellen Seite, allerdings hat sich dort anscheinend ein Fehler eingeschlichen: Die dort gezeigte Verschlüsselung basiert auf dem Klartext “… AS USUALO“ (mit „O“ am Ende).

Schlüsselerzeugung

SECOM verwendet einen einfachen Schlüsselsatz, aus dem die den Algorithmus benötigten Schlüssel abgeleitet werden. Dabei werden Schlüssel für die Substitution und die zwei Transpositionen benötigt. Durch das Verfahren der Kettenaddition (siehe unten) kann auch aus einem kurzen Schlüssel eine ausreichende Zahl pseudozufälliger Ziffern erzeugt werden.

Im Beispiel lautet der Satz:

Zur Erzeugung der Schlüssel werden zunächst die ersten 20 Buchstaben des Schlüsselsatzes in zwei Hälften zu je 10 Buchstaben aufgeteilt. Jeder dieser Abschnitte wird dann in eine Reihe von Ziffern umgewandelt, indem die Buchstaben entsprechend ihrer Reihenfolge im Alphabet eine Ziffer zugeordnet bekommen, wobei 0 die höchste Ziffer ist. Bei mehreren gleichen Buchstaben im Abschnitt wird für folgende Buchstaben einfach hochgezählt (also abc→123, acb→132, abb→123, aaa→123 usw.).

In unserem Beispiel sieht das zunächst so aus:

Die zwei Ziffernfolgen werden dann addiert, und zwar Ziffer für Ziffer und „modulo 10“, also ohne Überträge:

Das Ergebnis hiervon wird dann via Kettenaddition auf 50 pseudozufällige Ziffern erweitert. Die Kettenaddition funktioniert so, dass zunächst die ersten beiden Ziffern der Folge addiert werden (wieder modulo 10), dann die zweite und dritte Ziffer in der Folge usw. Die bei jedem Schritt erhaltene Ziffer wird an das Ende der Ziffernfolge angehängt. So lässt sich der anfängliche Schlüssel aus 10 Ziffern auf beliebige Längen erweitern, wobei das Ergebnis eben durch die verkettete Addition der Schlüsselteile pseudozufällig bleibt.

Das Verfahren ist hier schematisch dargestellt, in Klammern sind die zu addierenden Ziffern des Schlüssels angegeben:

Im Beispiel erhalten wir so den folgenden pseudozufällige Schlüssel von 50 Ziffern Länge, der als Basis für die einzelnen Schritte der Verschlüsselung verwendet wird.

Von diesem Schlüssel werden nun die letzten 10 Ziffern nach ihrer Größe sortiert. Wie oben ist auch hier die 0 die größte Ziffer, und bei mehreren gleichen Ziffern wird wiederum weitergezählt:

Das Ergebnis hiervon ist der Schlüssel, der für die Substitution verwendet wird.

Verschlüsselung

Substitution

Die hier verwendete Substitution basiert auf einem sogenannten “straddling checkerboard“ (zu deutsch etwa „gespreiztes Schachbrett“). Hierbei handelt es sich um eine monoalphabetische, gespreizte Substitution. Dies bedeutet, dass das durch den zuvor erzeugten Schlüssel definierte Substitutionsalphabet über die ganze Nachricht beibehalten wird („monoalphabetisch“). Ein Klartextzeichen wird dabei in ein oder zwei Geheimtextzeichen verschlüsselt („Spreizen“). Als Geheimtextalphabet dienen die Ziffern 0 bis 9.

Die Verwendung eines gespreizten Alphabets ermöglicht, bestimmte Zeichen mit nur einem Geheimtextzeichen zu verschlüsseln. Verwendet man hierfür Zeichen mit hoher Frequenz im Ausgangstext (etwa E, N, …), lässt die Länge des Geheimtextes deutlich reduzieren. Zudem erwirkt diese Methode zusammen mit der folgenden Transposition eine Fraktionierung des Klartextes.

Die häufigsten zehn Zeichen im Englischen sind (in dieser Reihenfolge mit abnehmender Häufigkeit): E, T, A, O, I, N, S, R, H, L. Im Deutschen ist die Verteilung etwas anders, hier lautet die Liste: E, N, I, R, S, A, T, D, H, U. Falls die deutschen Umlaute außerdem nicht einzeln kodiert werden, ist das E in deutschen Texten durch die Umschreibung (ä→ae usw.) viel häufiger als in englischen (17.5% gegenüber 12.5%).

Mit dem zuvor erzeugten Schlüssel 8139065427 wird nun das Schachbrett angelegt. Die Schlüsselziffern nummerieren die zehn Spalten der Tabelle. In die erste Zeile werden hier die sieben häufigsten Buchstaben der englischen Sprache eingetragen.1. Die folgenden Zeilen werden mit dem restlichen Alphabet, dem Leerzeichen × sowie den Ziffern 0 bis 9 aufgefüllt (beginnend bei 1)

Hier sind nun einige Dinge zu beachten: Zunächst bleiben in der ersten Zeile drei Plätze frei. Hier wurde das Merkwort willkürlich als „ES.TO.NI.A“ geschrieben, genau so wäre aber auch etwa „ESTONIA…“ möglich gewesen. Die letzten drei Zeilen werden mit den Spaltennummern beschriftet, bei denen sich eine Leerstelle in der obersten Zeile befindet. Weiterhin beginnt das Auffüllen der einzelnen Zeilen nicht am linken Rand, sondern in der Spalte, die der Zeilennummer entspricht (hier dargestellt durch einen Pfeil). Das folgende Beispiel sollte die Konstruktion veranschaulichen:

Beim Verschlüsseln wird nun jedes Klartextzeichen in der Tabelle aufgesucht. Befindet es sich in der ersten Spalte, entspricht die zugehörige Geheimtextziffer der Spaltennummer: E→8, S→1, I→4. Anderenfalls setzt sich der Geheimtext aus Zeilen- und Spaltennummer zusammen: L→38, B→33, 5→26.
Es wird deutlich, dass diese Verschlüsselung umkehrbar ist: Beginnt ein Geheimtext mit einer der Zeilennummern (hier also 3, 6 oder 2), kann es sich nicht um ein Zeichen der oberen Zeile handeln, da an der entsprechenden Stelle dort eine Lücke ist. Wäre dies nicht so, könnte der Geheimtext 33 nicht nur B, sondern auch irgendetwas anderes bedeuten.

Unser verwendeter Klartext wird also folgendermaßen verschlüsselt (zur besseren Übersicht wurden Leerzeichen eingefügt; das Leerzeichen im Klartext wird wie oben mit × wiedergegeben):

Damit ergibt sich der folgende Geheimtext mit einer Länge von 104 Zeichen gegenüber den 67 Zeichen des Klartextes. Bei einer voll bipartiten Verschlüsselung wäre der Geheimtext 2×67=134 Zeichen lang; durch das Spreizen werden also 30 Zeichen bzw. 23% eingespart:

Erste Transposition

Als nächstes wird der durch die Substitution gewonnene Geheimtext transponiert. Dabei kommt eine einfache Spaltentransposition zum Einsatz: Der Text wird zeilenweise in ein Raster mit fester Breite eingetragen, und dann in einer durch einen Schlüssel festgelegten Reihenfolge spaltenweise ausgelesen.

Durch die gespreizte Substitution sind einige der Klartextzeichen durch zwei Ziffern ersetzt worden. In Zusammenhang mit der Spaltentransposition führt dies zur sogenannten Fraktionierung des Geheimtextest.2

Bei SECOM wird die Transpositionsbreite aus dem Schlüsseltext ermittelt, ist also variabel. Dazu wird der durch Kettenaddition erweiterte Schlüssel verwendet. Vom rechten Ende beginnend, werden jeweils ungleiche Ziffern addiert, bis das Ergebnis größer als 9 ist. Danach wird dieses Verfahren noch einmal direkt von der aktuellen Position aus wiederholt, um auch die Breite der zweiten Transposition zu bestimmen. In unserem Beispiel heißt das:

Die Transpositionsbreiten betragen also 12 Spalten für die erste, und 11 Spalten für die zweite Transposition. Damit ergibt sich auch die Zeilenanzahl: Der Geheimtext ist 104 Zeichen lang, damit hat die erste Transposition eine Höhe von 104 / 12 = 9 Zeilen, wobei die letzte Zeile nur 104 % 12 = 8 Zeichen enthält. Die Transpositionstabelle wird nun also mit 12 Spalten angelegt und der Geheimtext aus der Substitution einfach zeilenweise, Ziffer für Ziffer, eingetragen:

Die Spalten werden anschließend mit dem zuvor ermittelten Schlüssel für die erste Transposition, 848982458982, nummeriert. Die Reihenfolge beim Auslesen ergibt sich nun, indem man die Schlüsselziffern in aufsteigender Reihenfolge und beginnend von links sortiert. Für diesen Schlüssel wäre demnach zuerst die 6., dann die 12. Spalte auszulesen usw. Die Leerstellen in der letzten Spalte werden ignoriert. Bei der Entschlüsselung führt dies nicht zu einem Problem, da sowohl die Transpositionsbreite als auch die Geheimtextlänge bekannt sind, so dass die Länge der letzten Zeile rekonstruiert werden kann. Im Beispiel wird das Verfahren nochmal verdeutlicht (die Spaltenreihenfolge ist hier durch Buchstaben dargestellt; a=1, b=2 usw.):

Damit ergibt sich der folgende Geheimtext:

Zweite Transposition

Der so erzeugte Schlüsseltext wird nun ein zweites Mal mit einer Spaltentransposition verschlüsselt. Hier handelt es sich allerdings um eine “disrupted transposition“ (zu deutsch etwa „gebrochene Transposition“). Dies bedeutet, dass beim Füllen der Tabelle mit dem zu verschlüsselnden Text die Zeilen zunächst nicht vollständig gefüllt werden. Stattdessen wird zuerst von links beginnend nach einem festgelegten Muster die Tabelle zeilenweise befüllt; danach folgen schließlich die verbliebenen Lücken.

Wie weit jede Zeile im ersten Schritt aufgefüllt wird, hängt vom verwendeten Schlüssel ab. Außerdem muss die Transpositionbreite bekannt sein, um so aus der Länge des Textes die Höhe der Tabelle ermitteln zu können. Ohne Kenntnis des verwendeten Hauptschlüssels ist es deshalb äußerst schwer, diese Transposition zu brechen.

Das hier verwendete Muster lässt sich wie folgt beschreiben. Zunächst einmal muss die Höhe H der Tabelle bekannt sein, d.h. die Anzahl verwendeter Zeilen. Diese ergibt sich aus der Transpositionbreite W und der Textlänge L, gemäß H = L / W. Ein eventuell vorhandener Divisionsrest entspricht dann der Anzahl Ziffern in der letzten Zeile, die in diesem Fall nicht vollständig gefüllt wird.

Die Längen der Zeilen in diesem Schritt ergeben sich aus dem Schlüssel. Von links aus wird die kleinste Ziffer im Schlüssel gesucht (in der Reihenfolge 1,2,..9,0; hier ist 0 also die größte Ziffer). Die erste Zeile wird bis zu dieser Spalte mit den Ziffernfolge aus der ersten Transposition aufgefüllt (wobei diese Spalte selbst zunächst leer bleibt). Die folgende Zeile ist um eine Ziffer länger usw. Dies wird so lange wiederholt, bis eine vollständig gefüllte Zeile erreicht wird. Danach wird die nächste Schlüsselziffer gesucht und die folgende Zeile bis zur entsprechenden Spalte aufgefüllt. Dies wird so oft wiederholt, bis die zuvor ermittelte Höhe erreicht ist. Bei der letzten Zeile ist unbedingt darauf zu achten, dass diese nur bis zur berechneten Länge gefüllt wird (dem Rest der Division L / W). Durch dieses Füllverfahren ergibt sich ein Dreiecksmuster in der Transpositionstabelle.

Im zweiten Schritt werden die Zeilen von oben beginnend mit dem verbleibenden Text aufgefüllt. Das Auslesen der Tabelle geschieht analog zur normalen Spaltentransposition; die Reihenfolge der Spalten ergibt sich hier wieder aus dem Schlüssel.

In unserem Beispiel sieht die Transposition wie folgt aus. Mit der Textlänge von 104 Ziffern und der Breite der zweiten Transposition von 11 Spalten ergibt sich eine Höhe von 104 / 11 = 9 R 5. Die Transpositionstabelle hat also 9 volle Zeilen plus eine, bei der nur 5 Spalten gefüllt sind. Aus dem Schlüssel 09792855878 folgt, dass die erste Zeile bis zur fünften Spalte gefüllt wird (mit a bezeichnet); nach acht Zeilen wird eine vollständig gefüllte Zeile erreicht:

Die nächste Zeile wird nun bis zur siebten Spalte (b) gefüllt. Da danach bereits die berechnete Tabellenhöhe erreicht ist, geht die folgende Zeile nicht bis zur achten, sondern nur bis zur fünften Spalte. Die zwei „fehlenden Spalten“ sind mit • gekennzeichnet:

Der verbleibende Text wird nun in die Lücken eingetragen, wobei wieder von oben begonnen wird:

Das Auslesen der Spalten geschieht wie bei der gewöhnlichen Transposition nach der Ziffernreihenfolge im Schlüssel (mit a, b, … gekennzeichnet):

Der finale Geheimtext lautet damit:

Es empfiehlt sich, den Geheimtext in Fünfergruppen zu notieren; dies erleichtert die Orientierung:

Die letzte Gruppe besteht hier nur aus vier Ziffern, da die Länge von 104 Ziffern nicht restlos durch 5 teilbar ist.

Entschlüsselung

Beim Entschlüsseln wird das Verfahren einfach in umgekehrter Reihenfolge durchlaufen. Vorher erfolgt dabei natürlich die Schlüsselerzeugung aus dem bekannten Schlüsselwort.

Mit der Breite der zweiten Transposition wird die Höhe der Tabelle berechnet und gemäß dem zugehörigen Schlüssel mit dem Geheimtext aufgefüllt. Das Auslesen erfolgt analog zum Befüllen nach obiger Beschreibung.

Der so erhaltene Text wird spaltenweise in die erste Transpositiontabelle eingetragen, deren Höhe zuvor ebenfalls aus der Breit und der Geheimtextlänge ermittelt wurde. Die Länge der letzten Zeile ergibt sich aus dem Divisionsrest. Die Tabelle wird daraufhin zeilenweise ausgelesen.

Der nun nur noch mittels Substitution verschlüsselte Text wird schließlich mit Hilfe des Schachbretts entschlüsselt und man erhält den Klartext, womit die Entschlüsselung abgeschlossen ist.

wxSECOM.py

wxSecom.py

Um die Benutzung von SECOM zu veranschaulichen, und um das Ver-/Entschlüsseln „von Hand“ mit dem Computer zu üben, habe ich ein Python-Programm entwickelt. Es besitzt eine GUI, die auf wxWidgets (bzw. wxPython) basiert. Das Programm sollte daher plattformunabhängig sein, denn sowohl Python wie auch wxPython sind für alle Plattformen verfügbar. Die GUI wurde mit dem wxFormBuilder erstellt; die entsprechende .fbp-Datei findet sich im unten verlinkten Archiv.

Um das Skript ausführen zu können, muss Python installiert sein. Weiterhin wird die wxPython-Bibliothek benötigt. Auf Linux-Systemen sollte diese im Paketarchiv verfügbar sein.3 Für Windows gibt es einen Installer auf der offiziellen Webseite.

Das Programm besteht aus drei Dateien, nämlich der Hauptdatei wxSecom.py sowie der GUI-Klasse _wxSecom.py und der eigentlichen SECOM-Implementierung _SECOM.py. Zum Starten muss nur die Hauptdatei ausgeführt werden!

Hinweis: Ich übernehme keine Haftung für Schäden, die durch das Benutzen dieser Software entstehen!

Features & Screenshots

Features

  • Vollständige Implementierung des SECOM-Algorithmus nach der Beschreibung von Dirk Rijmenants
  • Ver- und Entschlüsselung
  • Detaillierte Darstellung der Zwischenschritte (Schlüsselerzeugung, Subsitution, Transpositionen)
  • Änderbare Parameter wie Länge des erweiterten Schlüssels, minimale Transpositionsbreite und verwendetes Klartextalphabet in der Subsitution

Bekannte Probleme

Das Programm ist noch nicht ganz fertig: Es fehlen teilweise noch die Beschreibungen der Elemente in den Tooltips; außerdem soll auch der Geheimtext jeweils nach den einzelnen Schritten angezeigt werden, um diese leichter nachvollziehen zu können. Weiterhin ist geplant, die Felder unter „Key Setup“ editierbar zu machen, um auch hier mehr experimentieren zu können.

Ein bekannter Bug ist die Tatsache, dass bei ungültigen Zeichen im Klartext keine Verschlüsselung möglich ist. Stattdessen sollten ungültige Zeichen eventuell besser z.B. in ein Leerzeichen umgewandelt werden.

Screenshots

secom_main

secom_keysetup

secom_checkerboard

secom_transposition

secom_transposition2

Download

In den Archiven befinden sich alle benötigten Quellcode-Dateien. Die aktuellste Version steht oben.

Aktuelle Version: secom-20101101.tar.gz (TAR/GZ, 34.7 KiB, 01.11.2010)

Quellcode

Der vollständige Quellcode inkl. Änderungen kann über das git-Repository bei gitorious bezogen werden:
gitorious.org/wxsecom

Clone-URL: git@gitorious.org:wxsecom/master.git

Es ist auch möglich, den Quellcode direkt von gitorious.org herunterzuladen (ohne git; Download-Link im Repository).

Listings

Alternativ werden unten die zwei Hauptteile des Programms gezeigt: Die GUI und die SECOM-Implementierung in Python.

Achtung: Die unten gezeigten Quellcodes entsprechen möglicherweise nicht der aktuellen Version. Die immer aktuellen Dateien finden sich ausschließlich im oben verlinkten Archiv! Weiterhin werden unten nicht alle benötigtem Dateien gezeigt, sondern nur die Implementierung der GUI-Funktionen und die Implementierung des SECOM-Algorithmus.

  1. Merkwort: „ESTONIA“ – was aber nichts mit dem tragischen Ostseeunglück zu tun hat. Im Deutschen ist ein geläufiges Merkwort „INSERAT“; im Russischen „SNEGOPA“ (СНЕГОПА, russ. „Schnee“)
  2. Genau diese Fraktionierung führt dazu, dass sich Geheimtextzeichen, die eigentlich zu einem einzigen Klartextzeichen gehören, über den gesamten Geheimtext verteilen.
  3. Installation unter Ubuntu: sudo apt-get install python-wxgtk2.8
Bookmark the permalink.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind markiert *