Permutationschiffren

3.2. Permutationschiffren#

Im Gegensatz zu den in Substitutionschiffren diskutierten Substitutionschiffren werden bei Permutationschiffren (oft auch Transpositionschiffren genannt) keine Zeichen eines Klartextalphabets durch Zeichen eines Geheimtextalphabets ersetzt. Die Idee ist es die Reihenfolge der vorkommenden Zeichen so zu verändern, dass der Inhalt des Klartexts nicht mehr lesbar ist. Dieses Prinzip wird auch bei Anagrammen verwendet.

Es gibt vielfältige Möglichkeiten für Permutationschiffren. Wir wollen uns in diesem Abschnitt mit zwei populären Verfahren beschäftigen.

3.2.1. TRANSMAT-Verschlüsselung#

Wir betrachten eine Permutationschiffre, die einen vorgegebenen Klartext zunächst in Blöcke einer geheimen Größe aufteilt und innerhalb dieser Blöcke die Reihenfolge der einzelnen Zeichen um eine feste Größe verschiebt. Da diese Translation sich mit Hilfe von Matrizen leicht umsetzen lässt, nennen wir dieses Kryptosystem TRANSMAT-Chiffrierung. Das Prinzip dieser Verschlüsselung wird im Folgenden genauer beschrieben.

Algorithmus 3.3 (TRANSMAT-Verschlüsselung)

  1. Wir wählen als zu Grunde liegendes Alphabet \(\Sigma\) die lateinischen Großbuchstaben (ohne deutsche Umlaute) A,…,Z und nutzen als Klartext- und Chiffretextraum \(\mathcal{P} = \mathcal{C} = \Sigma^*\), d.h. die Menge aller Wörter über dem Alphabet \(\Sigma\).

  2. Schlüsselraum: Der Schlüssel \(k = (m,n) \in \mathcal{K}\) besteht aus einem Paar von zwei natürlichen Zahlen \(m,n \in \N\). Die Zahl \(m \in \N\) gibt die Anzahl der Zeilen und die Zahl \(n \in \N\) die Anzahl der Spalten für die verwendeten Matrizen an.

  3. Verschlüsselung:

    1. Der Klartext wird in Blöcke der Länge \(L = m\cdot n\) aufgeteilt. Ist die Zeichenanzahl des Klartexts nicht durch \(L \in \N\) teilbar, werden am Schluss willkürlich Buchstaben angehängt bis die Anzahl der Zeichen des resultierenden veränderten Klartexts durch \(L\) teilbar ist.

    2. Je \(L\) Zeichen eines Blocks des Ausgangstexts werden zeilenweise in eine \(m\times n\)-Matrix geschrieben. Der Chiffretext entsteht, indem die resultierende Matrix spaltenweise ausgegeben wird.

  4. Entschlüsselung: Die Entschlüsselung funktioniert umgekehrt zur Verschlüsselung dieser Chiffre. Das heißt man muss jeden Block aus \(L = m\cdot n\) Zeichen des Chiffretexts spaltenweise in eine \(m\times n\)-Matrix schreiben und anschließend zeilenweise auslesen. Alternativ kann man den Chiffretext auch zeilenweise in eine \(n\times m\)-Matrix schreiben und den Klartext durch spaltenweises Auslesen erhalten.

Wir wollen die Funktionsweise des Kryptosystems in Algorithmus 3.3 an einem Beispiel illustrieren.

Beispiel 3.10 (TRANSMAT-Verschlüsselung)

Wir möchten die TRANSMAT-Verschlüsselung zur Chiffrierung eines gegebenen Klartexts verwenden. Wir wählen zunächst als geheimen Schlüssel \(k = (m,n) := (3,4)\). Nun wird der Klartext DEPARTMENT MATHEMATIK zeilenweise in \(3\times 4\)-Matrizen geschrieben und am Schluss um 4 willkürliche Zeichen (WXYZ) ergänzt, damit der ergänzte Klartext durch die gewählte Blocklänge \(3 \cdot 4 = 12 = L\) teilbar ist:

DEPA  THEM
RTME  ATIK
NTMA  WXYZ

Der Chiffretext ergibt sich dann durch spaltenweises Auslesen der entstandenen Matrizen als

DRNETTPMMAEATAWHTXEIYMKZ.

Abschließend wollen wir uns noch mit der Sicherheit dieses Kryptosystems beschäftigen.

Bemerkung 3.4 (Kryptoanalyse für TRANSMAT-Verschlüsselung)

  1. Die TRANSMAT-Verschlüsselung ist eine symmetrische Permutationschiffre mit einer frei-wählbaren Blockgröße \(L = m \cdot n \in \N\), die vom geheimen Schlüssel \(k = (m,n) \in \mathcal{K}\) abhängt.

  2. Es ist klar, dass jeder einzelne Buchstabe im Klartext genauso oft wie im Chiffretext vorkommt, da nur deren Reihenfolge vertauscht wird. Klartext und Chiffretext haben also die gleiche Häufigkeitsverteilung, so dass eine Häufigkeitsanalyse für Monogramme, wie in Häufigkeitsanalyse beschrieben, keinen Sinn macht.

  3. Die TRANSMAT-Verschlüsselung ist besonders bei kurzen Chiffretexten unsicher, da hier nur wenige Kombinationen für den geheimen Schlüssel \(k = (m,n)\) ausprobiert werden müssen. Für sehr kurze Chiffretexte kann man sogar den Klartext erraten (ähnlich wie bei Anagrammen). Daher ist es häufig sinnvoll den Klartext mit einer genügend großen Anzahl an zusätzlichen Zeichen zu verlängern (im Englischen: padding ), um die Kryptoanalyse zu erschweren.

  4. Häufig reicht es durch Ausprobieren eine der beiden Schlüsselzahlen \(m,n\in\N\) zu erraten, denn bei korrekter Zeilenanzahl \(m \in \N\) lassen sich bereits Teile des Klartexts ablesen. Anschließend muss man nur noch mögliche Kombinationen für die Anzahl der Spalten \(n \in \N\) und die unbekannte Blockgröße \(L = m\cdot n\) ableiten und kann durch Ausprobieren den Klartext erhalten.

Inhalt