Die Skytale von Sparta in Python

Was du hier lernst

• Transposition
• Verschachtelte Schleifen
• range() mit Schrittweite
• Modulo-Rechnung
• Ganzzahldivision //
• Strings zusammensetzen

Die Erklärung stammt – leicht überarbeitet für Python 3 – aus dem Buch „Coding for Fun mit Python“ von Lars Heppert, Kapitel 4, Abschnitte 4.3 und 4.4.

Seit wann wird chiffriert?

Kürzestmögliche Antwort: seit einer Ewigkeit, mindestens seit der Zeit der Pharaonen. Allerdings waren die Mittel, um Nachrichten zu verschlüsseln, denkbar einfach im Vergleich zu den heutigen ausgeklügelten Systemen. Selbst die Verfahren der Römer sind für heutige Verhältnisse sehr leicht zu knacken – auch für dich.

Eines der ältesten überlieferten Verfahren ist unter dem Namen Skytale von Sparta bekannt. Die Griechen verwendeten es, um geheime Botschaften durch Transposition zu verschlüsseln. Bei einem Transpositionsverfahren werden die Buchstaben des Klartextes nicht verändert, sondern nur ihre Positionen innerhalb der Nachricht vertauscht.

Die Skytale beruhte darauf, dass Absender und Empfänger je einen Stab mit gleichem Durchmesser besaßen. Um den Stab wickelte man spiralförmig einen schmalen Streifen Pergament und beschriftete ihn längs zum Stab. Abgewickelt zeigt der Streifen nur noch Buchstabensalat. Zum Ablesen musste man das Pergament wieder um einen Stab mit demselben Durchmesser wickeln. Der Durchmesser des Stabes war also der Schlüssel und entsprechend geheim zu halten.

Ob die Spartaner ihre Stäbe wirklich zum Verschlüsseln benutzten, ist unter Historikern übrigens umstritten. Die antiken Quellen sind dünn, und manche Forscher halten die Skytale eher für ein Erkennungszeichen. Als Gedankenexperiment taugt sie trotzdem hervorragend.

Untereinander geschrieben

Wie sich die Zeichen verschieben, siehst du auch, wenn du den Text in Zeilen untereinanderschreibst:

heute ist sehr
schönes wetter

Zum Geheimtext gelangst du, indem du die beiden Zeilen spaltenweise liest: HSECUHTÖEN EISS TW ESTETHERR. Zum Entziffern musst du in diesem Fall nicht den Durchmesser des Stabes kennen, sondern die Anzahl der Zeichen pro Zeile. Mit diesem Wissen ist der Text leicht zu entziffern, aber auch ohne ist das Verfahren aus heutiger Sicht alles andere als sicher.

Trotzdem sind Transpositionen bis heute ein wichtiger Bestandteil vieler moderner Verfahren. Der Standard AES, der heute fast jede Internetverbindung schützt, vertauscht zum Beispiel in jeder Runde mit dem Schritt »ShiftRows« die Bytes seines Datenblocks – natürlich kombiniert mit weiteren, viel stärkeren Schritten.

Die Skytale von Sparta in Python

Die Skytale lässt sich mit Python sehr einfach nachprogrammieren und auch mit Papier und Bleistift simulieren. Beides schauen wir uns an. Beginnen wir mit der Funktion skytale_encrypt(), die sich um die Verschlüsselung kümmert:

def skytale_encrypt(text, umfang):
    text    = ensureSideCondition(text, umfang)
    length  = len(text)
    cipher  = ""
    for x in range(0, umfang):
        for y in range(x, length, umfang):
            cipher += text[y]

    return cipher.upper()

Der Parameter umfang gibt die Zeichen pro Zeile vor. Die Zeichen werden genau in diesem Abstand aneinandergehängt: Die äußere Schleife wählt mit x eine Spalte, die innere springt mit der Schrittweite umfang durch den Text – range(x, length, umfang) liefert die Positionen x, x + umfang, x + 2 · umfang und so weiter. Bei acht Zeichen pro Zeile sind das für die erste Spalte die Positionen 0, 8, 16 und 24, also genau die Zeichen, die in der Tabelle untereinanderstehen.

Die Nebenbedingung

Eine Nebenbedingung ist dabei zu beachten: Die Textlänge muss glatt, also ohne Rest, durch den Umfang teilbar sein. Sonst wäre die letzte Zeile der Tabelle kürzer, und beim Entschlüsseln würden die Spalten nicht mehr passen. Die Prüfung ist in die Funktion ensureSideCondition() ausgelagert, die den Text bei Bedarf um Leerzeichen erweitert:

def ensureSideCondition(text, umfang):
    length      = len(text)
    remainder   = length % umfang
    while remainder != 0:
        text       += " "
        length      = len(text)
        remainder   = length % umfang

    return text

Solange die Division durch den Umfang einen Rest lässt, hängt die Schleife ein Leerzeichen an. Unser Beispieltext hat 29 Zeichen, bei acht Zeichen pro Zeile kommen also drei Leerzeichen dazu.

Entschlüsseln mit vertauschtem Schlüssel

Die Entschlüsselung muss die Umwandlung vom zeilenweisen ins spaltenweise Lesen wieder rückgängig machen. Dafür brauchst du keine neue Funktion: Die Entschlüsselung nutzt dasselbe Verfahren wie die Verschlüsselung, nur mit einem anderen Schlüssel. Die beiden Schlüssel, die sich hier gegenüberstehen, entsprechen der Breite und der Höhe der Tabelle in Zeichen. Zum Verschlüsseln verwenden wir die Anzahl der Zeichen pro Zeile als Umfang, zum Entschlüsseln die Anzahl der Zeilen. Die beiden Werte lassen sich leicht ineinander umrechnen, denn du musst nur die Gesamtzahl der Zeichen durch den jeweils anderen teilen:

def skytale_decrypt(text, umfang):
    length      = len(text)
    umfang      = length // umfang
    plaintext   = skytale_encrypt(text, umfang)

    return plaintext.lower()

Die Aufrufe von lower() und upper() sorgen nur für die Konvention des Kapitels: Klartext steht in Kleinbuchstaben, Geheimtext in Großbuchstaben. Mehr dazu findest du auf der Seite zur Caesar-Verschlüsselung.

Die Skytale in Aktion

Die Funktionen verwendest du wie folgt:

key         = 8
plaintext   = "heute ist sehr schönes wetter"
cipher      = skytale_encrypt(plaintext, key)

print(plaintext)
print(cipher)
print(skytale_decrypt(cipher, key))

In der Konsole erscheinen drei Zeilen:

heute ist sehr schönes wetter
HTCEE HTUSÖTTENEEHER RS I   SSW
heute ist sehr schönes wetter

Die mittlere Zeile ist die Tabelle mit vier Zeilen zu je acht Zeichen, Spalte für Spalte gelesen: »htce« aus der ersten Spalte, »e ht« aus der zweiten und so weiter. Die drei angehängten Leerzeichen stecken im Geheimtext und am Ende des entschlüsselten Textes, du siehst sie nur nicht. Im gedruckten Buch blieb das »ö« im Geheimtext übrigens klein, weil upper() in Python 2 auf Bytes arbeitete und Umlaute nicht kannte. Python 3 rechnet mit Unicode und macht daraus ein »Ö«.

Die Skytale für unterwegs

Die Skytale ist in ihrer Anwendung so einfach, dass du sie leicht auch unterwegs verwenden kannst. Statt eines Stabes mit bestimmtem Umfang brauchst du nur die Anzahl der Spalten, also der Zeichen je Zeile. Zum Verschlüsseln trägst du den Text Zeile für Zeile in eine Tabelle mit der festgelegten Anzahl an Spalten ein und liest ihn Spalte für Spalte wieder aus:

Zum Entschlüsseln tauschst du einfach Zeilen und Spalten. Die Anzahl der Zeilen aus der ersten Tabelle ist jetzt die Anzahl der Spalten und umgekehrt:

Die Pfeile zeigen, in welcher Richtung der jeweilige Text zu lesen ist. Genau diese beiden Tabellen zeichnet auch die Animation oben. Unter »Probier mal« kannst du das Beispiel »gut und böse« aus den Abbildungen direkt nachspielen.

Wie sicher ist die Skytale?

Nicht sehr. Die Länge des Geheimtexts ist immer ein Vielfaches der Zeilenlänge, und damit kommen nur wenige Schlüssel in Frage. Bei 32 Zeichen sind es 2, 4, 8 und 16 – vier Versuche genügen. Hinzu kommt eine zweite Schwäche: Eine Transposition verändert keine Buchstaben. Im Geheimtext kommen deshalb genauso viele »e« und »n« vor wie im Klartext. Wer die Buchstaben zählt, erkennt sofort, dass hier ein deutscher Text nur durcheinandergewürfelt wurde.

Stärker wird es, wenn man Vertauschen und Ersetzen kombiniert. Die Caesar-Chiffre, die im Buch als Nächstes folgt, ersetzt jeden Buchstaben durch einen anderen. Im Ersten Weltkrieg setzte das deutsche Heer mit der ADFGVX-Chiffre auf genau diese Mischung aus Ersetzung und Transposition. Und moderne Blockchiffren wie AES wechseln in jeder Runde zwischen Ersetzen und Vertauschen ab.

Das Bild zum Programm

Die Animation ist neu auf dieser Website. Die Funktion wrapAndRead() schreibt den Text Zeichen für Zeichen in die Tabelle, danach liest sie ihn Spalte für Spalte wieder aus. Die Reihenfolge des Auslesens berechnet sie mit denselben beiden Schleifen wie skytale_encrypt(), hier nur als List Comprehension in einer Zeile:

order = [y for x in range(0, columns) for y in range(x, len(text), columns)]

Oben zeichnet drawRod() den Stab aus Abbildung 4.3. Jede Windung des Streifens trägt ein Zeichen der vordersten Zeile. Beim Ablesen leuchtet die Windung auf, deren Spalte gerade dran ist: Jede Spalte der Tabelle ist eine Windung des Streifens. Unten wächst mit drawStrip() der abgewickelte Streifen, so wie er verschickt wird. Für das Entschlüsseln ruft das Programm wrapAndRead() ein zweites Mal auf, nur mit vertauschter Tabelle: len(cipher) // receiverKey Spalten statt key. Das ist derselbe Trick wie in skytale_decrypt().

Probier mal

Jede Variante ändert den Code oben. Ein Klick auf »Ausprobieren« übernimmt die Änderung in den Editor und startet das Programm. »Zurücksetzen« holt das Original zurück.

1. 01Ein dickerer Stab

   Mit key = 5 passen nur noch fünf Zeichen in eine Zeile, dafür wird die Tabelle höher: sechs Zeilen statt vier. Der Geheimtext sieht völlig anders aus, obwohl wieder nur dieselben Buchstaben vertauscht werden. Ein Leerzeichen hängt ensureSideCondition() an, damit 30 Zeichen glatt aufgehen.

   - key         = 8
   + key         = 5

   Ausprobieren

2. 02Das Beispiel aus Abbildung 4.4

   Im Buch zeigt eine kleine Tabelle, wie die Skytale auch ohne Stab funktioniert: »gut und böse« mit vier Zeichen pro Zeile. Die Animation baut genau diese Tabelle nach, beim Entschlüsseln entsteht die gedrehte Tabelle aus Abbildung 4.5.

   - key         = 8
   + key         = 4
   - plaintext   = "heute ist sehr schönes wetter"
   + plaintext   = "gut und böse"

   Ausprobieren

3. 03Der falsche Stab

   Der Empfänger braucht einen Stab mit demselben Umfang. Mit einem zu dünnen Stab – hier receiverKey = 4 statt 8 – ergeben die Zeilen keinen Sinn. Die Konsole zeigt den Zeichensalat in einer vierten Zeile, die Animation beim Entschlüsseln ebenfalls.

   - receiverKey = key  # der Empfänger hat einen Stab mit demselben Umfang
   + receiverKey = 4  # der Empfänger hat einen zu dünnen Stab
   + print(skytale_decrypt(cipher, receiverKey))

   Ausprobieren

4. 04Alle Stäbe durchprobieren

   Wie sicher ist die Skytale? Die Länge des Geheimtexts ist immer ein Vielfaches der Zeilenlänge. Bei 32 Zeichen kommen deshalb nur 2, 4, 8 und 16 als Schlüssel in Frage – vier Versuche, und eine der Zeilen ist lesbar.

   - print(skytale_decrypt(cipher, key))
   + print(skytale_decrypt(cipher, key))
   + 
   + print()
   + print("Alle möglichen Stäbe:")
   + for guess in range(2, len(cipher)):
   +     if len(cipher) % guess == 0:
   +         print(f"{guess:2}  {skytale_decrypt(cipher, guess)}")

   Ausprobieren

5. 05Deine eigene Botschaft

   Ersetze den Text in plaintext. Die Skytale verträgt Ziffern und Satzzeichen, denn sie ersetzt nichts, sie vertauscht nur. Nur Groß- und Kleinschreibung gehen verloren: Nach der Konvention des Kapitels schreibt das Programm den Geheimtext groß und den Klartext klein. Ab etwa 64 Zeichen wird es in der Tabelle eng.

   - plaintext   = "heute ist sehr schönes wetter"
   + plaintext   = "Treffpunkt um Mitternacht am alten Leuchtturm!"

   Ausprobieren

#coding: latin1

# stellt sicher, dass die Länge des Textes ohne Rest durch den Umfang teilbar ist
def ensureSideCondition(text, umfang):
    length      = len(text)
    remainder   = length % umfang
    while remainder != 0:
        text       += " "
        length      = len(text)
        remainder   = length % umfang
       
    return text
        
def skytale_encrypt(text, umfang):
    text    = ensureSideCondition(text, umfang)
    length  = len(text)
    cipher  = ""
    for x in range(0, umfang):
        for y in range(x, length, umfang):
            cipher += text[y]
            
    return cipher.upper()

def skytale_decrypt(text, umfang):
    length      = len(text)
    umfang      = length/umfang
    plaintext   = skytale_encrypt(text, umfang)

    return plaintext.lower()

key         = 8
plaintext   = "heute ist sehr schönes wetter"
cipher      = skytale_encrypt(plaintext, key)

print plaintext
print cipher
print skytale_decrypt(cipher, key)