Substitutionsverfahren
Lea und Ben tauschen im Unterricht Zettel aus. Kein anderer soll lesen können, was drauf steht. Also schreibt Lea statt „TREFFPUNKT“ lauter scheinbar sinnlose Buchstaben. Ben weiß, wie er sie zurückverwandelt, der Rest der Klasse nicht. Wie funktioniert so ein Geheimcode, und wie sicher ist er wirklich? Das klären wir in diesem Abschnitt über Verschlüsselung.
Die Caesar-Verschlüsselung
Schon der römische Feldherr Julius Caesar soll Nachrichten geheim gehalten haben. Er verschob jeden Buchstaben um eine feste Anzahl von Stellen im Alphabet. Diese Zahl heißt Schlüssel.
Bei der Caesar-Verschlüsselung mit Schlüssel 3 wird jeder Buchstabe durch den Buchstaben ersetzt, der 3 Stellen weiter rechts im Alphabet steht. Am Ende geht es wieder bei A weiter.
Zum Entschlüsseln gehst du genauso viele Stellen zurück.
Verschlüssele das Wort INFORMATIK mit der Caesar-Verschlüsselung und dem Schlüssel 3 (A → D, B → E, …, Z → C).
Verschlüssele das Wort INFORMATIK mit der Caesar-Verschlüsselung und dem Schlüssel 3 (A → D, B → E, …, Z → C).
Entschlüssele den mit der Caesar-Verschlüsselung (Schlüssel 5, Verschiebung nach rechts) verschlüsselten Text: HFWJS
Entschlüssele den mit der Caesar-Verschlüsselung (Schlüssel 5, Verschiebung nach rechts) verschlüsselten Text: HFWJS
Schlüssel und Arten der Verschlüsselung
Wer den Schlüssel kennt, kann die Nachricht lesen. Bei der Caesar-Verschlüsselung benutzen Sender und Empfänger denselben Schlüssel. Das nennt man symmetrische Verschlüsselung.
Der Nachteil der symmetrischen Verfahren: Der Schlüssel muss vorher sicher übergeben werden. Asymmetrische Verfahren lösen dieses Problem. Sie werden zum Beispiel beim Aufbau einer HTTPS-Verbindung verwendet.
Wie viele Schlüssel hat die Caesar-Verschlüsselung? Bei 26 Buchstaben kann man um 0 bis 25 Stellen verschieben. Bei einer Verschiebung um 26 landet jeder Buchstabe wieder bei sich selbst, die Verschiebung um 0 verändert den Text auch nicht. Es gibt also nur 25 sinnvolle Schlüssel.
Erkläre den Unterschied zwischen symmetrischer und asymmetrischer Verschlüsselung. Zu welcher Art gehört die Caesar-Verschlüsselung?
Erkläre den Unterschied zwischen symmetrischer und asymmetrischer Verschlüsselung. Zu welcher Art gehört die Caesar-Verschlüsselung?
Lena verschlüsselt die Nachricht TREFFPUNKT BAHNHOF mit der Caesar-Verschlüsselung (Schlüssel 7). a) Gib den Geheimtext an. b) Wie viele verschiedene Schlüssel gibt es…
Lena verschlüsselt die Nachricht TREFFPUNKT BAHNHOF mit der Caesar-Verschlüsselung (Schlüssel 7).
- a) Gib den Geheimtext an.
- b) Wie viele verschiedene Schlüssel gibt es bei der Caesar-Verschlüsselung mit 26 Buchstaben, die den Text tatsächlich verändern?
Caesar knacken durch Ausprobieren
Du fängst einen Geheimtext ab und kennst den Schlüssel nicht. Weil es nur 25 Schlüssel gibt, kannst du einfach alle durchprobieren. Das nennt man Brute-Force-Angriff („mit roher Gewalt“). Du erkennst den richtigen Schlüssel daran, dass ein sinnvolles Wort entsteht.
Bei längeren Texten reicht oft schon das erste Wort, um zu entscheiden, ob der Schlüssel stimmt.
Du fängst den Geheimtext JHKH ZHJ ab. Du weißt, dass er mit einer Caesar-Verschlüsselung erzeugt wurde und der Klartext aus deutschen Wörtern besteht. a) Beschreibe, wie…
Du fängst den Geheimtext JHKH ZHJ ab. Du weißt, dass er mit einer Caesar-Verschlüsselung erzeugt wurde und der Klartext aus deutschen Wörtern besteht.
- a) Beschreibe, wie du den Schlüssel durch Ausprobieren findest.
- b) Entschlüssele den Text.
Caesar mit Zahlen: Rechnen mit Rest
Informatiker beschreiben das Verfahren mit Zahlen. Wir nummerieren die Buchstaben: A = 0, B = 1, …, Z = 25. Ein Klartextbuchstabe mit der Zahl $m$ wird mit dem Schlüssel $k$ zu
$$c = (m + k) \bmod 26$$Dabei ist $x \bmod 26$ der Rest, der bei der Division durch 26 bleibt. Das „Zurück zu A“ am Alphabetende ist genau dieser Rest.
Was passiert, wenn man zweimal hintereinander verschlüsselt, mit $k_1$ und dann mit $k_2$? Es gilt $((m + k_1) \bmod 26 + k_2) \bmod 26 = (m + k_1 + k_2) \bmod 26$. Das ist dieselbe Verschlüsselung wie mit dem einen Schlüssel $k_1 + k_2$. Mehrfaches Verschlüsseln ist also nur ein neuer Caesar-Schlüssel und bringt keinen Sicherheitsgewinn.
Die Caesar-Verschlüsselung lässt sich mit Zahlen beschreiben: Buchstaben werden mit A = 0, …, Z = 25 nummeriert, und es gilt $c = (m + k) \bmod 26$. a) Berechne die…
Die Caesar-Verschlüsselung lässt sich mit Zahlen beschreiben: Buchstaben werden mit A = 0, …, Z = 25 nummeriert, und es gilt $c = (m + k) \bmod 26$.
- a) Berechne die Verschlüsselung von Y mit $k = 9$.
- b) Gib die Formel für die Entschlüsselung an.
- c) Zeige, dass zweimaliges Verschlüsseln mit $k_1 = 8$ und $k_2 = 11$ einer einmaligen Verschlüsselung mit $k = 19$ entspricht, und begründe, dass Hintereinanderausführen die Sicherheit nicht erhöht.
Beliebige Substitution und Häufigkeitsanalyse
Statt das Alphabet nur zu verschieben, kann man es beliebig durcheinanderwürfeln. Jeder Buchstabe wird durch einen festen anderen ersetzt, zum Beispiel A → Q, B → W, C → L … Man nennt das eine monoalphabetische Substitution, weil für den ganzen Text nur ein Geheimalphabet benutzt wird.
Die Zahl der Schlüssel ist riesig. Für A gibt es 26 Möglichkeiten, für B noch 25, für C noch 24 usw. Insgesamt sind das $26! = 26 \cdot 25 \cdot 24 \cdot \ldots \cdot 1 \approx 4 \cdot 10^{26}$ Schlüssel. Ausprobieren ist also ausgeschlossen.
Trotzdem lässt sich das Verfahren knacken, und zwar mit der Häufigkeitsanalyse. In jeder Sprache kommen Buchstaben unterschiedlich oft vor. Im Deutschen ist E mit etwa 17 % der häufigste Buchstabe, danach folgen N (etwa 10 %), I, S, R und A. Eine feste Ersetzung verändert diese Häufigkeiten nicht, sie verschiebt sie nur auf andere Buchstaben.
| Buchstabe im Deutschen | E | N | I | S | R | A |
|---|---|---|---|---|---|---|
| ungefährer Anteil | 17 % | 10 % | 7,5 % | 7 % | 7 % | 6,5 % |
Die Schwäche liegt darin, dass gleiche Klartextbuchstaben immer zum gleichen Geheimtextbuchstaben werden. Das Muster der Sprache bleibt sichtbar.
Bei einer monoalphabetischen Substitution wird jeder Buchstabe durch einen festen anderen ersetzt. Ein Geheimtext der Länge 200 enthält den Buchstaben X 36-mal. a)…
Bei einer monoalphabetischen Substitution wird jeder Buchstabe durch einen festen anderen ersetzt. Ein Geheimtext der Länge 200 enthält den Buchstaben X 36-mal.
- a) Berechne den relativen Anteil von X in Prozent.
- b) Im Deutschen ist E der häufigste Buchstabe (etwa 17 %). Was vermutest du über X und wie nutzt man dies zum Entschlüsseln?
Vergleiche die Caesar-Verschlüsselung mit einer beliebigen monoalphabetischen Substitution. a) Berechne die Anzahl möglicher Schlüssel der beliebigen Substitution…
Vergleiche die Caesar-Verschlüsselung mit einer beliebigen monoalphabetischen Substitution.
- a) Berechne die Anzahl möglicher Schlüssel der beliebigen Substitution (Ausdruck mit Fakultät genügt).
- b) Erkläre, warum diese Verschlüsselung trotz der großen Schlüsselzahl nicht sicher ist.
- c) Beschreibe ein Verfahren, das dieses Problem verringert.
Vigenère: mehrere Geheimalphabete
Wie verhindert man, dass E immer zum selben Buchstaben wird? Man benutzt nicht einen Caesar-Schlüssel, sondern mehrere im Wechsel. Genau das macht die Vigenère-Verschlüsselung (ein polyalphabetisches Verfahren). Der Schlüssel ist ein Wort. Jeder Buchstabe des Schlüsselworts liefert eine Verschiebung (A = 0, B = 1, …). Das Schlüsselwort wird reihum wiederholt.
Im Beispiel wird N einmal zu Q und einmal zu E. Gleiche Klartextbuchstaben ergeben also verschiedene Geheimtextbuchstaben, und die Häufigkeitsverteilung wird „verwischt“. Die einfache Häufigkeitsanalyse funktioniert nicht mehr.
Je länger das Schlüsselwort ist, desto mehr Geheimalphabete werden benutzt und desto schwerer ist es zu knacken. Hat das Schlüsselwort nur einen Buchstaben, ist Vigenère eine Caesar-Verschlüsselung. Hat es die Länge des Textes und ist zufällig, gilt das Verfahren als nahezu unknackbar. Trotzdem lässt sich auch Vigenère knacken, wenn man die Länge des Schlüsselworts herausfindet. Dann teilt man den Text in einzelne Caesar-Texte auf.
Die Vigenère-Verschlüsselung nutzt ein Schlüsselwort, dessen Buchstaben reihum als Caesar-Schlüssel dienen (A = 0, B = 1, …). a) Verschlüssele HALLO mit dem…
Die Vigenère-Verschlüsselung nutzt ein Schlüsselwort, dessen Buchstaben reihum als Caesar-Schlüssel dienen (A = 0, B = 1, …).
- a) Verschlüssele HALLO mit dem Schlüsselwort BAD.
- b) Erkläre, warum die Häufigkeitsanalyse hier schwerer ist als bei Caesar.
- c) Beurteile, wie sich die Sicherheit mit der Länge des Schlüsselworts ändert.
Zurück zum Anfang: Lea kann ihren Zettel „TREFFPUNKT“ nur dann sicher verschlüsseln, wenn sie kein einfaches Caesar-Verfahren nimmt. Gegen 25 Schlüssel hilft Ausprobieren, gegen feste Buchstabenersetzung die Häufigkeitsanalyse. Ein langes Vigenère-Schlüsselwort ist schon deutlich stärker.