Caesar und Häufigkeitsanalyse: Abituraufgaben – Informatik Grundkurs

Dein Fortschritt:

0 / 0 Aufgaben

Treffpunkt im Klassenchat

AFB I–II

Jana und Paul verabreden sich im Klassenchat verschlüsselt. Sie nutzen das Caesar-Verfahren; den Schlüssel \(k = 11\) haben sie vorher mündlich vereinbart. Die Buchstaben werden wie in der Tabelle nummeriert, Leerzeichen bleiben stehen.

Nummerierung des Alphabets

Buchstabe	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
Nummer	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

A = 0 bis Z = 25; gerechnet wird modulo 26.

Geben Sie die Verschlüsselungsvorschrift für einen Buchstaben mit der Nummer \(x\) als Formel sowie die Anzahl der sinnvollen Schlüssel an.
Wenden Sie das Verfahren auf die Nachricht TREFFPUNKT MENSA an.
Erläutern Sie am Ergebnis aus b), was „monoalphabetisch“ bedeutet und welche Informationen ein Angreifer allein aus dem Geheimtext gewinnen kann.

Hinweise

Hinweis zu Aufgabe a)

Gesucht sind eine Formel mit „mod 26“ und eine Zahl. Überlege, welche Schlüssel den Text gar nicht verändern.

Hinweis zu Aufgabe b)

Arbeite mit einer Tabelle: Buchstabe → Nummer → Nummer + 11 → modulo 26 → Buchstabe.Anwenden heißt: das Verfahren mit den konkreten Werten vollständig durchführen.

Hinweis zu Aufgabe c)

Suche im Geheimtext nach Buchstaben, die mehrfach vorkommen, und vergleiche mit dem Klartext. Denke auch an die Leerzeichen.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Verschlüsseln: \(y = (x + k) \bmod 26\); Entschlüsseln: \(x = (y - k) \bmod 26 = (y + 26 - k) \bmod 26\).

Sinnvoll sind die 25 Schlüssel \(k = 1, \dots, 25\); \(k = 0\) (bzw. \(k = 26\)) lässt den Text unverändert.

Erwartungshorizont zu Aufgabe b)

Rechnung (Überlauf: Werte ab 26 um 26 verringern):

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Klartext	T	R	E	F	F	P	U	N	K	T	M	E	N	S	A
Nummer x	19	17	4	5	5	15	20	13	10	19	12	4	13	18	0
x + 11	30	28	15	16	16	26	31	24	21	30	23	15	24	29	11
mod 26	4	2	15	16	16	0	5	24	21	4	23	15	24	3	11
Geheimtext	E	C	P	Q	Q	A	F	Y	V	E	X	P	Y	D	L

Geheimtext: ECPQQAFYVE XPYDL

Erwartungshorizont zu Aufgabe c)

Monoalphabetisch heißt: Jeder Klartextbuchstabe wird im ganzen Text durch denselben Geheimtextbuchstaben ersetzt. Im Ergebnis wird das doppelte FF zu QQ, beide E werden zu P, beide T zu E.

Ein Angreifer sieht daher Muster des Klartexts: Doppelbuchstaben, sich wiederholende Buchstaben an entsprechenden Stellen und — weil die Leerzeichen stehen bleiben — die Wortlängen (10 und 5 Buchstaben). Kennt oder errät er ein einziges Buchstabenpaar (z. B. P ↔ E), hat er \(k = 15 - 4 = 11\) und damit den ganzen Text. Ohnehin genügen 25 Versuche (Brute Force).

Der abgefangene Redaktionsbrief

AFB II–III

Die Redaktion einer Schülerzeitung verschickt ihre Absprachen Caesar-verschlüsselt. Ein Mitglied der Konkurrenzzeitung fängt den folgenden Geheimtext ab; Leer- und Satzzeichen wurden entfernt, Umlaute als AE, OE, UE und ß als SS geschrieben. Der Geheimtext ist in Fünferblöcken notiert und enthält 258 Buchstaben.

Abgefangener Geheimtext

URNKN ANMJT CRXWM JBWND NQNOC NABLQ NRWCJ VOANR CJPKR CCNPN KCNDA NCNGC NKRBV RCCFX LQKNR OAJDK NLTNA JKMRN BNRCN VRCMN VAJNC BNUDN KNAWR VVCMR NBVJU MRNTU JBBNI NQWFN AWXLQ OXCXB EXVBY XACON BCQJC BLQRL TCBRN KRCCN JWMRN ANMJT CRXWM JBWJN LQBCN CANOO NWORW MNCFR NRVVN ARWMN APAXB BNWYJ DBNRV AJDVM ANRBC JCC

258 Buchstaben in Fünferblöcken.

Auszählung des Geheimtexts

Geheimtextbuchstabe	N	C	R	B	A	J	W	M
Anzahl	47	29	25	19	17	17	13	12

Buchstabe	E	N	I	S	R	A	T	D	H	U
Anteil in %	17,4	9,8	7,6	7,3	7,0	6,5	6,2	5,1	4,8	4,4

Oben: die acht häufigsten Geheimtextbuchstaben. Unten: Buchstabenhäufigkeiten der deutschen Sprache (nach Beutelspacher, gerundet).

Werten Sie die Auszählung im Hinblick auf den Schlüssel \(k\) aus. Sichern Sie Ihr Ergebnis mit mindestens zwei weiteren Buchstaben ab.
Ermitteln Sie den Klartext der ersten 14 Buchstaben.
Implementieren Sie in Python eine Funktion knacke(geheimtext), die den häufigsten Buchstaben bestimmt, ihn als E deutet und den entschlüsselten Text zurückgibt. Der Geheimtext besteht nur aus Großbuchstaben.
Beurteilen Sie, ob die Redaktion eine nur 20 Buchstaben lange Nachricht mit dem Caesar-Verfahren wirksam schützen kann.

Hinweise

Hinweis zu Aufgabe a)

Vergleiche die Spitzen beider Tabellen. Der Abstand zwischen dem häufigsten Geheimtextbuchstaben und E ist der Schlüssel; prüfe dann, ob die nächsthäufigen Buchstaben ebenfalls zu häufigen deutschen Buchstaben werden.

Hinweis zu Aufgabe b)

Schiebe jeden Buchstaben um \(k\) Stellen zurück — Überlauf beachten.

Hinweis zu Aufgabe c)

Gliedere in drei Schritte: Strichliste als Liste mit 26 Zählern, Index des Maximums suchen, jeden Buchstaben zurückschieben. Hilfreich: ord, chr, %.

Hinweis zu Aufgabe d)

Unterscheide die beiden Angriffe aus diesem Kapitel: Welcher braucht viel Text, welcher nicht?Beurteilen heißt: begründetes eigenes Urteil mit Fachargumenten.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

N ist mit 47 von 258 Buchstaben (≈ 18,2 %) der mit Abstand häufigste Geheimtextbuchstabe und entspricht damit E (17,4 %): \(k = 13 - 4 = 9\).

Absicherung mit \(k = 9\): C (2) → T (19), R (17) → I (8), B (1) → S (18), A (0) → R (17), J (9) → A (0). Die sechs häufigsten Geheimtextbuchstaben werden also zu E, T, I, S, R, A — lauter häufige deutsche Buchstaben. Der Schlüssel \(k = 9\) ist damit gut belegt.

Erwartungshorizont zu Aufgabe b)

Geheimtext	U	R	N	K	N	A	N	M	J	T	C	R	X	W
Nummer	20	17	13	10	13	0	13	12	9	19	2	17	23	22
− 9 mod 26	11	8	4	1	4	17	4	3	0	10	19	8	14	13
Klartext	L	I	E	B	E	R	E	D	A	K	T	I	O	N

Klartext: LIEBE REDAKTION (Leerzeichen ergänzt).

Erwartungshorizont zu Aufgabe c)

def knacke(geheimtext):
    anzahl = [0] * 26
    for c in geheimtext:          # Strichliste
        anzahl[ord(c) - 65] += 1
    max_i = 0
    for i in range(26):           # Maximum suchen
        if anzahl[i] > anzahl[max_i]:
            max_i = i
    k = (max_i - 4) % 26          # E = Nummer 4
    klartext = ""
    for c in geheimtext:          # um k zurück
        klartext = klartext + chr((ord(c) - 65 - k) % 26 + 65)
    return klartext

Gleichwertige Lösungen (z. B. mit anzahl.index(max(anzahl)) oder einem Dictionary) sind zulässig. Der Test knacke(geheimtext) mit dem abgefangenen Text liefert den Klartext „LIEBEREDAKTION…“.

Erwartungshorizont zu Aufgabe d)

Nein. Bei 20 Buchstaben ist die Häufigkeitsanalyse zwar unzuverlässig, weil die Statistik zu dünn ist. Das schützt aber nicht: Ein Angreifer probiert alle 25 Schlüssel durch (Brute Force) und erkennt den einzigen lesbaren Kandidaten sofort — per Hand in wenigen Minuten, per Computer in Sekundenbruchteilen.

Da das Verfahren bekannt ist (Kerckhoffs), liegt die ganze Sicherheit im Schlüssel, und der Schlüsselraum ist mit 25 viel zu klein. Die Redaktion sollte ein modernes Verfahren mit großem Schlüsselraum (z. B. AES) verwenden. Vollständig ist eine Antwort, die beide Angriffe betrachtet und zu einem eindeutigen Urteil kommt.