Mustersuche (Kryptologie)
Mit der Mustersuche können in der Kryptologie Geheimtexte entziffert werden, wenn sie monoalphabetisch verschlüsselt wurden. Bei anderen Verfahren wie ENIGMA ist sie ein Teilschritt der Entschlüsselung, hier für das Steckerbrett. Sie wird auch „Methode des Wahrscheinlichen Wortes“[1] (englisch Probable word method;[2] französisch L'attaque par mot probable) genannt. Die Methode wurde historisch verwendet und hat bei aktuellen kryptographischen Algorithmen keine Bedeutung.
Voraussetzung ist ein bekanntes Klartextfragment (ein Wort oder ein Satzteil), welches im Geheimtext auftritt. Gelingt es, die genaue Lage (Position) dieses Fragments im Text zu ermitteln, dann ist ein Einbruch erzielt, der häufig ausreicht, um die Verschlüsselung vollständig zu brechen.
Beispiel
Zum Beispiel liegt der folgende Geheimtext vor:
FVMZM FGMJZ QDGKK RGCRI KJZMR GQQQP LWWZI JZDVZ AZWQJ GIKZQ DZIMP IZEZM FZVKJ
Der Text ist relativ kurz (nur 65 Zeichen), so dass klassische Entzifferungsversuche mit Hilfe von statistischen Methoden der Kryptoanalyse kaum richtig greifen können. Eine Bestimmung der Häufigkeiten der Buchstaben und deren Verteilung lässt jedoch auch bei einem so kurzen Text bereits den Schluss zu, dass es sich möglicherweise um eine einfache monoalphabetische Verschlüsselung handelt.
Häufigkeitsreihenfolge: 12 6 6 5 5 5 5 3 3 3 3 3 2 1 1 1 1 0 0 0 0 0 0 0 0 0 Z M Q G I J K D F R V W P A C E L B H N O S T U X Y
Der Angreifer vermutet ferner, dass es sich um eine Nachricht von, für oder über Max Mustermann handelt, jedenfalls, dass dieser Name im Text verschlüsselt auftritt. Folglich nimmt er MAXMUSTERMANN als Wahrscheinliches Wort (engl.: Crib) an und versucht nun, seine genaue Lage im Text herauszufinden. Dazu bestimmt er zunächst das Muster des Textfragments und nummeriert ihre Buchstaben durch, wobei gleiche Buchstaben gleiche Nummern erhalten. So erhält man das Muster:
Wahrscheinliches Wort: M A X M U S T E R M A N N Muster: 1 2 3 1 4 5 6 7 8 1 2 9 9
Im nächsten Schritt untersucht er den Geheimtext für jede mögliche Lage des Cribs. Der Geheimtext ist 65 Zeichen lang und das Wahrscheinliche Wort hat eine Länge von dreizehn Zeichen. Folglich sind 65-13+1=53 Lagen möglich. Für jede dieser Lagen bestimmt er auf gleiche Weise – wie oben für das Wahrscheinliche Wort – das Muster des Geheimtextfragments.
Lage 1: F V M Z M F G M J Z Q D G Muster 1: 1 2 3 4 3 1 5 3 6 4 7 8 5
Lage 2: V M Z M F G M J Z Q D G K Muster 2: 1 2 3 2 4 5 2 6 3 7 8 5 9 . . . . . .
Lage 16: R G C R I K J Z M R G Q Q Muster 16: 1 2 3 1 4 5 6 7 8 1 2 9 9 . . . . . .
Lage 53: I M P I Z E Z M F Z V K J Muster 53: 1 2 3 1 4 5 4 2 6 4 7 8 9
Das Ergebnis der Mustersuche ist, dass nur an einer Stelle im Geheimtext, nämlich bei Lage 16, das Muster mit dem des Wahrscheinlichen Worts übereinstimmt. Alle anderen Positionen können, aufgrund des dort nicht übereinstimmenden Musters, als mögliche Lagen sicher ausgeschlossen werden.
Im nächsten Schritt der Entzifferung wird nun das Wahrscheinliche Wort in der ermittelten passenden Lage über den Geheimtext geschrieben:
..... ..... ..... maxmu sterm ann.. ..... ..... ..... ..... ..... ..... ..... FVMZM FGMJZ QDGKK RGCRI KJZMR GQQQP LWWZI JZDVZ AZWQJ GIKZQ DZIMP IZEZM FZVKJ
Die somit identifizierten Buchstaben (Klartext kleingeschrieben und Geheimtext großgeschrieben) R=m, G=a, C=x, I=u, K=s, J=t, Z=e, M=r, G=a und Q=n können über dem restlichen Geheimtext ergänzt werden.
..rer .arte n.ass maxmu sterm annn. ...eu te..e .e.nt ausen .eur. ue.er .e.st FVMZM FGMJZ QDGKK RGCRI KJZMR GQQQP LWWZI JZDVZ AZWQJ GIKZQ DZIMP IZEZM FZVKJ
Die weitere Entzifferung aufgrund der nun bereits gut lesbaren weiteren Klartextfragmente wie er.arten.ass (= erwarten dass), .eute (= heute) und .e.ntausen. (= zehntausend) ist für das geschulte Auge eines linguistisch erfahrenen Kryptoanalytikers nicht mehr schwierig: „Wir erwarten, dass Max Mustermann noch heute die zehntausend Euro überweist.“
Noch einfacher setzt man hierzu Computer-Programme ein, die vollautomatisch die Mustersuche und die anschließende restliche Entzifferung in Bruchteilen von Sekunden durchführen können.
Mit Hilfe der Mustersuche gelingt es somit, auch so kurze und scheinbar unknackbare Geheimtexte zu entziffern, die aufgrund ihrer geringen Länge mit Hilfe statistischer Methoden allein kaum angreifbar sind.
Siehe auch
- Data-Mining – („Datenschätze heben“) – das systematische Anwenden von (meist statistisch-mathematischen) Methoden, auf einen Datenbestand mit dem Ziel, neue Muster zu erkennen
- Mustersuche bei der Entzifferung der Enigma
Literatur
- Friedrich L. Bauer: Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie. 3., überarbeitete und erweiterte Auflage. Springer, Berlin u. a. 2000, ISBN 3-540-67931-6.
Einzelnachweise
- ↑ Friedrich L. Bauer: Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie. 3., überarbeitete und erweiterte Auflage. Springer, Berlin u. a. 2000, S. 276.
- ↑ Claude Shannon: Communication Theory of Secrecy Systems. In: Bell System Technical Journal. Band 28, Nr. 4, 1949, S. 710 f., doi:10.1002/j.1538-7305.1949.tb00928.x (englisch).