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.

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.

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.length;

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

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

---

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.

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.

---

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.

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.

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:

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.

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.

---