Substitutionsverfahren


1. Atbash

Im letzten Kapitel wurde bei den Transpositionsverfahren die Reihenfolge der Buchstaben verändert. Ein weiteres Verschlüsselungsverfahren ist das Substitutionsverfahren, bei dem ein Buchstabe durch einen anderen Buchstaben ersetzt wird.

Von hebräische Gelehrten wurde in der Zeit ca. 500 v. Chr. unter anderem die Geheimschrift Atbash verwendet. Bei dieser wird ein „umgedrehtes“ Alphabet verwendet. Es wurde das erste Zeichen des hebräischen Alphabets (Aleph) mit dem letzten Zeichen (Taw) vertauscht, das zweite (Beth) mit dem vorletzten (Sin), usw..


2. Caesar-Verfahren

2.1 Caesar-Verschlüsselung

Gaius Julius Caesar ist sicherlich einer der bekanntesten römischen Kaiser. Er lebte in der Zeit von 100-44 vor Christus und soll im gallischen Krieg eine Verschlüsselung benutzt haben, die heute nach ihm benannt wird. Der Imperator ersetzte jeden Buchstaben in seiner Botschaft durch den drei weiter hinten stehenden Buchstaben. Damit ist auch das Caesar–Verfahren ein Substitutionsalgorithmus, denn jeder Buchstabe wird durch immer den gleichen Geheimtextbuchstaben ersetzt.

Bilden Sie nun für alle folgenden Quests im Bereich Kryptologie ein Team mit mindestens 2 und maximal 3 Mitgliedern.

Quest 1:

Verschlüsseln Sie per Hand folgenden Text mit dem originalen Caesar-CODE, also mit der Verschiebung 3:

FERIEN SIND NOCH BESSER ALS SCHULE

Entschlüsseln Sie folgenden Chiffriertext mit der Verschiebung 3:

GDV IDFK LQIRUPDWLN LVW HLQ ZLFKWLJHV IDFK LQ GHU VFKXOH

Lassen Sie die Lösungstexte in der vereinbarten Weise Ihrer Lehrkraft zukommen.

(5 XP)

In der letzten Aufgabe war der verschlüsselte Text leicht zu entschlüsseln, da der Schlüsselcode bekannt ist. Schwieriger wird es, wenn der Text und die Verschiebung der Buchstaben im Alphabet nicht bekannt sind.

Es ist jetzt an der Zeit die doch etwas mühsame Verschlüsselung nach Caesar in das 21. Jahrhundert zu transportieren und diese dem Computer zu überlassen.

Exkurs: Fachwissen Arrays

Möchte man unterschiedlich viele Werte (z.B. alle Buchstaben des Alphabets) in einer Variablen speichern, so nutzt man hierfür Arrays (ähnlich einer Tabelle). Jeder dieser Werte steht dabei an einer bestimmten Position im Array – dem Index (also eine Ortsangabe). Gezählt wird für ein Array mit n Werten die Position von Index 0 bis Index n-1. Der erste Wert in einem Array hat also den Index 0. Mit folgendem Befehlt wird ein Array angelegt:

   var array_name = [item1, item2, ...];

item1 befindet sich hier an Position 0 und kann mithilfe des Befehls

   array_name[0]; 

angesprochen werden.
Beispiel:

var cars = ['Saab', 'Volvo‘, 'BMW'];
cars[0];  // liefert den Wert Saab zurück.

Über die Indexnummer können einzelne Elemente auch geändert werden.

Beispiel:

 var fruits = ['Banana', 'Orange', 'Apple', 'Mango'];
 fruits[0] = 'Kiwi';        // Ändert den ersten Wert 'Banana' in 'Kiwi' um

Da über den Index einzelne Werte des Arrays direkt angesprochen werden können, ist es nützlich die Anzahl der im Array gespeicherten Werte bestimmen zu können. Das funktioniert mithilfe des Befehls:

  array_name.lenght;

Beispiel:

var cars = ['Saab', 'Volvo‘, 'BMW'];
cars.length;  // liefert 3 zurück.

Mithilfe einer for-Schleife lässt sich nun bequem das ganze Array durchlaufen und zum Beispiel die Reihenfolge der Werte des ursprünglichen Arrays für ein zweites umdrehen.

Beispiel:

 var vorwaerts=['a', 'b', 'c', 'd'];  //d steht an Index 3, die Länge des Arrays ist 4

 var ruckwaerts=[]; //ein zweites Array, das noch leer ist

 for (i=0; i<vorwaerts.length; i++) {
 ruckwaerts[i]=vorwaerts[vorwaerts.length-1-i]; }

Die Methode array_name.reverse() dreht die Reihenfolge desselben Arrays um. Beispiel:

var vorwaerts=['a', 'b', 'c', 'd'];
vorwaerts.reverse();    //vorwaerts enthält nun die Einträge: d,c,b,a

Weitere Methoden, um ein Array anzupassen:

array_name.push(item) fügt einen Wert am Ende ein und gibt die neue Länge des Arrays zurück
array_name.pop() entfernt das letzte Element und gibt dessen Wert zurück
array_name.shift() entfernt das erste Element, passt alle restlichen Indizes an und gibt den Wert des ursprünglichen ersten Elements zurück
array_name.unshift(item) fügt einen Wert am Anfang ein und gibt die neue Länge des Arrays zurück
array_name.splice() ermöglicht es, Werte an beliebige Stellen einzufügen (Achtung: das ist etwas komplizierter!)

in Anlehnung an: w3schools-array-methods

Ende des Exkurses - zurück zur Verschlüsselung nach Caesar mithilfe des Computers

Schritt 1: Alphabet und Cäsar-Alphabet

Das Alphabet wird in einem Datenfeld (Array) gespeichert, so dass wir über den Index auf die Buchstaben zugreifen können:

  var alphabetArray = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];

Dann speichern wir das um 3 Buchstaben verschobene Cäsar-Alphabet in einem weiteren Array:

  var caesarArray = ['D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'A', 'B', 'C'];

Schritt 2: Cäsarverschlüsselung

Im zweiten Schritt müssen die Buchstaben des Original-Alphabets mit den Buchstaben des verschobenen Alphabets ersetzt werden. Das leistet folgender Algorithmus:

  function textVerschluesseln() {
      caesartext = '';
      for (var i = 0; i < eingabe.Eingabetext.length; i++) {
        var buchstabe = eingabe.Eingabetext.substring(i, i+1);
        for (var j = 0; j < alphabetArray.length; j++) {
          if (buchstabe == alphabetArray[j]) {
            caesartext = caesartext + caesarArray[j];
          }
        }
        if (buchstabe == ' ') { caesartext = caesartext + ' '; }
      }
    settings.setValue("Caesartext", caesartext);
  }

Dieser Algorithmus ist dem Code aus dem Modul Text zu Binärcode im Kapitel Codierung sehr ähnlich. Diskutieren Sie mit Ihren Teammitgliedern, bis Sie jede Zeile verstanden haben

Das Programm zur Cäsarverschlüsselung sieht dann wie folgt aus:

Quest 2:

Erweitern Sie das Programm so, dass der Text mit der Verschiebung 3 sowohl mit Kleinbuchstaben als auch mit Großbuchstaben verschlüsselt wird.

Lassen Sie den Programmcode in der vereinbarten Weise ihrer Lehrkraft zukommen.

(Wert 5 XP)


Bonusquest:

Erstellen Sie ein Programm, bei dem man die Verschiebung als Zahl eingeben kann, das verschobene Alphabet automatisch erzeugt wird und der Text entsprechend verschlüsselt wird.

Lassen Sie den Programmcode in der vereinbarten Weise ihrer Lehrkraft zukommen.

(Wert 15 XP)


2.2 Caesar-Entschlüsselung

Nun wechseln wir die Position. Nun sind Sie der neugierige Mitschüler, der die verschlüsselten Texte heimlich mitlesen möchte. Also müssen Sie nun ein Programm schreiben, dass einen Text ohne Kenntnis des Schlüssels wieder in einen Klartext umwandelt. Sie vermuten aber richtigerweise, dass es sich um einen Caesar-Code handelt.

Quest 3:

Folgenden Chiffriertext soll entschlüsselt werden?

DLZALYZALKL SPLNA PT SHUKRYLPZ HTTLYSHUK PU KLY UHLOL KLY UVYKZLLRBLZAL

Wie viele Möglichkeiten gibt es, den Code zu entschlüsseln? Versuchen Sie die Verschiebung herauszufinden und entschlüsseln Sie den Text.

Lassen Sie den entschlüsselten Text zusammen mit der Information um wie viele Stellen das Alphabet verschoben wurde in der vereinbarten Weise Ihrer Lehrkraft zukommen.

(5 XP)

Das Verfahren, durch Ausprobieren einen verschlüsselten Text zu entschlüsseln, nennt man Brute–Force–Methode. Vielleicht geht es auch eleganter.

Informieren Sie sich auf der Seite http://kryptografie.de/ zum Thema Häufigkeitsverteilung. Benutzen Sie Cryptool (Analyse – Werkzeuge der Analyse – Histogramm) um die Häufigkeitsverteilung im Text zu bestimmen und entschlüsseln Sie damit per Hand den oben genannten Text.

Quest 4:

Folgendes Programm soll analysieren, wie oft der Buchstabe "e" im Eingabetext vorkommt.

Ergänzen Sie analyse().

(5 XP)

Quest 5:

Versuchen Sie mit diesem Verfahren den Satz LQIRUPDWLN LVW HLQ ZLFKWLJHV IDFK LQ GHU VFKXOH zu entschlüsseln.

Wo liegt hier das Problem? Erläutern Sie kurz!

Nun könnte der Text aber auch in englischer Sprache verfasst sein. Wie ließe sich das überprüfen?

Dokumentieren Sie Ihre Überlegungen und lassen Ihre Dokumentation in der vereinbarten Weise Ihrer Lehrkraft zukommen.

(5 XP)


3. Chiffrierung mit einer eigenen Zuordnungstabelle

Eine viele bessere Methode ist die Verschlüsselung mit einer eigenen Zuordnungstabelle. Dabei wird für jeden Buchstaben im Text in einer eigenen Tabelle angegeben, welcher Buchstabe im Chiffretext zu verwenden ist.

Beispiel:

ABCDEFGHIJKLMNOPQRSTUVWXYZ_

EKATZLGMSCHN_BFJOPQRUWVXYID

Damit wird eine Nachricht wie folgt verschlüsselt:

Klartext: DIES IST EIN GEHEIMTEXT

Chiffretext: TSZQDSQRDZSBDGZMZS RZXR

Diese Verschlüsselung ist viel schwieriger ohne die zugehörige Tabelle zu entschlüsseln, als ein Verschlüsselung mit dem Caesar–Code.

Wie könnte man diesen Code trotzdem knacken?


4. Chiffrierung mit Schlüsselwort und Schlüsselbuchstabe

Eine weitere einfache, aber leicht umsetzbare Form der Verschlüsselung ist die Chiffrierung mit einem Schlüsselwort und einem Schlüsselbuchstaben.

Beispiel:

Schlüsselwort: GEHEIMSCHRIFT
Schlüsselbuchstabe: E

Zur Verschlüsselung werden alle doppelt auftretenden Buchstaben im Schlüsselwort gestrichen und dann unter die Position des Schlüsselbuchstabens unter das Alphabet geschrieben. Die restlichen Buchstaben werden aufgefüllt.

Also:

Tabelle

Ein Vorteil des Verfahrens ist, dass das Schlüsselwort und der Schlüsselbuchstabe leicht zum Beispiel mit Hilfe des gleichen Buches täglich ausgetauscht werden können.

Da jedoch in einem Text meistens einige Buchstaben häufiger auftreten als andere (z. B. kommt E sicher öfter vor als X), könnte ein Kryptoanalytiker beim Entschlüsseln der Botschaft auch hier einen Ansatz finden, indem er den häufigsten Buchstaben im Chiffretext findet und diesen z. B. durch E ersetzt. Auch wenn dies eventuell ein falscher Ansatz ist, ist dieses Vorgehen sicher besser, als alle 26 Buchstaben nacheinander auszuprobieren. Die Chancen zum Dechiffrieren des Textes erhöhen sich jedoch für den Angreifer, wenn auch Kombinationen von zwei Buchstaben (so genannte Digramme) berücksichtigt werden. Manche Digramme (wie z.B. BY) treten in einem deutschen Text niemals auf, während andere (wie z. B. ST oder DE) sehr oft vorkommen. Durch Untersuchung der Häufigkeiten von Buchstaben und Buchstabenkombinationen kann ein Angreifer einen Text leicht entschlüsseln.


5. Geschichte und Ausblick

Der französische Diplomat Blaise de Vigenere (1523-1596) verbesserte die Caesar-Verschlüsselung: das Alphabet wird nicht immer um die gleiche Anzahl von Stellen verschoben, sondern die Anzahl der Stellen wird variiert.

Beispiel:

Schlüssel: (2,1,3) Text: KLEEBLATT Weiterzählen um: 213 213 213 Geheimtext: MMH GCO CRT

Dieses ist das Prinzip des Vigenere–Codes. Hierbei handelt sich nicht mehr um ein monoalphabetische Verfahren, sondern um ein polyalphabetisches Verfahren, das offensichtlich sehr viel schwieriger zu knacken ist und sehr lange Zeit als unknackbar galt.

Ein ähnliches Verfahren verwandten die Deutschen im 2. Weltkrieg in Form der bekannten ENIGMA. Bei ihr werden Zeichengruppen eines Textes vertauscht und durch andere Zeichengruppen ersetzt. Der englische Geheimdienst konnte diesen Code durch Einsatz vieler Spezialisten knacken und damit den Ausgang des Krieges erheblich beeinflussen. Die Kryptologie als eigenständige Wissenschaft entwickelte sich nach dem 2. Weltkrieg, in dem sich das „Knacken“ von Geheimtexten eine wesentliche Bedeutung erfuhr, erheblich weiter.

Quest 6:

Informieren Sie sich genauer anhand der etwas angestaubten und leider in sehr schlechter Qualität vorliegenden Dokumentation "Krieg der Buchstaben", die 1995 zum 50. Jahrestag des Endes des zweiten Weltkriegs ausgestrahlt wurde, über die Entwicklung der Kryptologie und die Bedeutung ihres Einsatzes für den Kriegsverlauf im 1. und 2. Weltkrieg. Die etwa 45 Minuten dauernde Dokumentation liegt in 5 Teilen vor.

Teil 1 - Teil 2 - Teil 3 - Teil 4 - Teil 5

Verfassen Sie einen kurzen Text über die Bedeutung der Kryptologie für den Kriegsverlaufs im 1. und 2. Weltkrieg. Lassen Sie diesen Text in der vereinbarten Weise ihrer Lehrkraft zukommen.

(5 XP)