Brechen von polygrafischen monoalphabetischen Substitutions-Chiffren

Die häufigste polygrafische, monoalphabetische Substitutions-Chiffre ist die bigrafische, monoalphabetische Substitutions-Chiffre. Und hier die Variation bigrafisch zu bigrafisch. Das heißt nichts anderes, als der Klartext jeweils in Teile zu je zwei Buchstaben aufgeteilt wird und dann diese Buchstabenpaare (oder auch Bigramme genannt) durch anderen Bigramme ausgetauscht werden.

Wobei die Zuordnung fest ist, also jedes bestimmte Klartext-Bigramm immer wieder durch das gleiche Geheimtext-Bigramm ausgetauscht wird. Jedes "EN"-Bigramm im Klartext wird so z. B. zu einem "XU" im Geheimtext. Wichtig ist es, hier die Unterteilung in Zweierpaare zu beachten, die nicht überlappend ist. Das heißt: Bei ABCD gibt es die Bigramme AB und CD. Das BC ist kein Bigramm, da dies nur durch eine überlappende Betrachtungsweise zustande käme.

Übersicht der monoalphabetischen polygrafischen Substitutions-Chiffren

von Klartext	zu Geheimtext	über	fraktioniert	Chiffre	Bemerkung
AB	CD			Bigramm Chiffre	alle 676 Zuordnungen werden einzeln verteilt
AB	CD	5x5 Polybios		Playfair	Grundlage sind zwei 5x5 Polybios-Quadrate, in denen nach dem Schlüssel abgeleiteten Regeln neue Bigramme abgeleitet werden.
AB	CD	5x5 Polybios	X	Seriated Playfair	wie Playfair, aber zusätzlich durch zweiten numerischen Schlüssel fraktioniert
AB	CD	2 Kästen		Doppelkastenschlüssel	Zwei aus den zwei Schlüsseln generierte Rechtecke ("Kästen") werden gegenübergestellt und daraus werden ähnlich wie bei Playfair die neuen Bigramme abgeleitet
AB	CD	5x5 oder 6x6 Polybios		Four Square	Aus zwei Schlüsseln werden vier Quadrate generiert und gegenübergestellt, aus denen ähnlich wie bei Playfair die neuen Bigramme abgeleitet werden
AB	Σ (Symbol)			Porta Bigramm Symbol Substitution	alle 676 Bigramm-Zuordnungen werden einzeln auf 676 unterschiedliche Symbole verteilt
AB	CDE	5x5 oder 6x6 Polybios		Tri Square	Vom Prinzip her wie Four Square, aber mit nur drei Quadraten. Außerdem werden drei Schlüssel verwendet. Aus zwei Klartextbuhstaben werden drei Geheimbuchstaben
A	B (¼ C)	Morse Code	X	Fractionated Morse	Einzelbuchstaben werden in Morse Code gewandelt und dann vertikal kombiniert, was den Geheimtext ungefähr 25% länger macht als den Klartext
A	123 (½ 4)	Morse Code	X	Pollux	ähnlich wie Fractionated Morse, aber Umsetzung zu Ziffern
A	1 (¾ 2)	Morse Code	X	Morbit	ähnlich wie Pollux, aber es werden zwei Morse-Elemente zu einer Ziffer zusammengefasst
A	12	5x5 Polybios		Nihilisten Substitution	Über zwei Polybios Qudrate und zwei Schlüssel werden zwei Ziffern pro Buchstabe ermittelt
A	12	8x8 Quadrat		Grandpre	Aus acht Schlüsselwörter wird eine 8x8 Tabelle erstellt, in denen die Klartextbuchstaben nacheinander gesucht und durch ihre Positionsangaben ersetzt werden
A	12 oder 123 (20…131)	Codex		Heinrich IV Chiffre	Eigentlich ein Codex, bei dem die Buchstaben durch zwei- oder dreistellige Zahlen ersetzt werden
A	1 oder 12 (1…49)			Monome-Dinome	Ähnlich funktionierend wie die Straddling Checkerboard Chiffre und mit zwei Schlüsselwörtern

Chiffren, die eine Transposition an die Substitution anschließen, sind in der oberen Tabelle nicht enthalten. Diese sind:

von Klartext	zu Geheimtext	über	fraktioniert	Chiffre	Bemerkung
A	BC	5x5 Polybios		ADFGX	In der Substitutionsphase wird aus einem Schlüssel ein Polybios-Quadrat gebildet, dessen Achsen mit den Buchstaben A, D, F, G und X beschriftet sind. Jeder Einzelbuchstabe wird so zu einer zweibuchstabigen Positionsangabe im Polybios-Quadrat. S schließt sich eine Transpositions an, die sich aus einem zweiten Schlüsselwort ergibt.
A	BC	6x6 Polybios		ADFGVX	wie ADFGX, nur mit Erweiterung auf ein 6x6 Polybios-Quadrat, um auch Ziffern kodieren zu können
A	zu 12 zu B	5x5 Polybios	X	Bifid	In der Substitutionsphase wird aus einem Schlüssel ein Polybios-Quadrat gebildet, dessen Achsen mit den Ziffern von 1 bis 5 beschriftet sind. Jeder Einzelbuchstabe wird so zu einer Positionsangabe aus zwei Ziffern im Polybios-Quadrat. Es schließt sich eine Transpositions an, die diese Ziffern durchmengt.
A	zu 123 zu B	3x 3x3 Polybios	X	Trifid	Ähnlich Bifid, es werden allerdings drei 3x3 Polybios-Quadrate gebildet, die den Buchstabentausch und die Durchmischung bewerkstelligen.
A	zu 12 zu B	2x 5x5 Polybios	X	CM-Bifid	Ähnlich Bifid, aber mit zwei Schlüsseln und zwei 5x5 Polybiod-Quadraten
AB	zu 123 zu CD	9x3 und 3x9 Polybios	X	Digrafid	Digrafid ist eine Kombination der Bifid und Trifid Chiffre.

Brechen von bigrafischen, monoalphabetischen Substitutions-Chiffren

Nachdem man die Art der Chiffre bestimmt hat und sicher ist, dass es sich um eine monoalphabetische bigrafische Substitutions-Chiffre handelt, empfiehlt sich folgendes, weiteres Vorgehen.

Insbesondere sollte man auch den Koinzidenzindex bigrafisch berechnen, um monoalphabetische bigrafische Substitutionen von polyalphabetischen monografischen Substitutionen unterscheiden zu können, die beide einen sehr ähnliche einfachen Koinzidenzindex haben.

Es hilft sehr, zu wissen, welche Chiffre genau angewandt wurde, um einen passenden Angriff zu verwenden, der die Schwächen dieser Chiffre ausnutzt.

Die häufigste Art der monoalphabetischen bigrafischen Substitution ist bigrafisch zu bigrafisch. Das heißt es wird ein Buchstabenpaar (also zwei nacheinanderfolgende Buchstaben, auch Bigramm genannt) zu einem anderen Buchstabenpaar. Da es im normalen Alphabet 26 Buchstaben gibt, gibt es 26 mal 26 gleich 676 Buchstabenpaare und somit 676 Zuordnungen (was dann dem Schlüssel entspricht), was eine große Anzahl ist.

Die Bigramm Chiffre zeigt anschaulich, wie groß so eine komplette Ersetzungstabelle ist. Die kürzeste Art, diese Zuordnung auszudrücken, ist es, sie in 676 mal 2 gleich 1352 Zeichen zu speichern (sortiert von AA bis ZZ). Diese Schlüssellänge ist unhandlich. Weshalb oft keine komplette Bigramm-Tabelle benutzt wird, sondern die meisten Chiffren spezielle, kleine Tabelle aufbauen, die Bigrammzuordnungen aus kurzen Schlüsselwörtern erzeugen.

Solange uns aber nicht die genaue Chiffre, die verwendet wurde, bekannt ist, müssten wir eine komplette Bigramm-Zuordnungstabelle rekonstruieren, was bei kürzeren Chiffraten aussichtslos ist. Erst ab mehreren tausend Zeichen - oder wenn Klartextbestandteile bekannt sind (siehe Known-Plaintext-Attack) hat so ein Angriff Aussicht auf Erfolg, also dass der Klartext in annehmbarer Zeit rekonstruiert werden kann. Wobei man auch sicher sein kann, das der gewonnene Klartext der richtige ist und nicht nur einer aus vielen möglichen.

Es ist sinnvoller (weil wahrscheinlich schneller), die vermeintliche Chiffre mit unterschiedlichsten Schlüsselwörtern durchzuprobieren, also eine Wörterbuch-unterstützte Brute Force-Attacke durchzuführen. Und gegebenenfalls weitere Chiffre auszuprobieren, wenn anfangs kein Erfolg beschieden ist.

Analyse der Häufigkeitsverteilung der Bigramme

Erst bei langen Chiffraten mit mehreren tausend Zeichen ist eine Analyse der Häufigkeitsverteilung der Bigramme sinnvoll. Bei 676 möglichen verschiedenen Bigrammen muss der Geheimtext schon lang sein, damit die einzelne Bigramme häufig genug vorkommen, damit die ausgezählte Statistik aussagekräftig genug ist. Wobei uns hier ein wenig entgegen kommt, dass es manche Buchstabenpaare im Deutschen nicht oder nur extrem selten gibt, etwa nur als zusammengesetzt aus dem Ende des einen Wortes und dem Anfangsbuchstaben des nächsten Wortes. Wie zum Beispiel QX. Denn es gibt praktisch keine Worte im Deutschen, die auf Q enden und nur sehr wenige, die mit einem X beginnen.

Als Beispiel soll das gemeinfreie Märchen Hänsel und Gretel der Gebrüder Grimm (in dieser Version)) mit ersetzen Umlauten und ohne Satz- oder Leerzeichen dienen. Der bereinigte Text ist dann 12432 Zeichen lang.

Das Märchen hat als Klartext folgende Verteilung der Bigramme (nur die häufigsten 25, nach Häufigkeit sortiert, nicht überlappend):



Man erkennt schon an der Normalverteilung deutsch, dass sich nur die häufigsten drei Bigramme deutlich absetzen. Danach versandet das Gebirge zunehmend und die Unterscheidungskraft verliert sich. Es kann höchstens noch abgeschätzt werden, in welchen Bereich ein Bigramm gehört.

Im Gebirge des Märchens sind ebenfalls die ersten drei Bigramme heraus stehend. Danach flacht das Gebirge ab. Die ersten zwei Bigramme EN und ER stimmen sogar in der Häufigkeit überein. Allerdings ist das dritthäufigste Bigramm im deutschen CH (kommt z. B. in ICH, LICH und SCH vor) in dem Märchen dann erst auf Platz 4 statt wie normal auf Platz 3 vertreten.

Verschlüsselt man nun das Märchen mit der Bigramm Chiffre (mit der dort gezeigten Umsetzungstabelle) erhält man folgendes Häufigkeitsgebirge:



Zu diesem Gebirge muss dazu gesagt werden, dass die Option "nicht überlappend" bezüglich der Bigramme für das Häufigkeitsgebirge gewählt wurde, wie auch vorher schon beim normalsprachlichen Märchen. Dadurch werden nur die einzelnen Buchstabenpaare bei der Analyse angeschaut. Bei einer überlappenden Analyse würde man auch noch zwischen den Buchstabenpaaren kombinieren, was hier das Ergebnis verfälschen würde.

Auf diese Weise analysiert entspricht das Häufigkeitsgebirge der Bigramme exakt dem des Klartextes, es wurden "lediglich" die Buchstabenkombinationen ausgetauscht. So ist es möglich - vorausgesetzt das Chiffrat ist lang genug und hat dadurch genügend statistische Aussagekraft - auf die ersten Bigramme zurückzuschließen. Denn dies sind mit erhöhter Wahrscheinlichkeit dieselben, wie sie in der natürlichen deutschen Sprache vorkommen.

Vergleicht man Klartext und Normalverteilung, sieht man, dass EN und ER die beiden häufigsten Treffer bei beiden sind. Mit dem Wissen ist dann klar, dass EA im Chiffrat ursprünglich EN war und KE ursprünglich ER. Aber dieses Wissen hat man erst nach der Kryptoanalyse. Bis dahin kann man nur Annahmen treffen und probieren. Wobei es hier sehr viel schwieriger ist erfolgreich zu sein als bei der monografischen monoalphabetischen Substitution, bei der nur 26 Zuordnungen zu klären sind anstatt wie hier bei der bigrafischen monoalphabetischen Substitution gleich ganze 676.

Trotzdem können die vom monografischen Verfahren bewährten Methoden zum Erfolg führen. Insbesondere dann, wenn Teile des Klartextes und deren Position bekannt sind. Wäre man sich zum Beispiel sicher, dass der Klartext zu einem Chiffrat mit "Sehr geehrte Damen und Herren" beginnen würde, dann hätte man schon einen ganzen Satz von Buchstabenpaar-Zuordnungen gelöst. Wodurch sich andere Zuordnungen ggf. ausschließen und sich weitere Wörter vervollständigen lassen. Dabei muss man immer in Zweiergruppen denken, also immer ganze Buchstabenpaare nicht überlappend ersetzen.

Die Seite Brechen von monoalphabetischen Substitutions-Chiffren enthält auch für die bigrafische Kryptoanalyse hilfreiche Hinweise. Außerdem kann man die Tabellen zur Häufigkeitsverteilung konsultieren, um sich auch einen Überblick über extrem seltene und wahrscheinlich auszuschließende Buchstabenkombinationen zu machen. Von den 676 Buchstabenkombinationen kommen gut 250 in der deutschen Sprache nicht vor.

Code / Chiffre online dekodieren / entschlüsseln bzw. kodieren / verschlüsseln (DeCoder / Encoder / Solver-Tool)

Außerdem steht ein Kryptoanalyse-Tool (Solver) zum manuellen brechen von polygrafischen monoalphabetischen Substitutions-Chiffren zur Verfügung.

Quellen, Literaturverweise und weiterführende Links