3.2 Substitution

Die Buchstaben bleiben wo sie sind, aber nicht was sie sind.
Was könnte hinter folgenden Zeichen stecken?

Bei diesem ersten Beispiel wurde die Nachricht durch ein so genanntes Substitutionsverfahren verschlüsselt. Der Schlüssel ist ein allgemein bekannter Code.

Im Gegensatz zur Transposition, bei welcher jeder Buchstabe seine Position ändert, behält bei der Substitution jeder Buchstabe seine Stelle bei. Was die Nachricht unleserlich macht, ist die Tatsache, dass die Buchstaben selbst ihre Gestalt ändern.
Eine weitere geheime Botschaft ist hier notiert. Welche Botschaft könnte hier versteckt sein.

Die Substitutionsverschlüsselung kann entweder monoalphabetisch (sich dem gleichen Alphabet bedienend) oder polyalphabetisch (für jeden zu verschlüsselnden Buchstaben ein neues Alphabet nutzen) sein.

Monoalphabetische Algorithmen

Allgemeine monoalphabetische Verschlüsselung

„Monoalphabetisch“ wird ein Verschlüsselungsalgorithmus genannt, wenn das Geheimalphabet im Verlaufe der Verschlüsselung gleich bleibt. So wird z.B. ein A immer in ein f verwandelt, ein P immer in ein z etc.
Beispiel:
Eine einfache monoalphabetische Verschlüsselung wäre z.B. durch folgende Tabelle gegeben:

So würde die Nachricht

"Ich kenne das Geheimnis"

anhand dieser Tabelle verschlüsselt zu

iby shiddh tfp nhyhildip

Bei dieser Verschlüsselung reicht es Eve (der Angreiferin bzw. Kryptoanalytikerin) nicht aus, zu wissen, was der Verschlüsselungsalgorithmus war, es muss auch der Schlüssel, die Zuordnungstabelle oder ein Stück Klartext vorhanden sein. Verallgemeinert kann diese Überlegung werden durch die Maxime von Kerckoff.

Der holländische Kryptograph (Jean Guillaume Hubert Victor François Alexandre) Auguste Kerckhoffs stellte 1883 eine bis heute unbestrittene Maxime (ein Prinzip) auf:
„Die Sicherheit eines Kryptosystems darf nicht von der Geheimhaltung des Algorithmus¹⁾ abhängen. Die Sicherheit gründet sich nur auf die Geheimhaltung des Schlüssels“
(A. Kerckhoffs, zitiert aus Simon Singh, 2000).
^{1)Algorithmus: eindeutige Handlungsvorschrift zur Lösung eines Problems}

Abbildung: A. Kerckoff, Quelle: Wikipedia]]

Der konkrete Schlüssel ist in unserem Fall durch die Verschlüsselungstabelle 1 von oben gegeben, durch welche die Verschlüsselung definiert ist. Dieser Schlüssel muss unbedingt geheim bleiben. Er dient zusammen mit dem Algorithmus dem Sender und dem Empfänger dazu, die Nachricht zu ver- bzw. entschlüsseln.

Die Maxime von Kerckhoffs ist recht einleuchtend, denn die verschiedenen Möglichkeiten, wie man eine Nachricht verschlüsseln kann, sind jeweils recht begrenzt und neue Dechiffrier-Chiffrier-Algorithmen sprachen und sprechen sich recht schnell herum. Ein gutes Verschlüsselungsverfahren verdient diese Auszeichnung nur dann, wenn man die Nachricht nicht entschlüsseln kann, auch wenn man weiss, nach welchem Prinzip sie verschlüsselt wurde.

ENIGMA und die Schlüssel

Die Sicherheit und Geheimhaltung eines Schlüssels war vor allem in Kriegen von grosser Bedeutung. Als Beispiel sei hier die Verschlüsselungsmaschine der Deutschen im zweiten Weltkrieg namens ENIGMA genannt. Diese hatte den Ruf, unknackbar zu sein.
Die ENIGMA war so etwas wie eine elektrische „Verschlüsselungsschreibmaschine“. Diese hatte ein sog. Schlüsselbuch für die genaue Einstellung der Maschine, um die Nachricht zu verschlüsseln. Dies war der erste Schlüssel. Danach wurde aber die Nachricht ein zweites Mal verschlüsselt, entweder mit einem „Tagesschlüssel“, welcher täglich gewechselt wurde, oder gar eines für jede Nachricht wechselnden Nachrichtenschlüssels.
Übringens: Neben viel Wissen in Mathematik, Kreativität und Spionen gelang das Knacken der chiffrierten Nachrichten der Deutschen den Briten aber doch, nicht zuletzt durch Alan Turing, dem eigentlichen „Erfinder“ des ersten Computers.

Abbildung: Enigma Quelle:

Für unser Beispiel scheint dies (zumindest nach unserem aktuellen Wissensstand) gewährleistet zu sein. Auch wenn man weiss, dass für jeden Buchstaben im Klartext einfach ein anderer Buchstabe des gleichen Alphabets anhand der Verschlüsselungstabelle zugenordet wurde, scheint es fast unmöglich, den Text zu entschlüsseln. Wer allerdings im Besitz des Schlüssels (der Verschlüsselungstabelle) ist, kann kinderleicht entschlüsseln.

Caesar Verschlüsselung
Ein Spezialfall der monoalphabetischen Verschlüsselung (für militärische Zwecke), wurde zum ersten Mal von Julius Caesar im Gallischen Krieg erwähnt. Caesar schrieb an Stelle des Klartextbuchstabens jeweils den Buchstaben, welcher im Alphabet drei Stellen weiter steht.

Beispiel:

"Wir sind Lernende des Kollegiums"

wird durch die Caesar Verschlüsselung (Verschiebung 3) chiffriert:

Zlu vlqg Ohuqhqgh ghv Nroohjlxpv

Natürlich kann man die Verschiebung des Geheimalphabetes beliebig verändern. Bei dieser Verschiebung des Alphabets bleibt jedoch die Reihenfolge der Buchstaben im Klartextalphabet und im Geheimalphabet gleich.

Es gibt noch viele andere monoalphabetische Verschlüsselungsverfahren, welche hier genannt werden könnten. Die Gemeinsamkeit dieser Verfahren ist jedoch, dass diese allesamt durch starke Kryptoanalysealgorithmen geknackt werden können.

Kryptoanalyse: Knacken monoalphabetischer Texte

Lange Zeit galt ein monoalphabetisch verschlüsselter Text als unknackbar, denn es war schlicht unmöglich, die riesige Anzahl von verschiedenen Schlüsseln durchzuprobieren, bis man zufällig auf den Richtigen stiess.
Doch schliesslich entdeckte man in Arabien im neunten Jahrhundert eine Möglichkeit, wie man derartige Texte entschlüsseln konnte, während es in Europa noch einige hundert Jahre dauern sollte.

bdgtsbbpzdgongyztbesnpevwkazgynprnysbetskvnskuzsnyuqnwpkgzcbnwpnptncvcnpasouqancfqocjmbwnunpgsprnycbwnunpsprfwnyvwkzprnplsprnpzctzbzwysnunyknunpwouqnwpkhnylwpnfnynccunwbnzcctnenwnycnrzbspcnypngonpzorwnpbczkqycbvnwcrnpzubdgwnrrnyuqnwpkebwnunpgsprnycbwnunpsprfwnyvwkrnylqnpwkwprnytsnecnfqybczprbczprnztbmyzdgfqpnwpnoetskvnskrzbrwnhntcesnywoonyfnyznprnycnuqnwpkgzccnrzbmyqrslcwqpbnprnzsekysprozpkntprnypzdgeyzknunynwcbfqyrynwazgynpzpknlsnprwkcwpbknbzocbcnttcnuqnwpksnunyczsbnpresnpegsprnycninomtzynrnbywnbnpetwnknybgnyrwnzwytwpnbvwngnpwpvhwbdgnpltnwpnynsprbmzybzonynozbdgwpnpowcvhnwbczccfwnycywnuhnylnpfqyrnynwpbckyqnbbcnmzbbzkwnyancrnyhntcgzccnbnwpnpaspkenypetskwopnspsprbndgvwkzubqtfwnycysprnwpazgybmzncnykwpkrzbnybcnninomtzyunwrnyrzoztwknpsbetskknbnttbdgzecmzpzowprnptwpwnprwnpbcowcrnyasnpkbcnpfzywzpcnbwnunpgsprnycbwnunpsprfwnyvwkbcywdgzdgcrwnsnunynwptznpknynbqunyrndlpnsncyzketzndgnpbqhwnbmzybzonyncywnuhnylnfnyesnkcsprmtzcvesnyongyztbbndgbgsprnycmzbbzkwnynuwncnclqppcnuqnwpkzunypsypqdgunwhnpwknpzwytwpnbmsplcnpwpvhwbdgnpbncvnprwnonwbcnpetskknbnttbdgzecnpzsernytzpkbcyndlnzsepwdgckzpvbqkyqbbnoqrnttnvstncvchsyrnrwnbwnunpgsprnycbwnunpsprfwnyvwkmyzlcwbdgpsypqdgztbeyzdgcfnybwqpmyqrsvwnyc

zwvmopchvpanurmvbqccvwmpromvschprhurspmovmutvprvqrvcgqvdsqvcvcurovmbdvqjfvrnuabvavqrvrhfwrzqcjfüevmovrgvdqypreqcfqrtwapwcbvspjfcvrvrspdfpevrcqjfoqvprqaphumvrzpchivovrvrrvrcsvmhvymvphwmovmapmqrvrzpwrpnumbvyruvgzhoqvnqcwpdqcqvmwrbevchqjfhnumpeowmjfoqvmvpdqchqcjfvrspccvmvzzvyhvsqvopzduccvrcvvprvaurvruovmwrhvmspccvmchmuvavroqbqhpdvcdvevrvqrbvfpwjfhswmovqchcjfdqjfhgfpvruavrpdopoqvpdhevyprrhvzpevdnuanvmdumvrvrcufraqhvqrvaaqrqawaproqcrvxwvedqjfvmcvrhqavrhpdqhpvhpwzbvmuddhsqmosvmovrcqjfpwjfymqhqcjfvbvqchvmzümovrprqaphqurczqdavmspvmavryuvrrvrzqroqrbrvaubvfhrqjfhrwmpdcvqrhmpvbdqjfchvmcurovmrsufdpwjfpdcevchvmgqlpmzqdaqroqvtsprtqbipvfmqbvbvcjfqjfhvovmoqbqhpdcjfaqvovvqroqvdvwhvnurgqlpmfpevrbprtvpmevqhbvdvqchvhovaqchrwmvqrcfqrtwtwzübvriwchyvvgcsqaaqrb

Lösung

Al-Kindi (800 n. Chr. Kufa, im heutigen Irak), der als „Philosoph der Araber“ bekannte Gelehrte, welcher über 290 Bücher über jegliche Wissenschaften veröffentlichte, war der Erste, welcher die Gedankengänge aufzeichnete, die zum Entschlüsseln eines monoalphabetisch chiffrierten Textes nötig sind.
Er stellte fest, dass im Arabischen die Buchstaben „a“ und „l“ sehr häufig vorkommen, während der Buchstabe „j“ zehn mal weniger häufig auftaucht. Ist ein Geheimtext genügend lang, so wird sich nach dem Gesetz der grossen Zahlen die Häufigkeit der einzelnen Buchstaben der allgemein in der jeweiligen Sprache vorhandenen Häufigkeit annähern. So werden bei einem arabischen Text die zwei Symbole, welche am häufigsten vorkommen, mit grösster Wahrscheinlichkeit für die Buchstaben „a“ und „l“ stehen.
Verfeinert man diese Überlegungen, so muss man nicht alle möglichen Schlüssel durchprobieren, sondern man kann mit Hilfe von logischen Schlussfolgerungen den Text knacken, sogar bei unbekannter Sprache kann diese Häufigkeitsanalyse wertvolle Hinweise liefern.
Dies soll anhand eines deutschen Textes exemplarisch durchgeführt werden. Dazu benötigt man eine Zusammenstellung der Häufigkeitsverteilung der einzelnen Buchstaben und der häufigsten Bigramme (Buchstabenpaare) der deutschen Sprache.

Häufigkeitsverteilung der Buchstaben in der deutschen Sprache

Tabelle Bigramme, häufigste Buchstabenpaare

Der Text aus der obigen Aufgabe umfasst 1187 Zeichen ohne die Leerschläge mitzuzählen. Die Buchstabenhäufigkeit ist wie folgt:

Anhand dieser zweiten Tabelle und dem Vergleich der beiden Tabellen - und mit dem Wissen, dass der Text in deutscher Sprache, nur mit Hilfe von Substiturionen chiffriert wurde, können Rückschlüsse auf die zusammengehörenden Buchstabenpaare der Substitution gemacht werden. Auch kann es helfen, die Häufigkeit der meistgenutzen zwei aufeinanderfolgenden Buchstaben aufzulisten. Das könnten dann die Bigramme sein. Durch einge Versuche und etwas Ausprobieren kann man den Geheimtext oft dechiffrieren.
Genau diese Gegebenheiten mussten auch zum Knacken von AUFGABE: Kryptoanalyse, wie die Chiffre geknackt? genutzt werden.

Grenzen dieses Kryptoanalyseverfahrens

Das von Al-Kindi beschriebene Kryptoanalyseverfahren war ein sehr mächtiges Werkzeug, welches die Entschlüsselung von monoalphabetischen Texten ermöglichte. Doch auch dieses Verfahren hat gewisse Grenzen und Schwachstellen.
Bespielsweise kann die Botschaft: „Ein Traktat über die amurösen Aventüren des Balthasar Matzbach am Rande des Panamakanals“ nur sehr schwer mit der Häufigkeitstabelle entschlüsselt werden. Zum einen, weil der Text ziemlich kurz ist und zum andern, weil er nicht die gleiche Häufigkeitsverteilung hat wie ein „durchschnittlicher“ Text.

Denn Grundlage dieses Verfahrens ist die Häufigkeitsverteilung (der jeweiligen) der Buchstaben in einem Text. Diese Häufigkeitsverteilung kann in einem Text jedoch ganz anders gegeben sein.
Sehr gute Beispiele für Texte, die nicht diesen Verteilungen folgen, sind sogenannte lipogrammatische Texte. In diesen Texten wird ein zuvor festgelegter Buchstabe vermieden. Ein gutes Beispiel dafür gibt uns der Roman „La Disparition“ („Anton Voyls Fortgang“) von Georges Perec (1969 erschienen, übersetzt ins Deutsche von Eugen Helmlé). In diesem 200-seitigen Roman wird kein einziges Mal der Buchstabe e verwendet. Hier die ersten Seiten des Romans.
Die verschlüsselte Variante dieses Textes wäre nicht ganz einfach zu knacken, da der normalerweise häufigste Buchstabe e nie vorkommt. Ähnliche Überlegungen und Finten können natürlich auch die „Verschlüssler“ angewendet haben. Beispielsweise:

• den Text absichtlich orthografisch falsch schreiben
• Füllworte wie „und“ etc., die sehr häufig vorkommen, weglassen
• Füllworte oder Füllzeichen ohne Bedeutung „einbauen“
• Codeworte oder Codezeichen im Text einbauen

Die beiden letzten genannten Punkte können als sog. Nomenklator zusammengefasst werden, besteht aus einem Verschlüsselungsalphabet, evtl. einigen Füllzeichen und einer Liste von Codewörtern.
Diese Technik wurde auch von Maria Stuart genutzt, um einen Komplott gegen die englische Königin zu schmieden. Genauere Informationen zur Nomenklatora von Maria Stuart finden Sie hier.

Das Schicksal der Maria Stuart zeigte in dramatischer Art und Weise, dass auch die zusätzlichen Sicherheitsmechanismen einen gewieften Kryptoanalytiker nicht an der Entschlüsselung eines Textes hindern konnten. Dies war der Grund, warum man nach einem neuen System der Verschlüsselung suchte, welches ein grösseres Mass an Sicherheit bieten würde.
Kryptografie und Kryptoanalyse - Teil 3