Spaltentransposition

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Die Spaltentransposition ist eine kryptographische Methode, um einen Klartext zu verschlüsseln und so in einen Geheimtext umzuwandeln. Sie basiert auf der Transpositionsmethode. Dabei werden die einzelnen Zeichen der Botschaft (zumeist Buchstaben) umsortiert, und zwar nach einer bestimmten Verfahrensvorschrift, die durch einen geheimen Schlüssel gesteuert wird. Dies steht im Gegensatz zur Substitutionsmethode, bei der jedes Klartextzeichen an seinem Platz bleibt, jedoch durch ein anderes Zeichen ersetzt („substituiert“) wird.

Beim Spaltentranspositionsverfahren wird generell eine rechteckförmige Anordnung (auch als Matrix bezeichnet) benutzt, bestehend aus mehreren Zeilen (so viele, wie nötig sind, um den Klartext einzutragen) und einer durch den Schlüssel (zumeist ein Kennwort aus Buchstaben, auch Schlüsselwort genannt) vorgegebenen Anzahl von Spalten. Die Spaltenanzahl entspricht dabei der Anzahl der Buchstaben dieses Schlüsselworts. Anschließend wird der Klartext zeilenweise in die Matrix eingetragen.

Als Geheimtext werden nun die einzelnen Buchstaben des Klartextes spaltenweise aus der Matrix ausgelesen, wobei die Reihenfolge des Auslesens der Spalten durch die alphabetische Reihenfolge der Buchstaben des Kennworts bestimmt wird.

Der folgende Klartext soll mithilfe der Spaltentransposition verschlüsselt werden. Das Schlüsselwort sei „WIKIPEDIA“. Es besteht aus neun Buchstaben. Somit ist der Klartext zeilenweise in ein Rechteck der Breite 9 einzutragen. Falls in der letzten Zeile weniger als neun Buchstaben stehen, so bleibt der Rest leer.

Klartext:

DIESISTNUREINBEISPIELTEXTUNDERDIENTHIERINUNSERERWIKIPEDIAZURILLUSTRATIONDERSPALTENTRANSPOSITION

Rechteck:

WIKIPEDIA
---------
DIESISTNU
REINBEISP
IELTEXTUN
DERDIENTH
IERINUNSE
RERWIKIPE
DIAZURILL
USTRATION
DERSPALTE
NTRANSPOS
ITION

Die Reihenfolge des Auslesens wird durch das Schlüsselwort bestimmt, dessen einzelne Buchstaben in alphabetischer Reihenfolge zu nummerieren sind (A entspricht 1, D entspricht 2 usw. Identische Buchstaben werden in der Reihenfolge ihres Auftretens nummeriert, siehe die drei „I“ an Position 4, 5 und 6). Aus WIKIPEDIA wird so 947583261.

WIKIPEDIA
947583261

Der obige Text wird nun spaltenweise in der Reihenfolge dieser Nummerierung ausgelesen.

Ausgelesene Spalten:

1 (A)      2 (D)      3 (E)      4 (I)       5 (I)       6 (I)      7 (K)       8 (P)       9 (W)
UPNHEELNES TITNNIIILP SEXEUKRTAS IEEEEEISETT SNTDIWZRSAO NSUTSPLOTO EILRRRATRRI IBEINIUAPNN DRIDIRDUDNI

Um nicht die Länge der einzelnen Spalten beziehungsweise die Länge des Schlüsselworts zu verraten, wird der Geheimtext in Gruppen vorgegebener Länge, zumeist in Fünfergruppen gesendet, also:

Geheimtext (in Fünfergruppen):

UPNHE ELNES TITNN IIILP SEXEU KRTAS IEEEE EISET TSNTD IWZRS AONSU TSPLO TOEIL RRRAT RRIIB EINIU APNND RIDIR DUDNI

Doppelte Spaltentransposition

[Bearbeiten | Quelltext bearbeiten]

Die oben dargestellte „einfache“ Spaltentransposition bietet keine große Sicherheit gegen unbefugte Entzifferung. Sie kann aber durch einen zweiten Verfahrensschritt zur doppelten Spaltentransposition, auch Doppelwürfel genannt, verbessert werden. Hierzu fasst man den oben angegebenen Geheimtext nur als Zwischentext auf, auf dem man eine zweite Spaltentransposition mit einem zweiten Schlüsselwort durchführt. Dies ergibt den Geheimtext des doppelt spaltentransponierten Klartextes. Wichtig dabei ist, dass die Längen der beiden Schlüsselwörter und des (Klar)textes relativ prim zueinander sind um eine sichere Durchmischung zu erreichen.

Entschlüsselung

[Bearbeiten | Quelltext bearbeiten]

Der befugte Empfänger der Nachricht ist im Besitz des oder der Schlüssel, mit deren Hilfe er die Breite der Rechtecke ermitteln kann. Unter Umkehrung der oben beschriebenen Verfahrensschritte (nun spaltenweises Eintragen und zeilenweises Auslesen) lässt sich der Geheimtext entschlüsseln, also in den Klartext zurückwandeln.

Wie fast alle Handschlüsselverfahren, bieten in der heutigen Zeit weder die einfache noch die doppelte Spaltentransposition einen hinreichenden Schutz gegen unbefugte Entzifferung. So gelang es dem israelischen Kryptoanalytiker George Lasry einfache Spaltentranspositionen, selbst solche mit sehr langen Schlüsseln, mithilfe von Hill Climbing zu brechen.[1] Auch ein als Herausforderung speziell konstruiertes Kryptogramm, das im Jahr 2007 durch Klaus Schmeh mithilfe der doppelten Spaltentransposition erzeugt und veröffentlicht worden war,[2] konnte im November 2013 gebrochen werden.[3] Insofern sollte man heutzutage wirklich wichtige Geheimnisse nicht mithilfe solch historischer Verfahren vor fremden Blicken schützen wollen.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. George Lasry, Nils Kopal, Arno Wacker: Cryptanalysis of columnar transposition cipher with long keys. Cryptologia 2016, 40:4, S. 374–398, doi:10.1080/01611194.2015.1087074.
  2. The Top 50 unsolved encrypted messages – 13. Double Column Transposition Reloaded (englisch), abgerufen am 18. Januar 2021.
  3. George Lasry, Nils Kopal, Arno Wacker: Solving the Double Transposition Challenge with a Divide-and-Conquer Approach. Cryptologia 2014, 38:3, S. 197–214, doi:10.1080/01611194.2014.915269.