[JoGu]

Kryptologie

Mustersuche

a7Hzq .#5r<
kÜ\as TâÆK$
ûj(Ö2 ñw%h:
Úk{4R f~`z8
¤˜Æ+Ô „&¢Dø

Wörterlisten

Der zweite grundlegende Ansatz zur Kryptoanalyse der monoalphabetischen Substitution ist die Suche nach Mustern im Text, die den Buchstabenmustern von

entsprechen.

Dieses Verfahren wird mit Computerunterstützung wesentlich erleichtert. Listen aus mehreren 100000 Wörtern sind in wenigen Sekunden durchsucht. Solche Wörterlisten findet man im Internet zum Beipiel hier:

Sie wurden nur meist nicht für die Kryptoanalyse klassischer Chiffren angelegt; meistens haben sie den Zweck der Rechtschreibprüfung in Textverarbeitungen (Benutzer.dic bei MS-Word) oder TEX (für ispell). Oder sie dienen als Grundlage für Passwort-Rateprogramme (crack).

Wörterlisten sind auch heute noch - für moderne Chiffren! - ein wichtiges Hilfsmittel der Kryptoanalyse. Einfache klassische Beispiele sind hier und hier beschrieben.

Vorherberechnungen in der Kryptoanalyse

In der Prä-Computer-Ära wurden für die Kryptoanalyse umfangreiche Liste von Musterwörtern erstellt. Dies ist ein Beispiel für die Lookup-Table-Technik: Für Berechungen, die immer wieder durchgeführt werden, kann die Effizienz oft wesentlich gesteigert werden, wenn große Teile der Berechnung vorweg durchgeführt werden, um bei Bedarf schnell darauf zugreifen zu können. Weitere kryptoanalytische Beispiele werden wir noch kennenlernen.


Beispiel

Suchen wir in unserem Kryptogramm

FOALO BLAEG KEEAS PLOBE AIXOB XOAHO APOEN OBEIX JKOEE OJKPU
ENOBR CXBOP EESJJ HOMCP AMMOB LCNSP CKEUO XOPLC EELOB CPUBO
AROBL CENOB RCXBO PGOPP HCFOB PAIXH LOPEI XJKOE EOJLA OUSJL
OPOBO UOJLO BGBWV HSUBC VXAOX OAEEH KPHOB EIXCO HZOPA OMCJE
LOPGB WVHSC PCJWH AGOBO APNOB RCXBO PRKOB LOEEO PEAIX OBXOA
HMCPC KRLAO UOXOA MXCJH KPULO ECJUS BAHXM KECPU OQAOE OPAEH
XCHEI XQOBO MCOPU OJ
nach auffälligen Mustern, so springen gleich in der ersten Zeile AEGKEEA und JKOEEOJK ins Auge.

Es ist natürlich durch nichts garantiert, dass diese Muster nicht über eine Wortgrenze hinweggehen. Hier heißt es Probieren. Der Abgleich mit einer Wörterliste ergibt für AEGKEEA die Treffer (nach Bereinigung von Vorsilben, Endungen, Wortzusammensetzungen, Beugungen):

                   LOBL|AEGKEEA|SPL
Abiturientinnen         entinne *
Agentinnen              entinne *
Assistentinnen          entinne *
Auslassung              uslassu *
Ausmessung              usmessu
Ausreiseerlaubnis       reiseer *
Austritts               stritts
Autoscooter             toscoot
Barterrasse             arterra *
Buechernarren           ernarre *
Bundeskasse             eskasse
Diskussion              iskussi
Ehrenmanne              enmanne *
Eichentonne             entonne *
Eigensinne              ensinne *
Einreiseerlaubnis       reiseer *
Einzelfalle             elfalle *
Fehlerkorrektur         erkorre *
Gartenbeet              tenbeet
Geisteswissenschaft     eswisse *
Genugtuung              nugtuun *
Geplapper               eplappe
Gesetzeswissen          eswisse *
Getreideernte           reideer *
Globetrotter            etrotte *
Hotelhalle              elhalle *
Inspektionsmassnahmen   nsmassn *
Interventionsmassnahmen nsmassn *
Kanonendonner           endonne *
Konkurrentinnen         entinne *
Korrespondentinnen      entinne *
Landeskasse             eskasse *
Maiensonne              ensonne
Mietmutter              etmutte *
Motorboot               torboot *
Patientinnen            entinne *
Schlafsaal              lafsaal *
Sternenbanner           enbanne *
Studentinnen            entinne *
Tageskassen             eskasse *
Titelrollen             elrolle
Totalkollaps            alkolla
Wandelhalle             elhalle *
gefangennahm            angenna *
gestossen               estosse
getrottet               etrotte *
grauhaarig              rauhaar
uebelwollen             elwolle *
verdorre                erdorre
verharre                erharre
vernarre                ernarre
verwirre                erwirre
verworren               erworre
wechselvolle            elvolle *

Davon scheiden fast alle aus - die mit *markierten-, weil im Wort mindestens ein weiterer Buchstaben des Musters nochmal vorkommt, der im Kryptogramm an dieser Stelle nicht steht.

Das gleiche für das Muster JKOEEOJK - da es einen Buchstaben mehr hat, erwarten wir natürlich weniger Treffer:

                BEIX|JKOEEOJK|PUE
Hochseeschiffahrt    chseesch *
Industriestaates     estaates *
Klosterreste         sterrest *
Landessender         ndessend *
Presseprodukt        Pressepr
Universitaetsstaedte aetsstae *
Verschluesselung     luesselu
Zertruemmerung       ruemmeru *
verbesserbar         rbesserb *

Es gibt nur ein Paar von Treffern, bei dem die Buchstaben-Substitution verträglich ist:

LAEGKEEASP NOBEIXJKOEEOJKPU
diskussion verschluesselung

Damit haben wir schon einen so großen Teil des Schlüssels bestimmt:

a b c d e f g h i j k l m n o p q r s t u v w x y z
. . I L O . U X A . G J . P S . . B E . K N . . . .
dass der Rest der Entschlüsselung trivial ist.


Suche nach einem wahrscheinlichen Wort

Eine Variante der Mustersuche ist die Suche nach einem wahrscheinlichen Wort, von dem aus Kontextinformationen vermutet werden kann, dass es im Klartext vorkommt.

Im Beispiel könnten wir zu ahnen glauben, dass der Text etwas mit Kryptographie zu tun hat. Dann würden wir nach dem Wort oder Wortteil »schluessel« suchen. Und siehe da - wir finden zweimal EIXJKOEEOJ und sonst keine passende Stelle. Ein guter Anfang für die Entschlüsselung.


Autor: Klaus Pommerening, 28. Oktober 1999; letzte Änderung: 1. März 2008.