Samstag, 1. Mai 2010


Topthema

Donnerstag, 17. August 2006 | Topthema

About Security #68: Kryptographie — Polyalphabetische Substitution

(Link zum Artikel: http://www.entwickler.de/php/kolumnen/030749)

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.

N E U ! Security aktuell
T�glich aktuelle Security-Infos!

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.

About Security: Die komplette Serie

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.

Wenn Sie Fragen oder Themenvorschl�ge haben, k�nnen Sie diese gerne an die angegebene E-Mail-Adresse senden oder im Security-Forum einbringen!

Carsten Eilers

About Security � �bersicht zum aktuellen Thema "Kryptographie � Grundlagen"

Kommentare

Folgende Links könnten Sie auch interessieren