Monoalphabetische Substitution

Grundidee und Einordnung

Eine monoalphabetische Substitution ist ein klassisches Verfahren der Kryptographie. Dabei wird zur Verschlüsselung des Klartextes in einen Geheimtext genau ein festes Schlüsselalphabet verwendet. Dieses Schlüsselalphabet heißt auch Geheimalphabet. Buchstaben, Zeichen oder auch Buchstaben- und Zeichengruppen des Klartextes werden nach diesem einen Alphabet durch andere Buchstaben, Zeichen oder Gruppen ersetzt.

Der wichtigste Unterschied liegt zur polyalphabetischen Substitution: Dort werden mehrere oder viele verschiedene Alphabete verwendet. Beispiele für monoalphabetische Verfahren sind die Caesar-Verschlüsselung und das Playfair-Verfahren. Beispiele für polyalphabetische Verfahren sind die Vigenère-Verschlüsselung und die Schlüsselmaschine Enigma.

Einfache Substitution und Caesar-Verfahren

Bei der einfachen monoalphabetischen Substitution wird jeder einzelne Buchstabe des Klartextalphabets durch genau ein Zeichen des Geheimalphabets ersetzt. Genauer heißt diese Methode „monographische monoalphabetische monopartite Substitution“, meist aber einfach „einfache monoalphabetische Substitution“. Der Geheimtext wird auch Chiffrat genannt und zur Unterscheidung vom Klartext häufig in Großbuchstaben geschrieben.

Ein Beispiel: Wird dem Klartextalphabet a bis z das Geheimalphabet „U F L P W D R A S J M C O N Q Y B V T E X H Z K G I“ zugeordnet, dann wird aus „wikipedia ist informativ“ der Geheimtext „ZSMSYWPSU STE SNDQVOUESH“. Zum Entschlüsseln ersetzt man die Buchstaben des Geheimalphabets wieder durch die zugehörigen Buchstaben des Klartextalphabets.

Die Caesar-Verschlüsselung ist ein Sonderfall der einfachen monoalphabetischen Substitution. Dabei entsteht das Geheimtextalphabet durch zyklisches Verschieben des Standardalphabets. Die Anzahl der verschobenen Plätze ist der Schlüssel. Caesar benutzte dieses Verfahren zumeist mit dem Schlüssel „C“, also einer Verschiebung um drei Buchstaben. Beim Alphabet „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“ wird „wikipedia“ zu „ZLNLSHGLD“.

Erzeugung des Geheimalphabets

Es gibt verschiedene Möglichkeiten, ein Geheimalphabet zu bilden. Sehr einfache und besonders unsichere Varianten sind die Caesar-Verschiebung und Atbasch. Bei der Caesar-Verschiebung sind nur 25 verschiedene Schlüssel möglich. Bei Atbasch wird das Alphabet umgekehrt; es gibt nur einen festen Schlüssel, zum Beispiel „ZYXWVUTSRQPONMLKJIHGFEDCBA“ für das Klartextalphabet „abcdefghijklmnopqrstuvwxyz“.

Üblich ist auch die Erzeugung eines verwürfelten Geheimalphabets mithilfe eines Kennworts. Beide Kommunikationspartner kennen dieses Kennwort und bilden daraus auf gleiche Weise das Geheimalphabet. Beim Kennwort „Regenschirm“ entfernt man zuerst mehrfach vorkommende Buchstaben. Daraus wird „REGNSCHIM“. Diese Buchstaben bilden den Anfang des Geheimalphabets. Danach werden die fehlenden Buchstaben ergänzt. Alphabetisch aufgefüllt ergibt sich „REGNSCHIMABDFJKLOPQTUVWXYZ“.

Als Verbesserung können die restlichen Buchstaben in umgekehrt alphabetischer Reihenfolge ergänzt werden, sodass das Alphabet nicht oft mit „...XYZ“ endet. Dann entsteht „REGNSCHIMZYXWVUTQPOLKJFDBA“. Eine weitere Möglichkeit ist die progressive Auffüllung ab dem letzten Buchstaben des Kennworts, zum Beispiel „REGNSCHIMOPQTUVWXYZABDFJKL“. Ein völlig zufällig verwürfeltes Geheimalphabet ist ebenfalls möglich, lässt sich aber kaum auswendig merken und muss daher notiert werden, was es ausspähbar machen kann.

Sicherheit und Entzifferung

Die monoalphabetische Substitution wirkt auf den ersten Blick sicher, weil es sehr viele mögliche Verwürfelungen des Alphabets gibt. Für den ersten Buchstaben gibt es 26 mögliche Positionen, für den zweiten 25, dann 24 und so weiter. Insgesamt sind das 26·25·24·23···4·3·2·1 = 26! Möglichkeiten, ungefähr 4·10^{26} Fälle, entsprechend etwa 88 bit. Ein reines Ausprobieren aller Fälle, die Brute-Force-Methode, ist daher praktisch unmöglich.

Trotzdem ist die monoalphabetische Substitution unsicher. Schon relativ kurze Geheimtexte von dreißig bis fünfzig Zeichen reichen aus, um sie oft mit statistischen Untersuchungen und Mustersuche zu entziffern. Bei der Häufigkeitsanalyse zählt man die Buchstaben im Geheimtext. Da bestimmte Buchstaben in einer Sprache besonders häufig vorkommen, kann man vermuten, welcher Geheimtextbuchstabe etwa für „e“ steht. Danach sucht man nach Wortmustern und häufigen Wörtern, etwa Artikeln wie „der“, „den“, „dem“ oder Wörtern wie „ein“. Durch Ausprobieren, Dokumentieren und nötiges Zurückgehen, also Backtracking, erschließt man schrittweise immer mehr Klartextbuchstaben.

Ein leipogrammatischer Text kann diese Methode stark erschweren oder unmöglich machen. In einem solchen Text werden einer oder mehrere Buchstaben absichtlich nicht verwendet, zum Beispiel Wörter mit „e“. Dadurch verschiebt sich die normale Buchstabenhäufigkeit.

Mustersuche und Rätsel

Ein Klartextangriff nutzt bekannte oder vermutete Teile des Klartextes. Kennt man einzelne Begriffe, sucht man im Geheimtext nach passenden Mustern. Bei einer monoalphabetischen Substitution bleiben gleiche Buchstaben als gleiche Geheimtextzeichen erhalten. Deshalb sind Doppelbuchstaben und wiederkehrende Muster wichtig. Im Beispiel kann das vermutete Wort „internet“ zum Geheimtextmuster „NASXUAXS“ passen.

Monoalphabetische Substitutionen lassen sich mit Computerhilfe relativ leicht brechen und bieten keine ausreichende Sicherheit gegen Entzifferung. Als Krypto-Rätsel sind sie aber beliebt. Die American Cryptogram Association unterscheidet zwischen Aristocrats und Patristocrats. Bei Aristocrats bleiben Worttrennungen als Leerzeichen und Satzzeichen im Kryptogramm sichtbar. Bei Patristocrats werden Leer- und Satzzeichen unterdrückt, und der Geheimtext wird meist in Gruppen aus fünf Buchstaben angeordnet.

Ein literarisches Beispiel ist Edgar Allan Poes Kurzgeschichte „Der Goldkäfer“ von 1843. Darin wird die Entzifferung einer monoalphabetischen Substitution mithilfe von Häufigkeitszählung und lexikalischer Analyse ausführlich beschrieben.

Sonderformen und verwandte Verfahren

Die MAKE-PROFIT-Verschlüsselung ist eine sehr einfache monoalphabetische Verschlüsselung von Ziffern. Dabei werden die Ziffern 1 bis 0 durch die Buchstaben des leicht merkbaren Satzes „MAKE PROFIT.“ ersetzt: 1=M, 2=A, 3=K, 4=E, 5=P, 6=R, 7=O, 8=F, 9=I, 0=T. So wird zum Beispiel „3719346 87550 46025504 12892“ zu „KOMIKER FOPPT ERTAPPTE MAFIA“. Diese Methode ist weniger als Geheimcode geeignet, sondern wird eher genutzt, um Buchstaben dort in Ziffern umzuwandeln, wo keine Buchstaben verwendet werden können oder sollen, etwa bei Typencodes oder Preisangaben.

Verwandte Verfahren sind die homophone Verschlüsselung, bei der Klartextzeichen durch unterschiedliche Geheimtextzeichen ersetzt werden können, und Playfair als bigraphische monoalphabetische Substitution. Bei der Polygrammsubstitution, auch polygraphische Substitution genannt, werden nicht einzelne Zeichen, sondern Zeichen-N-Gramme wie Buchstabengruppen ersetzt. Bei der polyalphabetischen Substitution werden für die Zeichen des Klartextes viele Geheimtextalphabete verwendet.