Kryptologie: Einfache Kryptoanalyse
Angriffsmethoden auf die monoalphabetischen Substitution Bearbeiten
Lange Zeit wurde die monoalphabetische Verschlüsselung als sicher betrachtet und ausgiebig verwendet. Niemand wusste, wie sie zu knacken sei. Und wie es funktioniert, wurde auch nur per Zufall entdeckt.
Trivialmethoden Bearbeiten
Sei Dir dessen bewusst, daß die Trivialmethode, einfach alle Schlüssel durch zu probieren, durchaus eine legitime Methode ist. Man kann entweder alle Schlüssel von vorne bis hinten oder anderswie systematisch durchgehen, oder aber auch, und das ist gar nicht so abwegig, zufällige Schlüssel ausprobieren (dabei natürlich Misserfolg merken).
Manchmal kann die Schlüsselmenge auch eingegrenzt werden, auf Schlüssel, die wahrscheinlicher angewandt wurden. Sicherlich hast Du etwa die Hinweise bei der Passwort-Wahl am PC mitgekriegt, zB Sonderzeichen zu verwenden. Hintergrund dabei ist die Wörterbuchattacke, bei der zuerst Wörter aus einem (modifizierten) Wörterbuch durchprobiert werden, da diese wahrscheinlicher von einem Menschen als Passwort gewählt wurden.
All dies sind aber keine Methoden der Kryptoanalyse ieS. Es wird nicht das Chiffrat analysiert, sondern mit der Hau-Drauf-Methode, zwar uU systematisch, angegriffen.
Statistische Analyse Bearbeiten
Geschichte Bearbeiten
Im 8. Jahrhundert nuZ gab es in Arabien zahlreiche Koranschulen, in denen sehr viel Textforschung betrieben wurde, um zB anhand von Analysen der einzelnen Wörter das Alter festzustellen. Dabei fiel den Gelehrten auf, daß im Arabischen die Buchstaben in einer unterschiedlichen Häufigkeit vorkommen. Mit dieser Entdeckung war es nur noch ein kleiner Schritt, bis man diese Erkenntnis für die Entschlüsselung der monoalphabetischen Verschlüsselung verwenden konnte.
Funktionsweise Bearbeiten
Die Häufigkeitsanalyse funktioniert, weil die Verteilung der Buchstabenhäufigkeit durch die Cäsar-Chiffre nicht verändert wird. Bei der Analyse zählt man die einzelnen Buchstaben in dem Geheimtext schreibt sie nach Häufigkeit geordnet auf. Diese Tabelle vergleicht man mit der bekannten Buchstabenhäufigkeit der Sprache in der der Klartext verfasst wurde. Wenn nun beim Geheimtext herauskommt, daß B der häufigste Buchstabe ist und im Klartext das E, dann kann man folgern: entschlüsseln('B') = 'E'. Man kann also versuchen, die Häufigkeitstabellen abzugleichen, der zweithäufigste Buchstabe im Geheimtextalphabet ist vermutlich identisch mit dem zweithäufigsten des Klartextalphabets usw usf.
Analyse anhand der Monogrammhäufigkeit Bearbeiten
Hier die Häufigkeiten der Buchstaben in der deutschen Sprache (ermittelt aus allen Texten in der Wikipedia (erste Spalte) und den Wikibooks (zweite Spalte)). Dabei wurden Umlaute als AE etc. und die SZ-Ligatur als Doppel-S gezählt:
| Buchstabe | Häufigkeit (Wikipedia) | Häufigkeit (Wikibooks) |
|---|---|---|
| A | .0654 | .0649 |
| B | .0223 | .0211 |
| C | .0291 | .0297 |
| D | .0458 | .0445 |
| E | .1609 | .1596 |
| F | .0192 | .0173 |
| G | .0309 | .0305 |
| H | .0402 | .0405 |
| I | .0774 | .0821 |
| J | .0031 | .0029 |
| K | .0168 | .0166 |
| L | .0407 | .0403 |
| M | .0263 | .0271 |
| N | .0886 | .0929 |
| O | .0367 | .0349 |
| P | .0134 | .0148 |
| Q | .0005 | .0008 |
| R | .0767 | .0689 |
| S | .0640 | .0639 |
| T | .0623 | .0649 |
| U | .0410 | .0398 |
| V | .0094 | .0100 |
| W | .0142 | .0146 |
| X | .0013 | .0036 |
| Y | .0031 | .0030 |
| Z | .0107 | .0111 |
Man sieht deutlich, daß E, N, I und R in dieser Reihenfolge die häufigsten Buchstaben sind.
Zudem treten noch S, T und A recht häufig auf.
Mit dieser Information bestückt, kann man sich dem Dechiffrieren einer Nachricht zuwenden:
Man listet einfach alle Symbole, die im Text vorkommen, und zählt, wie oft welches Symbol vorkommt.
Dasjenige, welches am häufigsten ist, ist sehr wahrscheinlich ein E und das zweithäufigste ein N.
Die nächsten fünf Symbole sind oftmals eines der Zeichen I, R, S, T und A.
Hat man erst mal das E und das N gefunden, so ist es leicht, weitere Buchstaben herauszufinden. Man suche nach folgenden Symbolfolgen: EaN, EbNE, EcNEd, eEN, fENN, wobei die Kleinbuchstaben für noch unbekannte Symbole stehen. a, b und c sind sehr wahrscheinlich ein I, d kann ein R, M oder S sein, e und f sind ein D oder ein W.
Wenn man auf diesem Weg mehrere Buchstaben herausgefunden hat, wird es sehr schnell einfach, weitere Buchstaben zu erraten.
Erfolgssteigerung durch Betrachtung von Polygrammen Bearbeiten
Ansonsten kann man noch ausnutzen, daß auch Buchstabenpaare unterschiedlich oft vorkommen. Die zwanzig häufigsten Buchstabenpaare sind in nachfolgender Tabelle zu finden (Diesmal nur aus den Wikibooks):
| Buchstabenkombination | Häufigkeit (Wikibooks) |
|---|---|
| EN | .0397 |
| ER | .0393 |
| CH | .0270 |
| EI | .0215 |
| DE | .0204 |
| IN | .0203 |
| TE | .0186 |
| IE | .0166 |
| UN | .0135 |
| GE | .0131 |
| ES | .0130 |
| ST | .0129 |
| ND | .0125 |
| BE | .0116 |
| AN | .0113 |
| RE | .0113 |
| NE | .0108 |
| HE | .0104 |
| IC | .0100 |
| DI | .0099 |
Auf diese Art und Weise findet man sehr oft das CH heraus.
Mit den Dreierkombinationen findet man so sehr oft auch noch das SCH heraus.
Hier die Häufigkeiten, wieder bei den Wikibooks:
| Buchstabenkombination | Häufigkeit (Wikibooks) |
|---|---|
| ICH | .0113 |
| EIN | .0111 |
| DER | .0104 |
| SCH | .0101 |
| DIE | .0088 |
| CHE | .0073 |
| UNG | .0067 |
| INE | .0062 |
| UND | .0061 |
| DEN | .0061 |
| TEN | .0056 |
| CHT | .0055 |
| GEN | .0053 |
| TER | .0052 |
| NDE | .0050 |
| STE | .0047 |
| VER | .0045 |
| IST | .0042 |
| HEN | .0042 |
| ERE | .0039 |
Wenn man diese Häufigkeitsverteilung weiß, dann braucht man nicht einmal mehr einen Kontrolltext, da die zu erwartende Verteilung ja bereits bekannt ist.
Einschränkungen der statistischen Analyse Bearbeiten
Nachdem die Häufigkeitsanalyse entdeckt wurde, war eine Geheimschrift, die viele Jahrhunderte lang Sicherheit bot, hinfällig geworden. Mit der Verbreitung der Kenntnis wurde diese Verschlüsselung wertlos, da es bald überall auf der Welt professionelle Entschlüssler gab, die nichts anderes machten, als die Geheimbotschaften, die in ihre Hände fielen, zu entschlüsseln.
Die Analyse funktioniert allerdings nur, wenn man die Sprache kennt, in der die Nachricht geschrieben ist. Wenn man zum Beispiel fälschlicherweise annimmt, sie sei auf Deutsch, dann wird man den häufigsten Buchstaben als E erkennen, gesetzt dem Fall, die betreffende Botschaft ist aber auf Arabisch, wird einem das wenig nützen, da im Arabischen die häufigsten Buchstaben A und I sind.
Außerdem ändert sich relative Häufigkeit der Buchstaben über die Zeit hinweg. Während heute immer weiter Anglizismen Einzug in die deutsche Sprache finden, waren es früher Fremdwörter aus dem Lateinischen oder Französischem. Genauso fallen fachspezifische Texte schnell aus dem Rahmen: Ein IT-bezogener-Fachartikel wird wohl viel Computer-Terminologie verwenden und ist daher tendenziell Englischlastig.
Die Häufigkeitsanalyse stößt nicht zuletzt an seine Grenzen, wenn wenig Material zur Verfügung steht. Soll das 21-Zeichen-lange Chiffrat DQKVMIIMPPRVKHQKVDBHQ dechiffriet werden, so werden bestimmt einige Buchstaben gar nicht vorkommen und die Häufigkeit anderer Buchstaben stark von der Normalverteilung abweichen.
Übungsaufgaben Bearbeiten
Wenn Du des Programmierens fähig bist (oder eine Suchmaschine benutzen kannst), kannst Du Dich dem Knacken folgender Chiffrate versuchen. Sie sind beide in Deutsch verfasst.
Hier ein einfacher Text.
JREVZVAGREARGFHESRAJVYYZHFFXRVAJNFFREVAQRAPBZCHGRETVRFFRA
Überlege zuerst welche Methode sinnvoll ist.
Etwas komplizierter wird es mit folgendem Text:
Etwas Komplizierteres.
Die Lösungen und Implementierungsbeispiele sind im Appendix zu finden.
