Mustersuche

aus Wikipedia, der freien Enzyklopädie

Als Mustersuche wird in der Kryptologie eine Methode zur Entzifferung von Geheimtexten bezeichnet.

Dabei weiß, vermutet oder errät der Codeknacker, dass im zu entziffernden Geheimtext eine bestimmte Phrase (Crib) auftritt. Gelingt es, die genaue Lage (Position) dieser Phrase im Text zu ermitteln, dann ist ein Einbruch erzielt, der häufig ausreicht, um die Verschlüsselung vollständig zu brechen.

[Bearbeiten] 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 Kryptanalyse 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 die Phrase MAXMUSTERMANN als Wahrscheinliches Wort (engl.: crib) an und versucht nun, ihre genaue Lage im Text herauszufinden. Dazu bestimmt er zunächst das Muster der Phrase 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 9

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 6 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 Kryptanalysten nicht mehr schwierig. Noch einfacher setzt man hierzu Computer-Programme ein, die vollautomatisch die Mustersuche und die anschließende restliche Entzifferung in wenigen Millisekunden 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.