Channel Security

In dieser Folge erfahren Sie, wie die in About Security #67 vorgestellte Transposition gebrochen werden kann und lernen ein weiteres klasssisches Verschlüsselungsverfahren kennen, die Polyalphabetische Substitution.

Um die in About Security #67 vorgestellte Transposition zu brechen gibt es mehrere Ansätze. Einen Anhaltspunkt können vorhandene oder fehlende Buchstaben geben: Wenn beim Verschlüsseln die letzte Zeile mit Füllzeichen, z.B. 'X', auf die gewünschte Länge gebracht wird, kann daraus auf den Aufbau der Transposition geschlossen werden. In einem kurzen Text fehlende oder selten vorkommende Buchstaben können den möglichen Klartext einschränken. Wenn es dem Angreifer reicht, zu wissen, was mit Sicherheit nicht geschrieben wurde, muss er den Text dann unter Umständen gar nicht erst entschlüsseln. Auch die statistischen Eigenheiten der Sprache bleiben erhalten: Während im Klartext aufeinander folgende Buchstaben statistisch voneinander abhängen, lassen sich im Geheimtext entsprechende getrennte Buchstabenpaare finden, wenn der Text ausreichend lang ist.

Eine einfache Transposition ist auch durch einen Klartextangriff zu brechen. Zu entschlüsseln sei der Geheimtext aus der letzten Woche, nur dass er jetzt keine Leerzeichen mehr enthält. Die dienten letzte Woche nur zur Markierung der ausgelesenen Spalten.

Geheimtext:

DICSLESEINHBFTIREZBEURTNSILIEAIIIEOSRNOCSMEPESNHTLDIIPOTEIEENOD

Es wird ein wahrscheinlich im Klartext vorhandenes Wort benötigt, das länger als die vermutete Blocklänge ist. Die Blocklänge ist die Anzahl Zeichen im Text, innerhalb der eine Vertauschung erfolgt. Im Beispiel ist sie 8, entsprechend der Spaltenzahl im Rechteck. Das im Klartext vermutete Wort ist 'Transposition'. Jetzt kann man anfangen und Blocklängen durchprobieren: Bei einer Blocklänge von 5 müsste unter dem 'T' ein 'P' stehen, der Geheimtext also die Zeichenfolge 'TP' enthalten. Dies ist nicht der Fall. Bei einer Blocklänge von 8 müsste 'TI' enthalten sein. Dies ist der Fall. Dann müssten auch 'RT', 'AI' usw. enthalten sein. Auch dies trifft zu, die Blocklänge ist also 8.

DICSLESEINHBFTIREZBEURTNSILIEAIIIEOSRNOCSMEPESNHTLDIIPOTEIEENOD

Nachdem die Lage des bekannten Wortes ermittelt wurde, kann der Text darauf aufbauend weiter analysiert werden. In diesem, sehr einfachen, Fall kann nun schon entschlüsselt werden, indem der Geheimtext entsprechend umbrochen wird:

D I C S L E S E 
I N H B F T I R 
E Z B E U R T N
S I L I E A I I
I E O S R N O C
S M E P E S N H
T L D I I P O T
E I E E N O D

Der Klartext steht nun in den Spalten.

Statt bei der Verschlüsselung die Spalten des Würfels einfach nur auszulesen, können sie vorher auch vertauscht werden. Die Vertauschungen bilden dann zusammen mit der Spaltenzahl den Schlüssel. Auch ein Auslesen in anderen Richtungen ist möglich, z.B. abwechselnd von oben nach unten und von unten nach oben. All dies erhöht die Sicherheit des Verfahrens jedoch nicht wirklich.

Das Verfahren der Transposition ist sehr alt. Schon bei der im 5. Jahrhundert vor Christus von den Griechen verwendeten Scytale handelt es sich um eine Transposition. Die Scytale ist ein Stab, um den ein Pergamentstreifen gewickelt wird. Darauf wird der Länge nach die Nachricht geschrieben. Das abgewickelte Pergament enthält den Geheimtext, der Durchmesser des Stabes ist der Schlüssel: Um einen Stab gleichen Durchmessers gewickelt ist der Klartext wieder lesbar.

Polyalphabetische Substitution

Das Hauptproblem einfacher Substitutionen ist ihre Umkehrbarkeit: Jedes Geheimtextzeichen entspricht immer dem gleichen Klartextzeichen. Dadurch bleiben charakteristische Muster im Klartext im Geheimtext erhalten. Besonders auffällige Muster lassen sich sogar mit einem Wörterbuch-Angriff entschlüsseln, indem nach diesem Muster gesucht wird. So findet man leicht heraus, das IMIMSMIIM "totolotto" ist.

Bei der Polyalphabetischen Substitution wird daher die Substitution von der Position der Zeichen im Text abhängig gemacht. Ihr einfachster Fall ist die so genannte Vigenère-Chiffre.

Während bei der Cäsar-Chiffre

Geheimtextzeichen = Klartextzeichen + Schlüssel mod 26

(siehe About Security #66) eine Verschiebung um 'Schlüssel'-Zeichen erfolgte, wird bei der Vigenère-Chiffre ein Schlüsselwort verwendet, z.B. ABCDE. Dies wird wiederholt über den Klartext geschrieben:

ABCDEABCDEABCDEABCDEAB
eineinfachersatzmitabc

Dann werden die übereinander stehenden Buchstaben wie bei der Cäsar-Chiffre addiert, und man erhält den Geheimtext

EJPHMNGCFLESUDXZNKWEBD

Das Schlüsselwort der Länge 5 führt also zu fünf verschiedenen Cäsar-Chiffren, die der Reihe nach angewendet werden. Dabei werden Muster im Klartext verwischt: Aus 'ein' wird z.B. sowohl 'EJP' als auch 'HMN'. 'a' wird zu 'C', 'D' oder 'E'. Ohne die Länge des Schlüsselworts zu kennen, weiß ein Angreifer nicht, welche Geheimtextzeichen den gleichen Klartextzeichen entsprechen.

Auch dieses Verfahren ist unsicher. Ein möglicher Angriff wird in der nächsten Folge beschrieben. Außerdem geht es dann um weitere Verschlüsselungsverfahren, die Vernam-Chiffre und das One-Time-Pad.

Carsten Eilers

About Security – Übersicht zum aktuellen Thema "Kryptographie – Grundlagen"

• About Security #66: Kryptographie – Substitution
• About Security #67: Kryptographie – Transposition
• About Security #68: Kryptographie – Polyalphabetische Substitution
• About Security #69: Kryptographie – Vernam-Chiffre
• About Security #70: Kryptographie – Feistel-Netzwerke