Spaltentransposition
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.
Verfahren
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.
Beispiel
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:
9 (A) 7 (D) 6 (E) 2 (I) 4 (I) 8 (I) 3 (K) 5 (P) 1 (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
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 verwendet man am besten ein zweites unabhängiges Schlüsselwort mit unterschiedlicher Länge und fasst den oben angegebenen Geheimtext nur als Zwischentext auf, der in eine zweite Matrix (mit anderer Breite) erneut zeilenweise eingetragen wird und anschließend, entsprechend der Buchstabenreihenfolge des zweiten Kennworts, wieder spaltenweise ausgelesen wird. Dies ergibt den Geheimtext des doppelt spaltentransponierten Klartextes.
Entschlüsselung
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.
Entzifferung
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.
Literatur
- Friedrich L. Bauer: Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie. 3., überarbeitete und erweiterte Auflage. Springer, Berlin u. a. 2000, ISBN 3-540-67931-6.
- Klaus Schmeh: Nicht zu knacken, von ungelösten Enigma-Codes zu den Briefen des Zodiac-Killers. Hanser, München 2012, ISBN 978-3-446-42923-9, Kap. 5.
- Tim Wambach: Kryptanalyse der doppelten Spaltentranspositionschiffre. Master-Abschlussarbeit, Fachhochschule Trier, 2011. PDF; 1,6 MB. Abgerufen: 26. April 2016.
Weblinks
- Verfahrensbeschreibung bei der TU Freiberg. Abgerufen: 23. März 2016
- Cryptographie par transposition – Transpositions rectangulaires Erläuterungen sowie Chiffrier- und Dechiffrierwerkzeug (französisch). Abgerufen: 7. Juni 2016.
Einzelnachweise
- 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.
- The Top 50 unsolved encrypted messages – 13. Double Column Transposition Reloaded (englisch), abgerufen am 18. Januar 2021.
- 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.