Substitutionsverfahren und Sicherheit
Lena aus Köln und ihre Freundin Aylin schreiben sich in der Schul-Chatgruppe. Die Nachricht soll aber nur die beiden etwas angehen, auch wenn jemand den Chat mitliest. Wie kann man einen Text so verändern, dass nur der Empfänger ihn versteht? Und wie sicher ist so ein Verfahren wirklich? Das klärst du auf dieser Seite.
Die Caesar-Verschlüsselung
Schon der römische Feldherr Gaius Julius Caesar soll Nachrichten so verschlüsselt haben: Jeder Buchstabe wird im Alphabet um dieselbe Anzahl von Stellen verschoben. Eine Verschlüsselung, die jeden Buchstaben durch einen anderen Buchstaben ersetzt, nennt man ein Substitutionsverfahren.
Die Abbildung zeigt die Verschiebung um $k = 3$: Unter jedem Klartextbuchstaben steht der zugehörige Geheimtextbuchstabe.
Am Ende des Alphabets geht es vorne weiter: Nach Z folgt wieder A. Das ist wie eine Uhr, die nach 12 wieder bei 1 anfängt.
Verschlüssele das Wort SCHULE mit der Caesar-Verschlüsselung und dem Schlüssel 3 (jeder Buchstabe wird im Alphabet um 3 Stellen nach rechts verschoben; nach Z folgt…
Verschlüssele das Wort SCHULE mit der Caesar-Verschlüsselung und dem Schlüssel 3 (jeder Buchstabe wird im Alphabet um 3 Stellen nach rechts verschoben; nach Z folgt wieder A). Gib das Geheimwort an und beschreibe, wie du beim Buchstaben X vorgehst, wenn er vorkommt.
Entschlüssele den Text FDHVDU , der mit der Caesar-Verschlüsselung und dem Schlüssel 3 verschlüsselt wurde. Erkläre, in welche Richtung du die Buchstaben beim…
Entschlüssele den Text FDHVDU , der mit der Caesar-Verschlüsselung und dem Schlüssel 3 verschlüsselt wurde. Erkläre, in welche Richtung du die Buchstaben beim Entschlüsseln verschiebst.
Tim und Aylin wollen sich geheime Nachrichten schicken. Sie vereinbaren die Caesar-Verschlüsselung mit dem Schlüssel 7. a) Verschlüssele TREFFPUNKT UM ACHT (Leerzeichen…
Tim und Aylin wollen sich geheime Nachrichten schicken. Sie vereinbaren die Caesar-Verschlüsselung mit dem Schlüssel 7.
- a) Verschlüssele
TREFFPUNKT UM ACHT(Leerzeichen bleiben erhalten).
- b) Aylin antwortet mit der Nachricht
OHSS. Entschlüssele sie.
- c) Nenne ein Problem, das entsteht, wenn Tim und Aylin den Schlüssel über Messenger austauschen.
Caesar knacken: alle Schlüssel probieren
Angenommen, du fängst eine Caesar-Nachricht ab, kennst aber den Schlüssel nicht. Dann kannst du alle möglichen Schlüssel durchprobieren. Man sagt dazu auch Brute Force („rohe Gewalt“).
Wie viele Schlüssel gibt es? Bei 26 Buchstaben sind die Verschiebungen $1, 2, \dots, 25$ sinnvoll. Die Verschiebung 0 (und 26) lässt den Text unverändert. Es gibt also nur 25 Schlüssel. Das schafft ein Mensch mit Papier, ein Computer braucht dafür Bruchteile einer Sekunde.
Du musst nicht immer alles probieren. Oft hilft geschicktes Raten: Probiere erst die Schlüssel, bei denen ein auffälliger Buchstabe (zum Beispiel ein Buchstabe, der oft vorkommt) zu E wird. Oder achte auf kurze Wörter wie AM, IM, ES.
Lena aus Köln erhält die Nachricht WUHIIHQ DP EDKQKRI . Sie weiß nur, dass es sich um eine Caesar-Verschlüsselung handelt. a) Entschlüssele die Nachricht, indem du alle…
Lena aus Köln erhält die Nachricht WUHIIHQ DP EDKQKRI . Sie weiß nur, dass es sich um eine Caesar-Verschlüsselung handelt.
- a) Entschlüssele die Nachricht, indem du alle 25 möglichen Schlüssel systematisch ausprobierst, oder begründe, wie du den Schlüssel geschickt erraten kannst.
- b) Wie viele Schlüssel gibt es bei der Caesar-Verschlüsselung mit 26 Buchstaben (ohne den „Schlüssel“, der nichts verändert)? Was bedeutet das für die Sicherheit?
Monoalphabetische Substitution
Wenn nur 25 Schlüssel das Problem sind, kann man einfach jedem Buchstaben frei einen anderen Buchstaben zuordnen, ohne feste Verschiebung. Der Schlüssel ist dann eine ganze Substitutionstabelle.
Beispiel (Auszug): A→Q, E→W, H→M, L→X, O→T. Dann wird HALLO zu MQXXT.
Wie viele Schlüssel gibt es? Für A hast du 26 Möglichkeiten, für B noch 25, dann 24 usw. Das sind
mögliche Schlüssel, eine unvorstellbar große Zahl. Alle auszuprobieren ist praktisch unmöglich.
Gegeben ist die monoalphabetische Substitutionstabelle (Auszug): A→Q, E→W, H→M, L→X, N→B, O→T, S→K, T→R Verschlüssele damit das Wort HALLO. Erkläre außerdem in einem…
Gegeben ist die monoalphabetische Substitutionstabelle (Auszug):
A→Q, E→W, H→M, L→X, N→B, O→T, S→K, T→R
Verschlüssele damit das Wort HALLO. Erkläre außerdem in einem Satz, was „monoalphabetisch“ bedeutet.
Häufigkeitsanalyse
Ein Muster bleibt bei jeder monoalphabetischen Substitution erhalten: wie oft ein Buchstabe vorkommt. In deutschen Texten ist E der häufigste Buchstabe, Q oder X sind sehr selten.
| Buchstabe | E | N | I | S | R | A | T |
|---|---|---|---|---|---|---|---|
| ungefähr (in %) | 17,4 | 9,8 | 7,6 | 7,3 | 7,0 | 6,5 | 6,2 |
Das Vorgehen der Häufigkeitsanalyse:
-
Zähle die Buchstaben im Geheimtext.
-
Berechne die relative Häufigkeit: $\dfrac{\text{Anzahl}}{\text{Gesamtzahl der Buchstaben}}$ (in Prozent).
-
Ordne den häufigsten Geheimbuchstaben dem häufigsten Klartextbuchstaben zu (zuerst
E). -
Prüfe weitere Muster, zum Beispiel kurze Wörter, Doppelbuchstaben (
LL,TT) und typische Endungen wieENoderER.
In einem deutschen Text wurde mit einer monoalphabetischen Substitution verschlüsselt. Die Häufigkeitsanalyse des Geheimtextes (200 Buchstaben) ergibt: K kommt 34-mal…
In einem deutschen Text wurde mit einer monoalphabetischen Substitution verschlüsselt. Die Häufigkeitsanalyse des Geheimtextes (200 Buchstaben) ergibt: K kommt 34-mal vor, W 20-mal, Q 3-mal.
- a) Berechne die relative Häufigkeit von
Kin Prozent.
- b) Welcher Klartextbuchstabe ist für
Kam wahrscheinlichsten? Begründe mit deinem Wissen über die deutsche Sprache.
- c) Erkläre, warum diese Methode bei sehr kurzen Texten unsicher ist.
Der Geheimtext OFUUF XFMMF wurde mit einer Caesar-Verschlüsselung erzeugt. Der Klartext besteht aus zwei Wörtern. a) Bestimme den Schlüssel, indem du die Häufigkeit der…
Der Geheimtext OFUUF XFMMF wurde mit einer Caesar-Verschlüsselung erzeugt. Der Klartext besteht aus zwei Wörtern.
- a) Bestimme den Schlüssel, indem du die Häufigkeit der Buchstaben im Geheimtext nutzt, und entschlüssele.
- b) Erkläre, warum dein Vorgehen auch bei einem Text mit mehr als 100 Buchstaben zuverlässiger wäre.
- c) Beschreibe, wie man das Verfahren verändern müsste, damit die Häufigkeitsanalyse deutlich schwerer wird.
Verfahren beurteilen: Vigenère und Sicherheit
Verschlüsselung dient dem Schutzziel der Vertraulichkeit: Nur der Empfänger soll den Inhalt lesen können. Die Häufigkeitsanalyse zeigt: Ein Verfahren ist nicht schon deshalb sicher, weil es sehr viele Schlüssel hat. Man beurteilt ein Verfahren mit mehreren Kriterien:
-
Schlüsselanzahl: Kann man alle Schlüssel durchprobieren?
-
Widerstand gegen Häufigkeitsanalyse: Bleiben die Buchstabenhäufigkeiten sichtbar?
-
Aufwand: Wie mühsam ist es für Sender und Empfänger, zu ver- und entschlüsseln und den Schlüssel zu merken?
-
Schlüsselaustausch: Wie bekommt der Empfänger den Schlüssel sicher?
Eine Verbesserung ist die polyalphabetische Verschlüsselung nach Vigenère. Man wählt ein Schlüsselwort, zum Beispiel ABC. Die Buchstaben des Wortes geben der Reihe nach die Verschiebung an (A = 0, B = 1, C = 2) und wiederholen sich.
Dadurch wird die Häufigkeit der Buchstaben „verwischt“, die einfache Häufigkeitsanalyse reicht nicht mehr. Dafür müssen Sender und Empfänger ein Schlüsselwort geheim halten und mehr rechnen.
Der Vergleich der drei Verfahren nach den Kriterien:
| Kriterium | Caesar | Monoalphabetisch | Vigenère |
|---|---|---|---|
| Schlüsselanzahl | 25 | $26! \approx 4 \cdot 10^{26}$ | sehr viele (wächst mit der Länge des Schlüsselworts) |
| Widerstand gegen Häufigkeitsanalyse | keiner | gering | deutlich besser |
| Aufwand | sehr gering | mittel (lange Tabelle) | höher (Schlüsselwort, mehr Rechnen) |
Für eine Schul-Chatgruppe wäre also ein Verfahren wie Vigenère mit einem Schlüsselwort besser als Caesar, solange der Schlüssel nicht im Chat verschickt wird.
Ein weiteres Problem betrifft alle Verfahren: Der Schlüssel muss zum Empfänger gelangen. Schickt man ihn über denselben unsicheren Kanal wie die Nachricht (zum Beispiel per Messenger), kann ihn auch ein Mitleser kopieren.
Eine monoalphabetische Substitution hat $26! \approx 4 \cdot 10^{26}$ mögliche Schlüssel. Ein Computer testet $10^9$ Schlüssel pro Sekunde. a) Schätze, wie viele Jahre…
Eine monoalphabetische Substitution hat $26! \approx 4 \cdot 10^{26}$ mögliche Schlüssel. Ein Computer testet $10^9$ Schlüssel pro Sekunde.
- a) Schätze, wie viele Jahre er für alle Schlüssel bräuchte (1 Jahr $\approx 3 \cdot 10^7$ s).
- b) Trotzdem gilt das Verfahren als unsicher. Begründe das mit der Häufigkeitsanalyse.
- c) Beurteile, ob die Aussage „Je mehr mögliche Schlüssel, desto sicherer“ allgemein stimmt.
Vergleiche die Caesar-Verschlüsselung, die monoalphabetische Substitution und ein Verfahren, das die Buchstaben eines Schlüsselworts der Reihe nach (und immer wieder von…
Vergleiche die Caesar-Verschlüsselung, die monoalphabetische Substitution und ein Verfahren, das die Buchstaben eines Schlüsselworts der Reihe nach (und immer wieder von vorn) als Verschiebung für die einzelnen Buchstaben verwendet (Vigenère). Beurteile sie nach den Kriterien Schlüsselanzahl, Widerstand gegen Häufigkeitsanalyse und Aufwand für Sender und Empfänger. Gib zum Schluss eine begründete Empfehlung für die Verschlüsselung einer Schul-Chatgruppe.
Auf einen Blick
-
Ein Substitutionsverfahren ersetzt Buchstaben durch andere. Aus Klartext wird Geheimtext, zurück geht es mit dem Schlüssel.
-
Caesar: Verschiebung um $k$ Stellen, $c = (p + k) \bmod 26$; entschlüsselt wird in Gegenrichtung. Es gibt nur 25 sinnvolle Schlüssel, Durchprobieren knackt das Verfahren sofort.
-
Monoalphabetisch: Jeder Buchstabe hat eine feste Zuordnung. Es gibt $26! \approx 4 \cdot 10^{26}$ Schlüssel.
-
Häufigkeitsanalyse: Buchstabenhäufigkeiten bleiben erhalten (im Deutschen ist
Eam häufigsten). Das Verfahren braucht lange Texte. -
Vigenère (polyalphabetisch) verwischt die Häufigkeiten, ist aber aufwendiger.
-
Beurteilen heißt: Schlüsselanzahl, Widerstand gegen Häufigkeitsanalyse, Aufwand und Schlüsselaustausch vergleichen und begründet entscheiden.
-
Zurück zum Anfang: Lena und Aylin können Caesar nutzen, aber ihre Nachricht ist damit nicht wirklich sicher. Besser wäre ein Verfahren, das Häufigkeiten verbirgt, und ein Schlüssel, der nicht über den Chat verschickt wird.