Ein Computer kann sehr schnell alle 25 möglichen Originaltexte eines Caesar-verschlüsselten Geheimtextes berechnen. Schön wäre es, wenn der Computer auch den richtigen Originaltext automatisch bestimmen könnte.
Dazu nehmen wir an, dass der Originaltext in deutscher Sprache geschrieben wurde. Die folgenden Überlegungen sind natürlich auch in andere Sprachen übertragbar.
Bigramme
Bigramme sind Paare aufeinanderfolgender Buchstaben in einem Wort. Das Wort «BIGRAMM» enthält sechs Bigramme: «BI», «IG», «GR», «RA», «AM» und «MM». Man kann die Häufigkeit bestimmen, mit welcher Bigramme in der deutschen Sprache auftreten. Die folgende Tabelle zeigt die 30 häufigsten Bigramme:
| ER | 3.90% | IN | 1.71% | BE | 1.17% | AU | 0.89% | SC | 0.77% |
| EN | 3.61% | ND | 1.68% | ES | 1.17% | NG | 0.87% | LE | 0.73% |
| CH | 2.36% | IE | 1.48% | UN | 1.13% | SE | 0.83% | DA | 0.72% |
| DE | 2.31% | GE | 1.45% | RE | 1.11% | IT | 0.81% | NS | 0.71% |
| EI | 1.98% | ST | 1.21% | AN | 1.07% | DI | 0.81% | IS | 0.70% |
| TE | 1.98% | NE | 1.19% | HE | 0.89% | IC | 0.80% | RA | 0.69% |
Wenn ein Text viele Bigramme enthält, die häufig in der deutschen Sprache vorkommen, so ist es wahrscheinlich, dass dies ein deutscher Text ist. Aufgrund dieser Annahme definieren wir die «Deutschheit» eines Textes folgendermassen:
- Bestimme für jedes im Text vorkommende Bigramm dessen Häufigkeit in der deutschen Sprache.
- Multipliziere alle so erhaltenen Häufigkeiten.
Da die Häufigkeiten sehr kleine Zahlen sind, ergibt sich durch die Ungenauigkeit des Computers schon bald eine 0. Deshalb greifen wir zu einem Trick. Wir addieren die Logarithmen der Häufigkeiten.
Für den Text «Hallo» erhalten wir folgenden Wert:
| HA | AL | LL | LO | Total |
|---|---|---|---|---|
| −5.136198517 | −5.086437008 | −5.298317367 | −6.840096631 | −22.361049523 |
Für den Text «KJEXG» erhalten wir folgenden Wert:
| KJ | JE | EX | XG | Total |
|---|---|---|---|---|
| −11.626472734 | −7.308232846 | −7.824046011 | −10.819778284 | −37.578529875 |
Diesen Wert nennen wir «Fitness» eines Wortes bezüglich der Deutschen Sprache.
Aufgabe: Aufgabe Bigramme
Schreibe eine Funktion bigramms(word), welche alle Bigramme eines Wortes in einer Liste zurückliefert. Teste die Funktion mit folgender Anweisung:
print(bigramms("HALLO"))Die Ausgabe sollte so aussehen:
["HA", "AL", "LL", "LO"]::: extra Aufgabe Datenbank
Schreibe ein Programm, welches die untenstehende Datei mit den Häufigkeiten Deutscher Bigramme liest und eine Datenbank mit den logarithmisierten relativen Häufigkeiten erstellt.
:::
Aufgabe: Aufgabe Fitness 1
Schreibe eine Funktion fitness_word(word), welches die Fitness eines Worts wie folgt berechnet:
- Bigramme des Worts bestimmen.
- Für jedes Bigramm den Fitness-Wert in der Datenbank nachschlagen.
- Alle Fitness-Werte addieren.
Teste die Funktion mit folgenden Anweisungen:
print("Fitness von HALLO:", fitness_word("HALLO"))
print("Fitness von KJEXG:", fitness_word("KJEXG"))2
Aufgabe: Aufgabe Fitness 2
Schreibe eine Funktion fitness(text), welches die Fitness eines Textes berechnet, indem der Text in einzelne Wörter aufgeteilt wird.
Aufgabe: Aufgabe Caesar knacken
Erweitere das Programm so, dass es automatisch einen Caesar-verschlüsselten Text entschlüsseln kann.
Quellen: