Simulation der Enigma

1. Simulationsstrategie

Warum die Enigma so berühmt ist, und auch, wie sie funktioniert, wurde schon unter „Allgemeines“ ausführlich erläutert. Nun soll die Enigma mit einem C++-Programm simuliert werden. Sie denken vielleicht, dass dies ganz einfach ist und haben (weil Sie gut C++ können) auch schon die folgende Strategie im Kopf: Sie deklarieren einfach das folgende Array:

char Walze[26];

In dem Array Walze steht eine Substitutionstabelle für jeden der 26 Buchstaben. Wenn also an der Position 0 das Zeichen E steht, dann wird A durch E ersetzt. Wenn an Position 1 im Array Walze das Zeichen Z steht, dann wird B durch Z ersetzt. Und wenn an der Position 3 das Zeichen F steht, dann wird C durch F ersetzt, und an der Position für das Zeichen C steht ein F. Rotiert nun die Walze um einen Buchstaben, dann ist der Offset im Positionsindex Pos einfach 1 und nicht mehr 0- es wird also nun B durch Z ersetzt.

Ich selbst dachte am Anfang auch auf die obige Weise, stellte aber schnell fest, dass eine so einfache Ersetzungsstrategie nicht funktioniert. Schon an dem einfachen obigen Beispiel kann man die Probleme mit der einfachen Substitution sehr gut erkennen. Wenn die Walze nicht rotiert, dann wird auf dem Hinweg A durch E ersetzt, man müsste also in Walze[4] das Zeichen E eintragen, damit E auch wieder zu A wird. Ebenso verhält es sich mit dem Zeichen B, das durch Z ersetzt wird. Wenn jetzt die Walze rotiert, dann wird A nicht mehr durch E ersetzt, sondern durch Z. Der Index für das Zeichen für Z liegt nun außerhalb des gültigen Bereichs (nämlich an Position 26). Nehmen wir nun die Position 26 Modulo 26, dann erhalten wir Position 0 im Array. Z würde also nun durch E ersetzt, genau wie zuvor das Zeichen A. Versuchen wir nun, die Verschlüsselung rückgängig zu machen und schauen im Array Walze an der Stelle nach, an der nun das Zeichen E steht: Dies ist die Position 5, weil der Positions-Offset nach der Rotation +1 ist. An dieser Position steht aber das Zeichen C, und wir erhalten die folgenden Ersetzungen:

Hinweg : EèZ

Rückweg: ZèC

Die oben angewendete Verschlüsselung ist also nicht symmetrisch, und deshalb führen sehr einfach aufgebaute Substitutionstabellen auch nicht zum Ziel. Nehmen wir nun eine Substitutionstabelle für den Hinweg und eine für den Rückweg. Ich kann Ihnen versichern (da ich dies ausgiebig getestet habe), dass auch diese Strategie nicht zum Ziel führt, vor allem dann, wenn mehrere rotierende Walzen und ein Reflektor im Spiel sind. Es gibt dennoch eine sehr einfache Lösung, die sogar unabhängig vom Offset des Positionsindexes im Array Walze ist, nämlich die relative Schreibweise. Die relative Schreibweise bildet die Verdrahtung der Walzen direkt auf Zahlen ab. Wenn z.B. das A mit dem E verdrahtet ist, dann wird die Ersetzung dadurch abgebildet, dass einfach die Zahl +4 in Walze[0] eingetragen wird. Dies bedeutet sozusagen „Pin A führt 4 Pins weiter“. Wenn nun das F mit C verdrahtet ist, dann steht an der Position 2 im Array Walze einfach dien Zahl -3, was bedeutet „F führt 3 Pin zurück“. Auch Hinweg und Rückweg sind auf diese Weise vollständig symmetrisch, denn für den Buchstaben E muss auf dem Rückweg nur die Zahl +4 subtrahiert werden. Auf diese Weise erhält man wieder den Buchstaben A.

2. Simulation der Enigma durch C++

Die Enigma soll nun durch ein C++-Programm simuliert werden, und die simulierte Enigma soll drei Walzen enthalten. Das gewählte Modell ist hier die Standard-Version der M3, die zwischen 1923 und 1940 von der Kriegsmarine eingesetzt wurde. Meine Simulation wurde mit der Enigma gegengeprüft, die in der DASA in Dortmund steht (dies ist ein Nachbau, die eine Software-Emulation benutzt) und mit einer Original-M3, die im Heinz-Nixdorf-Museum in Paderborn steht. Die Enigma M4, die im Arithmeum in Bonn steht, konnte ich noch nicht vollständig gegenprüfen, weil diese Maschine einen modifizierten Walzensatz verwendet, der nicht dem Standard entspricht. Allerdings stimmen meine Ergebnisse mit den Maschinen in der DASA und im Heinz-Nixdorf-Museum vollständig überein. An dieser Stelle möchte ich mich noch einmal ausdrücklich bei Prof. Dr. Roth bedanken, der die Simulations-Software in der DASA entwickelt und mir tiefe Einblicke in die Funktionsweise der Enigma gegeben hat. Ebenfalls sehr geholfen hat mir eine Vorführung im Arithmeum in Bonn, bei der mir einige Original-Enigmen live vorgeführt wurden.

2.1 Ein korrektes Walzen-Array erstellen

Nehmen wir nun die Walze I der M3, die wie folgt verdrahtet ist:

Definieren wir nun zwei Arrays mit Integer-Zahlen für Hin- und Rückweg:

int Hin[26];

int Rueck[26];

Das Array

char S[26];

soll nun die initiale Substitutionstabelle für die Walze in Form von ASCII-Zeichen enthalten, so, wie wir es gewohnt sind. Dieses Array soll mit der C++-Klasse Walze bei der Erstellung des entsprechenden Walzen-Objekts schon vorher angelegt worden sein. S muss nun durch die folgende Schleife in das Array Hin und das Array Rueck übertragen werden:

for (i=0; i<L; i++)

{

j=S[i]-i-'A'; k=-j; // Hin enthält nur relative Angaben, wie z.B. "1 vor" oder "4 zurück"

Hin[i]=j; Rueck[S[i]-'A']=k; // Rueck enthält nur relative Angaben, wie z.B. "4 vor" oder "1 zurück"

}

Der Trick ist hier wie zuvor schon erwähnt, nur relative Angaben für die einzelnen Pins zu benutzen, die auch negativ sein können. Wenn z.B. Hin[0]=4 ist, dann ist A mit E verbunden, denn der A-Pin ist 4 Pinne weiter verbunden. In diesem Fall ist Rueck[4]=-4. Durch die Verwendung relativer Angaben sind Hin und Rueck auch bei Änderung der Spaltennummerierung symmetrisch. Durch den Trick mit den relativen Angaben ist die Verschlüsselung selbst nur noch ein Nachschlagen von Spalten in den zuvor erstellen Arrays Hin und Rueck.

2.2 Die C++Klasse Walze definieren

Die C++-Klasse Walze muss natürlich noch mehr Attribute besitzen, als die Arrays Hin, Rueck und S. So sind auch der Umschaltpunkt, die aktuelle Rotor-Position und die Ringstellung wichtig, sowie die Anzahl Buchstaben L, die sich in den Arrays Hin und Rueck befinden. Die Variable L ist deshalb wichtig, weil die Klasse Walze einen Konstruktor besitzen soll, der eine neue Walze wie folgt anlegt:

Walze W=new Walze([Konfigurations-String]);

Der Konfigurations-String soll beim Neuanlegen eines Walzen-Objekts übergeben werden und durch Kommata getrennt die Substitutionstabelle in Buchstabenform und die Umschaltpunkte definieren. Ferner muss es Methoden geben, um die aktuelle Walzenkonfiguration abzufragen und ggf. die Ringstellung und die Rotorposition neu zu setzen. Ferner muss es Funktionen geben, um die Walze um eine Position zu rotieren und anschließend abzufragen, ob der Umschaltpunkt (kurz USP) schon erreicht ist. Die Klasse Walze muss also wie folgt definiert werden:

class Walze

{

private: // Attribute

int *Hin; // Verdrahtungsarray für den Hinweg

int *Rueck; // Verdrahtungsarray für den Rückweg

int *USP; // Array mit Umschaltpunkten

int Ring; // Ringstellung (negativer Offset des Alphabetrings gegenüber der Übertragskerbe)

int Rotor; // Rotorstellung (positive Offset der Substitutions-Tabelle)

int L; // Anzahl der Pins der Walze (fast immer 26)

public: // Methoden

Walze(char *S); // Konstruktor

~Walze(); // Destruktor

void SetRing(int V); // Setzt den Ring-Offset

void SetRotor(int V); // Setzt die Rotor-Position

void Rotiere(); // Rotiert die gesamte Walze um eine Position nach vorn

bool GetUSP(); // Gibt true zurück, wenn der Umschaltpunkt erreicht ist

void Anzeigen(); // Zeigt S an

char Hinweg(int C); // Hinweg-Verschlüsselung (der Eingangsbuchstabe wird intern in ein int gewandelt)

char Rueckweg(int C); // Rückweg-Verschlüsselung (der Eingangsbuchstabe wird intern in ein int gewandelt)

};

Mit diesen Informationen kann jetzt die Konstruktor-Funktion der Klasse Walze erstellt werden:

Walze::Walze(char *S)

{

int i=0,j,k,Pos;

L=0; while (S[L]!=',') { L++; } // Länge der Walze bestimmen, bis zu Definition der USP (durch Komma getrennt)

Hin=new int[L]; Rueck=new int[L]; // Die Arrays Hin und Rueck im Speicher anlegen

USP=new int[L]; Umschaltpunkt-Array kann maximal die Größe L haben

Ring=0; Rotor=0; // Ring und Rotor zunächst auf A setzen

// Initialisierungsschleife für Hin und Rueck

for (i=0; i<L; i++)

{

j=S[i]-i-'A'; k=-j; // Hin enthält nur relative Angaben, wie z.B. "1 vor" oder "4 zurück"

Hin[i]=j; Rueck[S[i]-'A']=k; // Rueck enthält nur relative Angaben, wie z.B. "4 vor" oder "1 zurück"

}

Pos=L; while (S[Pos]<'A') { Pos++; } // Nach dem 2. Teil von S suchen, der die USP enthält

i=0; while (S[Pos]!=0) { USP[i]=S[Pos]-'A'; i++; Pos++; } // USPs erzeugen

USP[i]=-1; // -1=Ende der Liste der USPs

}

Der Destruktor der Klasse Walze löscht die zuvor angelegten Arrays Hin, Rueck und USP:

~Walze()

{

delete(Hin);

delete(Rueck);

delete(USP);

}

2.3 Den Verschlüsselungsalgorithmus programmieren

Bevor die eigentliche Substitution ausgeführt werden kann, muss die Ring- und die Rotorstellung festgelegt werden. Die Ringstellung wird durch die Funktion SetRing() eingestellt:

void Walze::SetRing(int V)

{

Ring=V-'A';

}

Die Ringstellung ist eigentlich ein negativer Offset gegenüber dem Alphabetring, hier wird aber das Vorzeichen nicht mitgespeichert. Die Ringstellung wird durch den entsprechenden Buchstaben angegeben, der sich auf dem Alphabetring mit dem Buchstaben A deckt. Deshalb muss der eigentlich Offset V-[ASCII-Wert des A-Zeichens] betragen und der übergebene Buchstabe V muss intern in einen Integer-Wert konvertiert werden.

Die Rotorstellung wird analog eingestellt:

void Walze::SetRotor(int V)

{

Rotor=V-'A';

}

Die Rotorstellung ist ein positiver Offset, auch hier wird das Vorzechen weggelassen, da es dies auch nicht geben kann. Der Substitutionsalgorithmus setzt später die korrekten Vorzeichen bei den Ring- und Rotor-Offsets. Durch die relativen Angaben in den Arrays Hin und Rueck wird die Abbildung der Rotation der Walze sehr einfach:

void Walze::Rotiere()

{

Rotor=(Rotor+1)%L;

}

L enthält die Anzahl der Eingangs-Pins an der Walze, die zuvor durch den Konstruktor der Klasse Walze ermittelt wurde. Die Rotorposition bestimmt den positiven Offset des Buchstabens A gegenüber dem Sichtfenster, in dem der entsprechende Buchstabe direkt nach der Rotation erscheint. Die Rotorposition selbst kann nur Werte zwischen 0 und L-1 annehmen. Hierfür wird ein Modulo-Operator benutzt.

Kommen wir nun zu den Umschaltpunkten. Zurzeit unterstützt meine Simulation nur einen USP, denn ich denke darüber nach, die Walzen und USPs später mit doppelt verketteten Listen zu verwalten, was viel flexibler ist, als die aktuelle Version. Es lohnt sich deshalb wahrscheinlich nicht mehr, wenn die alte Version mehr als einen USP zu unterstützt. GetUSP() ermittelt, ob die aktuelle Rotorposition den Umschaltpunkt erreicht hat:

bool Walze::GetUSP()

{

int U=(USP[0]+Ring)%L; // Der Ring verstellt auch den Umschaltpunkt nach vorn

U-=6; if (U<0) { U+=L; } // Die Kerbe für die Umschaltung hat einen negativen Offset

if (Rotor==U) { return true; }

else { return false; }

}

Eine veränderte Ringstellung verändert auch den Umschaltpunkt, und zwar derart, dass die Ringstellung einem positiven Offset entspricht. So lernen dies zumindest Studenten in ihren Seminaren über alte Kryptographieverfahren. Leider ist diese einfache Aussage so nicht ganz korrekt, denn das Sichtfenster, in dem der Buchstabe für den aktuellen Eingangspin erscheint, liegt bei der Enigma oben. Der Hebel für die Walzen-Rotation liegt jedoch auf der Rückseite der Enigma, deshalb sind die Kerben, die den Übertrag bewirken, um 6 Positionen versetzt. Der Buchstabe, der nach dem Übertrag erscheint, wird jedoch in Bezug zu dem Sichtfenster angegeben, das auch die aktuelle Rotorposition anzeigt. GetUSP() muss diese Tatsachen beachten, weshalb dann auch in der zweiten Zeile von U noch einmal 6 abgezogen wird. Negative Werte für U, die hier durchaus auftreten können, können an dieser Stelle nicht mit einem einfachen Modulo-Operator korrigiert werden, da der Modulo-Operator keine negativen Zahlen unterstützt. Stattdessen muss ein if-Konstrukt benutzt werden, das immer dann zu U L addiert, wenn U negativ geworden ist.

Nun kann die eigentliche Substitution programmiert werden. Dies ist nun nicht mehr weiter schwierig. Die Methode Hinweg() leistet die Substitution für den Hinweg und ersetzt den übergebene Buchstaben C durch einen neuen Buchstaben und gibt diesen dann zurück:

char Walze::Hinweg(int C) // Durch die realtiven Sprünge zu den Zielpins ist diese Funktion relativ einfach zu implementieren

{

int i; C-='A'; // Dies ist die Pinnummer ohne Offset (so, als wären Rotor und der Ring auf A)

i=C-Ring; if (i<0) { i+=L; } // negativen Ring-Offset und evtl. negativen Offset auf positiven abbilden

i=(i+Rotor)%L; // Rotorposition addieren (für positiven Offset braucht man nur einen Modulo)

C=C+Hin[i]; if (C<0) { C+=L; }

C%=L; return C+'A';

}

Die erste Zeile ermittelt die aktuelle Pinnummer, auf die der Buchstabe C abgebildet wird, wenn Ring- und Rotorposition nicht verändert wurden. Dies entspricht der Rotorstellung A und der Ringstellung A. Die zweite Zeile subtrahiert nun die Ringstellung als negativen Offset. Hier kann es zu negativen Werten kommen, und da die Modulo-Funktion nicht für negative Zahlen der Art (C-Ring)%L definiert ist, muss an dieser Stelle eine if-Abfrage benutzt werden. Diese if-Abfrage muss für den positiven Offset in der 3. Zeile nicht benutzt werden, hier reicht i=(i+Rotor)%L aus. Die Substitution selbst ist nun nicht mehr so schwer umzusetzen, denn diese kann einfach im Array Hin nachgeschlagen werden- natürlich unter Beachtung der Tatsache, dass hier relative Werte benutzt werden.

Die Funktion Rueckweg() ist ähnlich aufgebaut, wie Hinweg():

char Walze::Rueckweg(int C)

{

int i; C-='A'; // Dies ist die Pinnummer ohne Offset (so, als wären Rotor und der Ring auf A)

i=C-Ring; if (i<0) { i+=L; } // negativen Ring-Offset und evtl. negativen Offset auf positiven abbilden

i=(i+Rotor)%L; // Rotorposition addieren (für positiven Offset braucht man nur einen Modulo)

C=C+Rueck[i]; if (C<0) { C+=L; }

C%=L; return C+'A';

}

Die Hauptklasse der Simulation ist die Klasse Enigma. Diese Klasse bildet zurzeit die M3 ab, mehr Walzen und eine eigene Eintrittswalze, die zusätzliche Substitutionen durchführt, sind nicht Bestandteil der M3. Allerdings kann ein beliebiges Steckerbrett simuliert werden, und die Walzen können in einer beliebigen Reihenfolge eingesetzt werden. Die Klasse Enigma enthält die folgenden Attribute und Methoden:

class Enigma

{

void StringTausch(char *S, int A, int B) // Hilfsfunktion für das Steckerbrett

{

int i=S[A],j=S[B];

S[A]=j; S[B]=i;

}

int WalzenZaehler;

bool DBG;

char STB[100];

// Walze *ETW TODO:Testen verschiedener Eintrittswalzen

Walze *W[4]; // UKW=Walze 4

public:

Enigma(bool DebugOn); // Aufruf mit true dient zu Debugging- und Test-Zwecken

void WalzeEinsetzen(char *S);

void About(); // Info-Text zum Enigma-Programm

void RotiereWalzen(); // Dies rotiert alle Walzen

void SetSteckbrett(char *S);

void SetRinge(char *S);

void SetRotoren(char *S);

char EncC(char C); // EncC verschlüsselt ein einzelnes Zeichen, ohne die Rotorstellung zu ändern

};

Zurzeit ist die 4. Walze die Umkehrwalze, die den Strom zurückleitet. Es können also 3 Walzen eingesetzt werden. Der Konstruktor erzeugt zunächst eine leere Enigma mit einem ungesteckerten Steckerbrett:

Enigma::Enigma(bool DebugOn) // Erstellen einer Enigma mit DebugOn gibt jeden Verschlüsselungsschritt in der Konsole aus

{

// Zunächst wird eine ungesteckerte, leere Standard-M3 erstellt

int i;

char C;

DBG=DebugOn; WalzenZaehler=4; // Stack wächst nach unten, linke Walze (UKW) wird zuerst eingesetzt

strcpy(STB,"ABCDEFGHIJKLMNOPQRSTUVWXYZ"); // Leeres Steckbrett erzeugen

}

Der Parameter DebugOn=true gibt für jedes verschlüsselte Zeichen einen Teststring für den Hin- und Rückweg in der Konsole aus. DebugOn=false schaltet diese Funktion aus. WalzenZaehler ist zurzeit immer 4, es können also 3 Walzen und eine Umkehrwalze eingesetzt werden, die nicht rotiert. Wenn eine Walze eingesetzt wird, wird diese auf eine Art Stack gelegt, sodass die linke Walze zuerst eingesetzt wird:

void Enigma::WalzeEinsetzen(char *S)

{

WalzenZaehler--; W[WalzenZaehler]=new Walze(S); // TOS zeigt stets auf die Walze am weitesten rechts

}

Der TOS (top of stack) zeigt stets auf die Walze, die zuletzt eingesetzt wurde, und zwar von rechts aus gesehen. Dies entspricht auch der Standard-Schreibweise für den Spruchschlüssel (linke Walze zuerst, rechte Walze zuletzt). Verschlüsseln wir nun den Text aus dem Einführungsbeispiel im Abschnitt „Allgemeines“. Zuerst wird der Tagesschlüssel eingestellt, indem die Ring-Positionen festgelegt werden. Dies leistet die folgende Methode der Klasse Enigma:

void Enigma::SetRinge(char *S)

{

W[2]->SetRing(S[0]);

W[1]->SetRing(S[1]);

W[0]->SetRing(S[2]);

}

Bei der Ring-Einstellung wird die linke Walze zuerst angegeben, bei der M3 mit 3 Walzen steht die linke Walze in W[2], die rechte Walze in W[0]. Das Walzen-Array wird also in der Variable W abgelegt. Die Ringpositionen werden durch einen String angegeben, z.B. durch die Zeichenkette „RTZ“. Dies vereinfacht die Konfiguration der Enigma über die Linux-Konsole. Nach der Eingabe der Ringstellungen muss noch der Spruchschlüssel eingestellt werden. Dies leistet die folgende Methode:

void Enigma::SetRotoren(char *S) // TODO:Verkettete Walzenliste, dies ist flexibler als eine starre Verdrahtung

{

W[2]->SetRotor(S[0]);

W[1]->SetRotor(S[1]);

W[0]->SetRotor(S[2]);

}

Bei der Grundeinstellung für den Spruchschlüssel wird die linke Walze zuerst angegeben. Auch SetRotoren() nimmt als Parameter eine Zeichenkette entgegen. Auch hier vereinfacht dies die Konfiguration der Enigma über die Linux-Konsole. Das Steckerbrett wird nun durch die folgende Methode konfiguriert:

void Enigma::SetSteckbrett(char *S) // Buchstabenpaare mit zu steckernden Buchstaben

{

int i=0;

while (S[i]!=0)

{

StringTausch(STB,S[i]-'A',S[i+1]-'A');

i+=2;

while (S[i]==' ') { i++; }

}

Der Parameter S enthält jeweils Buchstabenpaare, die anschließend im Array STB miteinander vertauscht werden. Die Standardbelegung von STB ist die Buchstabenfolge

ABCDEFGHIJKLMNOPQRSTUVWXYZ

Einen Buchstaben mit einem anderen Buchstaben zu steckern bedeutet also, den Buchstaben in STB mit einem anderen zu vertauschen. Dadurch wird das Steckerbrett durch eine zusätzliche einfache Substitution abgebildet.

Nun kommt eine Sache, die viele Informatik-Studenten schon in die Verzweiflung getrieben hat, nämlich die Frage, wann die rechte Walze eigentlich rotiert. Die Antwort scheint zunächst ganz einfach zu sein: Erst wird der gerade gedrückte Buchstabe verschlüsselt, und danach rotiert die rechte Walze, die unter Umständen andere Walzen mitnimmt. Diese Annahme führt leider zu falschen Ergebnissen, denn die rechte Walze rotiert, sobald eine Buchstabentaste gedrückt wird um genau eine Position nach vorn. Die Rotation selbst leistet dann die folgende einfache Methode der Klasse Enigma:

void Enigma::RotiereWalzen()

{

W[0]->Rotiere();

if (W[0]->GetUSP()==true)

{

W[1]->Rotiere();

if (W[1]->GetUSP()==true)

{

W[2]->Rotiere();

}

Die Rotation der einzelnen Walzen ist also in der Tat mit einem einfachen verschachtelten if-Konstrukt möglich: Erst rotiert W[0], und wenn der Umschaltpunkt erreicht ist, rotiert auch W[1], was eine Abfrage auch von W[2] nach sich zieht. W[3] rotiert nicht, da die Umkehrwalze statisch ist. Im Endeffekt ist die Simulation der Enigma selbst auch simpel, nämlich mit der folgenden Methode:

char Enigma::EncC(char C) // Einzelnes Zeichen verschlüsseln (die Rotoreinstellungen bleiben unverändert)

{